No title

Mitcsenkov Attila, Paksy Géza (BME-TMIT) {mitcsenkov|paksy}@tmit.bme.hu 2010. 09. 27.



Háttér (FTTx/NGA hálózatok)



FTTx hálózatok tervezése



Hálózattervezés, mint optimalizálási feladat



Algoritmikus háttér



FTTxDesigner



Elért eredmények Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

2







Háttér (FTTx/NGA hálózatok) ◦ ◦ ◦ ◦

Szolgáltatások Piaci trendek Architektúrák Technológiák

◦ ◦ ◦ ◦

Célok Elvárások Munkafolyamat Ma elterjedt megoldások


Hálózattervezés, mint optimalizálási feladat ◦ ◦ ◦ ◦







Kihívások Modell Költségfüggvény Feltételek

Algoritmikus háttér ◦ ◦ ◦

Részfeladatok Bonyolultság Kidolgozott megoldások

◦ ◦ ◦

Történet, fejlesztők Keretrendszer moduljai Mintapélda / esettanulmány

FTTxDesigner

Elért eredmények ◦ ◦ ◦ ◦

Értékelés Alkalmazási lehetőségek Kapcsolatok, együttműködések Tervek

Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

3

•Szolgáltatások •Architektúrák •Technológiák

•Piac:

előrejelzések, trendek, stb.


2010.02.25.

4



Triple Play ◦ ◦



„Enabling technology” ◦ ◦ ◦ ◦ ◦



HDTV, UDTV, 3DTV, … VoD: Video on Demand Videoconferencing Interaktív online játékok e-Health/Commerce/Medicine/etc.

Sávszélesség igények (előrejelzés) ◦ ◦



Hang+video+adat: szolgáltatói szemszögből előny Egy hálózat, egy vezérlés, egy üzemeltetés: alacsonyabb költségek!

Rövidtávon: 100 Mb/s előfizetőnként Középtávon: 1 Gb/s előfizetőnként

„FTTH boom” az elkövetkező években: ◦

Global Industry Analysts Inc.:

◦

Deutche Telekom:

◦



Világszerte 183.9 millió FTTH/B előfizetés 2015-ig



4 millió háztartás (10%) 2012-ig = 10 milliárd €



2.5 millió háztartás (10%) 2012-ig = 1.5 milliárd £

British Telecom / Financial Times


2010.02.25.

5



Optikai hozzáférési hálózatok



Technológiák:

◦ Nagy sávszélesség, megbízhatóság ◦ Elérhető árú, egyszerű eszközök

◦ Passzív optikai hálózatok (xPON) ◦ Aktív optikai hálózatok (AON)  Pont-multipont (pl. AETH)  Pont-pont / dedikált (P2P)

◦ Optika + réz

 xDSL (ma VDSL, VDSL2, VDSL 2+)  CATV / HFC / DOCSIS



Architektúrák

◦ Beruházás mértéke ∼ időtállóság ◦ Hálózatfejlesztés („network evolution”)


2010.02.25.

6

•Célok

•Elvárások

•Munkafolyamat

•Mai

gyakorlat


2010.02.25.

7



Hálózattervezés ◦ Stratégiai tervezés: topológia és rendszerterv ◦ Kiviteli terv: további finomítás szükséges



Költségbecslés ◦ Előzetes becslés: megvalósíthatósági tanulmányok ◦ Topológia alapján: nagy pontosság!



Műszaki-gazdasági elemzés ◦ Technológiák, architektúrák összehasonlítása ◦ Döntéstámogatás


2010.02.25.

8



Automatikus / algoritmikus hálózattervezés ◦ CAD (Computer Aided Design)  Számítógéppel támogatott tervezés ◦ GIS (Geographic Information System)  Földrajzi adatok alapján



Motiváció: ◦ Költséget és időt takarítunk meg ◦ Matematikai eszközök, optimalitási garanciák ◦ Nem helyettesíti, hanem támogatja a tervezőt!


2010.02.25.

9



Rugalmasság ◦ Többféle FTTx rendszerhez ◦ Térkép alapján, adott szolgáltatási területhez ◦ Meglévő infrastruktúrához igazítva



Teljesítmény ◦ Nagy méretekben is (10.000+ végpont), sőt ott igazán fontos ◦ Közel optimális eredmények ◦ Belátható időn belül


2010.02.25.

10

Térkép

DB

Térkép++

DB++

Stratégiai terv

Hálózattervezés: kiviteli terv Elemzés, döntéstámogatás Megvalósít hatóság

Üzleti elemzés

Műszakigazdasági összehasonlítás



Finomítás kiviteli tervvé ◦



Technológia-választás ◦

Döntés



Részletes térkép és bemenő adatok: költséges A legígéretesebb változat kidolgozása

Felesleges munka és kiadások elkerülése


2010.02.25.

11



Tapasztalt szakemberek: „kézimunka” +Rugalmas, kreatív - Költséges, időigényes folyamat



Algoritmikus hálózattervezés

+Topológia előállítása, optimalizálása - Költségek túlzott egyszerűsítése (∑szálhossz)



Üzleti elemzés

+Átgondolt, részletes költségmodellek - Geometriai modellek, hiányzó topológia


2010.02.25.

12





Geometriai modellek Homogén területet feltételez ◦ Népsűrűség ◦ Úthálózat ◦ Infrastruktúra n houses in a row A FP1

l = distance between two houses

FP2 subscriber

α

Cable type 1 Cable type 2 Cable type 3 Cable type 4 Cable type 5

B

R

F

F

F

The central office at the center This serves n2 customers

F C

F

F F

F

D F

E F

F


2010.02.25.

13

•Kihívások •Modell

•Célfüggvény •Feltételek

•Algoritmikus

háttér


2010.02.25.

14



Hogyan fordítható le a feladat a „matematika nyelvére”?



Milyen az „optimális”, vagy legalábbis jó topológia?



Szükség van egy pontos és rugalmas modellre



Bonyolultság

◦ Modell ◦ Költség / célfüggvény ◦ Korlátok, feltételek

◦ Gazdasági szempontok: milyen költségekkel számolhatunk? ◦ Hálózati modell ◦ Költségmodell ◦ Technológiai kötöttségek kezelése

◦ NP-nehéz ◦ Nagy méretű problémák (10.000+ csomópont) Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

15



Rugalmas, pontos, paraméterezhető ◦ Különféle költségfüggvények



Minden szükséges adatot tartalmaz ◦ ◦ ◦ ◦ ◦

Leendő összeköttetések Távolságok Központ (CO) Előfizetői adatok Berendezés helyek


2010.02.25.

16





Ezek felderítése meghatározó fontosságú: mire törekszünk egyáltalán? Topológia-függő ◦ Pl. kábelhálózat



Topológia-független

◦ Pl. előfizetői modemek



CAPEX

◦ Kiépítés költségei



OPEX

◦ Üzemeltetési, fenntartási költségek Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

17



Kábelhálózat



Hálózati eszközök



Összefüggés:

◦ Lépcsős, kétszintű ◦ Összefüggőségek!

◦ Központ ◦ Elosztópont ◦ Végpont

◦ Több elosztópont  kevesebb kábel? ◦ Pontos arányok, viszonyok feltérképezése!


2010.02.25.

18



Hol lehet elosztópont? ◦ Tápfesz, hűtés, …



Hol lehet összeköttetést építeni? ◦ Milyen költséggel?



Mekkora az áthidalható távolság? ◦ Törzshálózat / Elosztóhálózat ◦ Erősen technológia-függő



Mekkora az elosztópont kapacitása? Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

19



Kábelhálózatok + hálózati eszközök költségét minimalizáló topológia, amely: ◦ Az elvárt szintű szolgáltatást nyújtja minden előfizetőnek ◦ Megfelel a kiválasztott technológia képességeinek (hossz- és kapacitáskorlátok) ◦ Az adott területhez illeszkedik



Ez alapján: ◦ vizsgálható a bonyolultsága ◦ bizonyos méretekig kiszámítható az optimum Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

20

•Részfeladatok •Bonyolultság •Kidolgozott

megoldások


2010.02.25.

21



Csoportok kialakítása

◦ Szegmentálási / klaszterezési feladat ◦ Specialitás: kötött méretű csoportok



Elosztópontok elhelyezése

◦ Optimális „központi” pozíció meghatározása



Összeköttetések nyomvonala ◦ Lépcsős költségfüggvény ◦ Steiner-fa feladat



Erős összefüggőség az egyes részfeladatok között! Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

22

Nehézségek:  Komplexitás: minden esetben NP-nehéz

◦ Valóságban nagy problémákkal érdemes foglalkozni ◦ Város / városrész méretű területek, Nx10.000 végpont



Egzakt optimalizálás reménytelen

◦ ILP: már párszáz végpont körül eredménytelen

Lehetséges megoldások:  Relaxáció

◦ Adott csoportosítás ◦ Rögzített elosztópontok ◦ Gyakorlati jelentősége kicsi



Approximáció (közelítő módszerek) ◦ Érvényes, közel optimális megoldás


2010.02.25.

23



Közelítő algoritmusok („heurisztika”) ◦ Kompromisszum: pontosság vs. gyorsaság  Nagy pontosságú közelítés  Offline probléma  „nem sürgős”  Korlát: 10-100.000 pont között is működőképes

◦ Specializált eljárások az egyes technológiákhoz  „No-free-lunch theorem”  Pontos közelítés érdekében specializálni kell  Eltérő hangsúlyok (költségek, korlátok) 

Dekompozíció ◦ Részfeladatok mentén Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

24





Részfeladatok megoldása Összefüggések kezelése ◦ Mindig tekintettel lenni a következő lépcsőkre

• Klaszterezési feladat

Elosztópontok • Splitter

• Switch

• Megfelelő élek „kiépítése” • Költség-minimum

• DSLAM

Csoportosítás

Összeköttetések


2010.02.25.

25



Költségek: ◦ Kábelhálózat magas ◦ Elosztópont alacsonyabb



Korlátok: 20 km nem éles korlát Fő cél: optimális csoportosítás



Megoldás:



◦ Megosztott kábelszakaszok maximalizálása ◦ Feszítőfa alapú csoportképzés ◦ Kész topológia: tipikusan fa… Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

26

Mitcsenkov Attila (BME TMIT) [email protected] 27

2010.02.25.



 

Költségek:

◦ Elosztópont + működtetése drága ◦ Kábelhálózat szintén…

Korlátok: 20+3 km megengedő Fő cél: ◦ Minimális elosztópont ◦ Optimális csoportosítás  Átfedések nélkül  Közeli elosztó



Megoldás:

◦ iteratív, „bottom-up” klaszterezési eljárás ◦ megfelelő csoportméret elérése ◦ nem átfedő területek Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

28



Költségek:

◦ DSLAM + üzemeltetés: drága ◦ Réz: szinte ingyen



Korlátok:

◦ 300/800 m „éles” rézhálózati korlát



Cél:

◦ minél kevesebb DSLAM használata



Megoldás:

◦ Mohó algoritmus ◦ Kritikus végpontok prioritása ◦ „Top-down clustering”


2010.02.25.

29



Költségek: ◦ Kábelhálózat drága ◦ Különösen a „belépési költség”



Cél: ◦ Kábelezési munka minimalizálása



Megoldás: ◦ Steiner-fa feladat ◦ Distance Network Heuristic (DNH):  Gráf-transzformációk + minimális súlyú feszítőfa


2010.02.25.

30

•Történet

•Fejlesztők

•Keretrendszer

moduljai •Mintapélda / esettanulmány


2010.02.25.

31





Eredeti cél: beruházási költségbecslés (2008) Résztvevők: ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦

Paksy Géza (2008-) Mitcsenkov Attila (2008-) Farkas Dávid (2009-2010) Katzenberger Péter (2009-) Steierlein Márton (2009) Bakos Péter (2009-) Rapp Alajos (2010-) Köles Gergely (2010-)


2010.02.25.

32

• Gazdasági elemzés • CapEx számítások • Business Case Analysis • Legígéretesebb technológia kiválasztása • Topológia-optimalizálás • Csoportosítás • Elosztópontok helye • Összeköttetések • Hálózati modell felépítés • Gráf • Élek, típusok és költségek



Földrajzi + infrastruktúra adatok ◦ ◦

Digitális térkép Meglévő hálózati infrastruktúra


2010.02.25.

33

Térkép & infrastruktúra

Előfizetők


Topológia

2010.02.25.

34

Sashegy, Budapest XI/XII. kerület

Egy helyi központ területe 5 km2 / 4500 előfizető Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

35



Inhomogén terület ◦ Családi, társas és bérházak



Meglévő infrastruktúra ◦ Rézhálózat ◦ Részben meglévő alépítmények



Különböző kábelezési technológiák ◦ Légkábelek ◦ Új földkábelek ◦ Meglévő alépítmény


2010.02.25.

36



Térkép, úthálózat és infrastruktúra 82 km úthálózat 





60 km meglévő infrastruktúra 2 km új légkábel 20 km új földkábel

35 km bekötő szakasz Gráf:  8000 pont  8500 él


2010.02.25.

37



Előfizetői adatbázis

4239 háztartás, 1079 épület Gráf: 10 300 pont 10 424 él


2010.02.25.

38

 

Technológiai, fizikai specifikációk (korlátok) Költség adatok (célfüggvény) 2 perc számítási idő

•Topológia •Rendszerterv •Elosztópontok helye


2010.02.25.

39


2010.02.25.

40



Topológia-információk, hálózati jellemzők ◦ Rendszerterv ◦ Berendezések helye ◦ Szál, kábel és berendezés igény



Business Case Analysis ◦ CAPEX, OPEX, Cash Flow, Payback, etc.



Műszaki-gazdasági elemzés, összehasonlítás ◦ GPON, Active Ethernet, VDSL, Point-to-Point Ethernet



Tetszőleges metrika alkalmazása lehetséges ◦ Széles körű topológia-adatokra támaszkodva ◦ A hálózat üzemeltető igényei alapján Mitcsenkov Attila (BME TMIT) [email protected]

2010.02.25.

41

CAPEX Million EUR

3,5 3 2,5 2

Equipments

1,5

Cable plant

1 0,5

0 P2P

GPON

AETH

VDSL


2010.02.25.

42

GPON

Pont-pont Ethernet


2010.02.25.

43

1 000,00

700

900,00 800,00

600

700,00

EUR / household

EUR / household

800

500 400 300 200

600,00 500,00 400,00

300,00 200,00

100

100,00

0

0,00 5 000

800

5 000

300



VDSL50

VDSL: 25 Mb/s vs. 50 Mb/s

300

Household / km2

Household / km2 VDSL25

800

GPON50



GPON100

GPON: 50 Mb/s vs. 100 Mb/s


2010.02.25.

44

•Értékelés

•Alkalmazási

lehetőségek •Kapcsolatok, együttműködések •Tervek


2010.02.25.

45



Közelítő algoritmusok, kettős elvárás: ◦ Pontosság ◦ Gyorsaság



Pontosság

◦ Nagy méretekben nehezen vizsgálható ◦ Lineáris programozás + trükkök: alsó becslés ◦ 10-15% eltérésen belül kisebb példák esetén



Gyorsaság

◦ 10.000+ előfizető esetén 5-20 perc között


2010.02.25.

46



Gyakorlati alkalmazásokban használható ◦ Gyors ◦ Pontos

  



Hálózattervezés Költség-becslés Üzleti elemzés Technológiák, architektúrák összehasonlítása


2010.02.25.

47



Látótér bővítése



Gazdasági elemzés



Térképi adatok kezelése



Illesztés nyilvántartó rendszerekhez



Algoritmikus fejlesztések



Értékelés és tapasztalatok

◦ Új technológiák (pl. WDM PON) ◦ Időben változó paraméterek ◦ OPEX elemzés

◦ GIS data interface, pl. OpenStreetMap ◦ Pl. GE SmallWorld ◦ Gyorsabb ◦ Pontosabb ◦ Rugalmasabb

◦ Átfogó tesztek, esettanulmányok


2010.02.25.

48



Kutatási együttműködések ◦ KTH Stockholm ◦ IBBT Gent ◦ AGH Krakkó



Ipari partnerek ◦ ◦ ◦ ◦

Magyar Telekom NETvisor GE SmallWorld Ericsson SE


2010.02.25.

49







Háttér (FTTx/NGA hálózatok) ◦ ◦ ◦ ◦

Szolgáltatások Piaci trendek Architektúrák Technológiák

◦ ◦ ◦ ◦

Célok Elvárások Munkafolyamat Ma elterjedt megoldások


Hálózattervezés, mint optimalizálási feladat ◦ ◦ ◦ ◦







Kihívások Modell Költségfüggvény Feltételek

Algoritmikus háttér ◦ ◦ ◦

Részfeladatok Bonyolultság Kidolgozott megoldások

◦ ◦ ◦

Történet, fejlesztők Keretrendszer moduljai Mintapélda / esettanulmány

FTTxDesigner

Elért eredmények ◦ ◦ ◦ ◦

Értékelés Alkalmazási lehetőségek Kapcsolatok, együttműködések Tervek


2010.02.25.

50

Kapcsolat: Mitcsenkov Attila BME TMIT [email protected] IE.327a


2010.02.25.

51

No title

Recommend Documents