Hálózatok tervezése VITMM215
Maliosz Markosz 20 2012 12.10. .10.27 27..
VPN topológia tervezés Adott: – fizikai hálózat topológiája – Költségmodell: fix szakaszköltség – VPN végpontok
2
VPN topológia tervezés VPN végpontok: A, C, K 1. megoldás: teljes szövevény – Minden végpontot minden végponttal összekötünk: n2-tel arányos az élek száma – Három alagút: AA-C, CC-K, AA-K – Teljesen összekötött Nem kell belső útválasztás: a végpontok a megfelelő alagútba küldik a forgalmat
3
VPN topológia tervezés 2. megoldás:
Hub
– Csillag topológia Élek száma nn-nel arányos Az egyik végpontot is kinevezhetjük a csillag középpontjának A központban kell útválasztás!
4
VPN topológia tervezés 3. megoldás: – SteinerSteiner-fa probléma ((NP NP--nehéz nehéz)) Ha nincsenek közvetlen élek, a végpontokon kívül több köztes csomópont is részt vesz a VPN VPN--ben Útválasztók az elágaztató csomópontoknál
– Heurisztikák: 1. heurisztika – minimális feszítőfa meghatározása a fizikai topológián – a felesleges élek eltávolítása
2. heurisztika – Minden VPN végpont párra felírjuk, hogy a fizikai hálózat alapján mi a minimális költségű út közöttük – Ez alapján kapunk egy teljes szövevényt – Ebben meghatározzuk a minimális feszítőfát (pl. Kruskal) Kruskal) – A min. feszítőfát visszavezetjük az eredeti hálózatra a költségek növekvő sorrendjében 5
Steiner fa 2. heurisztika – példa VPN végpontok: a, c, i, k
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html 6
Steiner fa 2. heurisztika – példa Teljes gráfot készítünk a legrövidebb utakból:
7
Steiner fa 2. heurisztika – példa A teljes gráfon meghatározzuk a minimális feszítőfát
8
Steiner fa 2. heurisztika – példa A minimális feszítőfa visszavezetése a fizikai hálózatra
9
VPN méretezés Csővezeték (pipe (pipe)) modell modell: – topol topológia ógia:: teljes szövevény csövekből adott a forgalmi mátrix a pontpont-pont csövek kapacitásának lefoglalása
Hose modell modell: – Szolgáltatói Szolgáltatói--cső megközelítés – Hose specifi specifikus kus állapot – VPN specifikus specifikus állapot 10
Hose modell modell: szolgáltatói csövek Méretezés a legrosszabb forgalmi értékre (worst (worst– –case traffic value value)) i o a VPN csomópontok között (azaz tk és tl minimuma (k, l) csomópont párra) a k és l közötti útvonal mentén, majd ezen csövek kapacitásának összegzése minden szakaszon, ezzel megkapjuk a teljes VPN kapacitás szükségletet az adott szakaszon nem tudja kihasználni a Hose korlátok közötti relációt a legkevésbé sávszélesség takarékos megoldás nincs erőforrás megosztás Példa: Példa: – VPN végpontok végpontok:: A, E, G – szimmetrikus, egységnyi forgalom igény minden VPN végpont pár között – feltételezés: a legrövidebb utak a következők: A-C-B-E, A A--C-D-G, E E--F-G – Teljes kapacitásigény: 3x2+3x2+2x2=16
11
Hose modell modell: Hose specifi specifikus kus állapot Hose paraméterek kapcsolatának kihasználása: ugyanazon forrástól induló (vagy ugyanoda érkező) több csővezetéknél nem egyszerűen összegezzük a kapacitásokat, mint az előbb, hanem az összeg és a forrás (célpont) hose paraméterének minimumát foglaljuk. forrás fák kialakítása erőforrás megosztás + explicit útvonalválasztás Példa:: Példa – csak erőforrás megosztással: megosztással: VPN kliens végpontok: végpontok: A, E, G szimmetrikus, egységnyi forgalom igény minden VPN végpont pár között feltételezés: a legrövidebb utak a következők: A-C-B-E, A A--C-D-G, E E--F-G A-C szakasz kapacitás foglalása: foglalása: 2x2 2x1 Teljes kapacitásigény: 15
– erőforrás megosztás + explicit útvonalválasztás: útvonalválasztás: útvonalak:: A útvonalak A--C-F-E, A A--C-F-G, E E--F-G Teljes kapacitásigény: 12
12
Hose modell modell: VPN specifikus specifikus állapot Minden szakaszra a legrosszabb esetben előforduló forgalom meghatározása az összes hose paraméter figyelembevételével A kapacitások meghatározása sokkal bonyolultabb (sokkal több a kényszer)) kényszer erőforrás megosztás + explicit útvonalválasztás Példa:: Példa – VPN kliens végpontok: végpontok: A, E, G – szimmetrikus, egységnyi forgalom igény minden VPN végpont pár között – explicit útvonalválasztás : útvonalak: A útvonalak: A--C-F-E, A A--C-F-G, E E--F-G Teljes kapacitásigény: kapacitásigény: 8
13
Tervezési módszerek áttekintése Topológia – Fa: Minimális költségű feszítőfa: Kruskal, Prim algoritmusa Minimális költségű útvonalak meghatározott gyökérből: Dijkstra algoritmusa
– Gyűrű Minimális költségű gyűrű = TSP: ILP, heurisztika
– VPN virtuális topológia: teljes szövevény csillag Steiner fa: 2 heurisztika
Forgalom menedzsment – Folyamproblémák Legrövidebb út: LP, Dijkstra algoritmusa Minimális költségű egytermékes folyam: LP Minimális költségű többtermékes folyam: – elágazó folyamok: LP – nem elágazó folyamok: ILP – Heurisztikák, pl. szimulált foglalás
Együttes topológia tervezés és útvonal meghatározása – Lineárisan szeparálható költség: ILP, Minoux mohó algoritmusa
14
