Optimizacija neblokirajućih paketskih mreža upotrebom praktičnog protokola za rutiranje sa balansiranjem saobraćaja

Abstract

Kvalitetan odabir strategije rutiranja u paketskoj mreži u velikoj meri utiče na pouzdanost mreže i kvalitet prenosa podataka u njoj. Odabrana strategija rutiranja utiče i na stepen iskorišćenja različitih mrežnih resursa. Loše odabrano rutiranje može prouzrokovati stvaranje uskih grla u mreži i dovesti do blokade određenih linkova. Takođe, od primenjene strategije rutiranja zavisi kašnjenje pri prenosu paketa, kao i cena mreže. U cilju odabiranja ispravne strategije rutiranja za neku mrežnu topologiju i date korisničke zahteve, vrši se optimizacija rutiranja u mreži. Proces optimizacije rutiranja za cilj ima određivanje putanja paketa tako da se postigne što bolja vrednost neke od mrežnih performansi. U zavisnosti od problema koji se rešava, optimizacija rutiranja može imati za cilj maksimizaciju propusne moći mreže, minimizaciju cene mreže, minimizaciju kašnjenja u prenosu i slično. U ovome radu bavićemo se problemima optimizacije rutiranja u cilju maksimizacije propusne moći i minimizacije cene mreže. Pri tome, želimo da komunikaciona mreža bude neblokirajuća. To znači da mreža mora garantovati servis za sve korisnike koji generišu ili primaju saobraćaj u okviru dozvoljenih granica. Nezavisno od trenutnog stanja saobraćaja u mreži, korisnički zahtevi za slanje ili prijem paketa moraju biti usluženi, ukoliko ne izlaze iz okvira dozvoljenih vrednosti. Okosnicu ovog rada predstavlja predlog nove šema rutiranja zasnovane na balansiranju saobraćaja i rutiranju po najkraćoj putanji, koju nazivamo rutiranje sa balansiranjem saobraćaja (RBS). Predložena šema rutiranja može se optimizovati tako da se ostvari maksimalna propusna moć mreže ili minimalna cena mreže, a za optimizaciju se koristi linearno programiranje. Glavnu prednost predložene strategije rutiranja predstavlja realna mogućnost njene implementacije. Naime, rutiranje po najkraćoj putanji je u širokoj primeni, a predložena šema rutiranja je modifikacija koja se relativno lako realizuje. Dimenzija linearnog programa koji koristimo je prihvatljiva za praktičnu primenu, kao i vreme...

The choice of the routing strategy in a packet network has the great impact on the reliability and the overall quality of data transmission. The chosen routing strategy also has an impact on the usage of different network resources, and bad routing decisions can cause bottlenecks in the network, and limit the throughput. Additionally, network latency as well as network cost also depend on the chosen routing scheme. In order to determine the best routing strategy for the given network and expected traffic, routing optimization is performed. The goal of routing optimization is achieving the best possible value for the chosen network performance metric. Depending on the problem that is being solved, optimization can be performed to maximize the network throughput, minimize the network cost, minimize the latency, etc. In this paper, we will address the problems of network throughput maximization, and network cost minimization. We will focus on the non-blocking networks, which guarantee the service to all users that are generating and receiving the traffic within the defined boundaries, regardless of the current traffic distribution in the network. In this paper, we will propose the novel routing scheme, based on load balancing and shortest path routing. We will refer to the proposed scheme as load balanced routing (LBR). The proposed routing protocol can be optimized using linear programming, in order to minimize the cost, or maximize the network throughput. The proposed routing scheme can easily be deployed in practice. Namely, shortest path routing is widely used, and the proposed routing is a modification that can relatively easy be implemented. The dimension of the linear program is acceptable, as well as the time needed to perform the optimization. With the proposed routing, it is possible toguarantee the service to the greater number of users, then in case of the regular shortest path routing. Also, the cost of servicing a given number of users is smaller if the proposed routing is applied instead of the shortest path routing. First, we will introduce the proposed load balanced routing, and the linear program for its optimization. Then, we will analyze the performance of the proposed routing scheme, and compare it with the performance of the shortest path routing. In particular,...