Localized Quality of Service Routing for the Internet

by Nelakuditi, Srihari; Zhang, Zhi-Li

• ISBN13: 9781402074776
• ISBN10: 1402074778
• Format: Hardcover
• Copyright: 2003-07-01
• Publisher: Kluwer Academic Pub

Summary

Under Quality of Service (QoS) routing, paths for flows are selected based upon the knowledge of resource availability at network nodes and the QoS requirements of flows. QoS routing schemes proposed differ in the way they gather information about the network state and select paths based on this information. We broadly categorize these schemes into best-path routing and proportional routing. The best-path routing schemes gather global network state information and always select the best path for an incoming flow based on this global view. On the other hand, proportional routing schemes proportion incoming flows among a set of candidate paths. We have shown that it is possible to compute near-optimal proportions using only locally collected information. Furthermore, a few good candidate paths can be selected using infrequently exchanged global information and thus with minimal communication overhead. Localized Quality Of Service Routing For The Internet, describes these schemes in detail demonstrating that proportional routing schemes can achieve higher throughput with lower overhead than best-path routing schemes. It first addresses the issue of finding near-optimal proportions for a given set of candidate paths based on locally collected flow statistics. This book will also look into the selection of a few good candidate paths based on infrequently exchanged global information. The final phase of this book will describe extensions to proportional routing approach to provide hierarchical routing across multiple areas in a large network. Localized Quality Of Service Routing For The Internet is designed for researchers and practitioners in industry, and is suitable for graduate level students in computer science as a secondary text.

Author Biography

Srihari Nelakuditi: University of South Carolina U.S.A. Zhi-Li Zhang: University of Minnesota U.S.A.

Table of Contents

Dedication	v
List of Figures	xi
Preface	xiii
Acknowledgments	xv
Introduction	1	(6)
Problem Setting	7	(6)
Bandwidth Guarantees	7	(1)
Explicit Routing	8	(1)
Link State Updates	9	(1)
Performance Metrics	10	(3)
Related Work	13	(8)
Global QoS Routing	13	(3)
Localized QoS Routing	16	(2)
Sticky Random Routing	17	(1)
Learning Automata based Routing	17	(1)
Hybrid QoS Routing	18	(3)
Localized Proportional Routing: Theoretical Models	21	(22)
Global Optimal Proportional Routing	21	(3)
Localized Proportional Routing	24	(12)
Virtual Capacity Model	25	(2)
Virtual Link based Minimization	27	(3)
Virtual Path based Minimization	30	(2)
Performance Comparison	32	(4)
Alternative Paths and Localized Trunk Reservation	36	(7)
Localized Link-level Trunk Reservation	37	(1)
Localized Path-level Trunk Reservation	38	(2)
Effectiveness of Localized Trunk Reservation	40	(3)
Localized Proportional Routing: Practical Schemes	43	(28)
Heuristic Equalization Strategies	43	(3)
Equalization of Blocking Probabilities	43	(1)
Equalization of Blocking Rates	43	(3)
Proportional Sticky Routing	46	(18)
Proportional flow routing	47	(1)
Computation of flow proportions	48	(2)
Performance Evaluation and Analysis	50	(7)
Heterogeneous Traffic	57	(6)
Sensitivity of psr	63	(1)
Routing Stability	63	(1)
Approximation of ebp	64	(7)
Proportion Computation	65	(1)
Performance Evaluation	65	(6)
Candidate Path Selection	71	(16)
Hybrid Approach to QoS Routing	72	(1)
Widest Disjoint Paths	73	(4)
Performance Analysis	77	(10)
Simulation Environment	78	(1)
Performance of wdp	78	(4)
Comparison of wsp and wdp	82	(5)
Hierarchical Proportional Routing	87	(12)
Hierarchical Routing	87	(1)
Topology and State Aggregation	88	(2)
Hierarchical Source Routing	90	(1)
Hierarchical Next-hop Routing	91	(1)
Performance Evaluation	92	(7)
Simulation Environment	93	(1)
Convergence and Adaptivity	93	(2)
Blocking Performance	95	(4)
Conclusions and Future Work	99	(2)
References	101	(6)
Index	107