Optimizacija i implementacija naprednih protokola za rutiranje

Abstract

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.

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.