Hegyi Péter
Labor Jegyzokönyv
Önálló laboratórium beszámoló
Készítette: Hegyi Péter
BME-TTT
Neptun-kód: OLU8OK
E-mail cím:
[email protected] Konzulens(ek):
Cinkler Tibor, Maliosz Markosz
Email címe(k):
[email protected],
[email protected]
Tanév:
2002/03. 1. félév
Téma címe: Védett virtuális magánhálózatok (VPN-ek) kialakítása Feladat: megosztott védelmi utak keresése VPN üzemi útvonalak mellé saját algoritmus segítségével
1. A laboratóriumi munka környezetének ismertetése, a munka elõzményei és kiindulási állapota
Bevezetõ/elméleti összefoglaló
A virtuális magánhálózatok (továbbiakban VPN-ek) tulajdonképpen hálózatok a hálózaton: lehetővé teszik igénylőik számára, hogy bár a valóságban több telephellyel rendelkeznek, mégis úgy lássák, gépeik egy helyi hálózaton vannak összekötve. Ezt azonban nem úgy valósítják meg, hogy minden telephely közé kihúznak egy-egy kábelt, hanem a különböző telephelyek közötti sávszélesség igényeket egy már létező, univerzális hálózaton vezetik el. [1] A gyakorlatban ez úgy néz ki, hogy a telephelyek valódi helyi hálózatait egy peremgép csatlakoztatja a nagyobb hálózathoz, azon keresztül megy minden igény a többi telephely felé, illetve azon keresztül jönnek be hozzánk más telehelyek igényei. Ez azért jó, mert így az egyes telephelyeket tekinthetjük egy gráf pontjainak, és így a pontok között akarunk valamekkora kapacitású csatornát létrehozni. Ez lehet, hogy nem egy közvetlen élen lesz ez a csatorna, hanem a hordozóhálózatot reprezentáló gráf több éle, csúcspontja is részt vehet benne.[1] -1-
29/06/2004
Hegyi Péter
Labor Jegyzokönyv
Nyilván a hordozóhálózaton való forgalmat meg kell fizetni valamilyen szolgáltatónak. Az is igaz, hogy aki VPN-t akar kialakítani, annak inkább egy lefoglalt fix sávszélesség kell, mint lehetőség a csatlakozásra, és aztán forgalom után fizetni. Ezért VPN tervezésekor feladatunk az, hogy egy gráfban minél kisebb költségű (például minél rövidebb) útvonalon lefoglaljuk az igényelt sávszélességet. Az ilyen legrövidebb útvonalak megkeresése is egy feladat. [2] De ezzel még nem vagyunk készen, hiszen a hálózaton előfordulhat, hogy egy-egy összeköttetés megszakad. Ezért gondoskodnunk kell a minőségi szolgáltatás érdekében védelmi útvonalakról is. Ezt lehetne úgy is megtenni, hogy minden egyes üzemi útvonal mellé lefoglalunk egy-egy másik útvonalat (hozzárendelt védelem), de szerencsére ekkora pazarlásra a valóságban nincsen szükség: a meghibásodások elég ritkák, így tervezhetünk úgy, hogy egyszerre mindig maximum egy kapcsolat nem működik a nagy hálózaton. Ezért létrehozhatunk úgynevezett megosztott védelmet. Ekkor egy élen védelemnek csak annyi kapacitást foglalunk le, amekkora a legnagyobb rajta védett igény kapacitása. Ez persze csak akkor igaz, ha nem védünk olyan igényt is ugyanezen az élen, amellyel amúgy van akár egy közös üzemi útvonala is az igénynek. Mert ekkor nyilván a vizsgált élen együtt védett, közös üzemi élet használó igények üzemi élenkénti kapacitásösszegeinek maximumának megfelelő kapacitást kell foglalni a vizsgált élen. [2] Még ezen belül is lehet spórolni, hiszen kevesebb élen nagyobb sávszélesség lefoglalása kevesebb pénzbe kerül, mint sok élen kis sávszélességé. Ezért én feladatomul azt kaptam, hogy védjem úgy az üzemi útvonalakat, hogy minél kevesebb élet kelljen lefoglalni, inkább egy élet a lehető legtöbbször használjanak a védelmi útvonalak.
A munka állapota, készültségi foka a félév elején
Félév elején készen volt egy program, ami üzemi útvonalakat vezetett el, de az olyan segédprogramot használt, amire nekem nem volt szükségem a feladatom megoldásához, így azért hogy itthon is tudjak haladni a feladatommal gyakorlatilag előlről kellett kezdenem a munkát. Az eddigi programból csak a hálózatokat, és a VPN-eket leíró file beolvasását végző függvényeket kaptam csak meg. ezenkívül cikkeket adtak a konzulensek a félév során, ezeket a tanulmányozott irodalom jegyzékében említem meg.
-2-
29/06/2004
Hegyi Péter
Labor Jegyzokönyv
2. Az elvégzett munka és eredmények ismertetése Az általam konkrétan elvégzett munka bemutatása
A munka elkezdéséhez előszöris meg kellett ismerkedni a témával, ehhez a konzulensek adtak nekem cikkeket. Miután át tudtam látni, miről is szól a téma a felkínált feladatok közül kiválasztottam az igények védelmét, a bevezető végén említett elv alkalmazásával. Ehhez előszöris az algoritmust kellett kitalálni. Ennek bemutatására készítettem egy ábrát (1. függelék). Az alogritmus a deklarációval, inicializációval indul. Az igényeket egy tömbben tárolom. Mindegyik igényhez tárolom, hogy honnan, hova, mekkora kapacitást igényel, és hogy melyik VPN-hez tartozik. Az éleket egy kétdimenziós tömbben tárolom, ahol az első koordináta az, hogy honnan, a második koordináta az, hogy hova vezet az él. Egy tömbelemben tárolom, hogy honnan, hova megy az él, mekkora a kapacitása, és tárolom, hogy az egyes igények hogy viszonyulnak hozzá: mindegyik igényhez van egy változó, melyben tárolom, hogy az adott igény használja-e az adott élet üzemi, vagy védelmi útvonalnak, illetve, hogy próbálkoztam-e már vele. Ennek funkciója kiderül később. Ezután a Dijkstra algoritmus segítségével létrehozom az igények üzemi útvonalait. Cél, hogy minél kevesebb élen kelljen átmennie az üzemi útvonalnak. A Dijkstra algoritmus használatán kívül nem történt optimalizálás: a feladatom nem erről szólt. Miután elvezettem az üzemi útvonalakat jöhetett a védelem. Az elv az volt, hogy egy élet minél többször felhasználjunk. Ezt halmazokkal oldottam meg. Létrehoztam halmazokat, és megcímkéztem őket aszerint, hogy a bennük tárolt élek hány igény védelmében vesznek részt. Ha egy élet felhasználtunk valamelyik igény védelmekor, akkor eggyel nagyobb cimkéjű halmazba került. A védelmet pedig úgy kerestem, hogy mindig megnéztem, hogy van-e a legnagyobb cimkéjű használt halmazban megfelelő él. Ha nem volt, akkor eggyel kisebb cimkéjűt néztem. Mi számít megfelelő élnek? A keresés csúcsról csúcsra ment. Beadtam az igény kezdőpontját, és kerestem egy onnan induló élet. Ha volt, akkor azt bevettem a védelmi útvonalba, és annak végpontjához kerestem csatlakozót egészen addig, míg a talált él végpontja az igény végpontja nem lett. Ennek megfelelően a "van megfelelő csatlakozó?" doboz a következőket vizsgálja: • az él az utolsó él végpontjából (vagy az igény kezdőpontjából) induljon • a talált él kapacitása megfeleljen (igénynek, plusz a társ üzemi éleknek, lásd fent) • az igény eddigi védelmi útvonala ne használja (oszcillálna az első élen a keresés) • az igény üzemi útvonala se használja • ne menjen át olyan ponton amin már átment (körök kizárása) • eddig ne legyen vele sikertelen próbálkozás (lásd mindjárt) Előfordulhat, hogy ennyi feltételnek nem felel meg egy és se, eltévedtünk, és már a -1 cimkéjű halmazba akar tovább menni a program. Ekkor az utoljára kiválaszott él helyett másikat választunk. Ezt könnyen megtehetjük, hiszen csak meg kell keresni, hogy melyik
-3-
29/06/2004
Hegyi Péter
Labor Jegyzokönyv
az az él, ami az éppen feldolgozott igénynek védelmi útvonala, és a jelenlegi kiindulópontunkba vezet. Ehhez az élhez beírjuk, hogy sikertelen próbálkozás volt, és indítjuk újra a keresést: most már átugrik rajta a program. Ha megint nem találunk jó élet, nincsen semmi gond, ugyanilyen módszerrel még visszább tudunk lépni. Ez egy fajta backtrack algoritmus így. Ha már el se tudunk indulni, vagy mindnhogyan megakadunk, akkor nem tudjuk megvédeni az igényt. Ha pedig sikerül, akkor kiválasztjuk a következő védendő igényt, és indulunk előlről. (a halmazok azért maradnak) Az ezt megvalósító program elkészült, de alaposan letesztelve még nincsen, így össze se tudtam még hasonlítani másik algoritmusokkal az enyémet. Így csak kipróbáltam három különböző méretű hálózaton, hogy működik-e a program, és milyen gyors: egy 9, egy 18 és egy 36 csomópontos hálózaton vezettem el igényeket. A 9 csomópontos hálózatra, melyben 3 VPN összesen 44 igényét akartuk elvezetni a program úgy futott le, hogy indítás után azonnal adta is vissza a promptot, pedig egy igen vaskos naplót is késztített közben. Hatékonyságáról annyit érdemes megjegyezni, hogy van benne 18-szor felhasznált él is, de a legtöbb védelmi élet is 12-nél többször használjuk. Konkrét adat az egyik 14-szer felhasznált élre, hogy összesen 596 egységnyi kapacitást véd, de csak 195 egységnyi kapacitást foglaltunk le rajta. A 18 illetve 36 csomópontos hálózat naplóját nem elemezgettem ennyire alaposan, mert csak a futási időt akartam tudni. A tesztet egy 486 DX4 100 MHz-es gépen futtattam, ami itt azért érdekes, mert még a 36 csomópontos hálózaton is el tudta vezetni ez a gép 94 másodperc alatt a 3VPN által kért 916 igényt, azzal együtt, hogy egy 1 MByte-os naplót készített közben a merevlemezre! A kód maga 15 file-ból áll, 24 kByte és 1167 sor. Összefoglalás
• • • •
elolvastam a kapott cikkeket készítettem egy algoritmust a feladat megoldására lekódoltam az algoritmust dokumentáltam a félévet
3. Irodalom, és csatlakozó dokumentumok jegyzéke A tanulmányozott irodalom jegyzéke:
• [1] Jeremy De Clercq, Olivier Paridaens-Scalability Implications of Virtual Private Networks, IEEE Communications Magazine, May 2002 • [2] Cinkler Tibor, Maliosz Markosz-Configuration of Protected Virtual Private Networks • [3] Józsa Balázs Gábor, Orincsay Dániel-Shared Backup Path Optimization in Telecommunication Networks -4-
29/06/2004
Hegyi Péter
Labor Jegyzokönyv
• [4] Michal Pióro-Design problems in robust optical networks Csatlakozó egyéb elkészült dokumentációk / fájlok / stb. jegyzéke:
A következő file-ok az opt.ttt.bme.hu szerveren a ~hegyi/public_html/onlab1/program könyvtárban találhatók: Makefile dijkstra.cpp dijkstra.h filereader.cpp filereader.h main.cpp matrices.cpp matrices.h pickelement.h prior.cpp prior.h protect.cpp protect.h setoftype.h structs.h
a programot fordító, futtató make segédprogram bemenete a Dijkstra algoritmus implementációja a Dijkstra algoritmus deklarációja állományműveletekkel kapcsolatos függvények implementációja állományműveletekkel kapcsolatos függvények deklarációja főprogram az inicializáció, adatfeltöltés függvényeinek implementációja az inicializáció, adatfeltöltés függvényeinek deklarációja igényválasztó, illetve "jó él" kivevő algoritmusok függvényei védelmi útvonalakat kereső függvény implementációja védelmi útvonalakat kereső függvény deklarációja egy igény védelmét megvalósító függvény implementációja egy igény védelmét megvalósító függvény deklarációja a feladatban haszbált halmaz osztály sablonja a feladatban szereplő adatszerkezetek deklarációja
Természetesen ugyanitt megtalálhatóak a .cpp kiterjesztésű állományokból készített .o kiterjesztésű objektum állományok, melyek az összefordításnál kerülnek felhasználásra. Ugyanezen a szerveren, de a ~hegyi/public_html/onlab1/logs könyvtárban található a log9, a log18 és a log36 állomány, mely a 9, 18, illetve a 36 csomópontos hálózaton futtatott program naplója. Ugyanezen a szerveren, de a ~hegyi/public_html/onlab1/mintaadatok könyvtárban található a bemenet9.txt, bemenet18.txt, és a bemenet36.txt állomány, melyek a tesztadatokat szolgáltatták, és amikről már ejtettünk szót. A program a ~hegyi/public_html/onlab1/mintaadatok/bemenet.txt állománnyal dolgozik, de ezt a Makefile-ban át lehet írni. Ez a dokumentáció a ~hegyi/public_html/onlab1/doc könyvtárban található olu8ok.rtf néven.
-5-
29/06/2004
Hegyi Péter
Labor Jegyzokönyv
Függelék 1. függelék
START
Megosztott VPN védelem
deklaráció, inicializáció
D halmaz üres?
igen
nem
igen választunk belőle egy igényt
KÉSZ
W halmaz üres?
nem
Dijkstra az igényre
választunk belőle egy igényt
élek tömbjében rögzíteni a választott üzemi éleket
a from kezdőpontot meghatározzuk
akt=max
D halmazból igényt átrakni W halmazba
van megfelelő csatlakozó? akt=akt-1
igen
nem
nem akt=0?
igen from végpontú, ebben az igényben használt él keresése
a talált élet eggyel kisebb halmazba rakjuk,sikertelen voltát ebben az igényben rögzítjük,és kihúzzuk
-6-
from=a talált él másik végpontja
a talált él 1gyel nagyobb prioritású halmazba lép
igen akt+1>max?
nem
from=igény végpontja?
max=akt+1
nem
igen igényt a W halmazból P-be rakjuk
29/06/2004
