Title
Optimizacija i implementacija naprednih protokola za rutiranje
Creator
Maksić, Nataša D., 1983-
Copyright date
2014
Object Links
Select license
Autorstvo-Nekomercijalno-Bez prerade 3.0 Srbija (CC BY-NC-ND 3.0)
License description
Dozvoljavate samo preuzimanje i distribuciju dela, ako/dok se pravilno naznačava ime autora, bez ikakvih promena dela i bez prava komercijalnog korišćenja dela. Ova licenca je najstroža CC licenca. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/deed.sr_LATN. Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Datum odbrane: 15.12.2014.
Other responsibilities
mentor
Smiljanić, Aleksandra, 1970-
član komisije
Reljin, Irini, 1952-
član komisije
Čiča, Zoran, 1979-
član komisije
Todorović, Branislav.
Academic Expertise
Tehničko-tehnološke nauke
University
Univerzitet u Beogradu
Faculty
Elektrotehnički fakultet
Alternative title
Optimization and implementation of the advanced routing protocols
Publisher
[N. Maksić]
Format
166 listova
description
Telekomunikacije i elektronika - Arhitektura svičeva i rutera / Telecommunications and electronics - Switch and router architecture
Abstract (sr)
Ova disertacija u prvom delu analizira protokole rutiranja u topologijama data
centara. Posebna pažnja je posvećena dvofaznim protokolima rutiranja koji u pravilnim
topologijama data centara sa velikim brojem alternativnih putanja omogućavaju
izbegavanje zagušenja u mreži. U disertaciji je predložen novi algoritam za
optimizovano dvofazno balansiranje, LB-ECR, koji omogućava bolje iskorišćenje
komunikacionih mreža data centra. Korišćenjem metoda linearnog programiranja LBECR
maksimizuje protok bez gubitaka za date saobraćajne zahteve svičeva. LB-ECR se
oslanja na ECMP rutiranje koje je uobičajeno u data centrima jer koristi alternativne
putanje iste cene. Dvofazno balansiranje omogućava pojednostavljenje linearnog
modela eliminacijom saobraćajnih tokova i smanjuje mogućnost zagušenja
raspoređivanjem saobraćaja po manje iskorišćenim linkovima mreže. Pojednostavljenje
linearnog modela omogućava njegovo rešavanje za mreže velikih data centara.
Disertacija sadrži pregled topologija i načina rutiranja u data centrima i rezultate
poređenja različitih algoritama rutiranja u tipičnim topologijama data centara.
Pored optimizacije rutiranja, disertacija razmatra algoritme ažuriranja lukap
tabela rutera. Drugi deo disertacije sadrži pregled lukap algoritama i algoritama
ažuriranja, i ispitivane su performanse ažuriranja dva napredna lukap algoritma.
Izvedene su formule za proračun najgoreg slučaja zauzeća memorija lukap bloka, dok
rezultati simulacije pokazuju zauzeće memorije za tipične tabele rutiranja. Prikazani su i
rezultati broja pristupa memorijama lukap bloka u toku ažuriranja, kao i kompleksnost
algoritama ažuriranja i vreme izvršavanja za tipične tabele rutiranja.
Treći deo disertacije obuhvata opis implementacija algoritama rutiranja sa
balansiranjem i algoritama ažuriranja lukap tabela, kao i načina integracije ovih
implementacija u okviru rutera.
Abstract (en)
The first part of this dissertation presents analysis of the routing protocols in
data center topologies. Emphasis is put on two-phase routing protocols which enable
congestion avoidance in data center topologies, which are regular and have significant
number of alternative paths. This dissertation proposes new two-phase routing
algorithm, LB-ECR, which enables better utilization of data center networks. Using the
method of linear programming, LB-ECR maximises the loss-free throughput for the
given required traffic of the switches. LB-ECR is based on ECMP routing which is
common in data centers due to its utilization of alternative equal-cost paths. Two-phase
balancing enables simplification of the linear model by eliminating traffic flows and
decreases the possibility of congestion by distributing traffic among less used links.
Simplification of the linear model simplifies its solution for large data centers. The first
part of this dissertation gives an overview of the network topologies and the routing in
data centers, and performance comparison of different routing algorithms in typical
data center topologies.
In addition to the routing optimization, this dissertation examines the algorithms
for updating the lookup tables of Internet routers. The second part of this dissertation
provides an overview of the lookup and update algorithms. Updating performance of
two advanced lookup algorithms is examined. We develop formulas for the worst-case
memory requirements for two fast lookup algorithms, while we show through
simulations the memory requirements for typical routing tables. We also evaluate the
number of memory accesses to the lookup modules during updates, the complexity of
the updating algorithms, as well as their execution time for typical routing tables.
The third part of this dissertation encompasses description of the
implementations of the two-phase routing algorithms and of the lookup update
algorithms, as well as the integration of these components inside the router.
Authors Key words
ruter, data centar, optimalno rutiranje, ažuriranje IP lukap tabela, implementacija
Authors Key words
router, data center, optimal routing, IP lookup table updating, implementation
Classification
621.3
Type
Tekst
Abstract (sr)
Ova disertacija u prvom delu analizira protokole rutiranja u topologijama data
centara. Posebna pažnja je posvećena dvofaznim protokolima rutiranja koji u pravilnim
topologijama data centara sa velikim brojem alternativnih putanja omogućavaju
izbegavanje zagušenja u mreži. U disertaciji je predložen novi algoritam za
optimizovano dvofazno balansiranje, LB-ECR, koji omogućava bolje iskorišćenje
komunikacionih mreža data centra. Korišćenjem metoda linearnog programiranja LBECR
maksimizuje protok bez gubitaka za date saobraćajne zahteve svičeva. LB-ECR se
oslanja na ECMP rutiranje koje je uobičajeno u data centrima jer koristi alternativne
putanje iste cene. Dvofazno balansiranje omogućava pojednostavljenje linearnog
modela eliminacijom saobraćajnih tokova i smanjuje mogućnost zagušenja
raspoređivanjem saobraćaja po manje iskorišćenim linkovima mreže. Pojednostavljenje
linearnog modela omogućava njegovo rešavanje za mreže velikih data centara.
Disertacija sadrži pregled topologija i načina rutiranja u data centrima i rezultate
poređenja različitih algoritama rutiranja u tipičnim topologijama data centara.
Pored optimizacije rutiranja, disertacija razmatra algoritme ažuriranja lukap
tabela rutera. Drugi deo disertacije sadrži pregled lukap algoritama i algoritama
ažuriranja, i ispitivane su performanse ažuriranja dva napredna lukap algoritma.
Izvedene su formule za proračun najgoreg slučaja zauzeća memorija lukap bloka, dok
rezultati simulacije pokazuju zauzeće memorije za tipične tabele rutiranja. Prikazani su i
rezultati broja pristupa memorijama lukap bloka u toku ažuriranja, kao i kompleksnost
algoritama ažuriranja i vreme izvršavanja za tipične tabele rutiranja.
Treći deo disertacije obuhvata opis implementacija algoritama rutiranja sa
balansiranjem i algoritama ažuriranja lukap tabela, kao i načina integracije ovih
implementacija u okviru rutera.
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.