Efektywne metody jednoczesnego wyznaczania optymalnego routingu i przydziału pasma w sieci

• Autorzy: Jaskóła P. , Karbowski A.

Identyfikatory

DOI

10.15199/59.2016.8-9.41

Warianty tytułu

EN

Effective methods of simultaneous routing and network bandwidth allocation

• Konferencja: XXXII Krajowe Sympozjum Telekomunikacji i Teleinformatyki (XXXII ; 26-28.09.2016 ; Gliwice, Polska)
• Języki publikacji: PL

Abstrakty

PL

Kluczowe dla inżynierii ruchu zadanie przydziału dostępnego pasma do strumieni ruchu można sformułować w kategoriach maksymalizacji użyteczności, będącej rosnącą funkcją przepływności. Nie powinno się go rozpatrywać w oderwaniu od zagadnienia wyznaczenia optymalnego routingu, gdyż wybór ścieżek determinuje obciążenie poszczególnych łączy, a wraz z ich przepustowością definiuje ograniczenia w zadaniu optymalizacji. Problem jednoczesnego wyznaczania optymalnego routingu i alokacji pasma należy niestety do klasy zadań NP-trudnych. W niniejszym artykule pokazano, że możliwe jest rozwiązanie zadań o niewielkiej wymiarowości przy użyciu efektywnych solwerów nieliniowego programowania mieszanego. Zaproponowano też sposób otrzymywania w czasie wielomianowym dopuszczalnych, suboptymalnych rozwiązań , który jest możliwy do zastosowania w większych zadaniach.

EN

The key problem of the network traffic engineering is an allocation of the available bandwidth to the traffic flows. It can be formulated in terms of maximizing the total utility, being a concave function of the allocation vector in the presence of constraints defined by the throughput of network links. This problem is coupled through the constraints with a routing problem, because the choice of paths determines the load on links. The problem of joint calculation of the optimal routing and bandwidth allocation is unfortunately NP-hard. The paper presents a mixed integer nonlinear programming formulation of the problem and demonstrates, that for small examples it can be solved in a reasonable time. The proposition of the heuristic method for obtaining suboptimal, feasible solution in polynomial time is then presented.

Słowa kluczowe

PL

inżynieria ruchu; maksymalizacja użyteczności; optymalizacja sieciowa; programowanie nieliniowe mieszane

EN

mixed integer nonlinear programming; network optimization; traffic engineering; utility maximization

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2016
• Tom: nr 8-9
• Strony: 947--951, CD
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Jaskóła P.

• Naukowa i Akademicka Sieć Komputerowa NASK, Kolska 12, 01-045 Warszawa

autor

Karbowski A.

• Naukowa i Akademicka Sieć Komputerowa NASK, Kolska 12, 01-045 Warszawa
• Instytut Automatyki i Informatyki Stosowanej Politechniki Warszawskiej

Bibliografia

• [1] D. Bertsekas, R. Gallager, Data Networks, Second Edition. Englewood Cliffs: Prentice-Hall International, Inc., 1992.
• [2] N. Brownlee, C. Mills, G. Ruth, “Traffic Flow Measurement: Architecture,” RFC 2722 (Informational), Internet Engineering Task Force, October 1999.
• [3] J. Rajahalme, A. Conta, B. Carpenter, S. Deering, “IPv6 Flow Label Specification,” RFC 3697 (Proposed Standard), Internet Engineering Task Force, March 2004.
• [4] F. Kelly, A. Maulloo, D. Tan, “Rate control in communication networks: shadow prices, proportional fairness and stability,” Journal of the Operational Research Society, vol. 49, str. 237–252, 1998.
• [5] W. Ogryczak, T. Śliwiński, A. Wierzbicki, “Fair resource allocation schemes and network dimensioning problems,” Journal of Telecommunications and Information Technology, vol. 3/2003, no. 3, str. 34–42, 2003.
• [6] P. Jaskóła, P. Arabas, A. Karbowski, “Simultaneous routing and flow rate optimization in energy-aware computer networks,” International Journal of Applied Mathematics and Computer Science, vol. 26, str. 231–243, 2016.
• [7] J. Wang, L. Li, S. H. Low, J. C. Doyle, “Can shortest-path routing and TCP maximize utility,” in Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, USA, March 30 - April 3 2003, str. 2049–2056.
• [8] M. Drwal, “Approximation algorithms for utility-maximizing network design problem,” in Progress in Systems Engineering. Springer, 2015, str. 411–416.
• [9] A. P. Bianzino, L. Chiaraviglio, M. Mellia, J.-L. Rougier, “Grida: Green distributed algorithm for energy-efficient ip backbone networks,” Comput. Netw., vol. 56, no. 14, str. 3219–3232, Sep. 2012. [Online]. http://dx.doi.org/10.1016/j.comnet.2012.06.011