Quality-of-service provisioning via stochastic path selection under Weibullian link delays

ABSTRACT

We study the problem of finding the most likely path satisfying a requested additive Quality-of-Service (QoS) value, such as delay. The link metrics are defined as random variables following Weibull probability distributions as empirically reported in [13] and analytically derived in [12]. The problem of finding the most likely path is NP-Hard [24]. Our approach involves reducing the complicated probability convolutions necessary to calculate the most probable path that satisfies a requested delay value. With the reduction of the objective function, an extended Bellman-Ford algorithm is devised to solve the problem. The resulting approach have the same complexity as the standard Bellman-Ford algorithm. Our reduced objective function only needs the location parameter of the Weibull distributions, hence avoiding the complexity of inferring the shape and scale parameters. We evaluate the performance of our approach by simulations and conclude with possible extensions of our work.

References

1. Network simulator - ns - 2. http://www.isi.edu/nsnam/ns/index.html.
2. R. K. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, First edition, 1993.
3. ATM Forum. Private Network-to-Network Interface Specification version 1.1. ftp://ftp.atmforum.com/pub/approved-specs/af-pnni-0055.002.pdf, April 2002.
4. B. Choi, S. Moon, Z. Zhang, K. Papagiannaki and C. Diot. Analysis of point-to-point packet delay in an operational network. IEEE INFOCOM 2004 Hong Kong, pages 1797--1807, March 2004.
5. A.-L. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286(5439):509--512, 1999.
6. BRITE: Boston University Representative Internet Topology Generator.
7. S. Chen and K. Nahrstedt. An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions. IEEE Network Magazine, pages 64--79, November/December 1998.
8. H. Frank. Shortest paths in probabilistic graphs. Operations Research, 17:583--599, 1969.
9. G. Apostolopoulos, R. Guerin, S. Kamat and S. Tripathi. Improving QoS routing performance under inaccurate link state information. Proceedings of the 16th International Teletraffic Congress ITC'16, Edinburgh, UK, June 1999.
10. M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Francisco, January 1979.
11. D. Ghosh and R. Acharya. A probabilistic scheme for hierarchical qos routing. IEEE ICON, pages 416--421, October 2001.
12. I. Norros. On the use of fractional Brownian motion in the theory of connectionless networks. IEEE JSAC, 13(6):953--962, August 1995.
13. K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, C. Diot. Measurement and analysis of single-hop delay on an IP backbone network. IEEE JSAC, 21(6):908--921, August 2003.
14. J. Kleinberg, Y. Rabani, and É. Tardos. Allocating bandwidth for bursty connections. In STOC '97 (El Paso, TX), pages 664--673. 1997.
15. T. Korkmaz and M. Krunz. Bandwidth-delay constrained path selection under inaccurate state information. IEEE/ACM ToN, 11(3):384--398, June 2003.
16. S. S. Lam. Back to the future part 4: the internet. SIGCOMM Computer Communication Review, 35(1):3--12, 2005.
17. W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the self-similar nature of ethernet traffic. IEEE/ACM ToN, 2(1):1--15, 1994.
18. D. H. Lorenz and A. Orda. Qos routing in networks with uncertain parameters. IEEE/ACM Transactions on Networking, 6(6):768--778, 1998.
19. A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: Universal topology generation from a user's perspective. Technical Report 2001--003, 1 2001.
20. P. V. Mieghem, F. Kuipers, T. Korkmaz, M. Krunz, M. Curado, E. Monteiro, X. Masip-Bruin, J. Sole-Pareta, and S. Sanchez-Lopez. Quality of Service Routing. Chapter 3 in Quality of Future Internet Services, EU-COST 263 Final Report, edited by Smirnov et al. in Springer LNCS 2856, pp. 80--117, December 2003.
21. J. Moy. Open Shortest Path First Version 2 (OSPFv2). Request for Comments 2328, http://www.ietf.org/rfc/rfc2328.txt, April 1998.
22. Paul Embrechts, Claudia Kluppelberg and Thomas Mikosch. Modelling Extremal Events for Insurance and Finance. Springer-Verlag, July 1997. (p. 51).
23. R. Guerin and A. Orda. QoS Routing in Networks with Inaccurate Information. IEEE INFOCOM '97 Kobe, Japan, pages 92--100, April 1997.
24. R. Guerin and A. Orda. QoS Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 7(3), June 1999.
25. Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). Request for Comments (RFC 1771), March 1995.
26. S. Chen and K. Nahrstedt. Distributed QoS Routing with Imprecise State Information. ICCCN, 1998.
27. A. Shaikh, J. Rexford, and K. G. Shin. Evaluating the impact of stale link state on quality-of-service routing. IEEE/ACM Trans. Netw., 9(2):162--176, 2001.
28. S. Uludag, K. Lui, K. Nahrstedt, and G. Brewster. Analysis of Topology aggregation Techniques for QoS Routing. to appear in ACM Computing Surveys, 2007.
29. S. Uludag, K.-S. Lui, and Z. E. Uludag. Probabilistic Path Selection under Inaccuracy via Augmented Shortest Path Algorithms. In IEEE Globecom 2006, San Francisco, CA, November 2006.
30. V. P. Chistyakov. A Theorem on sums of independent positive random variables and its applications to branching randon processes. Theory of Probability and its applications, 9(1):640--648, 1964.
31. B. M. Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1617--1622, December 1988.
32. L. Xiao, K.-S. Lui, J. Wang, and K. Nahrstedt. QoS Extension to BGP. Proceedings of 10th IEEE International Conference on Network Protocols (ICNP 2002), Paris, France, November 2002.
33. L. Xiao, J. Wang, K.-S. Lui, and K. Nahrstedt. Advertising interdomain QoS routing information. IEEE Journal on Selected Areas in Communications, 22(10):1949--1964, December 2004.
34. Y. Xiao, K. Thulasiraman, and X. Guoliang. Approximation and heuristic algorithms for delay constrained path selection under inaccurate state information. In IEEE International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks, QSHINE 2004, pages 130--137, Dallas, TX, October 2004.
35. O. Younis and S. Fahmy. Constraint-based routing in the internet: Basic principles and recent research. IEEE Communications Surveys & Tutorials, 5(1), 2003.
36. X. Yuan and G. Yang. Empirical Probability Based QoS Routing. In IEEE International Conference on Communications, ICC 2003, pages 1713--1717, Anchorage, Alaska, May 2003.
37. X. Yuan, W. Zheng, and S. Ding. A comparative study of qos routing schemes that tolerate imprecise state information. In International Conference on Computer Communications and Networks (ICCCN), pages 230--235, October 2002.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation evaluation

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

  • Network types

    • Packet-switching networks

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications

      • Software architectures

        • Simulator / interpreter

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Stochastic control and optimization