Minimális költségű hálózati topológia bővítés regionális hibák ellen
Modern életünk egyre jobban hagyatkozik az internetre, így a telekommunikációs hálózatok védelme egyre fontosabb kérdéssé válik. Az Internet kimaradások gyakran regionális szintű katasztrófák következményei, mint például egy földrengés, áradás, hurrikán vagy akár bombatámadás. A hálózat nagy kiterjedése miatt rengeteg olyan felhasználót is érint a hiba hatása, akik fizikailag messze vannak a katasztrófától. A dolgozatomban azt a kérdést járom körbe, hogy milyen módszerrel lehetne olyan hálózatokat tervezni, amelyek ellenálónak regionális hibáknak, vagyis miként garantálható, hogy egy katasztrófa ne tudja részekre szakítani a hálózatot? Milyen új összeköttetéseket lenne érdemes kiépíteni, hogy a hálózat “bombabiztos” legyen, és a közvetlenül nem érintett felhasználók ne maradjanak szolgáltatás nélkül?
A dolgozat első részében definiáljuk a probléma matematikai modelljét, amelyben a csomópontokat a síkon rögzített pontokon elhelyezett gráf csúcsainak, az optikai kábeleket pedig ezen csúcsok közt futó éleknek tekintjük. Ezek alpaján kombinatorikus geometriaia módszerekkel meghatározzuk a “veszélyzónákat”, amiket ha katasztrófa -földrengés, árvíz, vagy akár bombatámadás- érne, a hálózat több részre esne szét. Azután a feladatot részfeladatokra bontjuk, és geometriai algoritmusok segítségével keressük az így keletkező komponensek közötti új élek legolcsóbb útvonalait. Végül egy mohó heruiszitkus algoritmus segítségével választjuk ki a legolcsóbb kerülőutak halmazát. Az így kiegészített új hálózat már regionális katasztrófáktól védett lesz, akárhol lépjenek fel azok.
A kezdeti eredmények alapján bizakodunk, hogy a heurisztika nem csak optimumhoz közeli, hanem optimális megoldást is nyújthat, illetve a modell további érdekes kiegészítésekre, és általánosabb következtetések levonására is alkalmas lehet.
szerző
-
Hajdú Zsombor
Mérnök informatikus szak, alapképzés
alapképzés (BA/BSc)
konzulensek
-
Dr. Tapolcai János
egyetemi tanár, Távközlési és Mesterséges Intelligencia Tanszék -
Dr. Pašić Alija
egyetemi adjunktus, Távközlési és Mesterséges Intelligencia Tanszék
