Wyniki 1-2 spośród 2 dla zapytania: authorDesc:"Ilya Kalesnikau"

PORÓWNANIE DWÓCH METOD GENERACJI ŚCIEŻEK DLA PROBLEMU WYMIAROWANIA SIECI ODPORNYCH NA AWARIE DOI:10.15199/59.2017.8-9.52


  Global Rerouting (also known as unrestricted flow reconfiguration or dynamic rerouting [1,6]) is a traffic routing and protection strategy applicable to communication networks with multiple partial link failures. Such a network at any instant of time may change its state described by the currently available capacity of each link. In order to realize all demands and at the same time not to exceed the current link capacities, traffic flows should be appropriately controlled. The optimization problem related to the GR strategy can be formulated as a link-path linear program (LP). Such a LP formulation is non-compact due to an exponential number of possible paths in the network graph, so the path generation (PG) algorithm has to be applied. The PG algorithm is based on iterative adding new paths to the problem. Such paths are obtained by solving the so called pricing problem. It happens that the studied optimization can be as well formulated in the node-link notation. The resulting node-link LP unlike the link-path LP is compact, so there is no need to apply path generation. The reason for considering the link-path LP for GR is that such considerations are important for practical network routing protection strategies (GR is not applicable in practice), like flow thinning (FT) [4] or affine flow thinning (AFT) [5]. Using link-path LP for FT and AFT is unavoidable as the corresponding optimizations problems are NP-hard and hence their compact LP formulations are not known. Moreover, path generation for FT and AFT is technically more complicated and time consuming than for GR. In consequence, it is much easier to analyze various options of the path generation algorithm for GR than for FT and AFT, having in mind that the general conclusions from such analytical studies for GR will be valid for FT and AFT as well. In the presented paper we formulate an appropriate GR optimization problem, and derive and study two different versi[...]

WPŁYW SPOSOBU DOBORU DRZEW ROUTINGOWYCH NA PRZEPUSTOWOŚĆ RUCHOWĄ MULTICASTOWYCH SIECI RADIOWYCH DOI:10.15199/59.2019.7.42


  1. WSTĘP Rozpatrywany w artykule problem optymalizacyjny dotyczy maksymalizacji przepustowości kratowych sieci radiowych obsługujacych ruch multicastowy w trybie wielodostępu czasowego TDMA (time division multiple access [7]). Prezentowane rozważania stanowią rozszerzenie artykułu [5], w którym Czytelnik znajdzie dokładny opis poruszanej poniżej tematyki. Rozwiązywany problem zakłada, że na początku każdej kolejnej ramki TDMA węzeł źródłowy każdego z rozważanych strumieni ruchu generuje nowy pakiet, który będzie następnie dostarczony do ustalonego dla danego strumienia zbioru węzłów docelowych (ujść) ze skończonym (i rozsądnym) opóźnieniem. Transmisja generowanych w ten sposób pakietów odbywa się zgodnie z zadanym dla danego strumienia multicastowym drzewem routingowym, o korzeniu umiejscowionym w węźle źródłowym i obejmującym wszystkie węzły docelowe. W ramach ustalonego drzewa każdy węzeł (z wyjątkiem liści) transmituje pochodzące ze źródła (uprzednio odebrane) pakiety do swoich sąsiadów w drzewie korzystając z transmisji rozsiewczej (broadcast). Przedmiotem optymalizacji jest znalezienie najkrótszej ramki TDMA, która powtarzana cyklicznie zapewni bezstratną obsługę opisanego w powyższy sposób ruchu pakietowego. Zauważmy, że w celu określenia ramki należy dla każdej jej szczeliny czasowej wyznaczyć zbiór węzłów transmitujących oraz, dla każdego z nich, zbiór węzłów odbierających. Rozpatrywany problem może znaleźć zastosowanie na przykład w sieciach sensorowych, w których źródłami strumieni są sensory wysyłające cyklicznie pakiety zawierające wyniki pomiarów przeznaczone do węzłów sterujących pewnymi urządzeniami. W takich sieciach efektywność ruchowa rozumiana jako maksymalna częstotliwość pozyskiwania danych uzyskiwana jest właśnie poprzez minimalizację długości ramki. W przedstawionym artykule badamy wpływ sposobu predefiniowania multicastowych drzew routingowych przeznaczonych dla poszczególnych strumieni ruchu [...]

 Strona 1