Regisztráció és bejelentkezés

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 Médiainformatikai Tanszék
  • Dr. Pašić Alija
    egyetemi adjunktus, Távközlési és Médiainformatikai Tanszék