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

Przemysław Mariusz Jaskóła , Andrzej Karbowski

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.
Author Przemysław Mariusz Jaskóła
Przemysław Mariusz Jaskóła,,
-
, Andrzej Karbowski IAiIS
Andrzej Karbowski,,
- The Institute of Control and Computation Engineering
Journal seriesPrzegląd Telekomunikacyjny - Wiadomości Telekomunikacyjne, ISSN 1230-3496, e-ISSN 2449-7487
Issue year2016
No8-9/2016
Pages947-951
Publication size in sheets0.5
Keywords in Polishinżynieria ruchu, maksymalizacja użyteczności, optymalizacja sieciowa, programowanie nieliniowe mieszane
Keywords in Englishmixed integer nonlinear programming, network optimization, traffic engineering, utility maximization
Abstract in PolishKluczowe 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
DOIDOI:10.15199/59.2016.8-9.41
projectDevelopment of methodology of control, decision support and production management. Project leader: Zieliński Cezary, , Phone: 5102, start date 19-05-2015, end date 31-12-2016, 504/02233/1031, Completed
WEiTI Działalność statutowa
Languagepl polski
File
Jaskola-AKarbwoski-KSTiT2016.pdf (file archived - login or check accessibility on faculty) Jaskola-AKarbwoski-KSTiT2016.pdf 240.38 KB
Score (nominal)9
ScoreMinisterial score = 9.0, 27-03-2017, ArticleFromJournal
Ministerial score (2013-2016) = 9.0, 27-03-2017, ArticleFromJournal
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back