BME Informatikai Tudományok Doktori Iskola 

 

BME VIK, Távközlési és Médiainformatikai Tanszék, Nagysebességű hálózatok laboratóriuma (HSN Lab),
MTA-BME Jövő Internet Kutatócsoport

Témavezető: Dr. Rétvári Gábor

 

A jövő megbízható és hibamentesen működő internete 

A kutatási téma néhány soros bemutatása

Napjainkban az interneten a magas rendelkezésre állás sajnos nem biztosított, pedig rengeteg olyan valós idejű alkalmazás képezi már mindennapjaink részét, amelyek ezt megkövetelnék. A gyakran fellépő hibák esetén a hozzájuk közeli csomópontoknak gyorsan kell reagálniuk és a forgalmat elterelő útvonalakra kell továbbítaniuk. Kutatási célom, hogy a jelenlegi hálózati csomópontokban (routerekben) elérhető egyetlen módszer által nyújtott védelmet gráfelméleti eszközökkel elemezzem és hálózat-optimalizálási javaslatokat tegyek a maximális védelem növelése érdekében.

A kutatóhely rövid bemutatása

Munkámat a BME Távközlési és Médiainformatikai Tanszékén, azon belül is a Nagysebességű Hálózatok Laboratóriumában végzem, ahol az Ericssonnal karöltve folynak a jövő internetjével kapcsolatos kutatások, köztük a hálózati hibák elleni védelemmel foglalkozó vizsgálatok. 2012-ben Dr. Tapolcai János megnyerte a Lendület programot, aminek a kutatási célkitűzése a megbízható jövő internet biztosítása. A tanszéken megalapított kutatócsoportjának a kezdetek óta tagja vagyok.

A kutatás történetének, tágabb kontextusának bemutatása

Napjainkban az internet elengedhetetlen tényezője lett a hétköznapjainknak és már-már a társadalom kritikus infrastruktúrájának számít. Ez a tény arra készteti a szolgáltatókat, hogy a hálózatukat megszakítások nélkül tudják üzemeltetni és ezzel teljes mértékben elnyerni a felhasználók bizalmát. Manapság azonban nemcsak a szolgáltatók és a végfelhasználók érintettek ebben a kérdésben, hanem különböző multimédia-szolgáltatók is, hiszen az IP (Internet Protocol) elterjedésével, egyre több digitális tartalom „IP felett” jut el a háztartásokba, gondoljunk csak az IP alapú telefóniára, videótáras megoldásokra, valós idejű hírközlésre vagy akár az IPTV-re. Az internetnek szükségszerűen lépést kell tartania ezekkel a valós idejű alkalmazásokkal, amelyek folyamatos és megbízható kapcsolatot igényelnek. A megbízhatóság azt jelenti, hogy a hálózatban bármelyik időpillanatban a kapcsolat bármely két pont között biztosított, és egy esetleges hiba olyan gyorsan kezelve van, hogy a végfelhasználók ezt semmilyen módon nem érzékelik.         

Ennek érdekében az Internet Engineering Task Force (IETF) definiálta az ún. IP Fast ReRoute (IPFRR) rendszert, hogy ezt az időt lecsökkentse néhány tíz milliszekundumra. Mindezt úgy éri el, hogy a hibát észlelő csomópontok a hiba tényét nem terjesztik szét, hanem lokálisan, a csomagokat előre kiszámított alternatív útvonalakra terelik.

Első megközelítésként definiálták az ún. Loop-Free Alternates (LFA) módszert [1], ami egyszerű, szabványosított és már régóta elérhető napjaink routereiben. LFA esetén, amikor egy csomópont észleli, hogy a szomszédja már nem érhető el, akkor megpróbálja egy olyan másik szomszédjának továbbadni a csomagokat, amelyik nem fogja neki azt visszaadni és ezzel elkerülhető hurok képződése. Sajnos egy ilyen szomszéd létezése nem minden esetben áll fenn, hiszen ez nagymértékben függ a hálózati topológiától és annak paramétereitől (élköltségek, legrövidebb utak, stb.), így ez a módszer nem tudja garantálni a teljes védelmet tetszőleges hálózatokban. Ezért az elmúlt években számos kezdeményezés született [2-7] a 100%-os védelem biztosítására, azonban komplexitásuk, nem szabványos csomagtovábbítási módszerük és addicionális menedzsment költségeik miatt jelenleg egyik módszer sem használható, így a szolgáltatók számára még mindig csak az LFA lehet az egyetlen mentsvár a hálózati hibák ellen.

Nemrég azonban az IETF publikált egy még nem szabványosított, az LFA által nyújtott védelem növelését szolgáló módszert, melynek lényege, hogy a hibák elkerülése céljából az észlelő csomópont már nem csak a közvetlen szomszédait próbálja meg felhasználni a csomagok elterelésére, hanem távolabbiakat is. Erre utal a módszer neve is: Remote LFA (rLFA) [8]. Ugyanakkor az LFA-tól „örökölt” topológiafüggő tulajdonsága miatt, a 100%-os rendelkezésre állás tetszőleges hálózatokban történő biztosítása még mindig nyitott kérdés a kutatók számára.

A kutatás célja, a megválaszolandó kérdések

A hálózati operátorok még mindig mérlegelik a LFA vagy az rLFA „bekapcsolását”, hiszen nem egyértelmű az első pillanattól kezdve, hogy ezekkel a módszerekből ténylegesen mennyit profitálnának a saját hálózatukban, illetve mennyire befolyásolná ez a jelenlegi hálózatuk különböző aspektusait (pl. terheléselosztását).

A kutatásaim során ennek a döntésnek a meghozatalában próbálok segíteni, és olyan gráfelméleti eszközöket ajánlok, melyek nagymértékben segítik a módszerek és a valós hálózatok védelmi analízisét. Hasonló vizsgálatok már korábban is léteztek a már fent említett, nem szabványosított módszerekhez, de az LFA-val kapcsolatban eddig csak szimulációs eredmények születtek, a mélyebb matematikai elemzések pedig csak a csomópontok közötti élek meghibásodását vették figyelembe. Ami a Remote LFA-t illeti - tudomásom szerint, - semmilyen információ ezidáig nem volt elérhető arról, hogy különböző hálózatokban a módszer „hogyan teljesít”, mik a korlátai, vagy éppen hogyan lehetne javítani az általa nyújtott védelmen.

Módszerek

Mindezek fényében munkám elején a „szimpla” LFA által nyújtott védelem matematikai analízisének kiterjesztésére koncentráltam, mely a csomópontok meghibásodását is figyelembe veszi [S2]. Ebben az esetben beláttam, hogy a hálózatok pusztán gráfelméleti tulajdonságai alapján (csomópontok és élek száma, átlagos fokszám, stb.) hogyan változik az LFA lefedettség, mik az alsó és felső korlátok. Hasonló elemzéseket végeztem Remote LFA esetén is, továbbá megállapítottam, hogy mik védelem biztosításának szükséges és elégséges feltételei. Ugyanakkor megvizsgáltam, hogy melyek azok a „rossz” hálózatok, ahol az módszer nem tud megfelelő védelmet nyújtani. Megmutattam, hogy bár az LFA-nál mindig jobb védelmet tud nyújtani, léteznek olyan topológiák, ahol ez az érték közel nulla. Mindemellett rávilágítottam azokra az összefüggésekre, amelyek megmutatják milyen következtetéseket lehet levonni az egyik módszerrel kapcsolatban, ha van információnk a másikról [S5][S6].

Eddigi eredmények

A kezdeti LFA használatok rámutattak arra, hogy legtöbb esetben sajnos nem tudja garantálni a kívánt védelmet a valós hálózatokban. Az eddigi ismeretek alapján egyértelmű, hogy egy esetleges javulás érdekében a módszerhez nem érdemes nyúlni, hiszen attól kezdve az a többi alkalmazhatatlan megközelítés sorsára jut. Így az egyetlen járható út az, ha magához a hálózati topológiához nyúlunk hozzá és próbáljuk meg úgy „csavargatni”, hogy növeljük az LFA-k által nyújtott védelmet. Ezt az utat követtem én is, és különböző hálózat-optimalizálási módszereket tanulmányoztam és dolgoztam ki ennek érdekében. Az egyik ilyen módszer, ha a hálózatunkat már eleve az esetleges hibák elleni védelemre tervezzük meg. A másik az ún. LFA Graph Extension [9], amely a meglévő hálózatot megpróbálja a lehető legkevesebb új éllel kiegészíteni úgy, hogy az LFA lefedettség a lehető legnagyobb mértékben növekedjen. A módszer megalkotói megmutatták, hogy tipikusan 2-3 új él hozzáadásával 100%-os védelem érhető el.

Én először egy harmadik közelítésű módszert dolgoztam ki, mely az élköltségek optimalizálásával [S2][S4], megváltoztatja a legrövidebb utakat a hálózatban, és így LFA-kat biztosít olyan esetekben, ahol eddig nem volt. A problémáról (LFA Cost Optimization) beláttam, hogy bonyolultságát tekintve NP-teljes, így megfogalmaztam egy lineáris programot (ILP), valamint kidolgoztam több közelítő algoritmust és egy keretrendszert, melyben rengeteg paraméter függvényében válik ilyen értelemben optimalizálhatóvá a vizsgált hálózat. Megmutattam, hogy ezzel a módszerrel közel 100%-osra növelhető a védelem bizonyos hálózatokban. Mivel az előző két módszernek lehetnek megvalósítási szempontból korlátai, így egy negyedik megközelítésben összevetettem a kettőt és egy kombinált módszert dolgoztam ki [S1], mellyel (kb. 50%-kal) csökkenthető a fentiek szerint szükséges új élek száma.

Mivel a Remote LFA módszer is már a szabványosítás útján jár, ezért a védelmi szempontból történő teljesítőképességét megvizsgáltam az internetről szabadon hozzáférhető több valós hálózati topológiában is. Az LFA-hoz hasonlóan, ebben az esetben is javaslatot tettem egy védelem-növelő hálózat-optimalizálási módszerre [S5]. Első megközelítésben adaptáltam a fent említett LFA Graph Extension módszert és átdolgoztam. A problémáról (rLFA Graph Extension) szintén kiderült, hogy bonyolult, és mivel a módszer maga is több eshetőséget vizsgál a szimpla LFA-nál, így valószínűleg ez is NP-teljes. Ezért ebben az esetben is közelítő heurisztikát dolgoztam ki, mely segítségével megmutattam, hogy már néhány él hozzáadásával is elérhető a kívánt 100%-os védelem. Mindemellett, természetesen ennek a módszernek a kidolgozása során is ügyeltem azokra az esetekre is, ahol maga a csomópont is meghibásodhat [S6]. Mivel a csomópont hibák magukkal vonják több él együttes „kiesését” is a hálózatból, így ebben az esetben átlagosan csak 1-2 éllel kell több a teljes védelem elérése érdekében.

Néhány konkrétabb eredmény - amelyeket valós hálózatokon mértem - látható az alábbi táblázatban, ahol a bal szélső oszlopban a topológiák neve van, az η(G) jelöli a kezdeti LFA lefedettséget, míg μ(G) a kezdeti rLFA lefedettséget. η(G)_GE jelöli, hogy hány új élt kellett hozzáadni a hálózathoz a 100%-os LFA védelem elérése érdekében, míg ugyanez a remote LFA esetén a μ(G)_GE oszlopban látható. Végül, de nem utolsó sorban, az η(G)_CO oszlop jelöli, hogy pusztán az élköltségek optimalizálásával mekkora LFA lefedettség érhető el a különböző hálózatokban.

 

Valós hálózat	η(G)	η(G)_GE	η(G)_CO	μ(G)	μ(G)_GE
AS3257	0,946	3	0,997	0,954	1
Deltacom	0,542	79	0,662	0,885	4
Italy	0,784	12	0,919	0,951	2

Várható impakt, további kutatás

Munkám során a konzulensemen, Dr. Rétvári Gáboron (BME) kívül, együtt dolgoztam több ipari kutatóval is, többek között Dr. Császár Andrással és Dr. Enyedi Gáborral (Ericsson). Ezen kooperáció eredményeként a témában az egyik legrangosabb konferencián, 2011-ben megkaptuk a legjobb cikknek járó díjat is. Hasonlóan rangos konferencián publikált további eredményeimet is a legjobb cikknek járó díjra jelölték 2012-ben.

Közös munkánk további eredménye egy olyan alkalmazás, mely a hálózatok védelmi aspektusból történő elemzését és optimalizálását nagymértékben elősegítő és könnyítő említett módszereinket elérhetővé teszi hálózati operátorok számára. Továbbá, jelenleg is kapcsolatban vagyunk a Remote LFA-t szabványosító szervezet tagjaival, akikkel megvitatjuk kérdéseinket és segítjük munkájukat saját eredményeinkkel.

A jövőben mindenképpen szeretném eddigi Remote LFA kutatásaimat kiterjeszteni, és megvizsgálni a már az LFA esetén is jól teljesítő élköltségek optimalizálási lehetőségét is a nagyobb lefedettség elérése érdekében. A napjainkban egyre jobban teret hódító Software Defined Networks (SDN) terület lehetővé fogja tenni számomra egyéb megközelítések valós hálózatokon történő tesztelését és kiértékelését.

Saját publikációk, hivatkozások, linkgyűjtemény 

Kapcsolódó saját publikációk listája:s

[S1]	Levente Csikor, Máté Nagy, Gábor Rétvári, Network Optimization Techniques for Improving Fast IP-level Resilience with Loop-Free Alternates. INFOCOMMUNICATIONS JOURNAL 3:(4) 2-10. old. (2011)
[S2]	Levente Csikor, János Tapolcai, Gábor Rétvári, Optimizing IGP Link Costs for Improving IP-level Resilience with Loop-Free Alternates. COMPUTER COMMUNICATIONS 36:(6) 645-655. old. (2013)
[S3]	Levente Csikor, Gábor Rétvári, János Tapolcai, High Availability in the Future Internet. In Future Internet Architecture Book, Future Internet Assembly 2013: Validated Results and New Horizons, Lecture Notes in Computer Science, Springer, 64-76. old., ISBN: 978-3-642-38081-5 (2013)
[S4]	Gábor Rétvári, Levente Csikor, János Tapolcai, Gábor Enyedi, András Császár, Optimizing IGP Link Costs for Improving IP-level Resilience. In Proc. of 8th International Workshop on the Design of Reliable Communication Networks (DRCN), Krakkó, Lengyelország, 62-69. old., ISBN: 978-1-61284-123-6 (2011)
[S5]	Levente Csikor, Gábor Rétvári, IP Fast Reroute with Remote Loop-Free Alternates: the Unit Link Cost Case. In Proc. of RNDM 2012 4th International Workshop on Reliable Networks Design and Modeling. Szent Pétervár, Oroszország, 16-22. old., ISBN: 978-1-4673-2178-5 (2012)
[S6]	Levente Csikor, Gábor Rétvári, On Providing Fast Protection with Remote Loop-Free Alternates: Analyzing and Optimizing Unit Cost Networks. submitted to Telecommunication Systems Journal, (2013)

 

Linkgyűjtemény:

BME Távközlési és Médiainformatikai Tanszék

HSNLab

Lendület

 

Hivatkozások listája:

[1]	A. Atlas, A. Zinin, Basic specifiaction for IP fast reroute: Loop-Free Alternates. RFC 5286, 2008.
[2]	G. Schollmeier, J. Charzinski, A. Kirstädter, C. Reichert, K. Schrodi, Y. Glickman, C. Winkler, Improving the resilience in IP Networks. in. Proc. HPSR, 2003.
[3]	A. Kvalbein A. F. Hansen, T. Čičić, S. Gjessing, O. Lysne, Fast IP network recovery using multiple routing configurations. in Proc. IEEE INFOCOM, 2006.
[4]	S. Bryant, M. Shand, S. Previdi, IP fast reroute using Not-via addresses. Internet Draft, 2008.
[5]	S. Lee, Y. Yu, S. Nelakuditi, Z.-L. Zhang, C.-N. Chuah, Proactive vs. Reactive Approaches to Failure Resilient Routing. in Proc. IEEE INFOCOM, Hong Kong, 2004.
[6]	Z. Zhong, S. Nelakuditi, Y. Yu, S. Lee, J. Wang, C.-N. Chuah, Failure Inferencing based Fast Rerouting for Handling Transient Link and Node failures. in IEEE INFOCOM, 2005.
[7]	K. Lakshminarayanan, M. Caesar, M. Rangan, T. Anderson, S. Shenker and I. Stoica, Achieving convergence-free routing using failure-carrying packets. in. Proc. SIGCOMM, 2007.
[8]	S. Bryant, C. Filsfils, S. Previdi, M. Shand, N. So, Remote LFA FRR. Internet Draft, 2013.
[9]	G. Rétvári, J. Tapolcai, G. Enyedi, and A. Császár, “IP Fast ReRoute: Loop Free Alternates revisited. in INFOCOM, 2011, 2948–2956. old.