Forgalmi m´atrix becsl´ese Publik´aci´ok ´attekint´ese Bern´ath Attila 2009. j´ unius 24.
1.
´ Altal´ anos terminol´ ogia
ulni m´ert mennyis´egek Adott egy h´ al´ ozat, amiben a forgalmat akarjuk megbecs¨ alapj´ an. A h´ al´ ozat csom´ opontokb´ ol ´all, amiket egym´assal ´es a k¨ ulvil´aggal linkek k¨ otnek ¨ ossze (ezeket ir´ any´ıtottnak tekintj¨ uk). Vitathat´o, hogy mit tekint¨ unk egy csom´ opontnak: a PoP (Point of Presence) helysz´ıneken u ¨lnek a routerek obb is), amik egym´assal ´es m´as PoP helysz´ıneken lev˝o routerek(egy PoP-ban t¨ kel ¨ ossze vannak k¨ otve, teh´ at tekinthetn´enk csom´opontnak a routereket, vagy egy kev´esb´e r´eszletes vizsg´ alatn´al a PoP helysz´ıneket. Ezt k´es˝obb majd mindig megmondjuk, hogy az egyes cikkek mit tekintenek. Az alapprobl´ema teh´at, hogy szeretn´enk tudni, hogy bizonyos id˝ointervallum alatt egy adott csom´opontp´ ar k¨ oz¨ ott mennyi forgalom zajlott. Ezt m´atrix alakba ´ırva kapjuk a forgalmi m´ atrixot. Ezt k¨ ozvetlen¨ ul a´ltal´aban nagyon neh´ez ´es k¨olts´eges m´erni, viszont fontos lenne ismerni, ez´ert m´as mennyis´egeket m´er¨ unk ´es ezek alapj´an pr´ob´alulni. A forgalmi m´atrixot m´egse m´atrix alakba juk a forgalmi m´ atrixot becs¨ szokt´ ak ´ırni, hanem kiegyenes´ıtik egy vektorba (ami teh´at csom´opont-p´arokkal van indexelve): ennek jelent˝os´eg´et k´es˝obb l´atjuk majd. A forgalmi m´atrixot a tov´ abbiakban t-vel jel¨ ol¨ om, ami teh´at egy vektor: tp jel¨oli a forgalmat a p OD ´ p´ arra (n´eha az´ert ´ırunk olyat is, hogy tij ). Altal´ aban igaz, hogy j´o pontoss´aggal csak a statikus ´ allapotot tudjuk becs¨ ulni, a h´al´ozati hib´akat vagy topol´ogi´aban bek¨ ovetkez˝ o egy´eb v´ altoz´asokat k¨ovet˝o tranziens id˝oszakot nem, vagy csak pontatlanul. K¨ ul¨ onb¨ oztess¨ uk meg a h´al´ozatunkban azokat a csom´opontokat, amikb˝ol a k¨ ulvil´ ag fel´e (fel˝ ol) is van link: ezek a sz´els˝ o csom´ opontok (edge nodes) ´es az ilyen linkek a sz´els˝ o linkek (edge links), m´ıg a t¨obbi csom´opontot ´es linket bels˝ onek is fogjuk h´ıvni. Ha a csom´opontok routerek, akkor haszn´alatos az Edge Router (k¨ uls˝ o), illetve a Backbone Router elnevez´es (a bels˝okre). Tipikus esetben a vizsg´ alt h´ al´ ozatunkb´ ol kifel´e (ill. onnan befel´e) k´etf´ele link vezet: az egyik fajta a h´ al´ ozatunkhoz csatlakoz´o el˝ ofizet˝ ok (fogyaszt´ok, customer) fel´e/fel˝ol j¨on (access links), m´ıg a m´ asik fajta a h´al´ozatunkhoz kapcsol´od´o m´as auton´om h´al´ ozatok fel´e/fel˝ ol (peer links: ugyanabba a m´asik h´al´ozatba t¨obb link is vezethet uk azokat a linkeket, amik k´et bels˝o a mi h´ al´ ozatunkb´ ol). Core linknek nevezz¨
1
otnek ¨ ossze: core h´ al´ ozatnak a bels˝o csom´opontok ´es a core linkek csom´ opontot k¨ osszess´eg´et (azaz amit a bels˝o pontok fesz´ıtenek). ¨ Teh´ at a vizsg´ alt h´ al´ ozatunk nem gener´alja a forgalmat, csak tov´abb´ıtja a k¨ uls˝ o forr´ asb´ ol a k¨ uls˝ o c´el fel´e (ezt igaz´ab´ol mindig feltehetj¨ uk: ha egy bels˝o csom´ opont nem egy egyszer˝ u router ´es forgalmat is kezdem´enyez, akkor heuk egy sz´els˝ o csom´oponttal ´es egy r´ola lel´og´o fogyaszt´oval). Ezzel a lyettes´ıts¨ feltev´essel ´elve igaz´ ab´ ol csak k´et sz´els˝o csom´opont k¨oz¨ott van ´ertelme forgalomr´ ol besz´elni (a bels˝ o csom´opontok csak tranzit ´allom´asok), azaz a forgalmi m´ atrixot ilyen p´ arokra ´ertelmezz¨ uk. Enn´el m´eg r´eszletesebb adatot mutat egy olyan forgalmi m´ atrix, ami sz´els˝o link-p´arokra van ´ertelmezve: ebb˝ol az el˝obosszegz´essel kaphatjuk. M´as esetben k´ıv´ancsiak lehet¨ unk a core bit egyszer˝ u ¨ h´ al´ ozatunk forgalmi m´ atrix´ ara: ez az el˝obbiek b´armelyik´eb˝ol kisz´am´ıthat´o. H´ al´ ozati topol´ ogi´ anak nevezz¨ uk azt, hogy ´eppen aktu´alisan mely csom´opontok mely csom´ opontokkal vannak ¨osszek¨otve. Ezt ´altal´aban a routerek konfigur´ aci´ os f´ ajljaib´ ol lehet kiszedni. A routing protokoll mondja meg, hogy egy adott csom´ opontb´ ol egy m´ asik csom´opontba men˝o forgalmat mely u ´tvonalon (´ utvonalakon) kell elvezetni. Ennek le´ır´as´ara ´altal´aban a routing m´ atrixot haszn´aljuk: ennek sorai megfelelnek a h´al´ozat linkjeinek, oszlopai a csom´opont-p´aroknak (nevezik ˝ oket Source-Destination, azaz SD p´aroknak, n´eha meg Origin-Destination, azaz OD p´ aroknak). A m´ atrix egy eleme azt mondja meg, hogy az adott p´ar k¨ ozti forgalom h´ anyadr´esze megy ´at az adott linken (lehet 0 is, ha nem haszn´ alja). Ha minden OD p´ arra 1 u ´t van kijel¨olve, akkor a m´atrix elemei 0-k ´es uk meg, hogy ennek a m´atrixnak j´oval t¨obb oszlopa van, mint sora. 1-ek. Figyelj¨ Szok´ as a forgalmi m´ atrixot lenorm´alni, ´ıgy egy ig´eny-eloszl´ast kapunk, a statisztikai m´ odszerek ´ altal´ aban ezzel oper´alnak.
1.1.
H´ al´ ozat-tomogr´ afia (Network tomography)
A legk¨ onnyebben m´erhet˝ o ´es leg´altal´anosabban m´ert mennyis´eg a linkek terhel´ese. Ezt az u ´gynevezett Simple Network Management Protocol (SNMP) biztos´ıtja, ez szinte mindig rendelkez´esre ´all. Ezt minden linkre m´erve kapunk egy x vektort, ami teh´ at a linkekkel van indexelve. ´Igy az ismeretlen t traffic m´atrix (ami szint´en vektor, OD p´ arokkal indexelve) ´es x k¨oz¨ott az ¨osszef¨ ugg´est az x = At
(1)
m´ atrixegyenlet adja, ahol A a routing m´atrix. Mivel a linkek sz´ama j´oval kevesebb, mint az OD p´ arok sz´ama, ez egy er˝osen alulhat´arozott egyenlet, azaz rengeteg t kiel´eg´ıti (s˝ ot, azon t-k, amik kiel´eg´ıtik, egy eltolt alteret alkotnak), de ezek k¨ oz¨ ul csak egy ´ırja le val´oj´aban a forgalmat. A h´ al´ ozat-tomogr´ afiai m´odszerek ebb˝ ol az ¨ osszef¨ ugg´esb˝ ol (´es x m´er´es´eb˝ol) indulnak ki ´es pr´ob´alj´ak valamilyen szempont szerint a legjobb megold´as´at megtal´alni (1)-nek (az Idegen szavak ´es kifejez´esek sz´ ot´ ara szerint a tomogr´afia orvosi kifejez´es, r´etegfelv´etelt jelent). A h´ al´ ozati tomogr´ afia elnevez´est (tal´an) Vardi vezette be ([Var96]) 96-ban, aki statisztikai feltev´esek alapj´ an pr´ob´alta megkeresni (1) legjobb megold´as´at. Megk¨ ul¨ onb¨ oztet¨ unk statisztikus h´ al´ ozat-tomogr´ afiai m´odszereket, ahol a linkterhel´esi adatokra statisztikai feltev´eseket tesznek, ´es optimaliz´ al´ as-alap´ u h´ al´ ozat2
uk (1)-nek, ami valamitomogr´ afiai m´ odszereket, ahol olyan megold´as´at keress¨ lyen c´elf¨ uggv´enyt optimaliz´ al. A m´odszereket megk¨ ul¨onb¨oztethetj¨ uk aszerint is, hogy csak egy pillanatfelv´etelt haszn´alnak (azaz csak egy id˝ointervallumban m´ert link-terhel´esi/routing m´atrix stb. adatokat), avagy egy id˝osorra m´ert adatokat (azaz t¨ obb intervallumra a fentieket: ilyenkor olyan intervallumokat kell tekinteni, amikben a forgalmi m´atrix valamilyen szempontb´ol hasonl´o: p´eld´aul a d´elut´ ani cs´ ucsforgalom ´ or´ aj´aban a 12 darab 5 perces egym´ast k¨ovet˝o intervallumot).
1.2.
Gravit´ aci´ os modellek
A gravit´ aci´ os m´ odszerek sz´els˝o csom´opont-p´arokra (vagy esetleg sz´els˝o linkp´ arokra) hat´ arozz´ ak meg a forgalmi m´atrixot az u ´gynevezett gravit´aci´os modell alapj´ an, ami azt mondja, hogy ha i ´es j k´et sz´els˝o csom´opont, akkor a forgalom i-b˝ ol j-be ti,j = R · ti,∗ · t∗,j ahol ti,∗ azt jel¨ oli, hogy a h´al´ozatunkba mennyi forgalom j¨ott be ¨osszesen az i csom´ opontn´ al, m´ıg t∗,j hasonl´oan a j-n´el kil´ep˝o ¨osszforgalom (figyelj¨ uk meg, hogy ez ut´ obbiak k¨ ozvetlen¨ ul m´erhet˝ok a sz´els˝o linkek terhel´es´enek ¨osszegz´es´evel). R az u ´gynevezett frikci´ os faktor P (friction factor), ami ´ertelemszer˝ uen ugg´esb˝ol). Ezt a modellt egy norm´ al´ assal ad´ odik (p´eld´aul a ti,∗ = j ti,j ¨osszef¨ nevezz¨ uk a tov´ abbiakban egyszer˝ u gravit´ aci´ os modellnek. Egy ´altal´anosabb modellben az R f¨ ugghet i-t˝ ol ´es j-t˝ol is, de nyilv´an a pontos f¨ ugg´es meghat´aroz´asa ekvivalens a forgalmi m´ atrix meghat´aroz´as´aval. Fontos megjegyezni, hogy a gravit´aci´os modell ´altal adott megold´as nem felt´etlen¨ ul van ¨ osszhangban a link-terhel´esekkel (azaz az (1) nem felt´etlen¨ ul teljes¨ ul). Ez´ert ezek a m´ odszerek ´altal´aban csak m´as m´odszerekkel kombin´alva haszn´ alatosak: rendszerint a gravit´aci´os m´odszer szolg´altat egy kiindul´o megold´ ast, amit tov´ abbi m´ odszerekkel finom´ıtanak. Tov´abbi megfigyel´es, hogy a fenti egyszer˝ u gravit´ aci´ os modellben a tii komponensek se lesznek 0-k.
1.3.
Iterat´ıv Proporcion´ alis Fitting
Az Iterat´ıv Proporcion´ alis Fitting (IPF) t¨obb cikkben is szerepel, mint egy v´egs˝o ´ sim´ıt´ asi elj´ ar´ as. Altal´ aban arra szolg´al, hogy a kapott megold´as (forg. m´atrix) nemnegativit´ as´ at vissza´ all´ıtsuk. Ennek ´erdek´eben a negat´ıv komponenseket lenull´ azzuk, majd ezt a kiindul´o megold´ast jav´ıtjuk valamilyen iter´aci´oval addig, am´ıg az eredm´ennyel meg nem vagyunk el´egedve. A m´odszert [CDVWY00] ´ırja le r´eszletesen.
1.4.
Valid´ al´ as
Egy m´ odszer haszn´ alhat´ os´ ag´at valamilyen valid´al´asi elj´ar´as t´amaszthat al´a. Ehuks´eges (ide´ alis esetben), hogy rendelkez´esre ´alljon egy (de ink´abb t¨obb) hez sz¨ konzisztens forgalmi m´ atrix/routing m´atrix/link terhel´esi adat (azaz A, x ´es
3
unk t, amelyek teljes´ıtik (1)-et), illetve m´eg minden olyan adat, amit a m´odszer¨ haszn´ al. Ezek ut´ an A ´es x (ill. a t¨obbi adat) seg´ıts´eg´evel kisz´am´ıtjuk a becsl´es¨ unket t-re, ezt jel¨ olje tˆ, majd bizonyos m´er˝osz´amokkal jellemezz¨ uk a kett˝o elt´er´es´et egym´ ast´ ol (illetve ´ abr´azolhatjuk egy grafikonon a val´os t ´ert´ekek f¨ uggult ´ert´ekeket: itt arra sz´am´ıtunk, hogy a pontok a 45 fokos v´eny´eben a becs¨ egyenes k¨ ozel´eben helyezkednek el). K´etf´ele megk¨ ozel´ıt´es k´epzelhet˝o el arra, hogy honnan vegy¨ unk adatot a valid´ al´ ashoz: vagy m´er´essel kapjuk, vagy valamilyen szimul´aci´oval (szintetikus adat). A [ZRDG03]-ban olvashat´o egy ´erdekes megjegyz´es: a m´ern¨ok¨okkel val´o egyeztet´es sor´ an az der¨ ult ki, hogy az elv´ar´as nagy vonalakban az, hogy a m´atrix nagy elemeire (’nagy forgalmakra’) viszonylag kicsi relat´ıv hib´at szeretn´enek, m´ıg az ¨ osszes elemre nem t´ ul nagy abszol´ ut hib´at. Vajon ez t´enyleg ´ıgy van?
2.
Cikkle´ır´ asok
Az al´ abbiakban k¨ ovetkeznek a cikkle´ır´asok. Igyekeztem kronol´ogiai sorrendbe venni ˝ oket, de n´ehol nem tudtam meg´allap´ıtani a d´atumot (ezek persze nem tudom´ ayos publik´ aci´ ok, de hasznos olvasm´anynak tal´altam ˝oket): ezeket megpr´ ob´ altam bel˝ oni k¨ or¨ ulbel¨ ul.
2.1.
Vardi: Network tomography: estimating source-destination traffic intensities from link data, 1996 [Var96]
Ezt a cikket nem siker¨ ult megszereznem, de a m´odszer el´eg j´ol ¨ossze van foglalva [GJT04]-ben, ez´ert le´ırom. Sz´oval Vardi abb´ol indul ki, hogy tp ∼ Poisson(λp ) minden p OD-p´ arra, egym´ ast´ol f uggetlen ul, mivel ez a telefonh´al´ozatokn´al olyan j´ ol bej¨ ott. Kimutatja, hogy ekkor E{x} = Aλ
Cov{x} = A diag(λ)AT
ahol λ egy vektor. Nam´ armost vegy¨ unk n´eh´any m´er´est x-re, legyenek ezek x[1], . . . , x[K] ´es tekints¨ uk a tapasztalati momentumokat: x ˆ=
K 1 X ˆ= x[i] Σ K i=1
1 K
PK
i=1 (x[i]
−x ˆ)(x[i] − x ˆ)T
´es azt´ an megpr´ ob´ aljuk a m´er´est az elm´elettel ¨osszehozni, azaz megpr´ob´aljuk megoldani λ-ra a Aλ = x ˆ
ˆ A diag(λ)AT = Σ
egyenletrendszert. Vardi bebizony´ıtja, hogy λ statisztikailag meghat´arozott (statistically identifiable). Mindazon´altal a gyakorlatban ennek persze nem lesz 4
megold´ asa (m´ ar csak az´ert se, mert a forgalom nem biztos, hogy Poisson eloszl´ ast k¨ ovet), ez´ert valamilyen ´ertelemben kis hib´aj´ u megold´ast keres¨ unk. Vardi eredetileg azt javasolta, hogy a Kullback-Leibler t´avols´agot haszn´aljuk, de a [Csi91]-ban ´ırtak alapj´ an a legkisebb n´egyzetek m´odszere hely´enval´obb.
2.2.
Martin van den Nieuwelaar: The Traffic Matrix (A Traffic Measurement tool for the AUCS network) [vdN]
Ez nem annyira tudom´ anyos publik´aci´o, mint ink´abb egy esettanulm´any. Azt ´ırja le, hogy az AUCS Communications Services nev˝ u c´eg internet szolg´altat´assal foglalkoz´ o csoportj´ an´ al (amely egy eur´opai ´es tengerent´ uli internet tranzit h´ al´ ozatot u ¨zemeltet) hogyan val´os´ıtott´ak meg a forgalmi m´atrix m´er´est (igen, val´ oj´ aban m´er´est). Az´ert volt m´egis hasznos elolvasni, mert meg lehetett bel˝ole tudni sok fontos fogalmat ´es t´enyt, ´es j´ol r´avil´ag´ıtott a felmer¨ ul˝o probl´em´akra (nevezetesen: rengeteg adat keletkezik egy flow szint˝ u m´er´esn´el, az IP-c´ımek routerekhez rendel´ese n´eha v´altozik, a routerek interf´eszeit n´eha ki/be kapcsolj´ ak, amit˝ ol azok sz´ amoz´ asa megv´altozik stb). R¨oviden a The Traffic Matrix projektben azt csin´ alt´ ak, hogy a routerekb˝ol kinyerhet˝o statisztik´akat ¨osszegy˝ ujt¨ ott´ek a nagyobb POP csom´opontokban, ott aggreg´alt´ak ´es sz˝ urt´ek, majd ezt ozponti g´epre gy˝ ujt¨ott´ek ¨ossze tov´abbi feldolgoz´as ´es riportegy Amszterdami k¨ gener´ al´ as c´elj´ ab´ ol. Az irom´ any r´eszletesen le´ırja a tervez´esi d¨ont´eseket, kezdve azon, hogy milyen hardware-t v´alasztottak a k¨ ul¨onb¨oz˝o c´elokra, hogy milyen adatokat tartottak meg a statisztik´ab´ol ´es azt mennyire aggreg´alt´ak ´es sz˝ urt´ek sat¨ obbi. Amiket megtudtam ebb˝ol a le´ır´asb´ol ´es hasznosnak tartok a k¨ovetkez˝ ok. A Cisco routerek k´epesek u ´gynevezett Netflow statisztik´akat gener´alni, aminek r´eszletess´eg´et lehet szab´alyozni (a cikk ´ır´asakor m´eg nem mindegyik f´ele Cisco router tudta ezt). Ennek feldolgoz´as´ara egy Cflowd nev˝ u open-source (public domain) szoftvert lehet felhaszn´alni.
2.3.
Cao et al.: Time-varying network tomography: router link data, 2000, [CDVWY00]
Ezt a cikket se olvastam, csak [MTB+ 02] alapj´an kb meg´ertettem. Abb´ol a felt´etelez´esb˝ ol indul ki, hogy tp ∼ N (λp , φλbp ) minden p OD-p´ arra, megintcsak egym´ast´ol f uggetlen ul. Ez a modell teh´at azt is felteszi, hogy az ´ atlag ´es a sz´or´as ilyen speci´alis m´odon f¨ ugg egym´ast´ol. ulni a λp , φ ´es b ´ert´ekeket. Pr´ ob´ aljuk teh´ at a m´er´esek alapj´an megbecs¨ A [CDVWY00] szerz˝ oi a vizsg´alt adathalmaz elemz´es´evel arra jutnak, hogy a b = 2 j´ o v´ alaszt´ as lesz, m´ar csak a t¨obbit kell megbecs¨ ulni. Ehhez egy m´er´es sorozatot v´egz¨ unk ´es mindenf´ele bonyolult Expectation Maximization (EM) ulj¨ uk. m´ odszerrel ezeket megbecs¨
5
2.4.
Medina et al.: Traffic matrix estimation: Existing techniques and new directions, 2002 [MTB+ 02]
Ez a cikk is ¨ osszehasonl´ıt n´eh´any m´odszert, majd javasol egy u ´jat. 2.4.1.
Existing techniques
A vizsg´ alt m´ odszerek: 1. Az LP m´ odszer, ahol (1)-nek egy max s´ uly´ u megold´as´at keress¨ uk meg valamilyen okos s´ ulyoz´ assal. Err˝ol meg´allap´ıtja, hogy az [Gol]-ben javasolt s´ ulyoz´ asok mind gy´ aszosan teljes´ıtenek. 2. Bayes-i m´ odszer: A Bayes-i m´odszer a [TW98]-ban van le´ırva. 3. EM m´ odszer: Ez az, amit [CDVWY00]-ban van le´ırva (l´asd a 2.3 fejezetet). Ez a cikk szintetikus forgalmi m´atrixokkal teszteli a m´odszereket. N´egyf´ele szintetikus m´ atrixot gener´ al: konstans (minden OD p´arra az ig´eny 300Mbps), uniform (minden ig´eny egy v´eletlen sz´am, amelyek a [100,500] intervallumb´ol vett egyenletes eloszl´ assal lettek gener´alva, azaz tp ∼ U ([100, 500])), Poisson (tp ∼ P oisson(λp ) ahol λp ∼ U ([100, 500])), Gauss (tp ∼ N (µp , 40) ahol µp ∼ U ([100, 500])) ´es bimod´alis (azaz tp 0.8 val´osz´ın˝ us´eggel N (150, 20) ´es 0.2 val´ osz´ın˝ us´eggel N (400, 20)). Azon m´odszerekn´el, ahol egy prior m´atrixot kell megadni, ott a kiindul´ asi m´ atrixot (azaz a j´o megold´ast”) torz´ıtj´ak el egy nor” m´ alis eloszl´ as´ u hib´ aval, azt adj´ak be priornak. ´ Erdekes jelens´egeket vizsg´alnak. P´eld´aul n´ezik azt, hogy mennyire ´erz´ekeny a m´ odszer a statisztikai feltev´esre (azaz milyen becsl´est ad egy m´odszer, ami Poisson-feltev´esb˝ ol indul ki, ha norm´alis eloszl´as´ u forgalmi m´atrixszal tesztelj¨ uk), hogy mennyire ´erz´ekeny arra, hogy mennyire j´o prior m´atrixot kapott. Azt tal´ alj´ ak, hogy bizonyos OD p´arokat a m´odszerek permanensen rosszul becs¨ ulnek. Erre k´et lehets´eges feltev´est vizsg´alnak: igaz e, hogy azokat neh´ez becs¨ ulni, akik t´ avol vannak egym´ast´ol, vagy igaz e, hogy azokat neh´ez becs¨ ulni, akik k¨ oz¨ otti u ´tvonalon nagyon sokak ´altal haszn´alt link van. Vizsg´alj´ak azt, hogy mennyit seg´ıt, ha a forgalmi m´atrix n´eh´any sor´at meg tudom m´erni (azaz n´eh´ any routern´el flow szint˝ u m´er´est csin´alunk): u ´gy tal´alj´ak, hogy nem sokat. Szerintem az a probl´ema ezzel a megk¨ozel´ıt´essel, hogy azt v´arj´ak el, hogy a m´ odszerek teljesen tetsz˝ olegesen gener´alt forgalmi m´atrixokra egyform´an j´ol m˝ uk¨ odjenek, nem csak olyanokra, amik a val´os´agban el˝o is fordulnak. 2.4.2.
New directions
A javasolt u ´j m´ odszer a diszkr´et kiv´alaszt´asi modellek elm´elet´en alapul (Discrete Choice Models, DCM, l´ asd [BAL89]). Nagyj´ab´ol arr´ol sz´ol, hogy azt, hogy az i-edik csom´ opont mennyire szeret a j-edikkel kommunik´alni, azt megpr´ob´aljuk le´ırni n´eh´ any param´eterrel (pl hogy mennyire vonz´o a j-edik, azaz mennyit fogad ¨ osszesen, illetve hogy mennyit k¨ uld az i-edik ¨osszesen), majd beletesz¨ unk 6
ult m´eg egy kis v´eletlent is, sz´ am´ıtva azokra a param´eterekre, amiket nem siker¨ sz´ am´ıt´ asba venn¨ unk. A random utility modell pontosan megmondja nek¨ unk, hogy ezeket a param´etereket ´es ezt a v´eletlent milyen matematikai formul´akkal vegy¨ uk figyelembe: ezt most itt k´ar lenne r´eszletezni. A z´ar´ojeles megjegyz´esekb˝ ol l´ athatjuk, hogy a gravit´aci´os modell igaz´ab´ol ennek egy speci´alis esete.
2.5.
Zhang et al.: Fast Accurate Computation of LargeScale IP Traffic Matrices form Link Loads, 2003 [ZRDG03]
A cikk szerz˝ oi egy olyan m´odszert dolgoztak ki, ami egy gravit´aci´os modell uttes alkalmaz´as´ab´ol ´all. Ezt el is nevezt´ek to´es egy tomogr´ afiai modell egy¨ mogravit´ aci´ os m´ odszernek (tomogravity method). A m´odszert az al´abbiakban v´ azlatosan ismertetj¨ uk, majd egyes v´azlatpontokat r´eszletesebben kifejt¨ unk. A c´el egy BR-BR forgalmi m´ atrix meghat´aroz´asa (BR=Backbone Router). 1. Egy ´ altal´ anos´ıtott gravit´aci´os modell alapj´an kisz´am´ıtanak egy link-link forgalmi m´ atrixot (azaz sz´els˝o link-p´arokra). 2. Ezt ´ attranszform´ alj´ ak BR-BR forgalmi m´atrix-sz´a, ez lesz a tomogr´afiai m´ odszer kiindul´ o megold´asa, jel¨olj¨ uk tG -vel. 3. Valamilyen j´ ozan megfontol´asok alapj´an cs¨okkentik a feladat m´eret´et, megallap´ıtva, hogy mely BR-BR p´arokra volt nagy val´osz´ın˝ ´ us´eggel 0 a forgalom. Tov´ abbi egyszer˝ us´ıt´eseket is javasolnak, amik tov´abb cs¨okkentik a feladat m´eret´et. 4. (Kvadratikus programoz´as) A singular value decomposition (SVD) nev˝ u m´ odszerrel meghat´ arozz´ak az A m´atrix pszeud´oinverz´et, aminek seg´ıts´eg´evel megkeresnek egy olyan megold´as´at (1)-nek, ami valamilyen szempontb´ ol legk¨ ozelebb esik tG -hez. Sajnos ennek lehetnek negat´ıv komponensei. 5. IPF-el jav´ıtj´ ak ki a kapott megold´ast ´es ez az output. R¨ oviden teh´ at a m´ odszer l´enyege, hogy az alulhat´arozott h´al´ozati tomogr´afiai feladatnak u ´gy keresik meg egy viszonylag j´o megold´as´at, hogy a gravit´aci´os modellel keresnek egy kiindul´o megold´ast ´es azt´an ehhez k¨ozeli megengedett megold´ as´ at keresik meg (1)-nek. 2.5.1.
´ Altal´ anos´ıtott gravit´ aci´ os modell
´ Az Altal´ anos´ıtott gravit´ aci´ os modell abban k¨ ul¨onb¨ozik egy egyszer˝ u gravit´aci´os modellt˝ ol, hogy link-link p´ arokat megk¨ ul¨onb¨ozteti abb´ol a szempontb´ol, hogy milyen k¨ uls˝ o csom´ opontot k¨otnek ¨ossze a h´al´ozatunkkal. ´Igy k¨ ul¨onbs´eget tesz transit peer (peering linkt˝ ol peering linkig, azaz k´et k¨ uls˝o h´al´ozat k¨ozti), outbound (acces linkt˝ ol peering linkig, azaz fogyaszt´ot´ol k¨ uls˝o h´al´ozatig), inbound ul¨onb¨oz˝o gravit´aci´os (az el˝ oz˝ o ford´ıtottja) ´es internal forgalom k¨oz¨ott. Ezekre k¨ t¨ orv´enyek alapj´ an sz´ amolja ki a forgalmat.
7
uket ehelyett a kor´abban A szerz˝ ok a valid´ al´ as sor´an vizsg´alj´ak a m´odszer¨ ismertetett egyszer˝ u gravit´ aci´os modellel is ´es az der¨ ul ki, hogy az ´altal´anos´ıtott gravit´ aci´ os m´ odszer sokkal jobban teljes´ıt. 2.5.2.
Kvadratikus programoz´ as
A k¨ ovetkez˝ o kvadratikus programoz´asi feladatot ´ırjuk fel: min ||t − tG || ahol t minimaliz´alja ||At − x||-et. Itt ||.|| az euklideszi t´ avols´ agot jelenti. Nem eg´eszen ´ertem, mi´ert nem At = x a felt´etel: valami olyasmit mondanak, hogy lehet, hogy az At = x-nek nincs is megold´ asa, mert x-et hib´ aval m´ert¨ uk, a m´er´es ideje alatt megv´altozhatott a unk ´eszre, sat¨obbi. topol´ ogia, amit nem vett¨ Egy kicsit ´ altal´ anosabb esetben nem a ||t − tG || a c´elf¨ uggv´eny (azaz nem mer˝ olegesen vet´ıt¨ unk a {t : At = x}-re), hanem ||(t − tG )/w|| valamilyen w s´ ulyokkal (itt az oszt´ as term´eszetesen komponensenk´enti oszt´as). Ezt szint´en vizsg´ alj´ ak k´etf´ele s´ ulyoz´ assal: a s´ ulyok line´arisan f¨ uggnek a gravit´aci´os modell adta megold´ as komponenseit˝ol, vagy ezek n´egyzetgy¨ok´et˝ol f¨ uggnek. 2.5.3.
Valid´ al´ as
Ezut´ an a cikk szerz˝ oi tesztelik (valid´alj´ak) a m´odszer¨ uket a k¨ovetkez˝o metodol´ ogia alapj´ an: egy viszonylag nagy h´al´ozaton (p´ar ezer router, ha j´ol eml´ekszem) rendelkez´es¨ ukre ´ allt kb 500 ´or´anyi (´or´akra ¨osszegzett) val´os forgalmi adat (azaz 500 forgalmi m´ atrix): ez term´eszetesen mintav´etelez´essel keletkezett, nem osszes forgalom m´er´es´evel, ennek gy˝ ujt´ese a [FGL+ 00]-ban le´ırtak alapj´an az ¨ t¨ ort´ent. Ezut´ an az OSPF szimul´aci´oj´aval a topol´ogia ´es a routing protokoll ismeret´eben kisz´ am´ıtott´ ak minden ´or´ara az aktu´alis A m´atrixot, majd a (1) osszef¨ ugg´es alapj´ an az ezekkel konzisztens x vektort. ¨ Ezek ut´ an oldalakon kereszt¨ ul grafikonokkal bemutatj´ak, hogy a m´odszer¨ uk el´eg j´ o pontoss´ agot produk´ al. A konkl´ uzi´o, hogy a legjobban a legbonyolultabb fel´ all´ as teljes´ıt (azaz ´ altal´ anos´ıtott gravit´aci´os modell ´es n´egyzetgy¨ok¨os s´ ulyoz´as a kvadratikus programoz´ as c´elf¨ uggv´eny´eben).
2.6.
Gunnar et al.: Traffic Matrix Estimation on a Large IP Backbone - a Comparison on Real Data, 2004 [GJT04]
Ez a cikk nem annyira u ´j m´odszert akar bemutatni, mint ink´abb ¨osszeveti a fellelhet˝ o m´ odszerek teljes´ıtm´eny´et, amire az ad kit˝ un˝o alapot, hogy rendelkez´es´ere ´ all egy viszonylag nagy IP h´al´ozatra egy csom´o forgalmi m´atrix adat. Eg´eszen pontosan a k¨ ovetkez˝o ´all rendelkez´es´ere: a Global Crossing t´arsas´agnak az IP backbone h´ al´ ozata tud MPLS-t (MultiProtocol Label Switching, m´eg nem
8
ul forgalmi m´atrixot tudom pontosan, hogy ez micsoda), amivel lehet k¨ozvetlen¨ m´erni. Egyszer˝ us´ıt´esi c´elb´ ol a h´al´ozatot sz´etszedt´ek az eur´opai ´es az amerikai r´eszre, ´es PoP-PoP forgalmi m´atrixot m´ertek 5 perces id˝ointervallumokra egy teljes 24 ´ or´ an kereszt¨ ul. A routing m´atrixot itt is ink´abb a h´al´ozat szimul´al´ as´ aval hat´ arozt´ ak meg (ehhez egy MATE nev˝ u eszk¨ozt haszn´altak, ez esetleg nek¨ unk is hasznos lehet). Az egy v´arosban lev˝o PoP-okat ¨osszevont´ak 1 PoP-´a: ha ´ıgy esetleg el˝ ofordult, hogy 2 PoP k¨oz¨ott t¨obb u ´tvonal is haszn´alatos volt, akkor a legnagyobb forgalm´ uu ´tvonalat vett´ek alapul (de ez ritka volt). Ja, mellesleg itt a routing m´ atrix 0-1 ´ert´ek˝ u volt nekik. ´Igy kaptak az eur´opai h´al´ozatra 12 PoP-ot ´es 72 linket, m´ıg az amerikaira 25 PoP-ot ´es 284 linket. Az ¨ osszehasonl´ıtott m´ odszerek a k¨ovetkez˝ok voltak: 1. Gravit´ aci´ os modell: Tekintik az egyszer˝ u gravit´aci´os modellt (l´asd a 1.2 r´eszt), persze f˝ oleg mint kiindul´asi m´atrixot ad´o modellt. 2. Entr´ opia m´ odszer: a [ZRLD03]-ban tov´abbfejlesztett Kruithof-f´ele projekci´ os elj´ ar´ ast h´ıvj´ ak ´ıgy, a l´enyege: van egy kiindul´asi (prior) forgalmi m´ atrixunk t(p) ´es rendelkez´esre ´all A (routing m´atrix) ´es x (link terhel´es vektor) ´es oldjuk meg a k¨ovetkez˝o feladatot t-re:
min ||At − x||22 + σ −2 D(t||t(p) ) t≥0
ahol
ahol t(p) ´es t norm´ altak (ig´enyeloszl´asok) ´es D a Kullback-Leibler t´avololi. A σ −2 ∈ [0, 1] azt fejezi ki, hogy miben hisz¨ unk jobban: ha s´ agot jel¨ 0-hoz k¨ ozeli, akkor a m´er´esben, ha 1-hez k¨ozeli, akkor a prior m´atrixban. 3. Worst-case bounds (determinisztikus megk¨ ozel´ıt´es): Biztosan als´o korl´atot kapunk a forgalmi m´ atrix p-ik komponens´ere, ha megoldjuk a min tp ahol At = x, t ≥ 0 ´ Hasonl´ oan sz´ amolhatunk fels˝o korl´atokat is minden komponensre. Erdekes m´ odon az als´ o ´es a fels˝o korl´atok ´atlaga eg´esz j´o becsl´est ad, ami p´eld´aul haszn´ alhat´ o egy prior m´atrix el˝o´all´ıt´as´ara. Gond csak az, hogy sokat kell sz´ amolni. 4. Poisson-feltev´eses becsl´es: a Vardi-f´ele m´odszert vizsg´alj´ak ([Var96]), azzal a m´ odos´ıt´ assal, hogy a Kullback-Leibler t´avols´ag helyett a legkisebb n´egyzetek m´ odszer´et tekintik, azaz v´eg¨ ul is a k¨ovetkez˝o feladatot oldj´ak meg λ-ra:
ˆ 2 min ||Aλ − x ˆ||22 + σ −2 ||A diag(λ)AT = Σ|| 2 λ≥0
ahol 9
Itt is a σ −2 ∈ [0, 1] azt fejezi ki, hogy miben hisz¨ unk jobban: ha 0-hoz k¨ozeli, akkor az els˝ o momentumokban, ha 1-hez k¨ozeli, akkor er˝osen hisz¨ unk a Poisson feltev´esben. Megeml´ıtik, hogy ezt a m´odszert meg lehet csin´alni Poisson helyett valami generalized linear modelling felt´etelez´esb˝ol is kiindulni, mint az Cao et al. [CDVWY00]-ban van le´ırva. Mellesleg k¨ ul¨on vizsg´alja, hogy a k¨ozepek ´es a kovarianci´ ak hogy viszonyulnak egym´ashoz, mivel a Cao et al. [CDVWY00] cikkben egy speci´alis kapcsolat van f¨olt´eve: ezt viszonylag hely´enval´ onak tal´ alj´ ak. 5. Regulariz´ alt ´es Bayes-i m´ odszerek: A Bayes-i m´odszer a [TW98]-ban van le´ırva. 6. Fanout-becsl´es: Ezt a m´odszert tal´an m´egis ez a cikk vezeti be. Azon alapul, hogy m´ıg a forgalom adott pontp´ar k¨oz¨ott ingadozik, addig a fanout viszonylag ´ alland´ o: ezt az adatok is al´at´amasztani l´atszanak. Az αi,j fanout annak a val´ osz´ın˝ us´ege, hogy egy tetsz˝oleges csomag, ami az i-edik csom´ opontn´ al l´ep be a h´al´ozatba, a j-edikn´el fog t´avozni. Azaz αi,j = ti,j / · ti,∗ . Az el˝ obbi feltev´es teh´ at nagyj´ab´ol azt jelenti, ha j´ol ´ertem, hogy m´ıg az v´ altozik, hogy egy adott PoP helysz´ınhez k¨ot¨ott felhaszn´al´ok h´any megab´ ajtot t¨ oltenek le (vagy fel?) a www.cs.elte.hu oldalair´ol, addig ennek osszlet¨ olt´eshez k´epest viszonylag ´alland´o. ar´ anya az ¨ A fanout-ra fel´ırva a (1)-et m´eg mindig egy ugyanolyan alulhat´arozott egyenletrendszert kapunk, azonban ha egy id˝osort vesz¨ unk, ahol a fanoutot ´ alland´ onak tekintj¨ uk, akkor el´erhetj¨ uk, hogy j´ol- (s˝ot, t´ ul-) hat´arozott legyen a rendszer¨ unk: AT [i]α = x[i] i = 1 . . . K X αnm = 1 n = 1, . . . N m
α ≥ 0, αii = 0 (K az id˝ osor hossza, T [i] pedig a diagon´alis sk´al´az´asi m´atrix, ami a fanoutot forgalomm´ a sk´ al´ azza: vegy¨ uk ´eszre, hogy ez m´erhet˝o). Azaz azt tett¨ uk fel itt, hogy az α[i] ugyanaz minden i-re. Persze itt is valamilyen hibaminimaliz´ al´ os m´ odszert kell tekinteni, teh´at a feladat a k¨ovetkez˝o lesz: PK 2 min i=1 ||AT [i]α − x[i]||2 P ahol n = 1, . . . N m αnm = 1 4-t´ ol kezd˝ od˝ o m´ odszereket nevezi statisztikus m´odszereknek, amit nem teljesen ´ertek (mit˝ ol lesz p´eld´ aul a fanout-becsl´es statisztikai). osszehasonl´ıt´asa oldalakon kereszt¨ ul van r´eszletezve grafikonokA m´ odszerek ¨ kal ´es t´ abl´ azatokkal. Mi csak a v´egs˝o konkl´ uzi´oban szerepl˝o t´abl´azatot k¨oz¨olj¨ uk 10
itt: az ´ert´ekek az MRE ´ert´ek´et mutatj´ak, ami egy m´er˝osz´am a relat´ıv hiba m´er´es´ere. Europe America Worst-case bound prior 0.10 0.39 Simple gravity prior 0.26 0.78 Entropy w. gravity prior 0.11 0.22 Bayes w. gravity prior 0.08 0.25 Bayes w. WCB prior 0.07 0.23 Fanout 0.22 0.40 Vardi 0.47 0.98
2.7.
Steve Uhlig et al.: Providing public intradomain traffic matrices to the research community [UQLB06]
A szerz˝ ok Netflow m´er´esek alapj´an jelent˝os mennyis´eg˝ u forgalmi m´atrix adatot ´ tesznek k¨ ozz´e: ennek a k´ıs´er˝oje ez az ´ır´as. Az adatokat a GEANT h´al´ozatban m´ert´ek, ami 23 routerb˝ ol, 38 bels˝o linkb˝ol ´es tov´abbi 53 sz´els˝o linkb˝ol ´all. A routerek mindgyike sz´els˝ o. A BGP (Border Gateway Protocol) u ´tvonalakat egy dedik´ alt munka´ allom´ as gy˝ ujt¨otte, amin GNU Zebra nev˝ u szoftver futott. A Netflow trace-eket a k¨ ovetkez˝ok´eppen gy˝ ujt¨ott´ek: minden ezredik csomagnak ´ırt´ ak fel a statisztik´ aj´ at, majd fel¨osszegezt´ek a byte-ok sz´am´at minden (forr´as prefix, c´el prefix) p´ arra (el˝ osz¨or 5 perces intervallumokra). Azt´an mindezt a BGP routing adatokkal egy¨ utt beadt´ak egy TOTEM toolbox nev˝ u programnak (ami szint´en ny´ılt forr´ as´ u) ami tudja a BGP-t szimul´alni, ´es ezzel kisz´amoltak egy csom´ o forgalmi m´ atrixot, 15 perces id˝ointervallumokra, 4 h´onapon ´at (1 h´et sz¨ unettel a k¨ ozep´en). Az adatokat a v´eg´en persze anonimiz´alt´ak, ´es ´ıgy f´erhet˝o hozz´ a publikusan a http://totem.info.ucl.ac.be/dataset.html c´ımr˝ ol. Megtudhatjuk azt is ebb˝ ol az ´ır´asb´ol, hogy hol van m´eg ilyen m´ert adat egy m´ asik, az ABILENE h´ al´ ozatr´ol (http://www.cs.utexas.edu/~yzhang/research/AbileneTM).
2.8.
Ahmed Mansy and Constantin Dovrolis: The mythical traffic matrix [MD]
Ez egy szkeptikus hangv´etel˝ u r¨ovid ´ır´as (nem tudom´anyos publik´aci´o) arr´ol, hogy a forgalmi m´ atrix olyannyira v´altoz´ekony ´es statisztikailag is kisz´am´ıthatatlan, hogy m´eg megbecs¨ ulni se lehet j´ol, nemhogy el˝orejelezni, ez´ert a traffic engineering sz´ am´ ara nem igaz´an hasznos fogalom. Az´ert eml´ıtem m´egis, mert szerepel benne, hogy l´etezik 2 nyilv´anosan el´erhet˝o forgalmi m´atrix adathalmaz az Abilene ´es Geant h´ al´ ozathoz. M´asr´eszt felh´ıvja a figyelmet ez az ´ır´as arra a jelens´egre, hogy id˝ onk´ent egyes tartalomszolg´altat´ok nagyon n´epszer˝ uv´e v´alnak, ami ´ altal´ aban nem jelezhet˝ o el˝ore, de mindenk´eppen sz´amolni kell vele (reag´alni kell r´ a). M´ asr´eszt a szerz˝ ok azt javasolj´ak, hogy a forgalmi m´atrix el˝orejelz´es´en alapul´ o traffic engineering helyett m´er´es alap´ u dinamikus routol´ast kellene 11
haszn´ alni. Azt ´ıg´erik, hogy ezt fogj´ak kutatni a j¨ov˝oben: sajnos nem tal´altam m´ as publik´ aci´ ot t˝ ol¨ uk.
2.9.
Zhao et al: Robust traffic matrix estimation with imperfect information: making use of multiple data sources [ZGWX06]
Ez a cikk arra pr´ ob´ al v´ alaszt adni, hogy a m´er´esi pontatlans´agokat (netflow m´er´es hib´ ai, SNMP leolvas´ as hib´ai) hogyan vegy¨ uk figyelembe a forgalmi m´atrix becsl´esn´el. Ha minden ingress pontn´al netflow-t m´er¨ unk, akkor nagyj´ab´ol ismerj¨ uk a forgalmi m´ atrixot: az´ert csak nagyj´ab´ol, mert nyilv´an a netflow-t csak uk. Hogyan vegy¨ uk figyelembe azt, hogy ez csak mintav´emintav´etelez´essel m´erj¨ telez´essel kapott adat? Hasonl´oan az SNMP leolvas´asokban is hib´ak lehetnek, p´eld´ aul mert a sok router a sok interf´esz´en nem k´epes pontosan ugyanazt az id˝ointervallumot leolvasni. Ezeket a hib´akat (amelyek teh´at a netflow mintav´etelez´esi elj´ ar´ as´ ab´ ol illetve az SNMP leolvas´asok pontatlans´ag´ab´ol ad´odnak) zaj”” nak h´ıvj´ ak, megk¨ ul¨ onb¨ oztetend˝o az egy´eb hib´akt´ol (amik pl szoftver-, hardvervagy kommunik´ aci´ os- okokb´ ol egyes m´ert ´ert´ekeket elrontanak). Az ilyen pisz” kos adat” kisz˝ ur´es´ere is ad valamilyen m´odszert, de ezt nem r´eszletezem itt. A zaj kezel´es´ere azt javasolj´ak, hogy azt egy norm´al eloszl´as´ u hibak´ent vegy¨ uk figyelembe, aminek a sz´or´asn´egyzet´ere bonyolult k´epleteket ´ırnak. Azt is javasolj´ ak, hogy a netflow csomag szint˝ u mintav´etelez´es´et ´erdemes fel¨ ulvizsg´alni urt csomagokat az u ´gynevezett smart sampling”-el (teh´at a netflow ´altal kisz˝ ” m´eg megrost´ alni), amit˝ ol a k´epletek m´eg jobban elbonyol´odnak. Vannak m´eg tov´ abbi technikai r´eszletek arr´ol is, hogy hogyan gyors´ıtsuk fel a sz´am´ıt´ast. Az ´erdekesebb r´esz tal´ an az, hogy arra is adnak javaslatot, hogy hogyan vegy¨ uk figyelembe azt, ha csak n´eh´any ingress pontn´al van netflow m´er´es¨ unk. Azt javasolj´ ak, hogy azokon a helyeken, amiken ez nem ´all rendelkez´esre, ott haszn´ aljuk az ´ altal´ anos´ıtott gravit´aci´os modellt (l´asd a 2.5.1 alfejezetet), csak a zajhib´ at figyelembe vev˝ o norm´alis eloszl´as´ u val´osz´ın˝ us´egi v´altoz´o sz´or´asn´egyzet´et n¨ ovelj¨ uk λ-szoros´ ara az ilyen poz´ıci´okon. A k´ıs´erleti eredm´enyeik alapj´an a λ eg´eszen b˝ o intervallumb´ ol v´alaszthat´o.
Hivatkoz´ asok [BAL89]
Moshe E. BEN-AKIVA and Steven R. LERMAN, Discrete choice analysis, MIT press, Cambridge, Mass. [etc, 1989, Bibliogr. : p. 374-384. Index.
[CDVWY00] Jin Cao, Drew Davis, Scott Vander Wiel, and Bin Yu, Timevarying network tomography: router link data, J. Amer. Statist. Assoc. 95 (2000), no. 452, 1063–1075. MR MR1821715 [Csi91]
Imre Csiszar, Why least squares and maximum entropy? an axiomatic approach to inference for linear inverse problems, The Annals of Statistics 19 (1991), no. 4, 2032–2066. 12
[FGL+ 00]
Anja Feldmann, Albert G. Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, and Fred True, Deriving traffic demands for operational IP networks: methodology and experience, SIGCOMM, 2000, pp. 257–270.
[GJT04]
A. Gunnar, M. Johansson, and T. Telkamp, Traffic matrix estimation on a large ip backbone - a comparison on real data, 2004.
[Gol]
O. Goldschmidt, Isp backbone traffic inference methods to support traffic engineering.
[MD]
Ahmed Mansy and Constantin Dovrolis, The mythical traffic matrix.
[MTB+ 02]
A. Medina, N. Taft, S. Battacharya, C. Diot, and K. Salamatian, Traffic matrix estimation: Existing techniques and new directions, 2002.
[TW98]
Claudia Tebaldi and Mike West, Bayesian inference on network traffic using link count data, Journal of the American Statistical Association 93 (1998), no. 442, 557–576.
[UQLB06]
Steve Uhlig, Bruno Quoitin, Jean Lepropre, and Simon Balon, Providing public intradomain traffic matrices to the research community, SIGCOMM Comput. Commun. Rev. 36 (2006), no. 1, 83–86.
[Var96]
Y. Vardi, Network tomography: estimating source-destination traffic intensities from link data, J. Amer. Statist. Assoc. 91 (1996), no. 433, 365–377. MR MR1394093 (97a:62050)
[vdN]
Martin van den Nieuwelaar, : The traffic matrix (a traffic measurement tool for the aucs network), ????
[ZGWX06]
Qi Zhao, Zihui Ge, Jia Wang, and Jun Xu, Robust traffic matrix estimation with imperfect information: making use of multiple data sources, SIGMETRICS Perform. Eval. Rev. 34 (2006), no. 1, 133–144.
[ZRDG03]
Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg, Fast accurate computation of large-scale ip traffic matrices from link loads, 2003.
[ZRLD03]
Y. Zhang, M. Roughan, C. Lund, and D. Donoho, An informationtheoretic approach to traffic matrix estimation, 2003.
13
