Return to search

A CLUSTERING-BASED SELECTIVE PROBING FRAMEWORK TO SUPPORT INTERNET QUALITY OF SERVICE ROUTING

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.

Identiferoai:union.ndltd.org:PITT/oai:PITTETD:etd-01042005-200859
Date06 January 2005
CreatorsJariyakul, Nattaphol
ContributorsDr. Prashant Krishnamurthy, Dr. Taieb Znati, Dr. David Tipper
PublisherUniversity of Pittsburgh
Source SetsUniversity of Pittsburgh
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.library.pitt.edu/ETD/available/etd-01042005-200859/
Rightsunrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Pittsburgh or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.

Page generated in 0.0023 seconds