Útválasztás hálózati hiba esetén

Csomagkapcsolt hálózatokban, (mint például az internet illetve a modern telefonrendszerek) a logikai címekkel ellátott csomagok útját a forrástól a célig köztes csomópontokon keresztül az útválasztás határozza meg. A csomópontokban az útválasztás általában útvonalválasztó táblák alapján történik, melyek megmondják, hogy az adott csomagot melyik porton kell továbbítani. A probléma triviális megoldása az, hogy minden csomópontban, minden címhez el van tárolva a megfelelő port, amerre a csomagot továbbítva az eljut a céljáig. Ez a megoldás viszont csak kis hálózat esetén működőképes, mivel a lokális tárigény minden csomópontnál O(n∙log(n)) ahol n a csomópontok számát jelöli. A probléma megoldására az utóbbi években nagyon sok különböző útválasztó tábla lett kifejlesztve. Ezeknél a megoldásoknál az útválasztó táblák méretének csökkentése érdekében a forrás és a célpont közötti útvonal eltér az optimálistól.

Az általános útvonalválasztó táblák, amelyek minden irányítatlan gráfra működnek érzékenyek a gráf valamelyik élének kiesésére, ami a valós rendszerek esetén egy igen gyakori esemény. Célunk, hogy egy él kiesése ellenére a hálózat továbbra is bármely két csúcspont között képes legyen csomagok továbbítására bárminemű felhasználói beavatkozás, vagy a csomópontok közötti plusz kommunikáció nélkül. Ahhoz, hogy ezt elérjük, szükség van a különböző csomópontok közötti út egyes éleihez tartozó helyettesítő út meghatározására. Ez irányítatlan gráfok esetén megoldható O(m+n∙log(n)) futásidőben ahol n a csúcsok, m pedig az élek száma, amihez J. Hershberger és S. Suri [1, 2] algoritmusát használom.

Megvizsgálok néhány, viszonylag egyszerű, de hatékony útvonalválasztó sémát, hogy meghatározzam, milyen módosításokkal lehet elérni a szükséges tárkapacitás és a multiplikatív hiba lehető legkisebb mértékben történő növelésével, a helyes működést legfeljebb 1 hibás él esetén. A vizsgálatot a triviális útválasztó táblán és a Lenor J. Cowen [3] által kidolgozott, fontos csomópontok kiválasztásán alapuló legfeljebb 3-as multiplikatív hibával működő sémán végzem el, de az alapgondolat más hasonló felépítésű útválasztó táblák esetén is alkalmazható.

Irodalom:

[1] J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp.252-259, October 14-17, 2001

[2] John Hershberger , Subhash Suri, Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?", Proceedings of the 43rd Symposium on Foundations of Computer Science, p.809, November 16-19, 2002

[3] Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM Symposium on Discrete Algorithms, pp.255-260, January 17-19, 1999

szerző

• 
  Berghammer Tamás
  villamosmérnöki
  nappali

konzulens

• 
  Friedl Katalin
  egyetemi docens, Számítástudományi és Információelméleti Tanszék

helyezés