Tudományos Diákköri Konferencia Csomagkapcsolt hálózatok hívásengedélyezési algoritmusának megvalósítása neurális hálózattal László Endre /RC6SHM/
Konzulens: Dr. Levendovszky János
Pázmány Péter Katolikus Egyetem Információs Technológiai Kar
1
Tartalomjegyzék 1. Absztrakt
4
2. Bevezetés és motiváció 2.1. Probléma felvetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Lehetséges megoldás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. A dokumentum felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 4 5 6
3. Technológiai összefoglaló 3.1. Az ATM hálózat ismertetése . . . . . . . . . 3.2. CAC (Call/Connection Admission Control) szerz®dés betartásában . . . . . . . . . . . . 3.3. CAC modelljének ismertetése . . . . . . . .
6 6
. . . . . . . . . . jelent®sége ATM . . . . . . . . . . . . . . . . . . . .
4. Forgalmi modell 4.1. ON/OFF modell . . . . . . . . . . . . . . . . 4.2. Aggregált forgalom valószín¶sége . . . . . . . 4.3. Meg gyelt terhelés valószín¶sége . . . . . . . 4.4. Össz forgalom valószín¶sége . . . . . . . . . . 4.5. A hívásengedélyezési feladat a modell alapján
. . . . . . . . . . . . . hálózat QoS forgalmi . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8
. . . . .
9 10 10 10 10 11
5. Hívásengedélyezési algoritmus parametrikus esetben 5.1. Megvalósítás, problémák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Numerikus eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Numerikus számítások számításigényének csökkentése . . . . . . . . . . . . . . . . .
12 15 18 19
6. Hívásengedélyezési algoritmus nemparametrikus esetben 6.1. Bayes-döntés megvalósítása neurális hálózattal . . . . . . . . . . . . . . . . . . . . . 6.2. Nemparametrikus döntés neurális hálózatokkal . . . . . . . . . . . . . . . . . . . . . 6.3. Teljesít®képesség analízis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21 21 21 22
7. El®recsatolt neurális hálózat irányított tanulással 7.1. A tanuló halmaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2. Az optimális hálózat megválasztása . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3. A tanuló algoritmus megválasztása . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4. A hálózat teljesít® képessége . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5. A korlátok alapján megválasztott tanuló halmaz összehasonlítása az teljes intervallumon megválasztott tanuló halmazzal . . . . . . . . . . . . . . . . . . . . . . . . . . .
24 25 26 27 28
8. Szimuláció NS2 (Network Simulator v2) hálózati szimulátor 8.1. Hálózati szimulátorok . . . . . . . . . . . . . . . . . . . . . . . 8.2. NS2 bemutatása . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.1. Az keretrendszer bemutatása . . . . . . . . . . . . . . . 8.3. A szimulátor alapjai . . . . . . . . . . . . . . . . . . . . . . . . 8.4. Kett®s implementáció: OTcl és C++ objektumok kapcsolata . . 8.5. NAM (Network Animator) bemutatása . . . . . . . . . . . . . .
31 31 32 32 33 38 41
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
segítségével . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . . .
. . . . .
. . . . . .
. . . . .
. . . . . .
. . . . . .
9. FANN (Fast Arti cial Neural Network Library) a nemparametrikus döntés implementálására 9.1. FANN bemutatása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2. A függvénykönyvtár felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3. Gra kus frontend a hálózat tanításához . . . . . . . . . . . . . . . . . . . . . . . . . 9.4. Tapasztalatok a nemparametrikus döntés megvalósítása során . . . . . . . . . . . . .
2
29
41 41 42 43 43
10.A hívásengedélyezés megvalósítása NS2 szimulációs környezet és FANN neurális hálózat segítségével 44 11.Összefoglalás és konklúzió
45
12.Felhasznált eszközök
47
13.Hivatkozások, felhasznált irodalom
48
3
1. Absztrakt A mai infokommunikációs technológiák lehet®vé teszik a felhasználók számára, hogy csomagkapcsolt hálózatokon keresztül részesüljenek hálózati szolgáltatásban. Ilyen hálózat például egy ATM (Asynchronous Transmission Protocoll) vagy MPLS (MultiProtocol Label Switching) hálózat. Egyre nagyobb az igény olyan szolgáltatásokra, mint amit a VoIP (Voice over Internet Protocol), a teleconference vagy más video stream alapú tartalomközlés nyújt. Ezen technológiák megszorítást adnak az alattuk m¶köd® csomagkapcsolt hálózatok -esetünkben ATM/MPLS hálózat-, m¶ködésére. A csomagveszteség valószín¶sége (CLP - Cell Loss Probability), a késleltetés (MCD - Mean Cell Delay) és a jitter paraméterek, mint QoS (Quality of Service - Szolgáltatás Min®ség) paraméterek, írják le ezeket a megszorításokat. CAC (Call Admission Control - Hívásengedélyezési Felügyelet) egyszer¶ értelmezésben annak eldöntése, hogy a hálózatra jelentkez® fél forgalmát elfogadjuk-e vagy sem. Pontosabb de níció szerint: olyan események sorozatának kivitelezése a hálózat által, melyek egy hívás felállítás folyamán a virtuális csatorna (ATM) kialakításának elfogadását eredményezi. A CAC a torlódási kontrol (Congestion Control) stratégia egyik f® eleme, valamint az áramkör kapcsolás és CBR forgalmi szerz®dés betartásának egyetlen módja. A CAC feladata annak eldöntése, hogy egy új, csatlakozó hívó fél beengedésére van-e elég szabad sávszélessége (adatátviteli sebesség) a hálózatnak, vagyis a beengedése esetén el®fordulhat-e a forgalmi szerz®dés megszegése. Ha ilyen egy adott valószín¶séggel el®fordulhat, akkor a potenciális hívó felet nem szabad beengedni a hálózatra. A döntés után a hálózat értesíti a hívó felet, az elutasító vagy elfogadó válaszról. A CAC algoritmusokkal tehát a hálózat sávszélességét igénybe vev® felhasználók számát igyekszünk megfelel®en korlátozni, mely így a QoS kritériumok betartása mellett szavatolja a hálózat optimális kihasználtságát is. Így a CAC egy preventív jelleg¶ Congestion Control. Ebben a munkában egy ilyen CAC algoritmus megvalósítását végeztem el neurális hálózat segítségével. Ez magában foglalja a szükséges függvénykönyvtárakat és az algoritmus teljesít®képességének mérését a modell alapján. A neurális hálózat tanítását egy statisztikus forgalmi modellb®l nyert tanuló halmazzal végeztem. Ezen algoritmus alapjai publikált cikkekben taglaltak. A szimulációs eredményeket valamint egyéb részeredményeket és részfeladatokat jelen dokumentumban bemutatom. Megismertem egy a napjainkban igen elterjedt hálózati szimulációs eszközt, az NS2-t és felmértem képességeit. Megismertem egy hatékony el®recsatolt neurális hálózat implementációt, a Fast Arti cial Neural Network Library-t (FANN). Valamint e kett®t ötvözésének céljából beágyaztam egy, az FANN-en alapú neurális hálózatot az NS2 hálózati szimulátor keretrendszerébe.
2. Bevezetés és motiváció A következ®kben röviden összefoglalom a távközlési hálózatokban felmerül® problémák forrását és valamint ezek lehetséges megoldását.
2.1. Probléma felvetés A mai infokommunikációs technológiák lehet®vé teszik a felhasználók számára, hogy csomagkapcsolt hálózatokon keresztül részesüljenek hálózati szolgáltatásban. Egyre nagyobb az igény olyan szolgáltatásokra, mint amit a VoIP (Voice over Internet Protocol), a teleconference vagy más video stream alapú tartalomközlés nyújt. Ezen technológiák megszorítást adnak az alattuk m¶köd® csomagkapcsolt hálózatok m¶ködésére. A megszorítások nem csak az IP réteget, hanem az az alatt meghúzódó ATM (Asynchronous Transmission Protocoll) réteget is érintik. A csomagvesztés (CLP - Cell Loss Probability), a késleltetés (MCD - Mean Cell Delay) és a jitter paraméterek, mint QoS 4
(Quality of Service - Szolgáltatás Min®sége) paraméterek, jól leírják ezeket a megszorításokat. Két módja van a QoS kritériumok betartásának: Napjainkban elterjedten használt a hálózat méretezésén alapuló megoldás. Ez lehet®vé teszi,
hogy hálózat bizonyos részein el®re lefoglalt er®forrás mindig a rendelkezésünkre álljon. Ez egy hatékony megoldás a QoS biztosításra, azonban jelent®s er®forrástól fosztja meg hálózatot.
CAC (Call Admission Control - Hívásengedélyezési Felügyelet) algoritmusokkal a hálózat sávszé-
lességét igénybe vev® felhasználók számát igyekszünk megfelel®en korlátozni, mely így a QoS kritériumok betartása mellett szavatolja a hálózat optimális kihasználtságát is.
A CAC feladata [1] tehát megbecsülni annak valószín¶ségét, hogy ha egy jelentkez® felhasználót beengedünk a hálózatra, vajon mekkora valószín¶séggel fogja az aggregált forgalom túllépni a csomópont kapacitását: P (aggregált forgalom > csomópont kapacsitása)
és ez alapján eldönteni, hogy ez a valószín¶ség kisebb-e a γ QoS paraméter által meghatározott cellaveszteségnél: P (aggregált forgalom > csomópont kapacitása) < e−γ
A CAC algoritmusnak mindemellett teljesítenie kell még néhány egyéb feltételt is: A hálózat minél optimálisabb kihasználtsága érdekében a lehet® legtöbb felhasználót kell
beengedni.
Egyszer¶ forgalomleírókat kell kérni a felhasználóktól. A felhasználók által meghatározott forgalom leírókat valószín¶ségi változóként kell kezelni -
ezek meghatározás ugyanis mérésb®l származik, ami pedig torzítás vihet a rendszerbe.
Amennyiben feltételezzük, hogy a forgalomleírók megbízható, pontos értékek, a forgalmi paraméterek valamilyen függvényével felülr®l tudjuk becsülni a farok eloszlás integrálját (összegét): P (aggregált forgalom > csomópont kapacitása) < ψ(leíró1 , . . . , leíróM )
Ekkor a CAC feladata annak ellen®rzése, hogy a ψ(leíró1 , . . . , leíróM ) < e−QoS
egyenl®tlenség teljesül-e vagy sem. Ha teljesül, elfogadjuk az adott forgalmi kon gurációt, ellenkez® esetben elutasítjuk.
2.2. Lehetséges megoldás Sokat javíthatunk a hálózat teljesítményén (megbízhatóságán), ha a cellavesztés valószín¶ségét tudjuk valahogy csökkenteni. Cellaveszteség akkor lép fel a hálózat egy csomópontján, ha az nem képes a kapott cellák továbbítására a hálózati csomópont átereszt®képességének teljesít®képessége, vagyis a korlátozott sávszélesség vagy számítási teljesítmény miatt. Ez akkor következik be, ha a router kiszolgálások száma kisebb, mint a szolgáltatásigények száma. Ha feltételezzük, hogy a forgalmat leíró paraméterek ismertek számunkra, megpróbálhatunk következtetést adni arra vonatkozóan, hogy a különböz® felhasználók által aggregált forgalom milyen méretet fog ölteni. Ezen forgalmi leíró paraméterek alapján konstruálhatunk olyan statisztikai modelleket, melyek kell®en jól leírják a rendszer viselkedését, a hálózat sávszélesség igényét. A modell alapján következtetést tudunk adni, hogy egy új felhasználó beengedése a hálózatra hogyan fogja befolyásolni a hálózat terheltségét, vagyis tudjuk-e biztosítani a QoS által el®írt paramétereket. E 5
paraméterek ismeretében választ tudunk adni arra a kérdésre, hogy az adott felhasználót beengedjük a hálózatra, vagy sem. Ennek eldöntés a hosszú farkú eloszlások (Long Tail Distribution) vizsgálatával oldható meg. A forgalmi paraméterek meghatározása - legyen az a router vagy a felhasználó feladata, méréseken alapul, ami magában hordozza e paraméterek becslésének pontatlanságát. Ilyen esetben a rendszer bizonytalansága egy újabb problémát vet fel, mely beillesztése a meglév® modellbe, növeli annak komplexitását, számítás igényét. Ilyen esetben válik hasznossá az el®recsatolt neurális hálózatok (Feed Forward Neural Networks) generalizáló képessége. El®recsatolt neurális hálózatokkal ugyanis ismeretlen nemlineáris rendszer identi kációt végezhetünk. Megjegyzés: A rendszer kiegészíthet® egy puerel (buer), mely a túlcsorduló cellákat tárolja. A puer tárkorlátossága végett viszont nem halmozódhat fel bármekkora számú cella a memóriában. A puer FIFO (First In First Out) adattárolása végett a sor végén lév® cellákat eldobja a router. Így tehát ismét cellaveszteség lép fel. Ebben az esetben természetesen egy más statisztikai forgalmi modellt kell alkalmazni.
2.3. A dokumentum felépítése A munka különböz® szakaszai jól elkülöníthet®k, ezért ezek magyarázata külön-külön fejezetben kapott helyet: 1. Technológiai összefoglaló - röviden összegzi a dologozat témájának technológiai hátterét, az ATM, CAC és QoS fogalmát. 2. Forgalmi modell - leírj azt a statisztikai forgalmi modellt, mely alapján a hívásengedélyezési algoritmus m¶ködik. 3. Hívásengedélyezési algoritmus parametrikus esetben - részletezi a hívásengedélyezési algoritmus azon esetét, amikor a forgalmi modellben szerepl® On/O valószín¶ségi paraméter megbízható értékeknek tekinthet®k. 4. Hívásengedélyezési algoritmus nemparametrikus esetben - részletezi a hívásengedélyezési algoritmus azon esetét, amikor a forgalmi modellben szerepl® On/O valószín¶ségi paraméter a becslés és a felhasználók kommunikációs szokásai miatt nem tekinthet®k x értéknek, hanem egy valószín¶ségi változóként kezelend®k. 5. Szimuláció NS2 (Network Simulator v2) hálózati szimulátor segítségével - bemutatja az NS2 hálózati szimulátort és képességeit, valamint alkamasságát egy CAC algoritmus tesztelésére. 6. FANN (Fast Arti cial Neural Network Library) a nemparametrikus döntés implementálására bemutatja a FANN függvénykönyvtárat és alkalmazhatóságát CAC algoritmus megvalósítására. 7. A hívásengedélyezés megvalósítása NS2 szimulációs környezet és FANN neurális hálózat segítségével - bemutatja az elképzelést mely 8. A számítások során alkalmazott eszközök 9. Összefoglalás és konklúzió 10. Hivatkozások, felhasznált irodalom
3. Technológiai összefoglaló 3.1. Az ATM hálózat ismertetése Az ATM (Asynchronous Transfer Mode) [15] digitális adatátviteli technológiát az 1980-as években kezdték el alkalmazni. A cél egy egyszer¶ felépítés¶ hálózati struktúra volt, mely képes valós idej¶ 6
video-konferencia, audio és egyéb szolgáltatásokat biztosítani. Az ITU és az ATM Forum volt felel®s a protokoll kidolgozásáért. Az ATM az ISO-OSI második, adatkapcsolati rétegébe sorolt csomagkapcsolt protokoll. A transzfer adatot cellákra tördelve továbbítja a hálózaton. Ez a protokoll abban különbözik a többi csomagkapcsolt technológiától, hogy a cellák mérete x, nem változó, mint pl. IP, Ethernet. E protokoll a vonalkapcsolás és a kis, x méret¶ cella révén ötvözi a WAN hálózat kiépítésének lehet®ségét és a valós idej¶ adatkapcsolatot. Az ATM kapcsolatorientált vonalat hoz létre a két végpont között virtuális áramkörön keresztül. A kisméret¶ cellák alkalmazása a valós idej¶ alkalmazások érdekében történt. Az adat ugyanis a multiplexálás következtében jitterrel terhel®dik, vagyis nagy lesz az egyes csomagok közötti késés varianciája. A kisméret¶ cellák használatával a multiplexálás jobban "elkeveri" a különböz® forrásból származó adatokat, ezáltal csökkentve a jittert. Pl. a hang valós idej¶ dekódolásában nagy ennek a jelent®sége, ugyanis a dekódernek be kell várnia adott mennyiség¶ adatot, hogy utána azt dekódolhassa. Egy cella méret technikai megfontolások és politikai érdekek után 53 byte-ra lett választva. Ebb®l 48 byte a payload (adat) és 5 byte a header (fejléc). Az ATM egy csatorna-alapú transzport rétegként funkcionál. Virtuális áramköröket (VC - Virtual Circuit) használ az adatok továbbítására. Ezt a cella fejlécében elhelyezett 8 vagy 12 bites Virtual Path Identi er (VPI) és 16 bites Virtual Channel Identi er (VCI) párosa határozza meg. Vagyis egy virtuális áramkört egy VPI/VCI páros határoz meg. A routolás e VPI/VCI páros szerint történik. Az ATM protokoll másik kulcs eleme a forgalmi szerz®dés (tra c contract) [19]. E szerz®dés a QoS (Quality of Service) része. Négy alap szerz®dés és ezek variációja létezik. A forgalom irányítása ezek alapján történik. A négy alapszerz®dés a következ®: 1. CBR - Constant Bit Rate: egy konstans Peak Cell Rate (PCR) van meghatározva. 2. VBR - Variable Bit Rate: egy átlag cella ráta van meghatározva. A folyam egy bizonyos határt átlápve problémássá teheti a m¶ködést. 3. ABR - Available Bit Rate: minimális bit ráta van meghatározva. 4. UBR - Unspeci ed Bit Rate: a forgalom az össz fennálló kapacitást kihasználhatja. A Constant Bit Rate (CBR) szolgáltatási kategóriát [19] olyan folyamatos, állandó bit ráta alapú kapcsolatoknál alkalmazzák, ahol egy folyamatos szinkronizáció van a forgalmi forrás és a végcél között. A CBR forgalmi szerz®dést olyan esetekben használják, ahol a végpontok megkövetelik az el®rejelezhet® válaszid®t és a statikus, állandó méret¶ sávszélességet, amely a kapcsolat fennállása folyamán elérhet®. Az elérhet® sávszélességet a Peak Cell Rate (PCR) határozza meg. Az ilyen alkalmazások magukba foglalnak olyan szolgáltatásokat, mint a video konferencia, VoIP vagy bármely más igény alapú (on-demand) szolgáltatás. Telefon (VoIP) és natív hang alapú szolgáltatásokhoz a CBR kis késleltetési idej¶ forgalmat szolgáltat megjósolható kézbesítési karakterisztikákkal. Ennél fogva kiválóan alkalmas áramköri emulációra. Hogy a szoláltató tudja magát tartani a szerz®dési feltételekhez, "tra c shapinget" vagy "tra c policinget" használt. Tra c shaping esetén a hálózatra csatlakozáskor a rendszer biztosítja a vonal számára a szükséges er®forrást. Tra c policing estén a cellák eldobásával védekezik a rendszer a hálózat túlterhelése ellen. Hívásengedélyezést alkalmaznak, mikor a hívó fél jelzi a rendszer felé, hogy egy virtuális csatornát igényel a hívott fél felé. Ekkor a rendszer lefoglalja a kapcsolathoz szükséges virtuális áramkört.
7
3.2. CAC (Call/Connection Admission Control) jelent®sége ATM hálózat QoS forgalmi szerz®dés betartásában CAC [16,18,20] egyszer¶ értelmezésben annak eldöntése, hogy a hálózatra jelentkez® fél forgalmát elfogadjuk-e vagy sem. Pontosabb de níció szerint: olyan események sorozatának kivitelezése a hálózat által, melyek egy hívás felállítás folyamán a virtuális csatorna kialakításának elfogadását eredményezi. CAC-ot kapcsolatorientált hálózatoknál alkalmazzák. A CAC a torlódási kontrol (congestion control) stratégia egyik f® eleme, valamint az áramkör kapcsolás és CBR forgalmi szerz®dés betartásának egyetlen módja. A CAC feladata annak eldöntés, hogy egy új, csatlakozó hívó fél beengedésére van-e elég kapacitása a hálózatnak, vagyis a beengedése esetén el®fordulhat-e a forgalmi szerz®dés megszegése [17]. Ha ilyen eset el®fordulhat, akkor a potenciális hívó felet nem szabad beengedni a hálózatra. A döntés után a hálózat értesíti a hívó felet, az elutasító vagy elfogadó válaszról. Nem elég azonban annak biztosítása, hogy a hálózat a forgalmi szerz®désnek megfelel®en m¶ködjön. Ez ugyanis negatívan befolyásolhatja a hálózat kihasználtságát (utilization). Ez egy nagyon fontos aspektusa a CAC feladatának. A következ®kben taglalt modell és megoldás e kihasználtság növelését célozza meg.
3.3. CAC modelljének ismertetése A mai infokommunikációs technológiák lehet®vé teszik a felhasználók számára, hogy csomagkapcsolt hálózatokon keresztül részesüljenek hálózati szolgáltatásban. Ilyen például egy ATM (Asynchronous Transmission Protocoll) vagy IP (Internet Protocol) hálózat. Egyre nagyobb az igény olyan szolgáltatásokra, mint amit a VoIP (Voice over Internet Protocol), a teleconference vagy más video stream alapú tartalomközlés nyújt. Ezen technológiák megszorítást adnak az alattuk m¶köd® csomagkapcsolt hálózatok -esetünkben ATM hálózat-, m¶ködésére. A csomagveszteség valószín¶sége (CLP Cell Loss Probability), a késleltetés (MCD - Mean Cell Delay) és a jitter paraméterek, mint QoS (Quality of Service - Szolgáltatás Min®sége) paraméterek, jól leírják ezeket a megszorításokat. Két módja van a QoS kritériumok betartásának: Napjainkban elterjedten használt a hálózat méretezésén alapuló megoldás. Ez lehet®vé teszi,
hogy hálózat bizonyos részein el®re lefoglalt er®forrás mindig a rendelkezésünkre álljon. Ez egy hatékony megoldás a QoS biztosításra, azonban a hálózat jelent®s er®forrását lefoglalja.
CAC (Call Admission Control - Hívásengedélyezési Felügyelet) algoritmusokkal a hálózat sávszé-
lességét igénybe vev® felhasználók számát igyekszünk megfelel®en korlátozni, mely így a QoS kritériumok betartása mellett szavatolja a hálózat optimális kihasználtságát is. Így a CAC egy preventív jelleg¶ Congession Control.
A CAC feladata [1] tehát megbecsülni annak valószín¶ségét, hogy ha egy jelentkez® felhasználót beengedünk a hálózatra, vajon mekkora valószín¶séggel fogja az aggregált forgalom túllépni a csomópont kapacitását: P (aggregált forgalom > csomópont kapacsitása)
és ez alapján eldönteni, hogy ez a valószín¶ség kisebb-e a γ QoS paraméter által meghatározott cellaveszteségnél: P (aggregált forgalom > csomópont kapacsitása) < e−γ
A CAC algoritmusnak mindemellett teljesítenie kell még néhány egyéb feltételt is: A hálózat minél optimálisabb kihasználtsága érdekében a lehet® legtöbb felhasználót kell
beengedni.
Egyszer¶ forgalomleírókat kell kérni a felhasználóktól.
8
A felhasználók által meghatározott forgalom leírókat valószín¶ségi változóként kell kezelni -
ezek meghatározás ugyanis mérésb®l származik, ami pedig torzítás vihet a rendszerbe.
Amennyiben feltételezzük, hogy a forgalomleírók megbízható, pontos értékek, a forgalmi paraméterek valamilyen függvényével felülr®l tudjuk becsülni a farok eloszlás integrálját (összegét): P (aggregált forgalom > csomópont kapacitása) < ψ(leíró1 , . . . , leíróM )
Ekkor a CAC feladata annak ellen®rzése, hogy a ψ(leíró1 , . . . , leíróM ) < e−QoS
egyenl®tlenség teljesül-e vagy sem. Ha teljesül, elfogadjuk az adott forgalmi kon gurációt, ellenkez® esetben elutasítjuk. Amennyiben nem ismertek a forgalom leírók vagy a mérés miatt nem megbízhatóak, a rendszerben ezzel a bizonytalansággal is számolni kell. Ebben az esetben az optimális Bayes-döntés (MAP Maximum A Posterior) adja meg számunkra a legmegbízhatóbb eredményt. E döntést a meg gyelt aggregált forgalom függvényében tudjuk meghozni: ϕopt (y) = max P (Y = y | ξ = di )P (ξ = di ) i
ahol ϕopt
y
az optimális döntést hozó függvény a meg gyelt aggreagált forgalom
A Bayes-döntés részletes tárgyalása az 5. fejezetben található meg. Az el®re csatolt neurális hálózat képes optimális Bayes-döntés megvalósítására [2]. Ez a képessége teszi lehet®vé alkalmazását CAC algoritmusként.
4. Forgalmi modell A következ®kben tárgyalt forgalmi modell [1] segítségünkre lesz parametrizált hívásengedélyezési algoritmus megalkotásához, és a nemparametrikus hívásengedélyezési algoritmus teljesít®képességének méréséhez. Felhasznált jelölések: M
n
(mi , hi )
C γ yi
A forgalmi osztályok (tra c class) száma. Egy forgalmi osztály magába foglalja azon felhasználókat, akik azonos forgalomleíró paraméterekkel rendelkeznek. Ezek szerint a VoIP, FTP, HTTP stb. forgalomat lebonyolító felhasználók külön-külön forgalmi osztályba tartoznak. Forgalmi állapot vektor. Egy M elem¶ vektor, mely a rendszer állapotát írja le, ahol az egyes elemek (ni ) az i -ik forgalmi osztályban jelen lev® felhesználók száma Forgalom leírók - számpáros, mely az i -ik forgalmi osztályban lév® egy entitás által generált forgalom várható értékét és csúcsértékét reprezentálja A csomópont forgalmi kapacitását jelöli. Ezt az értéket túllép® össz forgalom cellavesztést eredményez (puer nélküli routere esetén). QoS paraméter. A csomagvesztés (CLP) valószín¶ségét írja el®, erre fels® korlátot ad: CLP < eγ Az i-ik osztályban meg gyelt aggregált forgalom. 9
4.1. ON/OFF modell Az ON/OFF modell Bernoulli eloszlású valószín¶ségi változónak tekinti az osztályok instanciáit. Ez természetesen csak egy közelítése a valós adatforgalmat generáló entitásnak. A valóságban egy felhasználó általában VBR (Variable Bit Rate) forgalmat generál. Ez a modell egyszer¶bb és bizonyított, hogy egy rosszabb eset (worst-case) modell. Egy jelenlev® entitás eszerint vagy az osztályra jellemz® teljes sávszélességgel használja a hálózatot, vagy kikapcsolt állapotban van. Ennek megfelel®en a két állapot valószín¶sége: P (Xi = 0) = 1 − pi
P (Xi = hi ) = pi
ahol pi =
mi pi
Mivel az ON/OFF forrás modell egyfajta worst-case modell, biztosak lehetünk abban, hogy ha a CAC algoritmus teljesíti az ezen a modellen alapuló kritériumokat, akkor az valós forgalom esetén is biztonságosan fog m¶ködni, vagyis másodrend¶ hiba (nem kellene elfogadni, mégis elfogadjuk) nem fog el®fordulni.
4.2. Aggregált forgalom valószín¶sége i Az i -ik osztályon belüli aggregált forgalmat Yi = nk=1 Xi = ni Xi valószín¶ségi változó adja. Az i -ik osztályban összegz®dött forgalom valószín¶sége, vagyis hogy ni felhasználó esetén yi bekapcsolt felhasználó valószín¶ségét a következ® binomiális eloszlás határozza meg:
P
P (Yi = yi ) =
ni yi pi (1 − pi )ni −yi yi
4.3. Meg gyelt terhelés valószín¶sége Az i -ik osztályokban aggregált forgalmak független egymástól, ezért a meg gyelt terhelés, vagyis az össz aggregált terhelés valószín¶sége az egyes osztályok aggregált forgalmának valószín¶ségeinek szorzatával számolható: P (Y = y) =
M Y ni yi pi (1 − pi )ni −yi yi
i=1
ahol Y = (Y1 , Y2 , · · · , YM ) .
Yi =
Pni
k=1 Xi = ni Xi
y = (y1 , y2 , · · · , yM ) yi
Yi az i-ik osztályt leíró valószín¶ségi változó, ami az i-ik osztály aggregált forgalomát határozza
meg. Valószín¶ségi változó ni számú Xi valószín¶ségi változó összege. Meg gyelt forgalomvektor. Meg gyelt forgalom az i-ik forgalmi osztályból.
4.4. Össz forgalom valószín¶sége Az össz forgalmat úgy de niáljuk, mint az egyes osztályokban aggregált forgalmak összege: Y =
M X
Yi =
i=1
M X i=1
10
ni Xi
Annak a valószín¶sége, hogy az össz forgalom egy bizonyos k értéket vesz fel, binomiális eloszlású valószín¶ségi változók összegeként számolható. Független valószín¶ségi változók összegének valószín¶sége az eloszlásuk konvolúciójával számolható. Adott ξ és η binomiális eloszlású független valószín¶ségi változók, melyek nem negatív értéket S vesznek fel. Ismert az eloszlásuk, mely rendre fi = P (xi ) és hi = P (xi ) , ahol xi ∈ R+ {0}. b1 , b2 , . . . , bM sorozat elemeire igaz, hogy 0 ≤ bi < ∞ és c = bj , ahol jN, 1 < j < M . Ekkor γ =ξ+η
valószín¶ségi változóra a következ®k igazak: P (γ = c)
= P (ξ + η = c) =
M X
(ξ + bi − bi + η = c|bi )P (bi )
i=1
=
M X
P (ξ = c − bi , η = bi )
i=1
=
M X
P (ξ = c − bi )P (η = bi )
i=1
=
M X
fj−i hi
i=1
= f ∗h
Ennek megfelel®en az össz aggregált forgalom valószín¶sége: P (Y = k) =
n1 y1 ni yi n1 −y1 ∗ ··· ∗ p1 (1 − p1 ) pi (1 − pi )ni −yi ∗ · · · ∗ y1 yi nM ∗ pyMM (1 − pM )nM −yM yM
4.5. A hívásengedélyezési feladat a modell alapján A fenti modell ismeretében megfogalmazhatjuk a következ® két feladatot: Ha ismertek (meghatározhatók) a pi , i = 1, . . . , M paraméterek, hogyan becsülhet® felülr®l a farok eloszlás farka: M X ni Xi > C) < Ψ(p1 , . . . , pM ) P( i=1
Ha nem ismert (nem határozhatók meg) a pi , i = 1, . . . , M paraméterek, viszont meg tudjuk gyelni az osztályonkénti aggregált forgalmat, vagyis y = (y1 , y2 , · · · , yM ) -t, hogyan határozhatjuk
meg, hogy milyen döntést kell hoznunk: Accept(elfogadás):
M X X P( ni Xi > C) = P (Y = k) < e−γ i=1
k>C
vagy Reject(visszautasítás): M X X P( ni Xi > C) = P (Y = k) > e−γ i=1
k>C
11
Az utóbbi eset a hipotézivizsgálat feladata mely meg kell, hogy er®sítse a egyik feltevést: elfogadjuk vagy elutasítjuk az adott forgalmi vektort a meg gyelt aggregált forgalom alapján.
5. Hívásengedélyezési algoritmus parametrikus esetben Mikor egy ATM hálózaton hívásengedélyezést végzünk, a felhasználók feladata, hogy a forgalom leíróikat közöljék a CAC-ot végz® szerverrel. Ezen leírók alapján meghatározhatók a forgalmi paraméterek (Pi ). A forgalmi paraméterek nem a valós, pontos értékek - mivel mérésb®l származnak -, ezért valószín¶ségi változóként kezeljük ®ket, és feltételezzük, hogy Pi várható érték¶, σi szórású normál eloszlás írja le ®ket: pi ∼ N (Pi , σ 2 ). A következ®kben taglalt levezetést a [11] hivatkozásban taglalt levezetéssel analóg módon végzem el. Legyen ξ az a valószín¶ségi változó, mely a CAC optimális döntése szerint veszi fel értékét. Ez egy számunkra ismeretlen eloszlású valószín¶ségi változó, mely két értéket vehet fel: ξ =Accept(elfogad) vagy ξ =Reject(elutasít). Ez a két lehet®ség lefedi a ξ döntés teljes eseményhalmazát: ξ ω = {Accept, Reject}
Lévén, hogy ξ -r®l semmit nem tudunk, hipotézis vizsgálattal fogjuk eldönteni, hogy melyik a lehet® legjobb döntés: ξˆ = Accept(elfogad)
vagy
ξˆ = Reject(elutasít)
Legyen a döntést hozó függvényünk ϕ:Y→ω
vagyis ahol
ϕ(y) = di
y = (y1 , . . . , yM )Y és di ω
ϕ függvény jóságának eldöntéséhez de niálunk egy költségfüggvényt: C : ω xω → R
vagyis C(ξ, ϕ(Y )) R
Minél kisebb C függvény értéke, annál jobbnak tekintjük ϕ következtetést. C(ξ, ϕ(Y )) is valószín¶ségi változó, mivel ξ és Y értékét®l függ. A költségfüggvény csak ξ és Y egy realizációja esetén min®síti ϕ döntés helyességét. A ϕ következtetés függvényt a várható értékével
jellemezhetjük:
R(ϕ) = E(C(ξ, ϕ(Y ))) R(ϕ) a globális kockázat (speciális esetben a ϕ-t jellemz® hibafüggvény). A gyakorlatban Y egy realizációjét tudjuk meg gyelni, ez az y = (y1 , . . . , yM ) vektor. ξ egy realizációja di eleme ω halmaznak. ξ eloszlását qi = P (ξ = di ) apriori valószín¶ségek adják, amik viszont nem ismertek el®ttünk.
A hipotézis tehát, aminek helytállóságát vizsgáljuk a Hi = P (ξ = di ), i = 1, 2 . Legyen a költségfüggvény a következ®: 12
( C(di , dj ) = 1 − δij =
1, ha i 6= j 0, ha i = j
Ekkor R(ϕ)
= E(C(ξ, ϕ(Y ))) = =
2 X 2 X
C(di , dj )P (ξ = di , ϕ(Y ) = dj ) =
i=1 i=1
=
2 X 2 X
(1 − δij )P (ξ = di , ϕ(Y ) = dj ) =
i=1 i=1
=
2 X 2 X
P (ξ = di , ϕ(Y ) = dj ) −
i=1 i=1
=
1−
2 X
2 X 2 X
δij P (ξ = di , ϕ(Y ) = dj ) =
i=1 i=1
P (ξ = di , ϕ(Y ) = dj ) =
i=1
=
1 − P (ξ = ϕ(Y )) =
= P (ξ 6= ϕ(Y ))
A P (ξ = di | Y = y) feltételes, aposzteriori valószín¶ségek, melyek Y meg gyelési tartományt D1 és D2 döntési tartományra osztják. Ezen tartományok azokat a meg gyelhet® vektorokat tartalmazzák,
melyek meg gyelése esetén Accept-re vagy Reject-re döntünk:
D1 = {y : ϕ(y) = Accept} D2 = {y : ϕ(y) = Reject}
Látható tehát, hogy ϕ döntés megadható döntési tartományaival. Számunkra ez nagyon el®nyös, mivel a neurális hálózatok jól alkalmazhatók halmaz szeparációra. Legyen a j-ik döntési tartomány Dj∗ olyan, hogy ∀yDj∗ esetén P (ξ = dj | Y = y) ≥ P (ξ = di | Y = y) teljesüljön minden i 6= j -re. Ez azt jelenti, hogy y pontosan akkor eleme Dj∗ döntési tartománynak, ha y meg gyelés esetén {ξ = dj } hipotézis feltételes valószín¶sége a legnagyobb. Az optimális, Bayes-döntés tehát: ϕopt (y = di ),
ha y Di∗
Mivel a P (ξ = di | Y = y) a posteriori valószín¶ségek nem ismertek, a következ® képpen tudjuk ®ket meghatározni: P (ξ = di | Y = y) =
P (Y = y | ξ = di )P (ξ = di ) P (ξ = di , Y = y) = P (Y = y) P (Y = y)
Azonban P (Y = y)-tól nem függ a fenti kifejezés (ξ -re sz¶kített) maximuma, a következ® igaz: max P (ξ = di | Y = y) = max P (Y = y | ξ = di )P (ξ = di ) i
i
Az optimális ϕopt döntésre a fentiek akkor teljesülnek, ha ez a döntés minimális hibával dönt.
13
De niáljuk tehát a ϕopt optimális döntést meghatározó függvényt: ˆ = minP (ξˆ = Accept, ξ = Reject)+ ϕopt : minP (ξ 6= ξ) ϕ
ϕ
+ P (ξˆ = Reject, ξ = Accept) = = minP (ϕ(y1 , . . . , yM ) = Accept, ξ = Reject)+ ϕ
+ P (ϕ(y1 , . . . , yM ) = Reject, ξ = Accept) = = minP (ϕ(y1 , . . . , yM ) = Accept | ξ = Reject)P (ξ = Reject)+ ϕ
+ P (ϕ(y1 , . . . , yM ) = Reject | ξ = Accept)P (ξ = Reject)
Arra törekszünk, hogy ez a döntés minimális hibával adjon döntést az Accept vagy Reject hipotézisre. Ekkor ez a döntésfüggvény a Bayes-döntés vagy maximum a posteriori döntés. A Bayesdöntést tehát a ϕ(y) függvény fogja elvégezni: ϕopt (y) = max P (Y = y | ξ = di )P (ξ = di ) i
Ez a formula átírható, egy transzformációval a következ® képpen is értelmezhet®: ϕopt (y) = sgn(P (Y = y | ξ = Accept)P (ξ = Accept)− − P (Y = y | ξ = Reject)P (ξ = Reject))
ahol
1 esetén Accept −1 esetén Reject
( ϕopt (y) =
Vagyis akkor fogadunk el egy Accept hipotézist, ha annak valószín¶sége egy meg gyelt y aggregált forgalom vektor esetén nagyobb, mint a Reject hipotézis valószín¶sége. Hasonlóképpen a Reject hipotézisre: akkor fogadjuk el, ha annak valószín¶sége nagyobb, mint az Accept-é. Ekkor a függvény kimenete negatív lesz. Mivel forgalomleírókat valószín¶ségi változóknak tekintjük, ezért a forgalmi paramétereket valamilyen f (p1 , . . . , pM ) s¶r¶ségfüggvény írja le, és így az apriori valószín¶ségek a követekz®képpen számolhatók: Z
Z ···
P (ξ = Accept) = Z P (ξ = Reject) =
···
p:ψ(p)<e−γ Z p:ψ(p)>e−γ
f (p1 , . . . , pM )dp1 . . . dpM f (p1 , . . . , pM )dp1 . . . dpM
ahol ψ(p) függvény a farok eloszlás egzakt, legkisebb, numerikus fels® becslése. Továbbá az a posteriori valószín¶ségek a következ®k: P (Y =y | ξ = Accept) = Z Z M Y ni yi = ··· pi (1 − pi )ni −yi f (p1 , . . . , pM )dp1 . . . dpM p:ψ(p)<e−γ i=1 yi P (Y =y | ξ = Reject) = Z Z M Y ni yi = ··· pi (1 − pi )ni −yi f (p1 , . . . , pM )dp1 . . . dpM p:ψ(p)>e−γ i=1 yi
14
Mivel Y binomiális, diszkrét eloszlású, f (p1 , . . . , pM ) viszont folytonos (s¶r¶ségfüggvény) és mindekét eloszlás p1 , . . . , pM valószín¶ségekt®l függ, a Y eloszlását bevihtejük az integrandusba. A fenti formulákban szerepl® s¶r¶ségfüggvényt olyanra kell választani, ami a legjobban leírja a felhasználók által átlagolt forgalmi leírók eloszlását. Mivel a p = (p1 , . . . , pM ) forgalmi paraméterek ezen átlagokból származnak, az eloszlásukat jól leírja például a normál eloszlás: M
X (pi − Pi )2 1 exp f (p1 , . . . , pM ) = − 1 2 QM 2σi2 i=1 (2π)M i=1 σi2
!
2 ahol P = (P1 , . . . , PM ) a várható értékeket jelöli, σ 2 = (σ12 , . . . , σM ) pedig a szórásnégyzete, varianciát. A szórásnégyzet értelmezhet® úgy is, mint a felhasználók megbízhatósága a forgalom leírók becslése szempontjából. Ezt gyelembe véve a felhasználókat e szolgáltatás igénybevételekor felárral lehet terhelni. Felhasználva a normál eloszlást az a priori és az a posteriori valószín¶ségek a következ®k lesznek:
P (ξ = Accept) = ! Z Z M X 1 (pi − Pi )2 dp1 . . . dpM = ··· 1 exp − 2σi2 p:ψ(p)<e−γ (2π)M QM σ 2 2 i=1 i=1 i
P (ξ = Reject) = ! Z Z M X 1 (pi − Pi )2 = ··· dp1 . . . dpM 1 exp − 2σi2 p:ψ(p)>e−γ (2π)M QM σ 2 2 i=1 i=1 i
és P (Y = y | ξ = Accept) =
Z
M Y ni
Z ···
p:ψ(p)<e−γ i=1 yi
pyi i (1 − pi )ni −yi
M
X (pi − Pi )2 1 − 1 exp QM 2σi2 2 i=1 (2π)M i=1 σi2
P (Y = y | ξ = Reject) =
Z
M Y ni
Z ···
p:ψ(p
)>e−γ
i=1
yi M
! dp1 . . . dpM
pyi i (1 − pi )ni −yi
X (pi − Pi )2 1 − 1 exp QM 2σi2 2 i=1 (2π)M i=1 σi2
! dp1 . . . dpM
5.1. Megvalósítás, problémák Az implementálást Matlab 2007b környezetben végeztem. A megvalósítás folyamán nagy segítségemre volt [10] hivatkozásként megjelölt könyv. A feladatok igyekeztem részfeladatokra bontani, hogy növeljem az általam írt függvények minél általánosabb felhasználhatóságát. A parametrikus hívásengedélyezés feladatát a következ® részfeladatokra bontottam, melyek az esetek többségében egy-egy függvénynek felenek meg: 15
calc_P_overall_load()
A farok eloszlást P számolja ki, a megadott paraméterek alapján. Kimenete egy sor vektor, melynek k = M i=1 yi -ik eleme annak valószín¶ségét határozza meg, hogy n = (n1 , . . . , nM ) forgalmi vektor esetén mekkora a k aktív felhasználók száma. Ha az argumentumban megadott p1 változó nem egy konstans, hanem egy vektor, akkor ennek megfelel®en a kimenet egy mátrix lesz, melynek k-ik oszlopvektora a k aktív felhasználó valószín¶ségét adja meg különböz®, a p1 vektorba de niált valószín¶ségeknek megfelel®en. P (Y = k) =
n1 y1 ni yi p1 (1 − p1 )n1 −y1 ∗ · · · ∗ pi (1 − pi )ni −yi ∗ · · · ∗ y1 yi ni ∗ pyMM (1 − pM )nM −yM yM
formulát valósítja meg. tail_test()
A farok eloszlás alapján kiszámolja (összegzi) a farok valószín¶séget, majd ezt a valószín¶séget összehasonlítja a QoS paraméter által el®írt CLP valószín¶séggel. P(
M X
ni Xi > C) =
i=1
X
P (Y = k) < e−γ
k>C
döntést végzi el. calc_P_Y()
Az argumentumban meghatározott y meg gyelt terhelési vektor el®fordulásának valószín¶ségét határozza meg. P (Y = y) =
M Y ni
i=1
yi
pyi i (1 − pi )ni −yi
formulát valósítja meg. aprior()
A P (ξ = di ) a priori valószín¶séget számolja ki, ami gyakorlatilag egy csonka haranggörbe integrálását jelenti. Az integrálást 0.001 maximális hibával végzi. Az implementálás folyamán ügyelni kellet, hogy a csonka haraggörbe (lásd a 1 ábrát) által okozott torzítást visszaállítsam. A normális s¶r¶ségfüggvény integrálja a [0,1]x[0,1] tartományon nem adja ki az 1 értéket. Ebb®l kifolyólag a két apriori valószín¶ség összege nem fedte le a teljes eseményhalmazt. Ez indokolta, hogy egy normalizálást végezzek a kapott a priori valószín¶ségen a normális s¶r¶ségfüggvény [0,1]x[0,1] tartományú integráljával. A Matlab dblquad() két dimenziós integráló függvénye az általunk implementált függvényre megszorítást ad [10]. A függvényünk képes kell, hogy legyen arra, hogy ha az els® paramétert vektorként adja meg a dblquad() függvény, akkor a kimenetünk is vektor legyen. Ennek megfelel®en a hipotézis vizsgálatok eredményének összege nem adhat 1-et. A 2 ábrán látható, hogy a két hipotézist leíró függvény egymás komplementere. A színskálát a Matlab automatikusan választotta meg, ezért van jelen mind két ábrán a maximális intenzitás - a vörös csúcs. aposterior()
A P (Y = y | ξ = di ) a posterior valószín¶séget számolja ki. Mivel ebben a formulában is szerepel a csonka haranggörbe, itt is el kellett végezni a fent említett Ebben az esetben normalizálást. QM ni yi ni −yi a kapott a posterior valószín¶séget normalizáltam a i=1 pi (1 − pi ) f (p1 , . . . , pM ) yi
[0,1]x[0,1] tartományú integráljával. Az integrálást ebben az esetben is 0.001 maximális hibával végeztem. 16
16
14
12
10
8
6
4
2
0 1 0.9 0.8 0.7 1
0.6 0.9
0.5
0.8 0.7
0.4
0.6 0.3
0.5 0.4
0.2
0.3 0.2
0.1 0
0.1 0
1. ábra. Az ábrán látható 2 dimenziós normál eloszlás a esetünkben nem értelmezett negatív valószín¶ségekre, integrálja tehát a [0,1]x[0,1] tartományon nem lehet 1. A felület p1 és p2 függvényében van ábrázolva.
1
1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0
0.1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
(a) Az a priori valószín¶ség integrandusa(b) Az a priori valószín¶ség integrandusa Accept hipotézis esetén Reject hipotézis esetén 2. ábra. A priori valószín¶ségek p1 és p2 függvényében.
17
bayes_decision()
Elvégzi a Bayes-döntést az els®jel meghatározása nélkül. A Bayes-döntés feladatából azért tartottam célszer¶nek kivenni szignum függvényt, mivel abban az esetben a valószín¶ségek különbésgei végleg elvesznének, és egy kés®bbi alkalmazás során nem lennének felhasználhatóak. calc_normpdf()
Két dimenziós, egymástól független normál eloszlást számol. Azért volt szükség a normpdf() Matlab függvény kiterjesztésére, mert a dblquad() által igényelt paraméterezhet®séget ki kellett elégiteni - a p1 ON/OFF valószín¶ség vektor is lehet. bayes_map_2D()
Egy adott forgalmi vektor esetén a Bayes-döntést határozza meg minden lehetséges y meg gyelésre azzal, hogy nem a visszatérési értékként adott mátrix elemei nem bináris értékek, hanem lebeg®pontos értékek - a sign() függvény nem lett rájuk lefuttatva.
5.2. Numerikus eredmények A következ® ábrán a farok eloszlásból számolt parametrikus hívásengedélyezést szemléltetem. A 3 ábrán az egyes forgalmi kon gurációkra adott döntés látható A következ® paramétereket alkalmaztam a számításnál: N = [100 100] Fels® korlát a lehetséges forgalmi kon gurációkra m = [0.1 0.8] ON/OFF modell várható értékei h = [1 1] ON/OFF modell csúcs értékei C = 20 Csomópont kapacitása gamma = 9 QoS paraméter
0 10 20 30
n2
40 50 60 70 80 90 100 0
20
40
60
80
100
n1
3. ábra. Parametrikus döntés demonstrációja - a kékkel jelölt forgalmi kon guráció elfodható. A 4 ábrán három példa látható a különböz® kapacitású csomópontok nemparametrikus hívásengedélyezés Bayes-döntési tartományaira. A számításoknál a következ® paramétereket alkalmaztam: n = [50 50] Forgalmi kon guráció P = [0.2 0.15] A becsült paraméter várható értéke sigma = [0.1 0.1] A becsült paraméter szórása 18
CLP = exp(−9) QoS paraméter
5.3. Numerikus számítások számításigényének csökkentése Egyes korábban implementált függvények számítási igénye igen nagy volt, ami akadályt jelentett a további fejlesztésben, tesztelésben. Ilyen problémát jelentett a MAP formula két szorzandója, az apriori feltételezés és a feltételes (evidence) valószín¶ségek kiszámításához szükséges integrálás id®igénye: Aprior formula elfogadási hipotézis esetén: Z P (ξ = Accept) =
Z ···
p:ψ(p)<e−γ
f (p1 , . . . , pM )dp1 . . . dpM
Evidence formula elfogadási hipotézis esetén: P (Y = y | ξ = Accept) = Z Z M Y ni yi = ··· pi (1 − pi )ni −yi f (p1 , . . . , pM )dp1 . . . dpM y −γ i p:ψ(p)<e i=1
Látható, hogy az integrálást a farok eloszlás által meghatározott régión kell elvégezni. A farok eloszláson alapuló döntést indikátor függvényként [10] használva végeztem az integrálást. Mivel a farok eloszlás az integrál változó, vagyis az On/O valószín¶ségek függvénye, ezért azt a [0,1]x[0,1] tartományon az összes valószín¶ségre ki kell számolni. Így lehet megkapni a négyzetes tartományon belüli, valós integrálási tartományt. A farok eloszlás kiszámítása azonban nagyon id®igényes, ami magával vonja az integrálási m¶velet lassulását. Egy új indikátor függvényt készítettem, mely inicializál egy mátrixot a farok eloszlás szerint. A mátrix minden eleme egy valószín¶ség párnak megfelel® farok eloszlás szerinti döntés. Az indikátor függvény minden meghívása alkalmával ennek a mátrixnak a megfelel® elemét adja vissza. A farok eloszlás farkát mindeddig egy for ciklussal összegeztem. Mivel azonban a Matlab beépített függvényei gyorsabbak (vekorizálás), ezért egy kumulatív vektor összegz® függvénnyel helyettesítve az összegzést, a döntést id®igényét kb. 70%-ra csökkentettem. Ezekkel a módosításokkal a Bayes-döntés kiszámításához szükséges id®t a tizedére tudtam csökkenteni.
19
4. ábra. Bayes-döntések demonstrációja. Jobb oldalon a bal oldali függvény el®jele látható C = 55, C = 46 és C = 40 csomóponti kapacitással
20
6. Hívásengedélyezési algoritmus nemparametrikus esetben Nemparametrikus döntés problémáját CAC esetén el®ször Gibbens[8] vette fel. Ebben az esetben a CAC feladata a rendelkezésre álló minták (gyakorlatban a mérések) alapján meghatározni a döntési intervallumokat. A nemparametrikus hipotézistesztelés részleteit a [1,2,3] hivatkozás tartalmazza. A statisztikán alapuló modellek el®nye, hogy nagy állapottér esetén pontos becslést tudnak adni a farok eloszlás által meghatározott döntésre. Hátrányuk viszont, hogy a forgalmi paraméterek eloszlása nem ismert (eddig csak feltételezéssel éltünk) és igen jelent®s számítási igényük nem teszi lehet®vé alkalmazásukat olyan real-time számítást igényl® rendszernél, mint egy ATM hálózat (router). Olyan ekvivalens metódusra van tehát szükség, mely ezt a feladatot valós id®ben tudja megoldani. Az el®recsatolt neurális hálózatok megoldást jelenthetnek erre a problémára nem-lineáris rendszer identi kációs képességük folytán.
6.1. Bayes-döntés megvalósítása neurális hálózattal Tegyük fel, hogy rendelkezésünkre áll egy, a meg gyelésekb®l álló tanuló halmaz: τK := {(y, dk ), dk {Accept, Reject}, k = 1, 2, . . . , K}
ahol y a meg gyelt aggregált forgalom vektor, di pedig ξ egy realizációja, esetünkben (szimuláció) a ϕopt (y) függvény értéke. A tanuló halmaz által meghatározott ϕ(y, τK ) nemparametrikus döntés K növelésével aszimptotikusan tart az optimális ϕopt (y) döntéshez ([2]): lim ϕ(y, τK ) = ϕopt (y) K→∞
6.2. Nemparametrikus döntés neurális hálózatokkal Az el®recsatolt neurális hálózatok aszimptotikusan jó Bayes-döntést valósítanank meg. Az azonosítani kívánt döntési függvény a következ®: ϕopt (y) = sgn(P (Y = y | ξ = Accept)P (ξ = Accept)− − P (Y = y | ξ = Reject)P (ξ = Reject))
Azt várjuk tehát a neurális hálózattól, hogy ezt a függvényt minél jobban közelítse: ϕopt (y) ≈ N et(y, wopt )
Az általam alkalmazott architektúra egy rejtett réteg¶, egy kimenet¶ hálózat: N et(y, w) = γ
N X
! wk yk
k
ahol γ(x) = 2
1 − 0.5 1 + e−αx
A végs® kimenet pedig sgn(N et(y, w))
formában áll el®. Ugyanis a szignum függvényt nem használhatjuk a neurális hálózat utolsó rétegénél, mivel a backpropagation tanítási algoritmusnál szükség van ennek a kimeneti, nemlineáris függvénynek a deriváltjára - a szignum függvény pedig nem dierenciálható a 0 pontban. Másrészr®l pedig a fent megadott sigmoid függvény deriváltja nagyban könnyíti a tanító algoritmus implementálását és csökkenti a tanítás futási idejét. 21
Tudjuk továbbá, hogy a neurális hálózatok által kifeszített függvénytér egyeneltesen s¶r¶ az Lp térben - ez teszi számunkra használhatóvá ezt az eszközt. Az el®recsatolt neurális hálózat w(K) opt : min w
K 1 X 2 ||dk − N et(yk , w)|| K k=1
optimális súly esetén aszimptotikusan optimális Bayes-döntést ad: lim N et(y, wopt ) = ϕopt (y) (K)
K→∞
További részletek a hatékony tanítás és minimális komplexitással kapcsolatban a [4] hivatkozásban található.
6.3. Teljesít®képesség analízis Több mérést végeztem különböz® paraméterekkel megválasztott neurális hálózatokkal. A közös ezekben a mérésekben, hogy egy rejtett réteggel és egy kimenettel rendelkez® architektúrával rendelkeznek valamint a rejtett réteg minden neuronja és a kimeneti neuron is sigmoid aktivációs függvénnyel rendelkezik. A valóságban a tanuló halmaz alapját azok a mérések képezik, amiket az egyes forgalmi kon gurációk meg gyelésekor számolunk. Ez esetben természetesen a korábbiak alapján készített döntési tartományok szolgálnak alapul, ezekb®l választjuk ki a tanuló halmaz elemeit. A valóságban több stratégiát is alkalmazhatunk a tanítóhalmaz el®állítására. Három megvalósítást készítettem, melyeket a következ®kben mutatok be és értékelem a hatékonyságukat.
22
60
Döntési tartományok a neurális hálózat alapján 60
50
50
50
40
40
40
30
A neurális hálózat hibás döntései: 1.96 %
y2
Nemparametrikus döntési tartományok és a tanulóhalmaz pontjai 60
y2
y2
1. A teljes döntési halmazon egyenletes eloszlás szerinti tanuló pont válogatás
30
30
20
20
20
10
10
10
0
0
10
20
30 y1
40
50
60
0
0
10
20
30 y1
40
50
60
0
0
10
20
30 y1
40
50
60
5. ábra. Bal oldalon: Nemparametrikus döntési tartományok és tanuló halmaz pontjai. Középen: döntési tartományok a neurális hálózat alapján. Jobb oldalon: A neurális hálózat hibás döntései: 1.96 % A tanuló halmaz alapján a hálózat els® és másodrend¶ hibát is vét, azonban csak kis valószín¶séggel sikerül jól tanítani a hálózatot. Ez a megoldás a megbízhatatlansága miatt nem tekithet® elfogadhatónak. Ezt mutatja a 5 ábra.
23
60
Döntési tartományok a neurális hálózat alapján 60
50
50
50
40
40
40
30
A neurális hálózat hibás döntései: 2.96 %
y2
Nemparametrikus döntési tartományok és a tanulóhalmaz pontjai 60
y2
y2
2. Az elfogadó tartományon egyenletes eloszlás szerint, a döntési határvonal mentén az elutasító halmazból normál eloszlás szerinti válogatás
30
30
20
20
20
10
10
10
0
0
10
20
30 y1
40
50
0
60
0
10
20
30 y1
40
50
0
60
0
10
20
30 y1
40
50
60
6. ábra. Bal oldalon: Nemparametrikus döntési tartományok és tanuló halmaz pontjai. Középen: döntési tartományok a neurális hálózat alapján. Jobb oldalon: a neurális hálózat hibás döntései: 2.96 % E szerinti tanuló halmaz felépítés közel áll a valósághoz - nagy érték¶ aggregált forgalmat kisebb valószín¶séggel fogunk mérni, mivel az azok által meghatározott kon guráció jelent®s csomagvesztést fog okozni. Ezt kiküszöbölend® pedig igyekszünk korlátozni a felhasználók számát. Ezt mutatja a 6 ábra.
60
Döntési tartományok a neurális hálózat alapján 60
50
50
50
40
40
40
30
A neurális hálózat hibás döntései: 2.58 %
y2
Nemparametrikus döntési tartományok és a tanulóhalmaz pontjai 60
y2
y2
3. A döntési határ mentén normál eloszlás szerinti tanuló pont válogatás
30
30
20
20
20
10
10
10
0
0
10
20
30 y1
40
50
60
0
0
10
20
30 y1
40
50
60
0
0
10
20
30 y1
40
50
60
7. ábra. Bal oldalon: Nemparametrikus döntési tartományok és tanuló halmaz pontjai. Középen: döntési tartományok a neurális hálózat alapján. Jobb oldalon: a neurális hálózat hibás döntései: 2.58 % Eddigi méréseim alapján ez a legmegfelel®bb választás a tanuló halmaz felépítésére. Ilyen mérések minden bizonnyal rendelkezésünkre állnának valós helyzetben is. A neurális hálózat viszonylag kis hibát vét és a tanítás nagy valószín¶séggel vezet használható súlyokhoz. Ezt mutatja a 7 ábra.
7. El®recsatolt neurális hálózat irányított tanulással Korábban az el®re csatolt neurális hálózatot úgy tanítottam, hogy az képes legyen a hívásengedélyezésre [1,2,4], feltéve hogy ismert az n forgalmi vektor és a hozzá tartozó meg gyelt aggregált forgalom y. Egy adott forgalmi vektor esetére tanítottam meg a hálózatnak a feladatot. A valóságban azonban a forgalmi vektor tört másodpercenként változik és bármilyen értéket felvehetnek elemei: ni ∈ N. Vagyis egy általánosabb választ adó architektúrára van szükség. Ez azt jelenti, hogy a tanuló halmaz elemei ezentúl nem az egy forgalmi vektorhoz tartozó aggregált forgalmi vektorokból és a döntésb®l áll, hanem magában foglalja a változó forgalmi vektort is. A tanuló halmaz elemeinek e 24
b®vítése dimenzióbeli kiterjesztést jelent, ami pedig a tanuló halmaz b®vítését teszi szükségessé. A neurális hálózat irányított tanulását kell megvalósítani úgy, hogy a releváns információt nem hordozó forgalmi vektorokat és azok aggregált forgalmát nem választjuk a tanuló halmaz elemei közé. Az irányított tanulással megválasztott tanuló halmaz elemek száma kisebb (az irreleváns pontok elanyagolása miatt), így gyorsítja a tanulási folyamatot és mivel releváns pontokat választ ki az eredeti feladatból, ezért kisebb tanulási hibához vezet. A hívásengedélyzés feladatát az összevont forgalmi és aggregált vektorok határozzák meg. Ez két forgalmi osztály esetén 2x2 ("forgalmi vektor" x "aggregált forgalmi vektor") azaz 4 dimenziót eredményez. Számos, a tanítás folyamán irreleváns pontot ki kell hagyni a tanuló halmazból. E pontokhoz azok a forgalmi vektorok tartoznak, melyek esetén bármely aggregált forgalmat meg gyelve elfogadó döntés az optimális: ϕopt (y) = Accept, ∀y egy n forgalmi vektorhoz tartozik
ahol
ϕopt
y
az optimális döntést hozó függvény meg gyelt aggregált forgalom egy n forgalmi vektor esetén
7.1. A tanuló halmaz A tanuló halmaz minden pontja a korábbiaknak megfelel®en három részb®l áll: egy n ∈ N2 forgalmi vektor, egy a forgalmi vektorhoz tartozó y ∈ N2 aggregált forgalom vektor és e két vektor alapján d ∈ {−1, 1} optimális döntés. A T tanuló halmaz formálisan a következ®: T = {(n, y, d)|n ∈ N2 , y ∈ N2 , d ∈ {−1, 1}}
n forgalmi vektort egy téglalap intervallumból egyenletes eloszlással választottam. Az intervallum fels® korlátja egy viszonylag kis érték.
Egy kisorsolt n vektor akkor fogadható el, ha az a korábban n vektorokra meghatározott alsó korlát fölött és fels® korláta alatt van valamint a tanuló halmazban még nem szerepel. Megfelel® találat esetén y vektorok kerülnek sorsolásra a binomiális eloszlásnak megfelel®en. A binomiális eloszlás valószín¶sége a két forgalmi osztálynak megfelel®en egyenl® az On/O modell valószín¶ségeivel. Egy y vektort akkor fogadunk el, ha az még nem szerepelt az adott n vektoron belüli tartományban. E két generált vektor és a hozzájuk tartozó optimális döntés egy triplettként kerül a tanuló halmazba tanuló pontként. Minden alkalommal mikor egy új n vektor esetén meg kell határozni egy y vektor döntését, egy id®igényes számítás fut le (a korábban taglalt indikátor mátrix kiszámítása). Ha ezen az n vektoron belül vagyunk kíváncsiak több y vektor döntésére, akkor ezek már nagyon gyorsan számolhatók. Mivel a tanuló halmazba sok pontra van szükség (ezres nagyságrend) ezért érdemes egy kisorsolt n vektorhoz több y vektort generálni, és meghatározni a döntést. Így gyorsan tudunk tanuló halmaz pontokat el®állítani. Ha viszont ezres nagyságrendben generálnánk különböz® n vektorokat, azok számítása nagy id®igény¶ lenne. Ezért választottam a korábban taglalt módszert. Meghatároztam, hogy hány különböz® forgalmi vektort (numN) és egy forgalmi vektoron belül hány különböz® aggregált forgalmi vektort (numY) sorsoljon a gép. A tanuló halmaz mérete így numN*numY elemb®l áll. Az alsó korlátot alkotó forgalmi vektorokra igaz, hogy esetükben csak a maximális aggregált forgalmi vektorok esetén elfogadó az optimális döntés. Ett®l kisebb n vektorok esetén bármely aggregált forgalom meg gyelése esetén (a legnagyobb esetén is!) mindig elfogadható az adott forgalmi kon guráció. Röviden ez azt jelenti, hogy kizárjuk a tanuló halmazból azokat a forgalmi vektorokat, amik minden esetben elfogadóak. A fels® korlátot alkotó forgalmi vektorokra igaz, hogy esetükben már a minimális aggregált forgalmi vektorok esetén is elutasítás az optimális döntés. Ett®l nagyobb n vektorok esetén bármely aggregált 25
Tanuló halaz korlátai és a tanuló halmaz n vektorai 120 Alsó korlát Felso korlát Tanuló halmaz
100
n2
80
60
40
20
0 0
20
40
60 n1
80
100
120
8. ábra. A határoló n vektorok és tanuló halmaz n vektorai. forgalom meg gyelése esetén (a legkisebb esetén is!) mindig elutasító az adott forgalmi kon guráció. Röviden ez azt jelenti, hogy kizárjuk a tanuló halmazból azokat a forgalmi vektorokat, amik minden esetben elutasítóak. A 8 ábrán kék körök jelzik a tanuló halmaz elemeinek n vektorait és piros csillagok az alsó és fels® korlátokat. Látható, hogy olyan n vektorok is bele kerültek a tanuló halmazba, melyek a határokon kívül vannak. Erre azért van szükség, mert a határoló n vektorok még nem hordozzák azt az információt, hogy az "alattuk" lév® forgalmi vektorok esetén minden aggregált forgalmi vektor elfogadó és "felettük" mind elutasító. A tanítás után így a hálózat arra is képes lesz, hogy a határ alatti n vektorok esetén is jó döntést hozzon. Érdemes azonban megvizsgálni a tanuló pontok eloszlását a hipotézisek tekintetében. A fent taglalt módszerrel megválasztott tanuló halmazba 5615 elutasító és 385 elfogadó tanuló pont került be. Ez befolyásolhatja a hálózat tanulásának sikerességét. Véleményem szerint a kiegyenlítetlen eloszlásnak is köszönhet®, hogy a viszonylag "kis" forgalmi vektorok esetén sok a hiba, ami a 10 ábrán is látható.
7.2. Az optimális hálózat megválasztása A hálózati architektúra és a tanuló halmaz megválasztásakor igyekeztem gyelembe venni az ököl szabályt, mely szerint a hálózat súlyainak ötszöröse a tanuló halmaz méretével kell, hogy megegyezzen. A 6000 elem¶ tanuló halmazhoz egy rejtett réteg¶ hálózat esetén 200 rejtett neuron szükséges. Mivel a rejtett réteg bemeneti 5 dimenziósak (biasszal együtt 6 dimenzió), a kimeneti réteg bemenetei pedig 180 (biasszal együtt 181 dimenzió), a súlyok száma: 6 · 180 + 181 · 1 = 1261 ≈ 1200 = 6000 5 (az egyenlet jobb oldala az ökölszabálynak megfelel®en). Mivel nem voltam teljesen meggy®z®dve arról, hogy ez a lehet® legjobb architektúra, igyekeztem meghatározni az optimális neuron számot keresztvalidációval (N-fold crossvalidation). A keresztvalidáció lényege, hogy a rendelkezésre álló adathalmazt N (például N=10) egyenl® számosságú részhalmazra osztjuk. Az egyes részhalmazokba a pontokat egyenletes eloszlással válogatjuk be a tanuló halmazból. Ezután kiválasztjuk az els® részhalmazt és a maradék N-1 (a példában 9) részhalmazt felhasználjuk a hálózat tanítására. A tanítás végeztével a kimaradt, els® részhalmazon meg 26
gyeljük a hálózat hibáját (MSE - Mean Square Error). Ezek után visszatesszük az els® részhalmazt és kivesszük a másodikat az adathalmazból. Felhasználjuk a maradék N-1-et (a példában 9-et) a tanításra és a másodikat a validálásra, MSE meghatározására, és így tovább. Ezt N (a példában 10) alkalommal végezzük el. Az N (a példában 10) validációs MSE értéknek kiszámoljuk az átlagát. Ez jól le fogja írni a hálózat képességét a feladat azonosításában. A hálózat rejtett neuronjainak számát változtatva ezt a keresztvalidációt megismételjük. Így kapunk egy validációs görbét a neuronok számának függvényében, aminek a minimuma ott lesz, amennyi rejtett réteggel a legjobban tudja azonosítani a hálózat a feladatot ezen a tanuló halmazon. Az validációs átlagolás mellett a Matlab tanító függvényének (train) kétszeri meghívásával igyekeztem pontosabb validációs eredményt elérni. A tanító algoritmus ugyanis leáll, ha a validációs hiba a tanítási ciklusok el®rehaladtával növekszik, ezzel megakadályozva a generalizáló képesség csökkenését. A tanítást újrakezdve azonban a validációs hiba mégis tovább csökken. Az eredményül kapott, a 9 ábrán látható görbe irregularitása megkérd®jelezi a módszer helyességét. Kiválasztottam néhány kirívóan rossznak mutatkozó méretet és újra elvégeztem a keresztvalidációt. Pár alkalommal a hálózat igen csak rossz eredményt mutatott, azonban az esetek többségében kiváló keresztvalidációs értéket kaptam. Nagy valószín¶séggel a hálózat inicializálásakor véletlenül választott kezdeti súlyok befolyásolták alkalmanként negatívan a taníthatóságot. A kezdeti elvárásokkal ellentétben tehát nem sikerült egy optimális architektúrát találni, ami különösen alkalmas lenne a feladat teljesítésére. Érdemes azonban számon tartani, hogy az iniciális, véletlen kezdeti súlyok nagyban befolyásolhatják a hálózat taníthatóságát. Ezek fényében megállapítható, hogy bármely kell®en kis hibával tanítható hálózat választható a feladat megoldására, ha az a megfelel® kezdeti értékekkel rendelkezik. Hiba a rejtett neuronok függvényében
Keresztvalidáció − abszolút hibák
140 120 100 80 60 40 20 0 0
20
40
60
80 100 120 Rejtett neuronok száma
140
160
180
200
9. ábra. Keresztvalidáció a (rejtett réteg) neuronok számának függvényében.
7.3. A tanuló algoritmus megválasztása Korábban a hálózat tanítására a Levenberg-Marquardt algoritmust használtam mivel gyors és kis hibával tanulja meg a feladatot. Az új feladat megoldására azonban már nem bizonyult hatékony módszernek, mivel nem követte a elfogadó és elutasító régiót határoló vonalat, "foltokban" jelentkeztek a hibák. A konjugált grádiens (Conjugate Gradient) alapú backpropagation algoritmusok jól teljesítettek, követték a 4 dimenzióban folyamatosan változó határoló felületet. Mind emellett gyorsabbak is a többi gradiens alapú algoritmusnál.
27
n=[10 20]
10 10 y1 n=[20 10]
0 0
20
20
5 0 0
10 y1 n=[20 30]
0 0
20
40
20 y1 n=[30 10]
0 0
40
20
5
20 y1 n=[30 20]
0 0
40
20 y1 n=[30 30]
40
0 0
0 0
40
40
20 y1
40
60
40
40 20
10 20 y1
20 y1 n=[30 40]
20
y2
20
20
40
y2
10 y2
30
10 y1 n=[20 40]
60
10
15
0 0
0 0
20
y2
10
10 y1 n=[20 20]
y2
30
y2
15
20
y2
0 0
20
y2
5
n=[10 40] 60 40
y2
20
n=[10 30] 40
y2
10 y2
30
y2
n=[10 10] 15
20 20 y1
40
0 0
20 y1
40
0 0
10. ábra. Hiba térképek 6000 tanuló pont és 200 rejtett neuront tartalmazó hálózat esetén. Zöld régió = Accept, piros régió = Reject, Kék régió = hibás döntések
7.4. A hálózat teljesít® képessége Számos architektúrát kipróbáltam különböz® tanuló halmazokkal. A 10 ábra jó példa az eredményre, 12 forgalmi vektor döntési térképét, hibáit mutatja. "Kis" n vektorok esetén a hálózat nem tud jól dönteni, még akkor sem, ha a határ alatti forgalmi vektorokat is tartalmaz a tanuló halmaz. A határt szigorúan gyelembe véve "kis" n vektorok esetén az ilyen jelleg¶ hiba sokkal jelent®sebb. Több határon aluli vektor talán megoldást jelentene erre a problémára - további vizsgálódás tárgyát képezi ennek a problémának a megoldása. "Nagy" n vektorok esetén a hálózat kiválóan teljesít, mint azt az ábra mutatja. A tanuló halmazt 6000 adatpont alkotja (200 n vektoron belül 30 y vektor) és a hálózat rejtett neuronjainak számát 200 neuronra az eredmény sokkal kielégít®bb a "kis" forgalmi vektorok esetén. Ez azonban a Polak-Ribiére Conjugate Gradient tanító algoritmus használata esetén már sok másodperces nagyságrend¶ tanítási id®t igényel. Az eredményt a 10 ábra mutatja. A generált döntési határok és a kirajzolt hibák azonban nem gy®ztek meg arról, hogy a hálózat valóban jó bináris osztályozó képességgel rendelkezik. A hiba számszer¶sítésének érdekében, a bináris osztályozó teljesítményének mérésére, az orvosi alkalmazásokban igen hasznos eszközt, a ROC (Receiver Operating Characteristic) görbét [13,14] használtam. Bináris osztályozás esetén, a százalékos hiba kiszámítása nem mindig ad megbízható mértéket az osztályozó teljesítményének mérésére. Pl. ha 100 pontból 99-et pozitívnak és 1-et negatívnak kellene klasszi kálni, és egy triviális osztályozót, a mindig pozitívan osztályozót választjuk, akkor 1%-os pontosságú osztályozót kapunk. Azonban lehet, hogy ez az egy negatív elem nagyon fontos információt hordoz, és a hiba ilyen esetben jelent®s. A korábbiakban taglalt osztály-eloszlások is félrevezet®k lehetnek. Ha ugyanis a teszt halmaz eloszlása különbözik a tanuló halmazétól, akkor egy egyszer¶ hibaszámítás félrevezet® lehet. Ekkor 28
érdemes gyelembe venni a következ® értékeket: TP (True Positive) helyesen pozitív osztályba klasszi kált elemek száma a halmaz pozitív
elemeire vetítve
TN (True Negative) helyesen negatív osztályba klasszi kált elemek száma a halmaz negatív
elemeire vetítve
FP (False Positive) helytelenül pozitív osztályba klasszi kált elemek száma a halmaz negatív
elemeire vetítve
FN (False Negative) helytelenül negatív osztályba klasszi kált elemek száma a halmaz pozitív
elemeire vetítve
A TP és FP értékeket felhasználva a bináris osztályozóra egy ROC (Receiver Operating Characteristic) görbét [8,9] határozhatunk meg. A görbe minden pontját úgy határozzuk meg, hogy a bináris osztályozót súlyozzuk a két bináris döntési érték között: [-1,1]. Vagyis a hálózat valós érték¶ kimentéhez hozzáadjuk a [-1,1] intervallum valamilyen felbontásban vett elemeit és ez után határozzuk meg az el®jelét. A ROC görbe alatti terület [13] számszer¶síti számunkra a döntés helyességét: 1 estén tökéletes osztályozót, 0.5 esetén a legrosszabb, véletlenszer¶ osztályozót kapunk. A terület meghatározza azt, hogy egy véletlenszer¶en kiválasztott elemet, az osztályozónk mennyi valószín¶séggel klasszi kál jobban, mint egy véletlen osztályozó. A 11 ábrán az általam tanított neurális hálózat ROC görbéjét és annak paramétereit tüntettem fel.
FFNN ROC görbéje
FFNN ROC görbéje
1
1
0.8 Area = 0.9997 SE = 0.0005
TP (Sensitivity)
TP (Sensitivity)
0.8
0.6
0.4
0.2
0 0
Area = 0.9986 SE = 0.0019 0.6
0.4
0.2
0.2
0.4 0.6 0.8 1−FP = TN (Specificity)
0 0
1
0.2
0.4 0.6 0.8 1−FP = TN (Specificity)
1
(a) ROC görbe a hálózat teljesítményének(b) ROC görbe a hálózat teljesítményének mérésére a tanító halmazon (6000 elem)mérésére a tanító halmaztól független, 0.0005 standard hibával. 2000 elem¶ halmazon 0.0019 standard hibával. 11. ábra. ROC görbék.
7.5. A korlátok alapján megválasztott tanuló halmaz összehasonlítása az teljes intervallumon megválasztott tanuló halmazzal Felmerülhet a kérdés, hogy a korábban kiszámított korlátokkal meghatározott tanuló halmaz hogyan befolyásolják a hálózat tanítását, teljesítményét a triviális, egyenletesen megválasztott tanuló halmazzal szemben. A továbbiakban a teljes tanuló halmazzal tanított hálózatot hasonlítom össze a korlátokkal megválasztott tanuló halmazzal tanított hálózattal. A két tanító halmaz a 12 ábrán látható. 29
Tanuló halaz korlátai és a tanuló halmaz n vektorai
A tanuló halmaz n vektorai
120
120
MAX MIN Tanuló halmaz pontjai
100
100
80
n2
n2
80
60
60
40
40
20
20
0 0
Alsó korlát Felso korlát Tanuló halmaz
20
40
60
80
100
0 0
120
n1
20
40
60 n1
80
100
120
(a) Az abszolút minimális és maximális(b) A határoló n vektorok és tanuló halmaz határok és a tanuló halmaz n vektorai. n vektorai. 12. ábra. A triviális és korlátokkal megválasztott tanuló halmaz. Mindkét hálózat 200 rejtett neuront tartalmaz. 5 halmazt használtam fel az tanító halmazok értékelésére: magát a 2 tanító halmazt, a két metódusnak megfelel® validációs halmazt és a korábban már használt 12 forgalmi vektor összes aggregált vektorából álló halmazt. A két tanító halmaz egyenként 6000 adatpontot (200 "forgalmi vektor" x 30 "aggregált vektor") számlál, még a validációs halmaz 2000 pontból (100 "forgalmi vektor" x 20 "aggregált vektor") áll. Két hálózatot tanítottam meg a feladat elvégzésére ezek a K (Korlátos halmazzal tanított) és T (Triviális, egyenletes eloszlású tanító halmazzal tanított). A tanítás eredménye nagyban befolyásolja az eredményeket, ezért mindkét hálózati típusból 10-10 hálózatot tanítottam meg a feladat elvégzésére. A 1 táblázatban szerepl® értékek ezen hálózatok átlag eredményei. A táblázatban szerepl® értékeket a hálózat típusának gyelembe vételével, párosával érdemes szemügyre venni.
Adat halmazok Alsó és fels® korlátos Triviális, egyenletes eloszlású Minták Halmaz mérete 6000(tanuló) 2000 6000(tanuló) 2000 6552 Hálózat K T K T K T K T K T # Accept 752 195 649 104 1123 # Reject 5248 1805 5351 1896 5429 FP 12 29 13 10 22 18 7 2 32 39 FN 26 32 13 15 34 25 3 9 232 216 Util. [%] 96.58 95.78 93.44 92.41 94.71 96.10 97.31 91.35 79.31 80.75 Breach [%] 0.23 0.55 0.71 0.54 0.41 0.33 0.35 0.08 0.59 0.71 ROC area 0.9983 0.9980 0.9945 0.9926 0.9965 0.9987 0.9994 0.9997 0.9601 0.9753 SE [x10−3 ] 0.8 1 3.4 4.0 1.3 0.9 1.5 1.3 3.7 3.0 1. táblázat. K - Korlátos halmazzal tanított hálózat, T - a triviális, egyenletes eloszlású halmazzal tanított hálózat. Utilization = TP rate, Breach of contract = FP rate. A hálózatok 200 rejtett neuront tartalmaznak és 6000(K)-6000(T) tanuló ponttal lettek tanítva. A táblázat tanúsága szerint a korlátos halmazzal tanított hálózat a tanító halmazoktól független, validációs halmazokon jobb kihasználtsági (utilization) rátával rendelkezik. A szerz®dés megsértésének (Breach of contract) rátája azonban enyhén magasabb ezen hálózatok esetében. Figyelembe véve azonban a ROC görbe alatti területet és az ebb®l számolt standard hibát, nem állítható határozottan, hogy a korlátos halmazzal tanított hálózat jobb lenne a triviális halmazzal tanítottól. A 10 ábrán látható, a hiba vizualizálására használt adatokból képzett, minta halmazon a triviális halmazzal tanított hálózat jobban teljesített. Ez minden bizonnyal annak köszönhet®, hogy a "kis" forgalmi vektorok esetén a korlátos halmazzal tanított hálózat nem viselkedik jól, túl sok False Negative hibát vét. E hibák miatt kisebb a True Positive döntések száma, ami azt jelenti, hogy a fogalmi vektorok, 30
amiket el kellene fogadni, a hálózat elutasítja. A(korlatos) A két tanuló halmaz felületének (a terület, ahonnan a pontokat kisorsoltam) arány: A(trivialis) = 0.3559. Ez egy újabb jelent®s érv a korláttal megválasztott halmaz mellett, ugyanis a dimenzió növeléséve (több forgalmi osztály bevezetésével) e hiper-térfogatok aránya jelent®s tanuló halmaz méretének csökkentését tesz lehet®vé. A korlátos halmazzal tanított hálózat tanuló halmazának méretét a korábbi arányszámnak megfelel®en 6000 ∗ 0.3559 = 2135-re választottam. A 6000-es korlátos tanuló halmaz részhalmazát választottam. 15 rejtett neuronnal rendelkez® rejtett réteg¶ architektúrát választottam. Az eredményt a 2 táblázat szemlélteti.
Adat halmazok Alsó és fels® korlátos Triviális, egyenletes eloszlású Halmaz mérete 6000(tanuló) 2000 6000(tanuló) 2000 Hálózat K T K T K T K T # Accept 752 195 649 104 # Reject 5248 1805 5351 1896 FP 33.4 29.1 22.8 12.4 42.0 26.8 8.3 4.2 FN 39.9 44.5 14.7 17.7 32.8 35.5 3.5 9.1 Util. [%] 94.69 94.08 92.46 90.92 94.95 94.53 96.63 91.25 Breach [%] 0.64 0.55 1.26 0.69 0.78 0.50 0.44 0.22 ROC area 0.9971 0.9984 0.9896 0.9957 0.9982 0.9987 0.9996 0.9993 SE [x10−3 ] 1.2408 1.0065 4.6188 3.2164 1.1398 0.9742 1.3046 1.7723
Minták 6552 K T 1123 5429 24.0 19.3 326.1 366.2 70.96 67.39 0.44 0.36 0.9440 0.9299 4.7692 4.9925
2. táblázat. K - Korlátos halmazzal tanított hálózat, T - a triviális, egyenletes eloszlású halmazzal tanított hálózat. Utilization = TP rate, Breach of contract = FP rate. A hálózatok 15 rejtett neuront tartalmaznak és 2135(K)-6000(T) tanuló ponttal lettek tanítva. Látható, hogy a K hálózat minden halmaz esetén jobban teljesít, vagyis jobb kihasználtsági tényez®vel (Utilization) rendelkezik. Levonható a következtetés tehát, hogy megfelel® hálózat esetén a korlátos tanuló halmaz jobb választás. Különösen akkor, ha egy nagyobb és több dimenziós forgalmi térben kell döntést hozni - egy valós alkalmazás esetén. Kisebb tanuló halmazzal ugyanis gyorsabb a hálózat tanítása.
8. Szimuláció NS2 (Network Simulator v2) hálózati szimulátor segítségével 8.1. Hálózati szimulátorok A hálózati szimulátorok nagyban megkönnyítik a fejleszt®k és a mérnökök feladatát azáltal, hogy a megalkott protokollokat gyorsan viszonylag jó modellekkel tudják tesztelni. Több hálózati szimulátor is létezik, melyeket új kommunikációs protokollok kidolgozásánál használnak: GloMoSim (Global Mobile Information Systems Simulation Library) - Csak wireless szimulá-
ciókat támogat, több ezer node szimulációját támogatja, rétegelt megközelítést alkalmaz, mely segítségével több réteg¶ szimulációt végezhet®, oktatási célokra igyen felhasználható
OPNET - Vezet® kereskedelmi termék, gra kus interfészen kerestül Windows és Linux alól
egyaránt használható, azonban zet®s termék
OMNET++ - Kiváló gra kus elemeket és egyéb fejleszt®i eszközökkel felvértezett, oktatási és
non-pro t tevékenység céljából felhasználható
NS2 - Nyílt forrású, szabadon terjeszthet® szoftver nagy felhasználói közösséggel, implementált
protokollok nagy választékával rendelkezik, kett®s implementációja (OTcl és C++) révén az implementációs lehet®ségek tágak. 31
Az NS2 hálózati szimulátor képességei megfeleltek az elvárásaimnak és mivel széles körben elterjedt valamint napjainkban az egyik legnépszer¶bb ilyen szoftver, ez a választás t¶nt a legjobbnak.
8.2. NS2 bemutatása Az NS (Network Simulator) hálózati kutatások céljára kifejlesztett diszkrétidej¶, eseményvezérelt szimulátor. Alapvet® eszközöket kínál TCP, útvonal választás (routing) és multicast protokollok teszteléséhez, fejlesztéséhez vezetékes és vezeték nélküli szimulációk segítségével. A vezeték nélküli szimulációval lehet®ség nyílik földfelszíni vagy szatellit kommunikáció megvalósítására. Az NS-t 1989-t®l kezd®d®en a REAL hálózati szimulátorból fejlesztették tovább, mely az elmúlt években jelent®s fejl®désen ment keresztül. A fejlesztések 1995-t®l a DARPA támogatásával zajlanak számos szervezet részvételén keresztül. A legf®bb fejlesztések a Californiai UC Berkeley-n folynak. A szoftver szabadon terjeszthet® és nyílt forráskódú (Open Source). Számos hozzájárulás taláható az interneten, melyek kib®vítik az NS2 képességeit, azonban ezek a fejlesztések rosszul dokumentáltak és ennél fogva körültekint®en kell használni. A készít®k sem vállalnak értük felel®séget ("Use without any warranty"). Jelenlegi válozata a 2-es verziószámot viseli, mely a szoftver nevében is benne foglaltatik: NS2. E verzió számos újítást foglal magában az els® változathoz képest. Le kell azonban szögezni, hogy az NS2 nem egy letisztázott, ki nomult termék, hanem jelenleg is folyó fejlesztések és kutatások terméke. A szoftver jelenleg is számos hibát (bugot) tartalmaz, melyek folyamatosan kerülnek napvilágra, melyeket miel®bb ki is javítanak. A felhasználók saját érdekükben hivatottak a mérési eredményeiket validálni és biztosítani, hogy nem tartalmaznak bugokat. A fejleszt®k jelenleg is dolgoznak azon, hogy automatizált validálási teszteken keresztül segítség a felhasználókat e hibák felfedésében. A felhasználók felel®sége annak biztosítása, hogy az általuk írt szimulációk ne tartalmazzanak bugoka és hogy az implementált szoftver az elvártnak megfelel®en m¶ködjön. Ezt a folyamatot hivatott támogatni az NS Manual kidolgozása. Az NS2 egy keretrendszer, mely a C++ és OTcl nyelv kett®s implementációja. Az OTcl a Tcl script nyelv objektum orientált változata. Futtattható Linux és Windows operációs rendszereken egyaránt. Windows esetén Cygwin segítségével valósítható meg a m¶ködtetése. 8.2.1. Az keretrendszer bemutatása
A keretrendszer megértése egy teljes érték¶ dokumentáció hiányában nagyban a forráskódok megismeréséb®l áll. Az ns-allinone-2.34\ns-2.34\tcl\lib\ns-lib.tcl forráskód tartalmazza a központi Tcl osztályt, a Simulator osztályt. NS2 hekkelése esetén ez a legjobb kiindulási osztály. Az NS2 a gyakorlatban nem más, mint egy kiterjesztett tudással rendelkez® Tcl interpreter. A 8.0 veriószámot visel® Tcl interpretert kiegészítették objektum-orientált képességekkel, így készült el az OTcl nyelv. A kapcsolatot az OTcl és a C++ között a tclcl OTcl függvénykönyvtár hivatott kezelni. Ez a könyvtár tehát interfészeket tartalmaz, melyek segítségével az adatok egy OTcl objektumból eljuttathatóak a neki megfelel® C++ objektumhoz. Az események kezelésének szempontjából fontos osztályok: Az Event osztály:
A scheduler.h osztályban de niált. A rendszeren belül küldött üzenetek ezen osztály egyedei. Minden Event osztályhoz létezik egy Handler osztály, ami a feldolgozáshoz szükséges metódusokat tartalmazza. Ezen osztály leszármazottai tartalmazzák a megfelel® réteg, protokoll vagy nyomkövetési funkciókat.
32
13. ábra. Az NS2 felépítése. A Packet osztály:
A packet.h fájlban de niált alap, csomagot leíró osztály. Ezen osztály tanulmányozása fontos új protokollok kidolgozásában.
A Handler osztály:
A scheduler.h osztályban de niált, az események kezelésének interfésze. Új esemény implementálása esetén ezen osztály leszármazottja írja le az elvégzend® feladatot.
8.3. A szimulátor alapjai Az NS2 egy esemény vezérelt szimulátor. Az ütemez® mindig a legkorábbi eseményt választja az ütemez® listából, és az általa el®írt feladat teljesítése után a következ® legkorábbi eseményhez tér vissza. A szimulációk egységideje a másodperc. NS2-ben adatok továbbítása nem történik, a csomagok küldése eseményekkel van modellezve. A nagyobb csomagok "kés®bb" érkeznek meg. A hálózati elemek csomagok továbbításával kommunikálnak, azonban ezek az események, vagyis a csomgatovábbítás, nem használnak szimulációs id®t. A csomagok tehát a szimulációs során 0 másodperc alatt továbbítódnak és inkább csak eseményeknek számítanak, mint valós adaforgalmonak. A csomagok ugyanis adatot (payload) nem tartalmaznak. Egy-egy szimuláció során minden egyes csomag gyelembe van véve. Bármilyen, a csomagon végzett m¶velet, amely szimulációs id® felhasználásával jár, az ütemez®be kerül és a megadott id® elteltével végrehajtódik. Az ütemez® ezen tulajdonság miatt id®zít®ként is használható. Egy szimuláció elemei: A Simulator osztály
A f® osztály, mely a szimulációs környezet kon gurálását végzi és a kés®bbiekben az egész szimuláció folyamatot felügyeli. Ennek az osztálynak csak egy egyede létezhet egy szimuláció során, csakúgy, mint a Scheduler osztálynak. Két f® komponens típust használ: szimulációs objektumokat és információ tároló objektumokat. A szimulációs objektumok (mint például a Scheduler) olyan kulcs fontosságú objektumok, melyek a Network Con guration Phase folyamán jönnek létre és a Simulation Phase folyamán használ a Simulator objektum. Ezzel szemben az információ tároló objektumok (pl. referenciák a létrehozott nodeokra) olyan adatokat tartalmaznak, amelyeket a különböz® objektumok között kell megosztani. Ilyen például a nodeok és a linkek referenciái, melyeket a szimulátor a routolási tábla elkészítésére használ fel. Ez az osztály hozza létre az objektumokat és eseményeket, valamint kezeli ezek ütemezését, meghatározza a használt protokollok fejléceit.
33
A Node-ok
A hálózat csomópontjai, melyek lehetnek végpontok vagy köztes csomópontok. Ágensek (Agent osztály egyedei) csatlakoztathatók hozzájuk, melyek nagyjából egy-egy protokollnak felelnek meg. Az összekötött szomszédos csomópontokat a linkek (Link osztály egyedei) kötik össze. Minden csomópontnak saját, egyedi azonosítója, címe van, ami alapján a nodeban lév® Addr Classifier dönti el, hogy a node entry_ pontjára érkezett csomagot továbbítja-e vagy a Port Classifier segítségével a megfelel® protokollnak adja-e át. Amennyiben a szóban forgó node egy multicast típusú node, a csomag további demultiplexálási folyamaton megy keresztül. A 14 szemlélteti ezt az osztályt.
14. ábra. Node, "ns-2 Tutorial (2), " Link-ek
Összekötik a csomópontokat simplex vagy duplex linkek segítségével (egy duplex link valójában két simplex linkkel van megvalósítva), többszörös hozzáférés¶ LAN vagy vezeték nélküli hálózatként. De niálható a sávszélességük, a csomagok késleltetése és sorbanállási rendszer is rendelhet® hozzájuk. Különböz® nyomkövetési objektumokat lehet de niálni, melyek nyílván tartják az érkezési, kiszolgálási, elvesztési és érkezési eseményeket. A linken áthaladó csomag két késleltetést®l is szenved: egyrészt a jelterjedési-, másrészt a csatornára bocsájtási késleltetést®l. Egy id®ben több csomag is jelen lehet a linken, hisz egymást a jelterjedési késleltetés miatt nem zavarják, azonban az küldeni egyszerre csak egy csomagot lehet a linkre. A 15 ábra mutatja egy link felépítését. A link kezeli a puerbe töltést (enqT_), a puerb®l kivételt (deqT_), csomag eldobást (drpT_), késleletést (ttl) stb.
Queue-ek
Részei a korábban taglalt Link objektumoknak. Tárolják és szükség esetén eldobják a csomagokat. Különbös® sorbanállási stratégiák vannak el®re implementálva a szimulátorban: Drop-tail (FIFO) - a sor túltelít®dése esetén az érkez® csomagokat eldobja a link. Random Early Detection (RED) - Véletlenszer¶en kiválasztott csomagok eldobásával igyekszik elejét venni a puer telít®désének. Ennek egy TCP kapcsolat esetén van igazán nagy jelent®sége. Class Based Queuing (CBQ, prioritás + Round Robin) Several Fair Queuing mechanisms (SFQ, DRR, ...)
34
15. ábra. Link, "ns-2 Tutorial (2), " Agent-ek
A logikai kapcsolatok végpontjai. Többé-kevésbé az ISO-OSI hierarchia harmadik (hálózati) és negyedik (transzport) rétegében de niált protokollokat valósítják meg, mint például a UDP, TCP, RTP stb. El®állítják és fogadják a csomagokat valamin kezelik a hozzájuk tartozó protokollokat. Esetenként kiegészíthet®k különleges fogadó és küld® feladatokat ellátó ágensekkel is, mint például a csomagokat elnyel® Null ágens (Agnet/Null) vagy a forgalom mérésére használt Agent/LossMonitor-ral.
A 16 ábra egy egyszer¶ forgalmi modellt demonstrál. A Node-ok kapcsolatával de niáljuk a hálózati topológiát. Ezen kapcsolatokkal tehát csak azt mondjuk meg, hogy melyik csomópont mely másik csomóponttal lesz kapcsolatban. Mivel azonban forgalmat is akarunk bonyolítani a csomópontok között, ezért egy Link objektum segítségével de niáljuk a csomópontok közötti "valós" kapcsolatokat. Egy link létrehozása esetén meghatározzuk a sávszélességét, a csomagkésleltetési idejét és a sorbanállási rendszer algoritmusát. Ezek után meg kell határozni az átviteli protokollt, melyek egymással kommunikáló ágensek fognak megvalósítani. Egy ágenst (az Agent osztály valamely leszármazottjának egyede) létrehozása után egy csomópontra kell illeszteni ($ns attach-agent $node0 $agent). Mivel eddig csak zikai és adatkapcsolati rétegen de niáltunk kapcsolatot két node között, szükséges az ágensek közötti hálózati kapcsolat rögzítése is ($ns connect $agent1 $agent2). Eddig a pontig tehát meghatároztunk egy adatforgalom lebonyolítására képes hálózatot. Annak érdekében, hogy adatforgalom induljon meg a hálózaton, valamilyen adatforrást (az alkalmazási rétegben) kell de niálnunk és azt hozzá kell rendelnünk a forrásként szolgáló csomóponthoz ($appl attach-agent $agent). Ez a prototípus hálózat ezek után képes lesz valamilyen alkalmazás által gerjesztett adatfogalmat továbbítani. Egy szimuláció elkészítésének általános sémája 1. Szimulátor elkészítése 2. Nyomkövetés aktiválása (tracing) 3. Hálózati csomópontok és topológia elkészítése 4. Linkek de niálása 5. Útvonal-választás aktiválása 35
16. ábra. Egyszer¶sített forgalmi modell. From: "2nd ISSNSM's Tutorial on Simulating Networks with Network Simulator 2 (ns-2), " 6. Hiba-modell kiválasztása, amennyiben szükséges 7. Forgalom de niálása 8. Alkalmazási adatok küldése Az eddigi ismeretek függvényében egy egyszer¶, két nodeból és az ®ket összeköt® linkb®l álló hálózaton mutatom be a szimulátorban lezajló csomagátviteli technikát. A hálózatot a 17 ábra mutatja. Adott tehát két node (csomópont) n0 és n1 valamint az ®ket összeköt® két simplex linkb®l Link n0−n1 és Link n1−n0 áll. A duplex linket tehát e két simplex link helyettesíti egy szimulációban. A csomagok routolása a nodeokban lév® Addr Classifier és Port Classifier végzi. Az n0 nodeon egy Agent/TCP bonyolítja le a forgalmat, még az n1 nodeon egy Agent/TCPSink nyeli el a TCP forgalmat. Az Application/FTP alkalmazási objektum FTP forgalmat szimulálva hoz létre adatot, melyeket az Agent/TCP ágensnek ad át. Az Agent/TCP becsomagolja az adatot és a dst_1.0 címmel kiküldi saját node-jának az entry_ pontjára. A cím els® (pont el®tti) része a cél (destination) címét jelöli, még a második a port, vagyis a szolgáltatás (protokoll) típusát. Az entry_ pontnál egy esemény váltódik ki, melynek hatására a csomaghoz tartozó handler objektum függvényei szerint a következ® történik. Az AddrClassifier alapján megvizsgálja, hogy a csomag fejlécében szerepl® cím szerint a melyik pointer alpján kell a csomagot tovább adni. Ez a folyamat gyakorlatilag egy cím demultiplexálás. Mivel a cím az 1-es, a demultiplexer a Link n0−n1-re továbbítja a csomagot, amely aztán az n1 node entry_ pontjára érkezik. Ekkor az n1 Addr Classifier megvizsgálja a csomag fejlécében lev® címet. Mivel ez az 1-es, ezért a csomagot a Port Classifier-nek adja át, amely szintén egy demultiplexerként m¶ködve az Agent/TCPSink-nek adja át a csomagot. Az Agent/TCPSink választ küld az n0 nodenak, a dst_=0.0 címmel. E csomag az n1-es node entry_ pontja után az Addr Classifier-re kerül, ahol a 0 cím miatt a Link n1−n0 linken keresztül eljut az n0 node entry_ pontjára, ahonnan a demultiplexálások után az Agnet/TCP kapja meg az adatot. A szimulációs adatok begy¶jtését két módon szokás végezni: 1. trace le segítségével - A teljes (vagy egy rész) szimulációs folyamatot, minden egyes átvitt csomag nyílvántartásával egy le-ba rögzítünk, amib®l kés®bb AWK vagy Perl script-tel elemezve kinyerjük a számunkra fontos adatokat. 36
17. ábra. PacketFlow, "ns-2 Tutorial (2), " 2. monitorozó objektumok segítségével Monitorozó objektumok - Ezen objektumok segítségével nyomon lehet követni a megérkezet és elveszett csomagok és byteok mennyiségét. Adatokat lehet gy¶jteni minden csomagról vagy egy teljes adatfolyamról ( ow monitor). Általában az Agent/Null ágenst szokták ilyen céllal használni, azonban UDP kapcsolat esetén az Agent/LossMonitor sokkal praktikusabbnak bizonyul. Ez az ágens lehet®vé teszi, hogy bizonyos egyedváltozóin keresztül meg tudjuk határozni az elveszett csomagok és byteok számát. Különösen hasznosak akkor, ha hosszas utófeldolgozás nélkül szeretnénk statisztikai adatokat gy¶jteni, megjeleníteni. Trace fájlok kiértékelése - Két alkalmazást is magában foglal az NS2 teljes fejleszt®i környezete. Ezek a NAM (Network AniMator) és az XGRAPH. A NAM bemutatása kés®bb következik. Az XGRAPH egy nagyon egyszer¶, gra konok készítésére és megjelenítésére alkalmas eszköz, melyet parancssorból a megfelel® argumentumok segítségével irányíthatunk. A trace leok és a gra konok adatait tartalmazó fájlok egyszer¶ struktúrájúak az egyszer¶ utó-feldolgozási munkák érdekében. Az értékek fehér karakterekkel vannak elválasztva.
Az adatok kiértékelése történhet a szimuláció alatt vagy a utó-feldolgozási eljárás segítségével. A szimuláció alatt csak nagyon fontos, kis mennyiség¶ adatot érdemes megjeleníteni. Ha csak lehetséges, a trace fájlokat érdemes kerülni, hiszen ezeknek nagy memória igénye és igen számításigényesek is. Az utófoldolgozás már egy jóval komplexebb folyamat. Az elkészült trace fájlok kiértékelése általában valamilyen script nyelven történik, mint például AWK vagy Perl. Megjelenítésükhöz pedig XGraphot és GNUPlotot szoktak alkalmazni. Trace fájlok - A trace fájlok nyílván tartanak minden egyes eseményt, ami a szimulátorban a csomagok kezelése során lezajlik. Ezeket az események struktúrált formában egy fájlba menthet®k és kés®bbi elemzésnek vethet®k alá. + − r r + − r
1.84375 1.84375 1.84471 1.84566 1.84566 1.84566 1.84609
0 0 2 2 0 0 0
2 2 1 0 2 2 2
cbr cbr cbr ack tcp tcp cbr
210 −−−−−−− 0 0.0 3.1 225 610 210 −−−−−−− 0 0.0 3.1 225 610 210 −−−−−−− 1 3.0 1.0 195 600 40 −−−−−−− 2 3.2 0.1 82 602 1000 −−−−−−− 2 0.1 3.2 102 611 1000 −−−−−−− 2 0.1 3.2 102 611 210 −−−−−−− 0 0.0 3.1 225 610
37
+ d − r + − +
1.84609 2 3 cbr 210 −−−−−−− 0 0.0 3.1 225 610 1.84609 2 3 cbr 210 −−−−−−− 0 0.0 3.1 225 610 1.8461 2 3 cbr 210 −−−−−−− 0 0.0 3.1 192 511 1.84612 3 2 cbr 210 −−−−−−− 1 3.0 1.0 196 603 1.84612 2 1 cbr 210 −−−−−−− 1 3.0 1.0 196 603 1.84612 2 1 cbr 210 −−−−−−− 1 3.0 1.0 196 603 1.84625 3 2 cbr 210 −−−−−−− 1 3.0 1.0 199 612
Ahol egy sor a következ® struktúrájú: <esemény>
< ag bitek> <sorszám> <egyedi csomagazonosító>
r: Receive d: Drop - csomag eldobás e: Error - hibás csomag +: Enqueue - csomag a puerbe került -: Dequeue - a csomag kikerült a puerb®l az esemény bekövetkezésének id®pontja forrás címe NS címzés szerint cél címe NS címzés szerint adot típusú forgalomból származó csomag csomag mérete byteban egyéb jelz® bitek adott folyamhoz tartozik a csomag forrás címe NS címzés szerint pontal elválasztva a porttól forrás portja NS portszámozás szerint cél címe NS címzés szerint pontal elválasztva a porttól cél portja NS portszámozás szerint a csomag sorszáma a szimuláció folyamán minden csomag egyedi azonosítót kap
8.4. Kett®s implementáció: OTcl és C++ objektumok kapcsolata OTcl Az OTcl script nyelv segítségével a hálózati topológia könnyen leírható és a a hálózati elemek, mint a node-ok, linkek, protokollok és alkalmazások könnyen kon gurálhatók. Jól leírja a szimulációs folyamatot, az adatforrások elindítását és leállítását, a veszteségeket a kommunikáció során, a szimuláció futási idejét és a különböz® események generálását. Könnyen lehet a paramétereket változtatni vagy újrakon gurálni a hálózatot. Gyorsan lehet vele több hálózati kon gurációt kipróbálni. A forrás kód egyszer¶, rövid és tömör, vagyis könnyen olvasható és értelmezhet®. A fejlesztési iterációs id® ezért sokkal rövidebb, mint C++ feljesztés esetén, mivel a modellt gyorsan, egyszer¶en lehet kon gurálni, és újrafuttatni. C++ A részletes, ki nomult protokoll implementáció alapvet® követelménye, hogy az rendszer programozási nyelven, gépi kódra fordítva tudjon futni. Ez a követelmény abból a tényb®l fakad, hogy az adatokat byte, illetve csomag szinten kell manipulálni. Ez nagy mennyiség¶ adat gyors feldologázást igényli, ami csak gépi kóddal tud hatékonyan futni. A hátránya ennek a hozzáállásnak, hogy a szoftver fejlesztésének körbefordulási ideje (turn around time) egy ilyen iteratív fejlesztésnél igen hosszú. Az kódot ugyanis le kell futtatni, megtalálni a benne rejl® hibákat, kijavítani azokat, újrafordítani és újra futtatni. Egy-egy csomag kezelésének módját C++-ban érdemes leírni, hiszen ez egy nagyon hatékony gépi kódot eredményez, mely ilyen nagy számú csomag esetén jó megoldás.
A 18 ábra kiválóan szemlélteti az NS2 keretrendszer kett®sségét, azt a hierarchikus rendszert, mely a feladatok komplexitásának függvényében alakult ki. Az ábra legfels® rétegében áll maga az implementálni kívánt hálózat, a tesztelni kívánt protokollokkal. A fejleszt® elképzelése szerint építi fel a hálózatot, mely csomópontokból, linkekb®l áll. Ezt a szimulációs közeget Tcl script nyelven írja le. Ez a leírás könnyen áttekinthet® és összevethet® a megvalósítani kívánt topológiával. A scriptben 38
meghatározhatjuk a szimuláció folyamatát, könnyen módosíthatjuk, és ágyazhatunk be új elemeket, amiket esetleg C++-ban implementáltunk, vagy módosíthatjuk a már meglév® osztályokat. Egy új protokoll kidologozása estén ez nagy valószín¶séggel be is következik.
18. ábra. OTcl és C++ kapcsolata [24] Ez a kett®sség azonban az megvalósított, vagy megvalósítandó osztályok esetén még több lehet®séget rejt. Az NS2 osztályok nagy többsége kett®s implementációval rendelkezik. Egyrészt egy OTcl másrészt egy C++-os megvalósítással. Egy OTcl-beli osztály tehát hozzá van kötve egy C++-beli osztályhoz, lásd a 19 ábrát.
19. ábra. OTcl és C++ kapcsolata [24] A két osztály együtt alkot egy alkalmazható eszközt. Jellemz®en azonban a C++-os implementáció tartalmazza az objektum valós, számításigényes részeit, még az OTcl osztály inkább csak interfész funkciót tölt be. A 20 ábrán látható, hogy az OTcl-beli Agent/TCP a C++-beli TcpAgent osztállyal van kapcsolatban. A kapcsolat úgy létesül, hogy az Agent/TCP konstruktor meghívja az super osztályának, az Agent-nek a konstruktorát, ami a TclObject objektumon keresztül létrehoza egy egyedét a C++-beli TcpAgent osztálynak. Ez az egyed a kés®bbiekben folyamán egy árnyék objektumként (shadow object) lesz nyílvántartva és hozzálinkelve az OTcl beli objektumhoz. A két nyelvbeni osztályneveket a TclClass C++ osztály leszármazott osztályában tudjuk meghatározni. 39
20. ábra. Az OTcl-beli Agent/TCP a C++-beli TcpAgent osztály kapcsolata [24] Az OTcl és C++ osztályok hierarchiája látható a 21 ábrán. Ha összevetjük 19 ábával meg gyelhetjük, hogy a hierarchiában szerepl® osztályok között kapcsolat van. Ez az összeköttetés is követi ezt a rétegzett felépítést. Az azért fontos, hogy egységes struktúrája legyen az osztályoknak és így könnyebben átlátható, továbbfejleszthet® legyen. Az NS lefordítás után, mikor étrehozunk egy OTcl objektumot, az nem több egy interfészszer¶ objektumnál, ez lesz az árnyék (shadow) objektum a valós, gépi kódot tartalmazó C++ objektumot fogja használni a feladatok végrehajtásához.
21. ábra. OTcl és C++ osztály hierarchiák [24] Az NS futtatása folyamán ha egy általunk implementált objektumnak meghívjuk egy parancsát, akkor az OTcl interpreter megnézni, hogy az osztály OTcl leírásában szerepel-e ehhez a parancshoz tartozó metódus (lásd a 22 ábrát). Amennyibe nem szerepel, a parancsot tovább adja az TclObject ostálynak, amely unknown() osztálymetódusának meghívásával átadja a parancsot a C++ osztály megfelel® objektumának (a példában TcpAgent). Amennyiben implementáltuk ennek a parancsnak a m¶ködését, akkor lefut az általunk megírt kód és egy kötött (binded) változón keresztül visszaadja a folyamat eredményét. Ha nem implementáltunk ilyen parancsot, akkor nekünk kell gondoskodni arról, hogy a parancsot tovább adjuk az általunk implementált osztály ®sének. Ha ott van ilyen parancs implementálva, akkor az lefut, ha nincs, akkor az is tovább adja az ®sének. Ez addig megy, még el nem jut a parancs a leggenerálisabb osztályig. Ekkor egy hiba (exception) váltódik ki és a program futása leáll. E hiba tehát futásid®ben jelentkezhet. 40
22. ábra. NS-b®l hívott parancs futtatása [24]
8.5. NAM (Network Animator) bemutatása A NAM egy Tcl/Tk alapú animációs eszköz, ami a szimulációs nyomkövetés (trace) és valós csomagok forgalmának követésére szolgál. Gra kus felhasználói felületén keresztül átrendezhet® a hálózat elrendezése. F® célja az NS funkcionalitásának b®vítése látványos animációk segítségével. Az NS szimuláció során generált trace le-t (namtrace) alapján "újrajátssza" számunkra a szimulációs. Lehet®ség van a csomópontok automatikus elhelyezéséne meghatározására (layout) vagy xen de niálni a különböz® node-ok pozícióját, színezni a különböz® forgalmi folyamokhoz tartozó csomagokat, gra kusan monitorozni a puerek (queue) állapotát. Szerkeszt®i képességi nagyon korlátoltak ennek az eszköznek, inkább csak megjelenítésre szolgál.
9. FANN (Fast Arti cial Neural Network Library) a nemparametrikus döntés implementálására Számos neurális hálózat implementáció létezik napjainkban, melyek szinte minden igényt kielégít® képességekkel rendelkeznek. Korábban a szimulációkat a Matlab Neural Network Toolboxával végeztem. A Matlab lehet®séget ad scriptjeinek C++ kódra való fordítására. Ez ebb®l fordított gépia kód azonban nem olyan optimális, mint egy natív C-s implementáció. Ezért tartottam fontosnak egy hatékonyabb, mégis sok kon gurációs opciót biztosító C++ vagy C függvénykönyvtárat keresni. A választásom az FANN-re (Fast Arti cial Neural Network Library) esett, mivel az igényeimnek megfelel® képességekkel, kiváló dokumentációval és nagy számú letöltéssel, vagyis nagy felhasználói közösséggel rendelkezik. A C++-kódba ágyazhatóság azért volt kritikus, mivel az NS2 protokolljainak implementációját is ebben a nyelvben érdemes elvégezni. Ezt a beágyazhatóságot a C-ben implementált FANN összeköt® kódon (binding) segítségével teszi lehet®vé.
9.1. FANN bemutatása A Fast Arti cial Neural Network Library egy nyílt forráskódú (open source) neurális hálózat függvénykönyvtár, mely C-ben írt több réteg¶, teljes vagy ritka összeköttetés¶ neurális hálózat implementációt tartalmaz. Cross-platform végrehajtása mind x és lebeg®pontos számításokkal támogatott. Az adathalmazok egyszer¶ kezelése érdekében magában foglal egy ehhez szükséges keretrendszert. Könnyen használható, sokoldalú, jól dokumentált és gyors. PHP, C++, .NET, Ada, Python, 41
Delphi, Octave, Ruby, Prolog Pure Data és Mathematica összekötési lehet®ségek (bindings) vannak. A referencia-kézikönyv taglalja a könyvtár felépítését és m¶ködését példákon és ajánlásokon keresztül. Egy gra kus felhasználói felület is kiegészíti a könyvtárat, az FannTool. A projekt weboldalán [27] olyan pozitív tulajdonságokat emeltek ki a fejleszt®k, mint a különböz® fajta backpropagation algoritmusok, az egyszer¶ hálózat konstruálhatóság, a gyors futtatás, az egyszer¶ és hatékony paraméterezhet®ség, jól dokumentáltság, cross-platform implementáció, egyszer¶ mentési és betöltési lehet®ségek, nyílt forráskód stb.
9.2. A függvénykönyvtár felépítése A föggvénykönyvtár viszonylag egyszer¶ struktúrájú, minden részfeladat szét van bontva a megfelel® forrásfájlba. Az FANN a következ® f® csomportokba sorolja [27] a feladatokat és ezáltal az implementált függvényeket: FANN Creation/Execution - az FANN/t úgy tervezték. hogy a neurális hálózatok mélyebb is-
meretével nem rendelkez® felhasználó is könnyen és egyszer¶en tudjon létrehozni ilyen hálózatot. A alap hálózatot létre lehet hozni egy függvény segítségével, egy másikkal pedig már meglév® hálózatot lehet betölteni. A fejlesztés során érdemes külön választani a hálózat létrehozását a hálózat futtatásától, mert rendszerint egyszer tanítjuk a hálózatot, viszont többször futtatjuk. Ide tartoznak még olyan függvények, melyek a réteg számának beállítását a súlyok inicializálását, a rétegek közötti kapcsolatok de niálását teszik lehelet®vé.
FANN Training - Rengeted tanítási metódus létezik neurális hálózatok tanítására ezek közül
néhányat támogat az FANN. Az egyes eljárások bizonyos feladatok esetén célravezet®bbek lehetnek, mint más metódusok. Két jelent®sen különböz® tanítási stratégia létezik: Fix topológiájú tanítás (Fixed topology training) - a neurális hálózati architektúra (topológia) el®re adott. A tanítás folyamán a súlyokat úgy változnak, hogy azok hálózat kimenetének a hibáját minimalizálják. Fejl®d® topológiájú tanítás (Evolving topology training ) - a tanítás egy üres neurális hálózattal kezd®dik, mely csak egy bemeneti és egy kimeneti neuront tartalmaz. A rejtett réteg neuronjait a tanítás folyamán növeli az algoritmus. Mindeközben természetes a hálózat súlyainak optimalizálása is történik. Az algoritmus egy olyan hálózatot eredményez, amelyik az inkrementális hálózatnövelés és tanítás folyamán a legoptimálisabb volt. Ez a tanítás a kaszkádolt tanítás (Cascade Training) opcióval valósítható meg.
Mindezek mellett ez a csoport tartalmazza az aktiváció függvények, tanítási algoritmusok, tanulási ráta és egyéb tanulási paraméter kiválasztásához szükséges függvényeket. FANN Cascade Training - a kaszkádolt tanítást, az el®z® pontban röviden bemutatott straté-
giához tartozó függvényeket foglalja magába ez a rész. A hálózat rejtett rétegeinek növelése vagy a rétegeken belüli neuronok számának növelése akkor jó stratégia, ha nem sejtésünk sincs, hogy milyen számú, vagy milyen felépítés¶ hálózatot kell alkalmaznunk.
FANN File Input/ Output - mint korábban arról már szó volt, egy neurális hálózatot el-
menthetünk egy szöveges (text) fájlba, kés®bb pedig be is tölthetjük azt a memóriába. Ezen funkciók mellett egy külön függvényt is implementáltak a fejleszt®k a xpontos architektúrák fájlba mentésére. 42
FANN Error Handling - a hibaüzeneteket általában a sztenderd hibakimentre irányítja az
FANN, azonban ezen üzentek fájlba is menthet®k és tovább elemezhet®k az itt lév® függvények segítségével.
FANN Datatypes - a FANN külön adattípusokat de niál a speci kus adatok kezelésére. Adott
egy C stuktúra (C++ alatt egy osztály) a neurális hálózat adatainak tárolására, egy másik a tanítási adatok elmentésére, egy harmadik a tanítási algoritmusok tárolására stb.
FANN Wrapper C++-hoz - két C++ osztállyal szolgálja a C-s implementációjú FANN C++-
ba való portolását. Az egyik osztály a korábban említett neurális hálózat és tanuló adathalmaz adatait és a hozzájuk tartozó függvényeket tartalmazza. Ez a wrapper külön osztályt biztosít a x-pontos, a lebeg®pontos, a dupla pontosságú lebeg® pontos implementációk számára. A saját szoftverünk implementációja során tudjuk meghatározni, hogy melyikre van szükségünk azzal, hogy a megfelel®höz tartozó fejléc fájlt includeoljuk a forráskódba.
9.3. Gra kus frontend a hálózat tanításához A fejleszt®k egy viszonylag egyszer¶, mégis minden felhasználói igényt kielégít® gra kus frontendet is készítettek az FANN-hez. Ennek segítségével a tanító- és teszthalmazok egyszer¶en betölthet®k, könnyen meg lehet határozni a rejtett rétegek számát, a rétegeben lév® neuronok számát, a tanító algoritmust, a tanítási stratégiát, az aktivációs függvényeket stb. Mindez azért különösen hasznos, mivel az architektúra megválasztásának nincs egy egységes, egzakt módja. Csakis a tapasztalat és az abból fakadó intuíció segíthet egy jó konstrukció felfedezésében. Ez a folyamat azonban egy igen hossza iteratív munka. A kiválasztott architektúrával le kell futtatni tanítási algoritmust. Egyegy futtatás után ki kell értékelni az eredményeket és ezek függvényében új paraméterekkel kell próbálkozni. Annak érdekében, hogy ez a munka hatékony és gyors legyen, egyszer¶ és gyors átparaméterezési lehet®ségre van szükség. Ez az amiben az FannTool [27] nagy segítségünkre lehet. A 23 ábra demonstrálja ezt az eszközt. A futás során a nyomon követhetjük a tanítás folyamatát egy gra kon vagy bejegyzés sor (log) segítségével. A FannTool nem csak a legalapvet®bb paraméterek beállítására ad lehet®séget, hanem egy igen precíz, a tanítási folyamat minden lehetséges módosítására kiterjed® parametrizálási lehet®séget ad. A 24 ábrán láthatók ezek az opciók. Megadhatjuk a tanítás leállásának különböz® kritériumait, a tanítási ráta értékét, a paraméterek inicializálását a tanítás kezdetén, az adathalmazok elemeinek véletlenszer¶ keverését és számos más dolgot írhatunk így el® a szoftvernek.
9.4. Tapasztalatok a nemparametrikus döntés megvalósítása során Különböz® tanuló- és validációs halmazokkal teszteltem a szóban forgó eszközt, és tapasztalataim szerint a tanító algoritmus sokkal hatékonyabban futott, mint a Matlabos implementációk. A MSE eredmények egy nagyságrenddel kisebbek voltak, mint a Matlabos szimulációban. Mindemellett egy tanítóhalmaz 100-szoros újrafelhasználása (epoch) a tanítás folyamán sokkal gyorsabb volt, mint Matlab esetében. Eben az esetben azonban több epochon keresztül kellett tanítani, még a hibafüggvény megállni látszott egy aszimptotikus határ mentén. Összességében azonban el lehet mondani, hogy a FANN egy határozottan jobb eredményt produkáló megoldás, mint a Matlab Neural Network Toolboxa. Természetesen ez csak a végs® alkalmazás esetén igaz. A Matlab megjelenítési képességei ugyanis sokat segíthetnek a tanított hálózat értékelésében.
43
23. ábra. A FannTool gra kus eszköz.
10. A hívásengedélyezés megvalósítása NS2 szimulációs környezet és FANN neurális hálózat segítségével A korábbi fejezetekben bemutattam, hogyan lehet hívásengedélyezést elvégezni parametrikus és nemparametrikus esetekben [1]. A nemparametrikus eset neurális hálózat segítségével valósítható meg. Az el®z® fejezetben bemutattam az FANN függvénykönyvtár képességeit, pontosabban azt, hogy képes a Matlabos szimulációkkal egyenérték¶ (min®ségileg jobb) eredményt produkálni. Egy korábbi fejezetben bemutattam az NS2 hálózati szimulátor kiváló képességeit és kib®víthet®ségét C++-ban. Ezekkel az eszközökkel már minden lehet®ség adott egy CAC szimuláció implementálására. Az általam elképzelt forgalmi szcenárióban (25 ábra) egy központi node végzi a CAC feladatot. E node egy másik nodeal van összekötve, ami további két nyel® (sink) node felé továbbítja a forgalmat. A két nyelp a két típusú forgalom elkülönítésére szolgál. Egyikben az els® osztály forgalma (piros csomagok) nyel®dik el, még a másikban a második osztályé (kék csomagok). A link a 0 és az 1-es node között az a bottleneck kapcsolati elem, ami miatt a csomagok továbbítás nem lehetséges nagy felhasználó szám esetén. A központi nodera csatlakoznak a felhasználók, akik mind ezen a linken keresztül küldik csomagjaikat. A csomagok mérete az ábrán a link sávszélességét®l, a késleltetési id®t®l és a csomag méretét®l függ. A szóban forgó hálózatban szerepl® osztályok paraméterei: 1-es osztály: csúcs sebesség h1 = 64kbps, átlagos sebesség m1 = 32kbps, ebb®l az On/O valószín¶ség p1 = 0.5, a felhasználók száma: n1 = 45, nyel®je a 2-es számú node. 2-es osztály: csúcs sebesség h2 = 128kbps, átlagos sebesség m2 = 96kbps, ebb®l az On/O valószín¶ség p2 = 0.75, a felhasználók száma: n2 = 20, nyel®je a 3-as számú node.
44
24. ábra. A FannTool gra kus eszköz nomhangolási beállításai.
Az aggregált forgalmat a 26 ábra mutatja. A szimulációt 4 másodpercig futtattam. A kezdeti felfutás után a hálózat kis ingadozással közel folytonosan aggregálja a 2.2Mbps környéki forgalmat.
11. Összefoglalás és konklúzió Az ATM hálózatok technológiai ismertetése után bemutattam az On/O forrás modellt, mely az egész munka alapját képezi. Ezen forrás modellb®l kiindulva megismertettem az olvasót egy széles körben alkalmazható forgalmi modellel, mely kiválóan leírja egy csomagkapcsolt hálózat m¶ködését. E paradigmára építve bemutattam ennek alkalmazhatóságát, leíró képességét és ugyanakkor a hátrányát, amely a paraméterek pontos meghatározásából és az integrálok nagy számításigényéb®l ered. A modellt kiterjesztve nemparametrikus esetre, ismertettem az el®recsatolt neurális hálózatok kiváló szeparáló képességét egy CAC feladat esetén. Mindkét esetben (parametrikus és nemparametrikus) elvégeztem az összes szükséges számítást, szimulációt, hogy veri káljam a modell hitelességét. A Call Admission Control feladatát nem-parametrikusan esetben vizsgáltam, mikor a forgalmi leírók értéke nem teljesen ismert, hanem egy valószín¶ségi változóval modellezhet®. Elkészítettem egy függvénykönyvtárat, mely segítségével modellezhet® egy hívás engedélyezési probléma megoldása. A könyvtár tartalmazza a statisztikai modellen alapuló függvényeket és a nem-parametrikus döntést megvalósító neurális hálózat alapú hívásengedélyezési algoritmusokat. A statisztikai modell az On/O forrás modellen alapuló Bayes-döntéshez köthet® eszközöket, még a neurális modell a 45
25. ábra. Példa egy forgalmi szcenárióra. Két osztályból származó forgalom csomagjainak továbbítását szemlélteti az ábra. Piros csomag: 1-es számú forgalmi osztály, kék csomag: 2-es számú forgalmi osztály
26. ábra. Példa egy forgalmi szcenárióra aggregált forgalmának mérésére LossMonitor segítségével. tanítóhalmaz generálásához és a szimuláció futtatásához tartozó eszközöket tartalmazza. Bemutattam két hatékony és hasznos eszközt, az NS2 hálózati szimulátort és a FANN neurális hálózat implementációt. A FANN kielégíti a CAC döntésekhez szükséges minden feltételt. Egy hatákony C implementáció, mely C++ kötésén (binding) keresztül beilleszthet® az NS2 szimulációs környezetbe. Az NS2 egy kiváló hálózati szimulátor, mellyel egy ilyen hívásengedélyezési szcenáriót fel lehet építeni. A két eszköz együtt tehát alkalmas a taglalt, neurális hálózatokon alapuló hívásengedé46
lyezés megvalósítására és demonstrálására. Valós alkalmazás esetén a neurális hálózat méretének megválasztását érdemes megfontolni. A hálózat megvalósítása ugyanis er®forrás függ®. A modell szimulációk során már három rejtett neuronnal is képes volt a hálózat jó eredményt elérni. Mivel azonban ennél a feladatnál nagyon fontos a kevés döntési hiba, ezért ett®l nagyobb réteget kell alkalmazni. Az el®z® fejezetben bemutatott 15 rejtett elem¶ hálózat a 2135 korlátos tanuló ponttal hasonló, esetenként jobb teljesítményt is elért, mint a 200 rejtett neuront tartalmazó, 6000 egyenletes eloszlású tanuló pontokkal tanított hálózat. Levonható a konklúzió tehát, hogy több forgalmi osztály és nagyobb kapacitású hálózat esetén nagy el®nyt élvez a korlátos tanuló halmaz, mivel a tanuló halmaz mérete csak töredéke lesz a triviális tanuló halmaznak. A hálózat tanításához szükséges számítás igényben tehát csökkenést eredményez ez a módszer. Mind emellett a kisebb tanuló halmazhoz kisebb hálózat társítható, ami a tanítást követ® alkalmazáskor sokkal kisebb számítási igény¶, gyorsabb döntést eredményez, így alkalmasabb a valós idej¶ felhasználásra. 6000 pont kiértékelése a 200 neuronnal rendelkez® hálózat esetén 182ms még 15 neuron esetén 26ms, ami 7-szeres sebesség különbséget jelent.
12. Felhasznált eszközök Hardware:
Hewlett Packard Compaq TC 4400 notebook Intel chipsettel, Intel Core2-Duo T7200 (2.0GHz, 4MB cache, 800MHz FSB) processzorral és 2 GB memóriával. F®ként Matlab 2007b szimulációk futtatására. A 6000 elemet számláló tanuló halmaz generálása 3-4 órát vett igénybe. Hewlett Packard EliteBook 2530p notebook Intel chipsettel, Intel Core2-Duo L9400 (1.86GHz, 6MB cache, 800MHz FSB) processzorral és 2 GB memóriával. F®ként NS2 és FANN szimulációk futtatására. Software:
Matlab 2007b, 2008a, 2009a, Home: http://www.mathworks.com/ NS - v2.34, Home: http://sourceforge.net/projects/nsnam/ les/ FANN - v2.1.0b, Home: http://leenissen.dk/fann/
47
13. Hivatkozások, felhasznált irodalom [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23]
J. Levendovszky, Cs. Vegso, E.C. van der Muelen, "Nonparametric decision algorithms for CAC in ATM networks," Elsevier, Performance Evalutaion 41 (2000), 133-147 J. Levendovszky, "Nonparametric estiamtions by neural networks," Internal Report, Department of Mathematics, Katholieke Univeriteit Leuven, Leuven, May 1996. L. Devroye, L. Gyor , G. Lugosi, "A Probabilistic Theory of Pattern Recognition," Springer, Berlin, 1996. J. Levendovszky, E.C. van der Muelen, "Nonparametric Bayesian estimation by feedforward neural networks," Proceedings of Prague Stochastics '98, Vol. 2, Prague, August 1998, pp. 347-350 M. de Prycker, "Asynchronous Transfer Mode Solution for Broadband ISDN," Ellis Harwood, Chichester, UK, 1991. J. Hui, "Resource allocation for broadband networks," IEEE J. Selected Areas Commun. 6 (9)(1998) 1598-1608. J. Hui, "Switching and Tra c Theory for Integrated Broadband Networks," Kluwer Academic Publisher, Dordrecht, 1990. R.J. Gibbens, F.P. Kelly, P.B. Key, "A decision theoretic approach to call admission control in ATM networks," IEEE J. Selected Areas Commun. 13(6) (1995). M. Yasuhiro, "A dimensioning scheme in ATM networks," Networks'92, May, 1992, pp. 171-176 Stoyan Gisbert, "Matlab (frissített kiadás)," Typotex 2005, ISBN-13 978-963-9664-82-1 Gy®r László, Gy®ri Sándor, Vajda István, "Információ és kódelmélet," Typotex 2002, ISBN 963 9132 84 5 R.J. Gibbens, F.P. Kelly, P.B. Key, "A decision theoretic approach to call admission control in ATM networks," IEEE J. Selected Areas Commun. 13(6) (1995). Hanley JA, McNeil BJ, "The meaning and use of the area under the Receiver Operating Characteristic (ROC) curve," Radiology 143 29-36 (1982). Metz CE, "Basic principles of ROC analysis," Semin Nuclear Med VIII(4) 283-298 (1978) Wikipedia, "Asynchronous Transfer Mode," Wikimedia Foundation, Inc., [Online document] 4 August 2009, Available at HTTP: http://en.wikipedia.org/wiki/Asynchronous_Transfer_Mode Wikipedia, "Connection Admission Control," Wikimedia Foundation, Inc., [Online document] 31 July 2009, Available at HTTP: http://en.wikipedia.org/wiki/Connection_Admission_Control Wikipedia, "Congestion control," Wikimedia Foundation, Inc., [Online document] 27 March 2009, Available at HTTP: http://en.wikipedia.org/wiki/Congestion_control Wikipedia, "Admission control," Wikimedia Foundation, Inc., [Online document] 14 December 2008, Available at HTTP: http://en.wikipedia.org/wiki/Admission_control Wikipedia, "Tra c contract," Wikimedia Foundation, Inc., [Online document] 24 February 2009 at 03:37, Available at HTTP: http://en.wikipedia.org/wiki/Tra c_contract Sexton M., Reid A., "Broadband Networking: ATM, SDH and SONET," Artech House Inc., Boston, London, 1997. ISBN 0-89006-578-0. Frank Eyermann, "2nd ISSNSM's Tutorial on Simulating Networks with Network Simulator 2 (ns-2), " ISSNSM - International Summer School on Network and Service Management, June 3, 2008 Ahmad Al Hanbali, "Introduction NS2 Simulator, " ATER Universite de Nice Sophia Antipolis, [Online document] January 18, 2007, Avaliable at HTTP: http://www.scribd.com/doc/6505211/Introduction-NS2-Simulator "The Network Simulator - ns-2," [Online document] Available at HTTP: http://www.isi.edu/nsnam/ns/
48
[24] [25] [26] [27]
Polly Huang, "Network Simulation and Testing, " EE NTU, [Online document] Available at HTTP: http://cc.ee.ntu.edu.tw/ phuang Teerawat Issariyakul, Ekram Hossain, "Introduction to Network Simulator NS2, " Springer Science+Business Media, LLC, ISBN: 978-0-387-71759-3, 2009 Jianping Wang, "ns-2 Tutorial (2), " Multimedia Networking Group, The Department of Computer Science, UVA, 2004 "Fast Arti cial Neural Network Library (FANN)," [Online document] Available at HTTP: http://leenissen.dk/fann/
49
