Czasopismo | PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE | Rocznik 2016 - zeszyt 8-9

EFEKTYWNE METODY JEDNOCZESNEGO WYZNACZANIA OPTYMALNEGO ROUTINGU I PRZYDZIAŁU PASMA W SIECI EFFECTIVE METHODS OF SIMULTANEOUS ROUTING AND NETWORK BANDWIDTH ALLOCATION

10.15199/59.2016.8-9.41

nr katalogowy: 101894
10.15199/59.2016.8-9.41

Kluczowe dla in˙zynierii ruchu zadanie przydziału dost˛epnego pasma do strumieni ruchu mo˙zna sformułowac ´ w kategoriach maksymalizacji uz˙ytecznos´ci, be˛da˛cej rosna˛ca˛ funkcja˛ przepływnos´ci. Nie powinno sie˛ go rozpatrywa ´c w oderwaniu od zagadnienia wyznaczenia optymalnego routingu, gdyz˙ wybór s´ciez˙ek determinuje obcia˛z˙enie poszczególnych ła˛czy, a wraz z ich przepustowos´cia˛definiuje ograniczenia w zadaniu optymalizacji. Problem jednoczesnego wyznaczania optymalnego routingu i alokacji pasma nale˙zy niestety do klasy zada´n NP-trudnych. W niniejszym artykule pokazano, z˙e moz˙liwe jest rozwia˛zanie zadan´ o niewielkiej wymiarowo´sci przy u˙zyciu efektywnych solwerów nieliniowego programowania mieszanego. Zaproponowano te˙z sposób otrzymywania w czasie wielomianowym dopuszczalnych, suboptymalnych rozwia˛zan´ , który jest moz˙liwy do zastosowania w wi˛ekszych zadaniach. Abstract: 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: in˙zynieria ruchu, maksymalizacja u˙zyteczno ´sci, optymalizacja sieciowa, programowanie nieliniowe mieszane Keywords: mixed integer nonlinear programming, network optimization, traffic engineering, utili[...]

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. ´ Sliwi´nski, 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

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 74316 "Entropy Based Intrusion-t..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD TELEKOMUNIKACYJNY - e-zeszyt (pdf) 2016-8-9 licencja: Osobista Produkt cyfrowy	30.50 zł

Prenumerata

PRZEGLĄD ELEKTROTECHNICZNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

762.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	1002.00 zł brutto 927.78 zł netto 74.22 zł VAT (stawka VAT 8%)

1002.00 zł

PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD ELEKTROTECHNICZNY - papierowa prenumerata roczna	960.00 zł brutto 888.89 zł netto 71.11 zł VAT (stawka VAT 8%)
PRZEGLĄD ELEKTROTECHNICZNY - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

1002.00 zł

Zeszyt

2016-8-9

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma