Hatékony algoritmus régiófüggetlen útvonlaválasztásra gerinchálózatokon

A katasztrófák okozta szolgáltatás-kiesések elkerülése érdekében a katasztrófa-biztos útválasztás kulcsfontosságú a távközlési gerinchálózatokban. A hálózat tervezésekor azonosítják a hibaeseményekkor egyszerre meghibásodni hajlamos hálózati elemek csoportjait. Ezeket a csoportokat közös kockázatú linkcsoportoknak (Shared Risk Link Group, SRLG) nevezzük. Ha az SRLG sík egy összefüggő régió által metszett linkek halmaza, akkor regionális SRLG-nek nevezzük. Regionális SRLG-k esetére egy viszonylag friss tanulmány polinomiális idejű algoritmust adott egy s-t csúcspár közötti maximális számú csomópont-független útvonal megtalálására síkbeli topológiában, ahol további kitét volt, hogy az útvonalak SRLG-függetlenek legyenek. A problémára létező algoritmusok azonban futási idejük és implementációs bonyolultságuk miatt nem praktikusak.

Ez a tanulmány egy általánosabb modellt vizsgál, ahol maximális számú nem keresztező, regionális-SRLG-független utat keresünk. A dolgozat egy hatékony és könnyen megvalósítható algoritmikus keretrendszert mutat be, amely egy tetszőlegesen választott legrövidebb útkereső alprogramot használ fel az esetlegesen negatív élsúlyozású gráfok esetében. A választott szubrutintól függően a keretrendszer megjavítja a korábbi legrosszabb esetre vonatkozó futási idő komplexitását, vagy nagy valószínűséggel közel lineáris várható idő alatt képes megoldani a problémát. A javasolt keretrendszer lehetővé teszi az első additív közelítést a probléma általánosabb, NP-nehéz változatára, ahol a cél a regionális-SRLG-diszjunkt útvonalak maximális számának megtalálása (melyek metszhetik egymást a síkban).

Az eredményeket kiterjesztjük továbbá a probléma kapacitásos megfogalmazására is, ahol minden S regionális SRLG legfeljebb egy hozzá tartozó adott pozitív egész számú útvonalat metszhet. Eredményeinket kiterjedt szimulációkkal igazoljuk.

szerző

Gyimesi Péter
Egyéb hazai egyetem

konzulensek

Vass Balázs
tanársegéd, Távközlési és Mesterséges Intelligencia Tanszék
Bérczi-Kovács Erika
adjunktus, ELTE (külső)
Dr. Tapolcai János
egyetemi tanár, Távközlési és Mesterséges Intelligencia Tanszék