Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form


Jariyakul, Nattaphol (2005) A CLUSTERING-BASED SELECTIVE PROBING FRAMEWORK TO SUPPORT INTERNET QUALITY OF SERVICE ROUTING. Master's Thesis, University of Pittsburgh. (Unpublished)

Primary Text

Download (1MB) | Preview


The advent of the multimedia applications has triggered widespread interest in QoS supports. Two Internet-based QoS frameworks have been proposed: Integrated Services (IntServ) and Differentiated Services (DiffServ). IntServ supports service guarantees on a per-flow basis. The framework, however, is not scalable due to the fact that routers have to maintain a large amount of state information for each supported flow. DiffServ was proposed as an alternate solution to address the lack of scalability of the IntServ framework. DiffServ uses class-based service differentiation to achieve aggregate support for QoS requirements. This approach eliminates the need to maintain per-flow states on a hop-by-hop basis and reduces considerably the overhead routers incur in forwarding traffic.Both IntServ and DiffServ frameworks focus on packet scheduling. As such, they decouple routing from QoS provisioning. This typically results in inefficient routes, thereby limiting the ability of the network to support QoS requirements and to manage resources efficiently. The goal of this thesis is to address this shortcoming. We propose a scalable QoS routing framework to identify and select paths that are very likely to meet the QoS requirements of the underlying applications. The tenet of our approach is based on seamlessly integrating routing into the DiffServ framework to extend its ability to support QoS requirements. Scalability is achieved using selective probing and clustering to reduce signaling and routers overhead.The major contributions of this thesis are as follows: First, we propose a scalable routing architecture that supports QoS requirements. The architecture seamlessly integrates the QoS traffic requirements of the underlying applications into a DiffServ framework. Second, we propose a new delay-based clustering method, referred to as d-median. The proposed clustering method groups Internet nodes into clusters, whereby nodes in the same cluster exhibit equivalent delay characteristics. Each cluster is represented by anchor node. Anchors use selective probing to estimate QoS parameters and select appropriate paths for traffic forwarding. A thorough study to evaluate the performance of the proposed d-median clustering algorithm is conducted. The results of the study show that, for power-law graphs such as the Internet, the d-median clustering based approach outperforms the set covering method commonly proposed in the literature. The study shows that the widely used clustering methods, such as set covering or k-median, are inadequate to capture the balance between cluster sizes and the number of clusters. The results of the study also show that the proposed clustering method, applied to power-law graphs, is robust to changes in size and delay distribution of the network. Finally, the results suggest that the delay bound input parameter of the d-median scheme should be no less than 1 and no more than 4 times of the average delay per one hop of the network. This is mostly due to the weak hierarchy of the Internet resulting from its power-law structure and the prevalence of the small-world property.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairZnati, Taiebznati@cs.pitt.eduZNATI
Committee MemberTipper, Davidtipper@tele.pitt.eduDTIPPER
Committee Member Krishnamurthy, Prashantprashant@mail.sis.pitt.eduPRASHK
Date: 6 January 2005
Date Type: Completion
Defense Date: 9 December 2004
Approval Date: 6 January 2005
Submission Date: 4 January 2005
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Telecommunications
Degree: MST - Master of Science in Telecommunications
Thesis Type: Master's Thesis
Refereed: Yes
Uncontrolled Keywords: Greedy algorithm; K-median; Linear Integer Programming; Multi-Constrained Path Problem; Network Clustering; P-median; Power laws of the Internet; QoS routing; Quality of Service routing; Selective Probing; Set Covering
Other ID:, etd-01042005-200859
Date Deposited: 10 Nov 2011 19:30
Last Modified: 15 Nov 2016 13:35


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item