Hálózati topológia összefüggőségének növelése

OData támogatás
Konzulens:
Dr. Zsóka Zoltán
Hálózati Rendszerek és Szolgáltatások Tanszék

A fejlődő világban a távközlő hálózatok szerepe egyre fontosabb, így ezek megbízhatóságának növelése lényeges kérdés, hálózati elemek kiesése a hálózati pontok elérhetetlenségét okozhatja. A megbízhatóság növelése érdekében, hogy a hálózat pontjai mindig elérhetőek maradjanak, a hálózat fizikai topológiája redundanciát tartalmaz, tipikusan kétszeresen csomópont-összefüggő. Már meglévő hálózatoknál azonban nem bővíthetjük a topológiát tetszőlegesen élekkel, hanem csak megadott élhalmazt használhatunk fel a kétszeres összefüggőség eléréséhez. Ezen felül optimális bővítést szeretnénk végrehajtani a hálózathoz hozzáadott linkek súlyainak minimalizálásával. Hasonló témájú írások elemzése után bemutatásra kerül a kétszeres pontösszefüggőséget vizsgáló ILP (Integer Linear Program) program részletes leírása. A megoldást több mintahálózaton is kipróbáljuk, illetve összehasonlítjuk korábbi, már meglévő heurisztikus megoldásokkal. A tesztelés során kapott eredmények azt mutatják, hogy az a lineáris program által adott értékek jobbak a heurisztikus megoldások értékeinél. Abban az esetben viszont, ha nincs megoldása a problémának és a hálózati topológiát nem lehet kétszeresen összefüggővé bővíteni, a heurisztikus algoritmusok részmegoldásokat adnak, míg a lineáris programmal nem érünk el eredményt. Az ILP program idő- és tárigénye sokkal nagyobb, mint a közelítő algoritmusoké, azonban valódi optimumot ad.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.