A Practical Approach to Trac Engineering using an Unsplittable Multicommodity Flow Problem with QoS Constraints

• Autorzy: Białoń P.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a practical approach to calculating intra-domain paths within a domain of a content-aware network (CAN) that uses source routing. This approach was used in the prototype CAN constructed as a part of the Future Internet Engineering project outcome. The calculated paths must satisfy demands for capacity (capacity for a single connection and for aggregate connections using the given path are considered distinctly) and for a number of path-additive measures like delay, loss ratio. We state a suitable variant of QoS-aware unsplittable multicommodity ow problem and present the solving algorithm. The algorithm answers to the needs of its immediate application in the constructed system: a quick return within a short and fairly predictable time, simplicity and modiability, good behavior in the absence of a feasible solution (returning approximately-feasible solutions, showing how to modify demands to retain feasibility). On the other hand, a certain level of overdimensioning of the network is explored, unlike in a typical optimization algorithm. The algorithm is a mixture of: (i) shortest path techniques, (ii) simplified reference-level multicriteria techniques and parametric analysis applied to aggregate the QoS criteria (iii) penalty and mutation techniques to handle the common constraints. Numerical experiments assessing various aspects of the algorithm behavior are given.

Słowa kluczowe

EN

multicriteria analysis; QoS-aware unsplittable multicommodity flow; traffic engineering

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2016
• Tom: nr 3
• Strony: 25--37
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Białoń P.

• Department of Advanced Information Systems, National Institute of Telecommunications, Szachowa st 1, 04-894 Warsaw, Poland

Bibliografia

• [1] W. Burakowski, H. Tarasiuk, A. Bęben, and G. Danilewicz, “Virtualized network infrastructure supporting co-existence of Parallel Internets”, in Proc. 13th ACIS Int. Conf. Softw. Engin., Netw. and Parallel & Distrib. Comput. SNPD 2012, Kioto, Japan, 2012, pp. 679–684 (doi: 10.1109/SNPD.2012.67).
• [2] A. Iwata, R. Izmailov, D.-S. Lee, B. Sengupta, G. Ramamurthy, and H. Suzuki, “ATM routing algorithms with multiple QOS requirements for multimedia internetworking”, IEICE Trans. Commun., vol. E79-B, no. 8, pp. 999–1006, 1996.
• [3] G. Tsaggouris and C. Zaroliagis, “QoS-aware Multicommodity Flows and Transportation Planning”, in 6th Workshop Algorithmic Methods and Models for Optimization of Railways (ATMOS’06), R. Jacob and M. M¨uller-Hannemann, Eds. OASIcs – OpenAccess Series in Informatics, Technical Report ARRIVAL-TR-030. Schloss Dagstuhl–Leibniz-Center for Informatics, Dagstuhl Publishing, Germany, 2006.
• [4] N. Garg and J. K¨onemann, “Faster and simpler algorithms for multicommodity flow and other fractional packing problems”, in Proc. 39th Ann. Symp. Foundat. of Comp. Sci. FOCS 1998, Palo Alto, CA, USA, 1998, pp. 300–309.
• [5] C. Duhamel and A. Mahul, “An augmented lagrangean approach for the QoS constrained routing problem”, Research Report LIMOS/RR07-15, Universit´ e Blaise-Pascal, Aubi´ere, France, 2007 [Online]. Available: http://limos.isima.fr/IMG/pdf/rr-07-15.pdf
• [6] M. Ghatee, “QoS-based cooperative algorithm for integral multicommodity flow problem”, Comp. Commun., vol. 34, no. 7, pp. 835–846, 2011.
• [7] A. M. Allakany, T. M. Mahomud, K. Okurama, and M. R. Girgis, “Multiple constraints QoS multicast routing optimization algorithm based on Genetic Tabu Search algorithm”, ACSIJ Adv. in Comp. Science: an Int. J., vol. 4, issue 3, pp. 118–125, 2015.
• [8] G. Apostopoulos, D. Williams, S. Kamat, R. Guerin, A. Orda, and T. Przygienda, “QoS routing mechanisms and OSPF extensions”, RFC2676, 1999 [Online]. Available: https://tools.ietf.org/ html/rfc2676
• [9] J. Wang and J. Crowcroft, “QoS routing for supporting multimedia applications”, IEEE J. Selec. Areas in Communi., vol. 14, no. 7, pp. 1228–1234, 1996.
• [10] Y. Wang and Z. Wang, “Explicit routing algorithm for internet traffic engineering”, in Proc. 8th Comp. Commun. and Netw., Boston, MA, USA, pp. 582–588, 1999.
• [11] R. G. Garroppo, S. Giordano, and L. Tavanti, “A survey on multiconstrained optimal path computation: Exact and approximate algorithms”, Computer Networks, vol. 54, no. 17, pp. 3081–3107, 2010.
• [12] A. Kuipers, “Quality of Service routing in the Internet. Theory, complexity and algorithms”, Ph.D. thesis, Delft University, Delft University Press, Delft, 2014.
• [13] A. P. Wierzbicki, M. Makowski, and J. Weesels, Eds., Model-Based Decision Support Methodology with Environmental Applications, Dordrecht, Netherlands: Kluwer Academic Publishers, 2000.
• [14] A. Bęben, Ed., “Specification of Parallel Internet Content Aware Network (version 2)”, The IIP project, Warsaw, Poland, Report 31.01.2012, Task Z2.6.
• [15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. MIT Press and McGraw-Hill, 2001 (1990).
• [16] A. Medina, A. Laghina, I. Matta, and J. Byers, “BRITE: Universal Topology Generation from a User’s Perspective”, Boston University, Boston, 2001, user manual” [Online]. Available: http://www.cs.bu.edu/brite/publications/usermanual.pdf