Heurisztikus algoritmus tervezése elosztott ponthiba lokalizálásra

Szerző: 
Gyimóthi László
Konzulens (TMIT): 
Év: 
2014
Szekció: 
Modellezés és szimuláció szekció
Helyezés: 
1. helyezés
Különdíj: 
BME TMIT - Trón Tibor Emlékdíj
OTDK éve: 
2015
OTDK szekció: 
Infokommunikáció és hálózatok I.
OTDK helyezés: 
OTDK I. helyezés
OTDK különdíj: 
NOVOFER Alapítvány Gábor Dénes Díj

Napjainkra az Internet megbízhatósága kulcskérdéssé vált. A hatalmas sávszélesség igényt kielégíteni képes optikai gerinchálózatok állandó felügyelete, valamint az esetleges hibák gyors detektálása, lokalizálása és javítása alapvető követelmény a szolgáltatók számára. Mivel a hibainformáció terjesztésre szolgáló elektromos jelzésrendszeri üzenettovábbítás a helyreállítási idővel szemben támasztott követelményekhez képest jelentős, felmerül az optikai réteg hibalokalizációs képességének szükségessége. Az optikai hibalokalizáció egy lehetséges megvalósítása ún. monitorozó utak használata, amelyek mindössze 1-1 bit információt hordozva kódolják, azonosítják a hálózat elemeit. A monitorozó utak segítségével a hálózatban megvalósítható az elosztott ponthibalokalizáció, vagyis a hálózatnak azon képessége, hogy bármely csomópont bármely másik csomópont hibáját detektálni, és egyértelműen lokalizálni tudja, ezáltal rendkívül gyors hálózati helyreállítás garantálható

Dolgozatomban egy általam megalkotott heurisztikus algoritmust mutatok be, amellyel elosztott ponthiba-lokalizáció hajtható végre optikai gerinchálózatokban. A javasolt rekurzív algoritmust valós hálózati topológiákon, illetve általam generált síkgráfokon egyaránt teszteltem, és a szakirodalomban megtalálható eddig ismert eredményekhez képest jelentős javulást sikerült elérni mind futási időben, mind célfüggvény értékben.