Roch A. Guérin
Ariel Orda
- 1 R. Cherukuri, D. Dykeman (Eds.), and M. Goguen (chair), "PNNI draft specification," ATM Forum 94-0471, Nov. 1995.Google Scholar
- 2 G. Apostolopoulos, R. Gurrin, S. Kamat, A. Orda, T. Przygienda, and D. Williams, "QoS routing mechanisms and OSPF extensions," Internet Draft, draft-guerin-qos-routing-ospf-0.5.txt, to appear as Experimental RFC. {Online}. Available HTTP: http://www.seas.upenn.edturguerin/qos_ospf.html Google Scholar
- 3 R. Gurrin, S. Kamat, and S. Herzog, "QoS path management with RSVP," in Proc. GLOBECOM, Phoenix, AZ, Nov. 1997, pp. 1914-1918.Google Scholar
- 4 T. E. Tedijanto, R. O. Onvural, D. C. Verma, L. G iin, and R. A. Gurrin, "NBBS path selection framework," IBM Syst. J.: Special Issue on Networking BroadBand Services, vol. 34, no. 4, pp. 629-639, Nov. 1995. Google Scholar
- 5 A. Shaikh, J. Rexford, and K. Shin, "Dynamics of quality-of-service routing with inaccurate link-state information," Univ. of Michigan, Ann Arbor, MI, Tech. Rep. CSE-TR-350-97, Nov. 1997.Google Scholar
- 6 G. Apostolopoulos, R. Gurrin, S. Kamat, and S. Tripathi, "Quality of service based routing: A performance perspective," in Proc. SIGCOMM, Vancouver, ON, Canada, Sept. 1998, pp. 17-28. Google Scholar
- 7 S. Shenker, C. Partridge, and R. Gurrin, Specification of Guaranteed Quality of Service, Request For Comments (Proposed Standard) RFC 2212, Internet Engineering Task Force, Sept. 1997. Google Scholar
- 8 S. Sathaye, "ATM forum traffic management specification version 4.0," ATM Forum 95-0013, Dec. 1995.Google Scholar
- 9 P. Samudra, "ATM user-network interface (UNI) signalling specification version 4.0," ATM Forum 95-1434, Dec. 1995.Google Scholar
- 10 G. Apostolopoulos, R. Gurrin, and S. Kamat, "Implementation and performance measurements of QoS routing extensions to OSPF," in Proc. INFOCOM, New York, NY, Mar. 1999, pp. 680-688.Google Scholar
- 11 J. Moy, OSPF version 2, Request For Comments (Standard) RFC 2178, Internet Engineering Task Force, July 1997.Google Scholar
- 12 R. Gurrin, A. Orda, and D. Williams, "QoS routing mechanisms and OSPF extensions," in Proc. GLOBECOM, Phoenix, AZ, Nov. 1997, pp. 1903-1908.Google Scholar
- 13 G. Apostolopoulos, R. Gurrin, S. Kamat, and S. Tripathi, "Improving QoS routing performance under inaccurate link state information," in Proc. ITC'16, pp. 1351-1362, June 1999.Google Scholar
- 14 D. H. Lorenz and A. Orda, "QoS Routing in networks with uncertain parameters," IEEE/ACM Trans. Networking, vol. 6, pp. 768-778, Dec. 1998. Google Scholar
- 15 D. H. Lorenz and A. Orda, "Optimal partition of QoS requirements on unicast paths and multicast trees," in Proc. INFOCOM, New York, NY, Mar. 1999, pp. 246-253. Google Scholar
- 16 L. Kleinrock and F. Kamoun, "Hierarchical routing for large networksmPerformance evaluation and optimization," Comput. Networks, vol. 1, pp. 82-92, 1977.Google Scholar
- 17 A. Bar-Noy and P. M. Gopal, "Topology distribution cost vs. efficient routing in large networks," in Proc. SIGCOMM, Philadelphia, PA, Sept. 1990, pp. 242-252. Google Scholar
- 18 W. C. Lee, "Topology aggregation for hierarchical routing in ATM networks," in Proc. SIGCOMM, pp. 82-92, Apr. 1995.Google Scholar
- 19 W. C. Lee, "Spanning tree methods for link state aggregation in large communication networks," in Proc. INFOCOM, Boston, MA, Apr. 1995, pp. 297-302. Google Scholar
- 20 U. Gremmelmaier, J. Puschner, M. Winter, and P. Jocher, "Performance evaluation of the PNNI routing protocol using and emulation tool," in Proc. ISS, Toronto, ON, Canada, Sept. 1997, vol. 1, pp. 401-408.Google Scholar
- 21 B. Awerbuch, B. Berger, L. Cowen, and D. Peleg, "Fast network decomposition," in Proc. 11th Ann. Symp. Principles of Distributed Computing, Vancouver, BC, Canada, Aug. 1992, pp. 169-177. Google Scholar
- 22 B. Awerbuch, B. Berger, L. Cowen, and D. Peleg, "Near linear cost sequential and distributed constructions of sparse neighborhood covers," in Proc. 34th Annu. Symp. Foundations of Computer Science, Palo Alto, CA, Nov. 1993, pp. 638-647.Google Scholar
- 23 N. Linial and M. Saks, "Low diameter graph decompositions," Combinatorica, vol. 13, no. 4, pp. 441-454, 1993.Google Scholar
- 24 Y. Bartal, "Probabilistic approximationof metric spaces and its algorithmic applications," in Proc. 37th Annu. Symp. Foundations of Computer Science, Burlington, VT, Oct. 1996, pp. 184--193. Google Scholar
- 25 B. Awerbuch, B. Berger, L. Cowen, and D. Peleg, "Fast distributed network decomposition and covers," J. Parallel Distrib. Comput., vol. 39, no. 2, pp. 105-114, Dec. 1996. Google Scholar
- 26 R. Gutrin and A. Orda, "QoS-based routing in networks with inaccurate information: Theory and algorithms," IBM, T. J. Watson Research Center, Yorktown Heights, NY, Res. Rep. RC 20515, July 1996.Google Scholar
- 27 A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: The multiple node case," IEEE/ACM Trans. Networking, vol. 2, pp. 137-150, Apr. 1994. Google Scholar
- 28 L. Georgiadis, R. Gutrin, V. Peris, and K. N. Sivarajan, "Efficient network QoS provisioning based on per node traffic shaping," IEEE/ACM Trans. Networking, vol. 4, pp. 482-501, Aug. 1996. Google Scholar
- 29 M. R. Garey and D. S. Johnson, Computers and Intractability. San Francisco, CA: Freeman, 1979.Google Scholar
- 30 J. B. Rosen, S. Z. Sun, and G. L. Xue, "Algorithms for the quickest path problem," Comput. Oper. Res., vol. 18, pp. 579-584, 1991. Google Scholar
- 31 A. Orda, "Routing with end to end QoS guarantees in broadband networks," this issue, pp. 365-374. Google Scholar
- 32 T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. Cambridge, MA: MIT Press, 1990. Google Scholar
- 33 R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Networks Flows. Englewood Cliffs, NJ: Prentice-Hall, 1993.Google Scholar
- 34 E. L. Lawler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart and Winston, 1976.Google Scholar
- 35 N. Megiddo, "Combinatorial optimization with rational objective functions," Math. Oper. Res., vol. 4, pp. 414-424, 1979.Google Scholar
- 36 R. K. Ahuja, J. L. Batra, and S. K. Gupta, "Combinatorial optimization with rational objective functions: A communication," Math. Oper. Res., vol. 4, p. 314, 1983.Google Scholar
Index Terms
- QoS routing in networks with inaccurate information: theory and algorithms
Recommendations
Multi-class QoS routing strategies based on the network state
With the exploding volume of traffic and expanding Quality of Service (QoS) requirements from emerging multimedia applications, extensive research has been carried out to address various issues in QoS routing with respect to the Internet. Traffic is ...
Analysis of Topology Aggregation techniques for QoS routing
We study and compare topology aggregation techniques used in QoS routing. Topology Aggregation (TA) is defined as a set of techniques that abstract or summarize the state information about the network topology to be exchanged, processed, and maintained ...
Routing with QoS constraints in integrated services networks
MMNET '97: Proceedings of the IEEE Conference on Protocols for Multimedia Systems - Multimedia Networking (PROMSMmNet'97)Abstract: Though the complexity for finding QoS guaranteed route in an integrated services network is proved to be NP-complete, the proof has been done without the assumption of any specific service discipline. Because each service discipline has ...
Reviews
Hosam M. F. Abo El Fotoh
The authors present a number of theoretical results on the effect of uncertainty of information about the available link bandwidth and link delay on routing decisions for flows that require QoS guarantees in terms of bandwidth and end-to-end delay. The notion of uncertainty is captured via weighted probabilistic graph models. The paper establishes two important results. First, if the uncertainty of the link bandwidth is expressed using a probability distribution function, an efficient algorithm exists. Second, the uncertainty in link delay yields an NP-hard problem. Two delay-related problems have been shown to be NP-hard, the first—where the delay is a function of the available link bandwidth (rate-based)—via a reduction from the shortest-weight-constrained-path problem, and the second (delay-based) via a reduction from the k th-largest-subset problem. The paper investigates some special cases where the complexity of the delay-related problems can be reduced. For example, efficient algorithms are presented for the cases of identical delays, identical PDFs, and exponential distribution. Also, near-optimal and pseudopolynomial algorithms are presented for the delay problem. The practicality of these results depends on the possibility of making estimates of the delay and bandwidth probabilities that truly capture the inaccuracy of the information about the network links. The paper would be of interest to both theoreticians and network designers.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments