Anàlisi espai-temporal multiresolució de matrius de teletrànsit

TREBALL DE FI DE CARRERA TÍTOL DEL TFC: Anàlisi Espai-Temporal Multiresolució de Matrius de Teletrànsit TITULACIÓ: Enginyeria Tècnica de Telecomunicació, especialitat Telemàtica AUTOR: Isaac Balasch DIRECTOR: David Rincón DATA: 15 de Juny del 2010 Títol: Anàlisi Espai-Temporal Multiresolució de Matrius de Teletrànsit Autor: Isaac Balasch Director: David Rincón Data: 15 de Juny del 2010 Resum En aquest document, es mostra la importància de les matrius de teletrànsit, les seves característiques i el mode en que són tractades a nivell matemàtic a través de models de difusió. Les matrius de teletrànsit, corresponents al volum d’informació que es transfereix d’un node d’una xarxa a qualsevol dels altres nodes, tenen molta rellevància en l’enginyeria de xarxes, especialment pel que fa a la recerca de models predictius del comportament d’aquestes. Els estudis realitzats amb matrius de teletrànsit, conjuntament amb models matemàtics com las wavelets de difusió, permeten caracteritzar el comportament d’una xarxa, fent prediccions sobre el seu comportament i el que és de vital importància pels operadors de les xarxes, configurar l’encaminament de forma adient. En el document es mostraran els conceptes matemàtics més rellevants per justificar la utilització de les wavelet de difusió a més de mostrar altres operadors amb els que s’ha treballat fins el moment per comparar-los amb el desenvolupat en aquest treball. S’ha realitzat un estudi en què s’ha aplicat un operador de difusió basat en el model de gravetat incorporant en el càlcul un valor de correlació temporal mesurat sobre les matrius. S’ha obtingut un operador que aconsegueix millors resultats que els obtinguts fins el moment amb altres operadors de difusió. Els resultats obtinguts, amb dades reals de les xarxes Abilene (xarxa nord-americana) i Geant (xarxa acadèmica europea) s’han mostrat des de las perspectives de l’error quadràtic mig (MSE), i des de l’àmbit de la compressibilitat de l’energia de la matriu en la mínima quantitat de coeficients en el domini transformat.. S’ha obtingut uns resultats bons, tot i així hauran de ser verificats per estudis més amplis, degut a la falta de capacitat de càlcul disposada. Title: Traffic Matrices Space-Temporal Multiresolution Analysis Author: Isaac Balasch Director: David Rincón Date: June, 15th 2010 Overview In this document it is shown the importance of traffic matrices, their characteristics and the ways they are treated at a mathematical level throughout diffusion models. Traffic matrices, which are the volumes of traffic exchanged between any two nodes in a network, are very relevant for network engineering, specially regarding the research of predictive models. The studies carried out with traffic matrixes, together with mathematic models such as diffusion wavelets, open the way for characterizing the behavior of a network, predicting it, and, what is of vital importance for network operators, to configure them in a proper way. In the document somerelevant mathematic concepts will be described, in order to justify the use of diffusion wavelets. Besides, the results of previous studies will be described and compared with the new techniques proposed in this work. A diffusion operator based on the gravity model, and incorporating in the calculation a space-time correlation value, has been proposed. It has been attempted to obtain an operator with better results than the ones achieved until now with other operators. The results obtained with data of Abilene (North American) and Geant (European) networks have been described from the mean squared error (MSE) perspective and from the compressibility of the energy of matrix in the fewest possible amount of coeficients. Even though good results have been obtained they should be verified by further studies due to the lack of available computation capability. ÍNDEX INTRODUCCIÓ .................................................................................................. 7 CAPÍTOL 1. MATRIUS DE TELETRÀNSIT .................................................. 8 1.1. Definició .............................................................................................................................. 8 1.2. Importància de les Matrius de Teletrànsit ....................................................................... 9 1.3. Aplicacions de les Matrius de Teletrànsit ....................................................................... 9 1.4. Obtenció de les Matrius de Teletrànsit ......................................................................... 11 1.5. Inferència de Matrius ....................................................................................................... 12 1.6. Model de Gravetat............................................................................................................ 12 CAPÍTOL 2. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN ANÀLISI MULTIRESOLUCIÓ .......................................................................... 15 2.1. Model Dispers .................................................................................................................. 15 2.2. Wavelets i l’anaàlisi Multiresolució (MRA) .................................................................... 15 2.3. Wavelets per imatges 2D ................................................................................................ 18 2.4. Wavelets de difusió ......................................................................................................... 19 2.5. Treballs previs: Wavelet de fidusió en 2D .................................................................... 23 CAPÍTOL 3. DADES ANALITZADES ......................................................... 29 3.1. Descripció de les dades .................................................................................................. 29 3.2. Utilització de les dades ................................................................................................... 30 CAPÍTOL 4. CORRELACIÓ TEMPORAL ................................................... 33 4.1. Coeficient de correlació .................................................................................................. 33 4.2. Anàlisi espai-temporal .................................................................................................... 38 CAPÍTOL 5. RESULTATS ........................................................................... 43 5.1. Abilene .............................................................................................................................. 43 5.2. Geant ................................................................................................................................. 50 5.3. Comparativa Abilene vs Geant ....................................................................................... 52 CONCLUSIONS ............................................................................................... 57 BIBLIOGRAFIA ............................................................................................... 59 GLOSSARI ....................................................................................................... 62 MATRIUS DE TELETRÀNSIT 7 INTRODUCCIÓ En aquest treball es realitzarà l’estudi de l’aplicació d’un operador de difusió sobre matrius de teletrànsit amb la intenció d’obtenir millors resultats que els obtinguts per altres operadors utilitzats fins el moment, respecte a la compressibilitat de la matriu en la mínima quantitat de coeficients (aquells que concentren la major part de l’energia de la matriu original). En un primer terme es realitzarà una introducció a les matrius de teletrànsit, aclarint què són i la seva rellevància a la enginyeria de xarxes. A més, en el primer capítol es mostraran els diferent mètodes d’obtenció de dades per generar las matrius i les eines matemàtiques per analitzar-les. En el segon capítol es mostrarà el tipus d’operacions aplicades sobre les matrius, realitzant una introducció al concepte d’anàlisi multiresolució. S’introduiran els models dispersos i la utilització de les wavelets per l’anàlisi multiresolució. S’explicarà l’evolució dels models matemàtics i la utilització de les wavelets per utilitzar-les en més d’una dimensió i a la seva vegada l’evolució per utilitzar-les en les matrius de teletrànsit amb les anomenades wavelets de difusió. En el tercer capítol es mostrarà com és el format de les dades amb les quals s`ha treballat, les dues xarxes reals de les quals s’han obtingut les dades per fer l’anàlisi, i les seves característiques. En el quart capítol es farà la descripció del operador de difusió utilitzat per realitzar l’estudi, amb el càlcul del coeficient de correlació utilitzat per introduirlo a l’operador que analitzarà les matrius. Al cinquè capítol es podran veure els resultats de l’estudi, on es podrà apreciar que depenent de les xarxes, els resultats són més o menys favorables. Això com s’explicarà, és possiblement degut a les diferents característiques de les dues xarxes. Per finalitzar es presentaran les conclusions extretes de l’estudi, així com les línies futures que es poden seguir. 8 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT CAPÍTOL 1. MATRIUS DE TELETRÀNSIT 1.1. Definició Les matrius de teletrànsit, (anomenades traffic matrices,TM) són una forma de descriure els volums de teletrànsit d’entrada i sortida intercanviats per nodes en una xarxa. Aquests nodes poden ser simplement routers o Points of Presence (PoPs), dels quals pengen altres nodes o xarxes senceres, (tipus LAN o MAN, per exemple). Per cada parell de nodes (entrada-sortida), les matrius de teletrànsit especifiquen la quantitat de teletrànsit que flueix sobre una ruta entre els nodes duran un determinat temps. En els nostres datasets, aquest interval és, per Abilene (la xarxa acadèmica nord-Americana), de cinc minuts i per a GÉANT (la xarxa acadèmica Europea), de quinze minuts. Les matrius no han de ser necessàriament simètriques, ja que la distribució del trànsit en una xarxa tampoc ho és. Un punt d’interès serà la generació de teletrànsit d’un node cap a ell mateix; això és degut a que en les matrius de teletrànsit tenim relacions per un origen X amb un destí X, és a dir parell X-X, (per exemple, SeattleSeattle or LA-LA). Aquest fet és acceptable si el node és un PoP, ja que part del teletrànsit generat pels usuaris relacionats a aquest PoP anirà dirigit a altres usuaris que també estan connectats al mateix PoP Fig. 1.1. Xarxa Abilene(USA) i representació gràfica d’una de les seves matrius de teletrànsit (3 de Març del 2004 des de les 12:00 a les 12:05). A les figures 1.1 i 1.2 es pot aprecia el resultat de representar una matriu de teletrànsit com si fos una imatge, amb l’origen a l’eix vertical i la destinació a l’eix horitzontal. MATRIUS DE TELETRÀNSIT 9 Fig. 1.2. Xarxa GEANT (Europa) i una representació gràfica d’una de les seves matrius de teletrànsit (22 de Febrer del 2005 des de les 19:45 a les 20:00). No apareixen nodes perquè les dades estan anonimitzades. 1.2. Importància de les Matrius de Teletrànsit Les matrius de teletrànsit tenen una gran utilitat potencial per la gestió de les xarxes IP i la capacitat de planificació a partir de la relació de tres paràmetres bàsics de la xarxa: origen, destí i volum de teletrànsit. Aquest tipus de matrius són utilitzades en enginyeria de teletrànsit a partir de les quals es pot configurar l’encaminament en termes de, per exemple, balanceig de carrega, qualitat de servei, etc. Donada la importància de les TMs, la disponibilitat de bons models és essencial pels operadors de xarxes, ja que se’ls donarà bones estimacions matricials amb la capacitat d’aplicar aquestes estimacions a les seves operacions diàries. Amb la informació que proporcionen es poden dissenyar noves xarxes, detectar anomalies, simulació de dades i fer prediccions de problemes a les xarxes en un temps determinat. Aquest és el motiu d’interès en els grups de recerca sobre la modelització de les matrius de teletrànsit i les seves prediccions. 1.3. Aplicacions de les Matrius de Teletrànsit Els operadors han buscat sempre (i segueixen fent-ho), obtenir els millors models d’estimacions o solucions noves i més precises, als problemes que el flux de teletrànsit sobre un enllaç pot produir: planificació, fallades, obtenció d’informació per la monitorització, detecció a priori de fluctuacions impredictibles. Aquests són els principals objectius en l’anàlisi de TM’s. 16 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT Fig. 2.1. Exemple d’anàlisi MRA. En el moment de començar, les senyal original és dividida en detalls (W) i aproximacions (V). En el següent pas, aquestes aproximacions seran descompostes denou en detalls i aproximacions. La transformada Wavelet [16,20] és una de les tècniques preferides per desenvolupar un MRA. Es pot entendre una wavelet com una funció matemàtica utilitzada per dividir la senyal en diversos components d’escala, per exemple, la senyal es pot representar en versions traslladada i dilatada d’una forma d’ona bàsica anomenada “wavelet mare”. Fig. 2.2. Exemple de wavelets mare: Esquerra “Mexican hat”, Dreta “Haar”, Abaix “Daubechies’”. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN LA MULTIRESOLUCIÓ 17 En el camp de processament de senyal és habitual utilitzar mètodes basats en wavelet per comprimir i eliminar soroll de les senyals, series temporals o imatges [16]. La transformada Discreta Wavelet (DWT) [25] analitza els senyals a través del seu producte escalar amb dues funcions base anomenades wavelet pare (o funció d’escalat φ(t)) i wavelet mare (ψ(t)), amb longitud finita. Aquestes són dilatades, en potencies de 2, y traslladades per cobrir la totalitat del domini de les senyals originals, obtenint l’anàlisi de la senyal pels instants t = 2j – k (on j és la escala i k és el desplaçament temporal). L’objectiu de la funció d’escalat és capturar freqüències baixes del senyal, mentre que les altes freqüències (o detalls) són analitzades per la wavelet mare. Si la funció base compleix certes condicions, la transformada resultant és ortonormal i pot ser implementada amb un filtre pas-baix i un filtre pas-alt (h(n) i g(n), respectivament, relacionats amb φ(t) i ψ(t)), com es mostra a la figura 2.3. Els filtres pas-baix mostren les successives aproximacions de les escales a mesura que van sent menys detallades. Es poden interpretar com una imatge que va passant pels filtres pas-baixos. A cada iteració els filtres pas-alts capturen els detalls de les altes freqüències: dx(j,k) agafa les diferencies entre ax(j-1,k) i ax(j,k), on j és un nivell més baix (o més borrós), de descomposició que j-1. Aquest mètode permet recuperar la senyal original únicament repetint el procés de forma inversa: sintetitzant aproximacions i detalls a partit dels coeficients de la transformada wavelet. Fig. 2.3 : Esquerra: filtres pas alt i pas baix en cadena per a una DWT i j=3 escales, obtenint les aproximacions V 3 a(3,K) i els detalls W 3 d(3,k) per a j = 1,2,3. Dreta: descomposició del espectre subseqüent normalitzat. En el domini freqüencial, DWT crea una descomposició per subbandes, on l’espectre es tractat a cada escala. Això produeix un anàlisi multiresolució on el senyal original és descompost a la seva aproximació final (per la freqüència més baixa que es mantindrà per la mitja de la senyal) i un grup de detalls a diferents altes freqüències (coeficients wavelet). En resum, la senyal x(n) és descomposta inicialment amb un parell de filtres. El senyal obtingut a la sortida del filtre pas-alt (g), és conegut com els detalls d1. El primer senyal obtingut a la sortida del filtre pas-baix (h) és l’aproximació a1. A la segona passa, es pot descompondre l’aproximació a1 en els seus detalls d2, i aproximacions a2. El senyal a2 pot ser descompost de nou en les seves aproximacions i detalls. 18 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT Aquest procés pot ser repetit tantes vegades com es requereixi. Una vegada descomposta la senyal es pot realitzar el procés invers per recuperar la senyal original. Si es descarten alguns coeficients dels detalls s’obtindrà una senyal aproximada. 2.3. Wavelets per imatges 2D Un dels camps on les wavelets han tingut una contribució important és en el processament i compressió d’imatges. Per exemple, JPEG 2000 [30] utilitza les wavelets 2D per reduir la quantitat de bytes necessaris per codificar una imatge, mantenint una qualitat acceptable. Fig. 2.4. : Esquerra, filtres pas alt i pas baix en cadena usats en el procés wavelet en 2D. A la dreta la descomposició del espectre normalitzat. Veure la diferència amb la wavelet d’1D a la figura 2.3. Les Wavelets 2D són una generalització de les wavelets clàssiques calculades en els eixos x i y d’unes dades bidimensionals. La forma en la que treballa és similar al procés explicat prèviament per senyals d’una dimensió. L’únic que s’ha de tenir en compte és la fragmentació de cada subespai en quatre, cada un correspon a les quatre combinacions dels filtres pas-alt i pas-baix, (h(n)-h(n); h(n)-g(n); g(n)-h(n); g(n)-g(n)), en els dos eixos verticals de la imatge, per tant, es tenen quatre combinacions de filtres pas-alts i pas-baix, com es pot apreciar a la figura 2.4. Com es pot veure a l’exemple de la imatge real de la figura 2.5, a la imatge descomposta es pot apreciar la imatge aproximada al requadre petit a dalt a l’esquerra, a la resta de requadres es pot apreciar els detalls de la primera escala (requadres més grans) i els de la segona escala. Per a cada cas s’obtenen tres sortides, las quals estan formades per la combinació dels filtres alt-baix, baix-alt i alt-alt. En aquestes imatges es pot notar que els detalls generen la construcció de la silueta de la imatge. Si s’aplica JPEG 2000, es podrien descartar alguns dels coeficients del detalls i mantenir una aproximació acceptant una certa pèrdua de qualitat. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN LA MULTIRESOLUCIÓ 19 Fig. 2.5. : Esquerra: exemple d’imatge original; Dreta: descomposició wavelet en 2D de la imatge. Exemple de Matlab. 2.4. Wavelets de difusió Si volem fer MRA sobre xarxes, hem d’estendre l’anàlisi multiresolució a grafs. El problema està en que no es pot aplicar el procés utilitzat amb les imatges per matrius de teletrànsit. La relació entre els dos nodes d’un graf, (una xarxa amb terminals o nodes i enllaços entre ells), no és exactament el mateix que la relació entre pixels d’una imatge, ja que un graf és molt més complex. En las imatges (per exemple JPEG), part de la compressió ve donada per inferència: el valor d’un pixel pot ser obtingut per el valor dels pixels propers. Si un pixel és negre, es pot assumir amb una gran probabilitat que el pixel que està situat a la seva dreta serà negre, o com a mínim obscur. Aquesta relació no ocorre a las matrius de teletrànsit. Las matrius de teletrànsit es defineixen sobre un graf, i els graf no satisfan les condicions dels pixels, encara que es visualitzin las matrius com una imatge. Dos pixels de la imatge són adjacents però a la xarxa poden representar dos nodes que estan a dos extrems diferents de la xarxa. Per tant es necessiten eines diferents que permetin aplicar l’anàlisi multiresolució sobre un graf. Per a realitzar aquest anàlisi es necessiten diferents classes de wavelets Una primera aproximació, desenvolupada per Crovella i Kolaczyk [5], introdueix les Graph Wavelets com una extensió per la transformada wavelet 2D. Això permet calcular la diferència entre las càrregues dels enllaços en nodes separats per un cert nombre de salts: el concepte d’escala és reemplaçat per la distància de salts entre enllaços. Els autors també mostren com els grafs wavelet poden ser usats per la detecció d’anomalies. El principal problema és la manca d’un algoritme computacional ràpid, i que la transformada no és ortonormal. A més els grafs wavelet no mostren el teletrànsit de manera dispersa: s’obté una descomposició redundant que és similar al resultat obtingut amb la transformada wavelet continua. 20 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT En aquest punt una altre generalització de wavelets entra en joc, la transformada Wavelet de Difusió (DW) [6,9] permet desenvolupar l’anàlisi multiresolució sobre un graf o un “col·lector” (manifold). Intuïtivament, un “col·lector” és un espai matemàtic on dos punts del mateix cos poden estar molt propers a l’espai Euclidià, però la distància sobre la superfície del cos pot ser molt més gran. Fig. 2.6. : Tira de Möbius (esquerra) i rotllo Suïs (dreta): exemples de “col·lectors”. Dos punts són propers en l’espai però llunyans al llarg del cos. Les Wavelet de Difusió, desenvolupades per Coifman i Maggioni [9], s’han convertit en una eina molt important, ja que permet realitzar un MRA sobre un graf. La primera passa és definir el graf i l’operador de difusió, on aquesta tindrà el mateix paper que la funció d’escalat a las wavelets clàssiques. Aquest operador està definit per una matriu i pot ser entès com la base sobre la qual la funció és projectada, o com la columna vertebral de la difusió. La idea que hi ha darrera de l’operador de difusió és la d’explorar el graf (distàncies, adjacències ... ), per mitja de la difusió induïda per l’operador. En els primers experiments [10,34] es va utilitzar un operador “random walk” sense ponderació . El “random walk” té en compte els nodes adjacents i els hi dona un pes igual a l’inversa de la quantitat d’enllaços que existeixen en cada node. Si es veu el graf com una cadena de Markov, la probabilitat de “salt” a través de cada enllaç és la mateixa (equiprobabilitat). Amb això s’obté una matriu simètrica i estocàstica per l’operador. En termes de teoria de grafs, la probabilitat de sortir d’un node a través d’un cert enllaç és l’invers del grau del node. Aquest operador agafa l’encaminament dels fluxos o altres propietats sobre la distribució del teletrànsit, això és únicament un primer exemple. La següent passa és dilatar l’operador per calcular las seves potències: les nèssimes potències del “random walk” en termes de la cadena de Markov associada són las probabilitats P ij de la sortida d’un cert node i a un node j en n passes o salts. A mesura que es prenen potències més altes, tendint a infinit, el que s’obté és la probabilitat d’anar d’un node a un altre en qualsevol nombre de salts (és a dir, en estat estacionari), i la interpretació és que l’operador s’ha “difós” sobre el graf. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN LA MULTIRESOLUCIÓ 21 Fig. 2.7: Exemple de “randomwalk” sense ponderar en una xarxa amb tres nodes. Assumint que una funció donada està definida pels vèrtex del graf, quan l’operador és aplicat a la funció, difumina la funció donada en el graf. El resultat és que els nodes més propers es van barrejant i confonen més ràpidament que els nodes més llunyans, (on la distància està definida en termes del graf). Al treballar sobre un graf en comptes d’una imatge (desenvolupant l’MRA), l’analogia resultant de la descomposició DWT serà una selecció de subbandes en termes del operador de difusió dels autovalors i autovectors. És ben conegut [19,24] que un operador lineal T pot ser expressat com : (2.1) on λi són els autovalors de T i vi són els autovectors associats. S’ha utilitzat una versió normalitzada de T, per que el valor més gran fos u. Unes altres propietats interessants són per exemple: λ n són els autovalors per T n com |λ|<1 el creixement de n ho farà |λ| tendint a zero. Els autovalors estan relacionats amb les freqüències incloses a cada subbanda. També podem veure un paràmetre addicional ε que determinarà la precisió de la descomposició. La idea és classificar els autovalors propis comparant-los amb ε, llavors els autovalors per sota d’ε seran identificats com a detalls, mentre que els que estiguin per sobre seran las aproximacions. Aquest procés serà repetit pas a pas fins que tots els autovalors menys un estiguin per sota del llindar marcat per ε [10]. S’ha de recordar que els autovalors seran la solució de l’equació: (A – λI) x = 0 (2.2) on A és la matriu del operador de difusió, I és la matriu identitat, λ és un autovalor i x és l’autovector associat. Per a una matriu (de l’operador de difusió) n x n, es tindran n solucions (n autovalors) i es poden deduir algunes coses dels grafs des dels seus propis autovalors. Per exemple, el numero de autovalors zero són els numero de components connectats en el graf, i λ 1 és l’anomenada connectivitat algebraica. Aquests autovalors son també útils per determinar famílies de grafs [6,19,24]. 22 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT L’expressió 2.2 pot ser aplicada al teorema espectral [24] ja que sota condicions específiques una transformació lineal d’un vector v pot ser expressada com una combinació dels seus autovectors (v i ) i els seus autovalors (λ i ): T(v)=λ 1 (v 1 ·v)v 1 + λ 2 (v 2 ·v)v 2 +...+ λ n-1 (v n-1 ·v)v n-1 (2.3) Després de tenir normalitzat l’operador per el seu valor més elevat, quant s’agafen las n th potències de T (T n ), n tendint a ∞, tots els autovalors seran zero, a excepció del més gran que serà u (aquest serà 1, ja que els autovalors estan normalitzats). En aquest moment només es tindrà un autovalor per sobre del llindar ε. D’aquesta forma, i aplicant l’operador de difusió una vegada i una altra, s’obtindrà un espectre dividit del graf, llavors, els autovalors mantinguts expandiran els seus subespais de baixes freqüències (detalls). A cada pas, els autovalors són ortonormalitzats de nou. Fig. 2.8. Autoespectre de les potencies d’un operador T. Es pot apreciar que a mesura que n augmenta més autovalors són descartats, per exemple assignant als detalls del subespai W. Quan n→∞, només el valor més elevat (1) es manté. Una vegada s’han obtingut els subespais d’aproximacions i detalls (V i i W i ) es pot projectar qualsevol funció F(v) (definida sobre els vèrtex del graf) sobre els subespais i obtenir un MRA de F(v). Aquest procés té un cost computacional molt elevat, però Coifman i Maggioni [9] van desenvolupar un algoritme ràpid per calcular-ho i obtenir els coeficients dels detalls i les aproximacions. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN LA MULTIRESOLUCIÓ 23 2.5. Treballs previs: Wavelet de fidusió en 2D El teletrànsit de les matrius es pot representar com una funció bidimensional F(x,y)=z on x i y són els nodes d’ingrés i sortida en aquest ordre i z representa el volum de teletrànsit. Tenint en compte que la transformada de Wavelet de Difusió només es pot aplicar a una funció d’una única dimensió F(x), s’ha d’estendre la Wavelet de Difusió a 2D i continuar amb la mateixa aproximació de la DWT en 2D [6]. S’ha pogut veure anteriorment en aquest document que el procés per estendre la DWT a 2D: descomposició en quatre subbandes (un parell per a cada dimensió) per a cada escala i repetint el procés a la següent pels subespais de les aproximacions (resultat dels filtres pas baix - pas baix). En termes generals, aquest és el mateix procés, on ara s’obtindran tres subbandes de detalls i nomes una aproximació. Anàlogament, la transformada DW en 2D seguirà projectant F(x,y) una vegada a cada “dimensió” (origen i destí) per obtenir un producte tensor de base 1D tant per les aproximacions com pels detalls. Els detalls de l’algoritme varien, però el procés és intuïtivament similar al de les wavelets clàssiques en 2D. En aquest cas els coeficients C vv1 , C vw1 , C wv1 i C ww1 generen les subbandes VV 1 , VW 1 , WV 1 i WW 1 (on VV és l’aproximació del subespai de freqüències baixes-baixes, WW és el subespai de detalls de les freqüències altes-altes, i VW i WV són les combinacions baxa-alta i alta-baixa). La transformada en 2D és també ortonormal i invertible, fet que permet reconstruir la funció original a partir dels coeficients. A la figura 2.9 es pot apreciar com es realitzar la descomposició tenint en compte tres subbandes (wavelet de difusió en dos dimensions), en comptes de quatre (waveletes de dos dimensions per imatge). Fig. 2.9. Dreta: arbre de descomposició (subespais definits i autovalors) per la wavelet de difusió en dos dimensions. Comparació amb la descomposició per una dimensió (esquerra) amb 10 autovalors. Las dimensions (n x m) en el cantó dret com a suport pels autovalors (λ). En els primers experiments amb DW en 2D es van estudiar més de 20000 matrius de teletrànsit tant d’Abilene com de Geant. Els dos objectius principals van ser veure com la difusió afecta a una matriu de teletrànsit amb la intenció d’analitzar la multiresolució subsegüent (comprovant la capacitat de reconstrucció, repetint el procés invers) i veure la compressibilitat obtinguda amb aquest mètode. Es va utilitzar com a operador el “random walk” sense ponderar normalitzat, i la precisió va ser de ε=10 -7 . Es pot apreciar la representació MRA d’una TM d’Abilene a la figura 2.11. Las aproximacions són els subespais VV (anomenats com a V, mentre que els detalls W són la suma 24 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT de WW, VW i WV). En els dos primers passos de la descomposició (V 1 i V 2 ) la reconstrucció és exactament la TM original degut a que W 1 i W 2 no tenen autovalors, per aquest motiu no han estat incloses aquestes imatges a la figura. L’efecte de del freqüències baixes es pot apreciar fàcilment a l’hora d’aplicar reiterativament l’ operador a les aproximacions, com també l’efecte de les altes freqüències en els detalls. Per la comprovació de la compressibilitat de la TM es van realitzat diferents tests agafant grans períodes de grups de dades (des de mig mes a la totalitat d’un, tant grans com permetien els “datasets” públics), amb l’objectiu de trobar quanta energia de la matriu original es mantenia concentrada en els primers coeficients. Es poden veure els resultats a la Taula 2.1. Taula 2.1. Preservació de l’energia en els coeficients en dos grups de dades representatius (8640 TMs d’Abilene, i 2880 TMs per GÉANT). A la figura 2.11 es pot apreciar com la imatge s’esborra a mesura que avança en el procés de difusió (a cada pas s’analitzen subbandes més petites). Això és el que s’obté quan la difusió és realitzada sobre la xarxa. Fig. 2.10. MSE normalitzat depenent del percentatge de coeficients de DW, per a un mes amb l’operador de difusió “random walk”. MODEL PER MATRIUS DE TELETRÀNSIT BASAT EN LA MULTIRESOLUCIÓ 25 Fig. 2.11. Descomposició: aproximació i detalls dels subespais associats dels autovalors per l’anàlisi multiresolució del exemple mencionat. 32 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT manera la matriu binaria ens indica la relació de veïnatge entre els nodes a la xarxa o graf i és molt útil quant es prova l’operador de difusió. Fig.3.3: Relació entre la xarxa Abilene (graf) i la seva matriu d’adjacència. A la figura 3.3 es pot trobar la representació de la matriu d’adjacència de la xarxa Abilene i els seus valors. La analogia és visible: els pixels vermells són els que tenen valor 1 i els pixels blaus són els que tenen valor 0. Cada valor [i,j] representa una combinació dels dos nodes: el primer 0 representa l’adjacència de Seattle a Seattle, (aquest és zero per que ell mateix no pot ser el seu propi veí). Si s’observa la primera línea, es trobarà els nodes veïns de Seattle en aquest ordre: Sunnyvale i Denver (la distribució es pot veure a la figura 1.1, Abilene). Es pot apreciar que en aquest cas la diagonal de la matriu d’adjacència és zero (la diagonal representar las adjacències de cada node amb ell mateix) encara que en el cas de l’estudi també es considera el teletrànsit que va d’un node cap a ell mateix (i per tant haurà de ser afegit a la matriu identitat). Existeix una variació d’aquesta matriu que és la matriu Laplaciana o també anomenada matriu d’admitància de l’adjacència. La matriu Laplaciana L, és definida sobre un graf de la següent manera: l ij = -1 si i i j són veïns (vèrtex v i i v j enllaçats per una vora), l ij = deg(v i ) només quan j = i, i l ij = 0 en qualsevol altre cas. La matriu Laplaciana mostra el veïnatge dels nodes en el graf: això està íntimament relacionat amb el random walk, de manera que també són importants en la definició de l’operador de difusió. En termes generals, quan es realitza una MRA sobre un graf, la relació amb el veïnat es pot considerar un bon punt de partida. DADES ANALITZADES 33 CAPÍTOL 4. CORRELACIÓ TEMPORAL L’estudi s’inicia a partir de la hipòtesis que existeix una correlació temporal entre la quantitat de teletrànsit transportada en una ruta en un temps t = n i t = n+1, per tant, en mostres consecutives. Seguint aquesta línea de recerca l’objectiu es fer un operador basat en aquesta autocorrelació apreciant la posterior difusió i compressibilitat. Fig.3.3: Volum de teletrànsit entrant en el node de Seattle en el transcurs d’una setmana. Es pot apreciar una regularitat entre els set gràfics. 4.1. Coeficient de correlació L‘objectiu d’aquesta primera part de l’estudi va ser obtenir un valor que relacionés les diferents matrius de teletrànsit entre elles. El paràmetre que es va utilitzar per relaciona les diferents matrius que es disposava de les xarxes a estudi va ser el volum de teletrànsit entre els diferents nodes. S’ha de tenir en compte a l’hora de realitzar l’anàlisi que les dues xarxes estudiades tenen una diferència de comportament fonamental. El comportament diferencial es troba en l’ús per part del usuaris de cadascuna de les xarxes. Abilene és una xarxa amb un volum de teletrànsit elevat, d’un ús molt freqüent entre els usuaris que en fan ús, volum constant de fluxos de teletrànsit. Pel que fa a Geant en el moment de la recol·lecció de las dades, l’any 2005, era una xarxa d’un ús molt més irregular, un teletrànsit de dades esporàdic, a ràfegues. Aquesta característica diferencial de les dues xarxes va generar que a l’hora de calcular el coeficient de correlació entre les diferents matrius aquest paràmetre fos calculat també de forma diferenciada. 34 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT En el cas de les dues xarxes el coeficient que es va buscar va ser el valor d’autocorrelació diari mig del teletrànsit per a cada ruta, però com s’ha comentat amb anterioritat en el cas d’Abilene, degut al comportament del teletrànsit entre rutes, el procés va ser més elaborat que no pas en el cas de Geant. 4.1.1. Correlació Abilene L’estudi es va realitzar obtenint els valors d’autocorrelació de cada una de les rutes per a cada un dels 167 dies que es disposava per fer l’estudi. En un principi aquest valor d’autocorrelació mig va ser de 0,750852, però l’estudi de les autocorrelacions de cadascuna de les rutes va desvela que existien algunes que, ja fos en moments puntuals o d’una forma continuada, donaven valors d’autocorrelació molt baixos, inclús negatius. Es va determinar que aquells valors d’autocorrelació que estiguessin per sota de 0,7 serien considerats inestables. Tenint en compte aquest fet, es va procedir a realitzar un anàlisis de les rutes en concret que presentaven valors inferiors al considerat d’estabilitat. A la Figura 4.1 es pot apreciar al gràfic superior els valors d’autocorrelació mig per un dia per a cadascuna de les rutes, i el gràfic inferior la quantitat de valors d’autocorrelació considerats estables per a cada ruta en valors mitjos d’autocorrelacions per hora del dia estudiat. Com s’ha explicat anteriorment, fent l’estudi d’inestabilitat es va apreciar que existien rutes que eren considerades inestables de forma puntual, però n’hi havia que ho eren de forma constant. Per determinar com d’inestables eren cadascuna de les rutes es va procedir a fer un càlcul de dies d’inestabilitat mostrat per cadascuna de les 144 rutes que disposa Abilene. Aquest càlcul va mostra que hi havia rutes que es mantenien inestables al llarg del temps i es va determinar d’eliminar del càlcul del coeficient d’autocorrelació global el valors d’autocorrelació mitjos mostrats per les rutes considerades inestables. Aquest pas es va determinar pel fet que es va considerar que aquests valors d’autocorrelació falsejaven el valor mig global d’autocorrelació. Per considerar una ruta inestable es va agafar com a criteri el determinar com a tal aquelles rutes que es mantenien inestables aproximadament el 50% dels dies totals que es disposava per l’estudi, es a dir sobre els 84 del 167 dies DADES ANALITZADES 35 Fig. 4.1. Gràfic superior: Valors autocorrelació mitjos per a cada ruta pel dia 1 de març del 2004. Gràfic inferior: Quantitat de valors d’autocorrelació estables per mitges horàries de cada ruta pel dia 1 de març del 2004. El número total de rutes d’Abilene són 144, les rutes descartades pel càlcul de valor d’autocorrelació global van ser 7 : 1. Ruta SNVA-IPLS, dies d’inestabilitat 145. 2. Ruta SNVA-NYCM, dies d’inestabilitat 117. 3. Ruta SNVA-ATLA-M5, dies d’inestabilitat 96. 4. Ruta DNVR-ATLA-M5, dies d’inestabilitat 81. 5. Ruta HSTN-ATLA-M5, dies d’inestabilitat 140. 6. Ruta ATLA-ATLA, dies d’inestabilitat 125. 7. Ruta ATLA-M5-SNVA, dies d’inestabilitat 102. De les set rutes descartades per realitzar el càlcul del valor d’autocorrelació es pot identificar que en quatre d’aquestes intervé el node ATLA-M5. Aquest node, com es pot veure a la figura 1.1, la seva comunicació amb el resta de la xarxa depèn únicament del node ATLA, aquest fet genera que el teletrànsit generat o amb destinació a ATLA-M5 sigui molt poc (i per tant més sensible a variacions). Tot i això fa que el trànsit d’aquest enllaç sigui molt variable. A la Figura 4.2 es pot apreciar al gràfic superior els valors mitjos d’autocorrelació de cadascuna de les rutes per un dia, i en el gràfic inferior es mostren els valors d’autocorrelació únicament de les rutes que s’han considerat estables. 36 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT Fig. 4.2. Gràfic superior: Valors autocorrelació mitjos per a cada ruta pel dia 1 de març del 2004. Gràfic inferior: Valors d’autocorrelació de cada ruta estable per mitges horàries de cada ruta pel dia 1 de març del 2004. Com es pot veure a la Figura 4.2 , el número de rutes inicials són les 144 totals d’Abilene, però les utilitzades pel càlcul del valor d’autocorrelació son 137, com es veu al gràfic inferior de la mateixa figura. Una vegada es va prendre la decisió de descartar les rutes inestables es va tornar a realitzar el càlcul del coeficient d’autocorrelació donant com a resultat un valor sensiblement superior que l’inicial, exactament 0,773337. D’aquest valor, pels càlculs posteriors de l’estudi, van ser descartats el quatre últims decimals, obtenint 0,77 com a coeficient d’autocorrelació global per l’anàlisi espai-temporal multiresolució de matrius de teletrànsit. 4.1.2. Correlació Geant Pel que fa a Geant l’estudi de l’autocorrelació va tenir una dificultat afegida, com s’ha comentat anteriorment, la falta de continuïtat en les mostres que es disposaven. Per aquest fet es van tenir que descartar dies sencers pel càlcul de la autocorrelació, ja que els vuits de matrius intercalats en mig del que en un principi semblaven períodes llargs d’anàlisi, generaven una distorsió del resultat, ja que les matrius no eren consecutives i per tant la correlació entre matrius no era real. Finalment es van pogué estudiar 106 dies sencers, amb els seus corresponents valors d’autocorrelacions per cada ruta. DADES ANALITZADES 37 El coeficient de correlació entre les diferents rutes va desvelar una inestabilitat molt més elevada que en el cas d’Abilene. Aquesta inestabilitat, com s’ha comentat anteriorment, ve determinada pel comportament d’us de la xarxa. Geant presenta un comportament d’us molt esporàdic, i a més, les rutes de teletrànsit són molt constants, es a dir, els fluxos de dades solen ser entre rutes concretes. Tenint en comte aquests fets es va determinar el no descartar cap valor d’autocorrelació ni cap ruta, a diferència de l’estudi realitzat amb Abilene, a l’hora de trobar el valor de correlació entre matrius. A la figura 4.3 es pot apreciar la inestabilitat de les rutes comentada. S’ha de tenir en compte que els dies que apareixen als gràfics no corresponen a la realitat, ja que les dades de Geant són parcialment confidencials, el dia a que fa referència el gràfic és a l’indicat en els arxius XML que contenen la matriu de teletrànsit avaluada. Fig 4.3. Superior i inferior: correlació de les 529 rutes de Geant en diferents dies. 38 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT Una vegada realitzat aquest anàlisi sobre les rutes de Geant el valor d’autocorrelació va ser 0.55671, com es pot apreciar molt més baix que l’obtingut a Abilene degut, com s’ha explicat, a la inestabilitat mostrada a la xarxa. En aquest cas es van mantenir tots els decimals del valor obtingut. 4.2. Anàlisi espai-temporal Una vegada es tenen les matrius de teletrànsit reals el repte és relacionar cadascuna d’aquestes matrius amb les altres. Generant un espai tridimensional, és a dir, amb les matrius obtenim una relació espacial en 2D, nodes origen i final, la relació que s’ha buscat és la temporal de cada matriu amb las següents i anteriors. La figura 4.4 mostra la idea de relacionar temporalment las matrius de teletrànsit sobre la topologia de la xarxa origen de les matrius estudiades, en aquest cas Abilene. Fig 4.4: Representació de la topologia d’Abilene en el temps. Com s’ha explicat anteriorment, el càlcul del valor d’autocorrelació es va realitzar per obtenir un valor matemàtic que ens relaciones temporalment les matrius estudiades. Una vegada obtingut el valor d’autocorrelació i conjuntament amb el model de gravetat es va realitzar l’anàlisi espai-temporal. L’anàlisi es va realitzar amb cinc mètodes diferents. Van ser quatre mètodes on es va introduir el valor d’autocorrelació d’una o altre forma i un mètode on no es va introduir el valor. DADES ANALITZADES 39 Els cinc mètodes d’anàlisi es poden diferenciar en dos grups. Aquest dos grups es diferencien pel moment en que el model de gravetat és aplicat. En el primer dels grups el model de gravetat és aplicat una vegada el valor d’autocorrelació ha estat incorporat a les matrius de teletrànsit. En el segon del grups el valor d’autocorrelació és incorporat després d’aplicar el model de gravetat sobre les matrius. En cadascun dels dos grups definits anteriorment van existir al mateix temps dues possibles variacions per cadascun, aquestes variacions es deuen a l’hora de com incorporar el valor d’autocorrelació. En el primer grup d’anàlisi el primer pas a realitzar va ser la generació d’una matriu que incorporava totes les matrius de teletrànsit que anaven a ser utilitzades per l’estudi, degut als requeriments de processador es va realitzar l’estudi sobre 12 matrius consecutives, és a dir una hora de teletrànsit d’Abilene. Les matrius de teletrànsit es van disposar sobre la diagonal principal de la matriu que les acollia, una sota de l’altre, en ordre temporal. Una vegada obtinguda aquesta “supermatriu” es va incorporà a aquesta el valor d’autocorrelació. La incorporació d’aquest valor a la “supermatriu” com s’ha explicat anteriorment va suposar dos variants de càlcul. En la primera variant es va introduir el valor d’autocorrelació a les diagonals adjacents a la diagonal formada per las matrius de teletrànsit. Aquesta disposició del valor d’autocorrelació es pot apreciar amb l’exemple amb dos matrius de la Fig. 4.5. Fig. 4.5. Exemple amb dos matrius de la inserció del valor d’autocorrelació a les diagonals adjacents a la diagonal principal de la “supermatriu”, on es troben les matrius de teletrànsit. En la segona variant d’aquest primer grup es va introduir el valor d’autocorrelació a totes les posicions de la “supermatriu” que no estaven 40 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT ocupades pels valors de les matrius de teletrànsit. Aquesta disposició del valor d’autocorrelació es pot apreciar amb l’exemple amb dos matrius de la Fig. 4.6. Fig. 4.6. Exemple amb dos matrius de la inserció del valor d’autocorrelació a totes les posicions de la “supermatriu” que no estaven ocupades pels valors de les matrius de teletrànsit. Els altres dos mètodes de càlcul es van generar a partir de la creació d’una “supermatriu” com en els cassos anteriors, amb la diferència amb els mètodes anteriors que aquesta “supermatriu” es va crear amb els valors probabilístics obtinguts a l’aplicar l’algoritme basat en el model de gravetat a cadascuna de les matrius de teletrànsit. Cada matriu de les matrius de teletrànsit va ser sotmesa al models de gravetat. Aquest retornava una matriu probabilística per a cada una de les rutes. Aquesta matriu de probabilitats es va inserir a la diagonal principal de la “supermatriu”, com a l’anterior cas fins a dotze matrius a la diagonal. Una vegada realitzat això es va introduir el coeficient d’autocorrelació, del mateix mode que en el primer i segon mètode, primer a las diagonals adjacents a la diagonal generada per las matrius de probabilitats i finalment a totes les posicions buides de la “supermatriu”. A les figures 4.7 i 4.8 es pot apreciar com les matrius queden disposades sobre la diagonal de la “supermatriu” generada. En el cas de la figura 4.7 el coeficient de correlació es va inserir a les diagonals adjacents, i en el cas de la figura 4.8 el coeficient de correlació es va inserir a totes les posicions que no eren ocupades per les matrius probabilístiques donades pel model de gravetat. Es mostren aquests dos exemples, dels quatre estudiats amb la incorporació de coeficient de correlació, pel fet que van ser els dos que millor resultats van proporcionar a l’estudi. Els mètodes de càlcul on s’aplicava el model de gravetat una vegada creada la “supermatriu” amb les dades de teletrànsit i el DADES ANALITZADES 41 coeficient de correlació es va descartar després d’obtenir els resultats, ja que eren pitjors als obtinguts amb els mètodes mostrats. Fig. 4.7. Mètode 3 d’estudi de les aproximacions i detalls de l’anàlisi multiresolució de matrius. Esquerra: Xarxa Abilene, matrius TM-2004-07-05-1800 a TM-2004-07-05-1855. Dreta: Xarxa Geant, matrius IntraTM-2005-01-06-11-00 a IntraTM-2005-01-06-11-45. Fig. 4.8. Mètode 4 d’estudi de les aproximacions i detalls de l’anàlisi multiresolució de matrius. Esquerra: Xarxa Abilene, matrius TM-2004-07-05-1800 a TM-2004-07-05-1855. Dreta: Xarxa Geant, matrius IntraTM-2005-01-06-11-00 a IntraTM-2005-01-06-11-45. Es va realitzar un últim mètode de càlcul en el que no s’incorporava en cap moment el valor d’autocorrelació, per poder valorar els resultats i observar si realment el coeficient que s’estava utilitzant suposava un avanç. Com posteriorment es podrà observar, els resultats donen crèdit a la utilització d’aquest valor d’autocorrelació com un pas endavant en l’anàlisi espai-temporal de matrius de teletrànsit. 48 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT FIG. 5.8. Energia acumulada respecte els coeficients. Eix x: quantitat de coeficients. Eix y: valor percentual de la quantitat d’energia. Mètode d’estudi 5. Segons els gràfics de les figures 5.6, 5.7 i 5.8, podem extreure dues conclusions. La primera és que el mètode 4, com s’ha demostrat al llarg de l’estudi és el que millor resultats aporta. En aquests gràfics el mètode 4 mostra clarament que en l’energia de las TMs estudiades es reflecteix en un percentatge molt menor de coeficients que en els altres dos mètodes. A la següent taula queda reflectit aquest fenomen: % Energia % coeficients Mètode 3 % coeficients Mètode 4 % coeficients Mètode 5 50% 1,885% 0,602 % 1,393 % 90% 11,950 % 3,255 % 11,058 % 99% 31,182 % 7,764 % 35,8989 % Taula 5.1. Comparació percentual de quantitat de coeficients respecte l’energia amb els tres mètodes d’estudi. Una altra conclusió que es pot extreure del gràfics referents a l’energia és importància en la forma en que s’introdueix el valor d’autocorrelació a l’operador de difusió. La taula 5.1 mostra que en el mètode 5, aquell que no incorpora el coeficient d’autocorrelació en el càlcul, ofereix millors resultats per percentatges del 50 i 90 per cent que no pas el mètode 3, el qual incorpora el coeficient d’autocorrelació. Com s’ha comentat anteriorment, per reflectir la incidència del valor d’ε, es va realitzar el mateix estudi que s’ha mostrat amb els gràfics percentuals de l’energia respecte els coeficients amb un valor d’ε = 10 -15 . DADES ANALITZADES 49 FIG. 5.9. Coeficients amb ε = 10 -15 (esquerra), i ε = 10 -8 (dreta). La figura 5.9 ens mostra les diferències entre els coeficients adquirits amb el mateix mètode d’anàlisi, en aquest cas opció 4, amb un valor d’ε diferent. Els dos gràfics són pràcticament idèntics a excepció de punts de concentració major de coeficients en el cas dels coeficients amb l’ ε = 10 -15 . FIG. 5.10. Superior esquerra: Energia respecte els coeficients mètode d’estudi 4 amb ε= 10 -15 . Superior dreta: Energia respecte els coeficients mètode d’estudi 4 amb ε= 10 -8 . Inferior esquerra: Ampliació amb valors energia amb ε= 10 -15 . Inferior dreta: Ampliació amb valors energia amb ε= 10 -8 . La figura 4.10 mostra la diferent distribució de l’energia respecte el coeficients amb diferents valors d’ε . 50 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT % Energia ε= 10 - 8 Abilene ε= 10 - 15 Abilene 50% 0,602 % 0,491 % 90% 3,255 % 2,623 % 99% 7,764 % 5,179 % Taula 5.2. Comparació percentual de quantitat de coeficients respecte l’energia amb diferents valors d’ ε. Com ens mostra la taula 5.2 amb un valor d’ ε menor s’obtenen millors resultats amb el mateix mètode d’estudi. Es a dir, amb el valor més baix d’ ε l’energia amb menor quantitat de valors es capta més energia de la matriu original, i per tant menys valors calen per realitzar la reconstrucció d’aquesta Tot i les dades aportades en aquesta taula, estudis anteriors amb diferents valors d’ ε demostren que aquesta relació no és lineal. El fet que el valor de la ε disminueixi no assegura que la relació dels coeficients amb l’energia de la matriu millori. Aquest fet es farà evident amb l’estudi realitzat sobre Geant. 5.2. Geant Respecte els resultats obtinguts amb Geant només s’ha avaluat amb l’opció 4, la que oferia millors resultats en el cas d’Abilene. 5.2.1. MSE Com en el cas d’Abilene els primers resultats que es mostren són referents a l’error quadràtic mig. DADES ANALITZADES 51 FIG. 5.11. Error quadràtic mig normalitzat en funció del percentatge de coeficients de la DW a Geant. Superior esquerra: MSE amb ε=10 -8 . Superior Dreta: Ampliació MSE amb ε=10 -8 . Inferior Esquerra: MSE amb ε=10 -15 . Inferior Dreta: Ampliació MSE amb ε=10 -15 . 5.2.2. Energia acumulativa segons coeficients En les figures 5.13 i 5.14 es pot apreciar la quantitat de coeficients resultants i el percentatge de l’energia respecte aquest coeficients. FIG. 5.13. Coeficients mètode d’estudi 4 amb Geant amb valors d’ ε diferents Esquerra: ε= 10 -8 . Dreta: ε= 10 -15 52 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT FIG. 5.14. Superior esquerra: Energia respecte els coeficients ε= 10 -8 . Superior dreta: Ampliació gràfic energia respecte els coeficients ε= 10 -8 . Inferior esquerra: Energia respecte els coeficients amb ε= 10 -15 . Inferior dreta: Ampliació gràfic energia respecte els coeficients ε= 10 -15 . A la taula 5.3 es realitzar una comparativa a partir dels gràfics anteriors, on es pot apreciar que, a diferència amb Abilene, el valor ε no té la mateixa rellevància. % Energia ε= 10 - 8 Geant ε= 10 - 15 Geant 50% 0,968 % 0,992 % 90% 6,179 % 6,131 % 99% 13,586 % 13,539 % Taula 5.3. Comparació percentual de quantitat de coeficients respecte l’energia amb diferents valors d’ ε. 5.3. Comparativa Abilene vs Geant 5.3.1. Comparativa MSE La primera comparativa que es mostrar és respecte l’error quadràtic mig. En aquesta comparativa es pot apreciar que els resultats d’Abilene són sensiblement millors que els de Geant. En el cas d’Abilene com s’ha comentat anteriorment el valor de la ε té una rellevància major que en el cas de Geant. DADES ANALITZADES 53 FIG. 5.15. Superior: Comparativa Abilene-Geant MSE amb ε= 10 -15 . Inferior: Comparativa Abilene-Geant MSE amb ε= 10 -8 . La comparativa dels MSE’s de cada una de les xarxes demostra que en el cas d’Abilene la incidència del valor d’ ε és més gran. Les diferències en els percentatges en el cas de Geant són imperceptibles. 5.3.2. Comparativa Coeficients En aquesta comparativa, una vegada més s’aprecia que el valor de la ε pren més rellevància en el cas d’Abilene. Els gràfics de Geant són pràcticament idèntics, mentre que en el cas d’Abilene, tot i ser molt semblants, es poden apreciar majors diferències. 54 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT FIG. 5.15. Superior esquerra: Coeficients Abilene amb ε= 10 -15 . Superior dreta: Coeficients Geant amb ε= 10 -15 . Inferior esquerra: Coeficients Abilene amb ε= 10 -8 . Inferior dreta: Coeficients Geant amb ε= 10 -8 . La comparativa amb els coeficients delata que en el cas de la xarxa Abilene la diferència dels valors d’ ε ha sigut molt més rellevant. En el gràfics dels coeficients d’ambdues xarxes s’aprecia que en el cas de Geant, la distribució dels coeficients és pràcticament idèntica. Abilene, per la seva banda, mostra una certa densitat superior en alguns trams del gràfic amb una ε més baixa. 5.3.3. Comparativa energia respecte els coeficients La comparativa de l’energia respecte els coeficients mostren clarament el que s’havia demostrat amb els anteriors gràfics comparatius. Els resultats són millors, en el cas d’Abilene quant ε té un valor menor. En el cas de Geant, no s’aprecien diferències. DADES ANALITZADES 55 FIG. 5.16. Superior esquerra: Energia respecte els coeficients Abilene amb ε= 10 -15 . Superior dreta: Energia respecte els coeficients Geant amb ε= 10 -15 . Inferior esquerra: Energia respecte els coeficients Abilene amb ε= 10 -8 . Inferior dreta: Energia respecte els coeficients Geant amb ε= 10 -8 . Una vegada més els gràfics de la distribució de l’energia en els coeficients demostra clarament que en el cas de Geant no hi ha percepció de canvi. En el cas d’Abilene és molt més evident l’evolució dels resultats de l’energia. En aquest cas las taules 5.2 i 5.3 denoten una millora significativa en el cas d’Abilene, i cap evolució en el cas de Geant. 5.3.4. Estudi de la mateixa hora en set dies consecutius Donat els resultats mostrats fins el moment es va decidir realitzar un estudi sobre un espectre més ampli de matrius de teletrànsit. Per realitzar aquest estudi es va utilitzar únicament el mètode quatre de càlcul amb una ε= 10 -15 , degut a que amb aquest valor d’ε, en el cas d’Abilene, s’havien assolit millors resultats. (Annexos, capítol 4). Per realitzar aquest estudi es va procedir a avaluar l’evolució del teletrànsit durant una setmana, a la franja horària de les 8 a les 14 hores. Una vegada determinat que el teletrànsit no presentava anomalies es va determinar, en el cas d’Abilene , agafar com a hora d’estudi la franja de les 09:00 a 09:55. En el cas de Geant no es pot afirmar amb seguretat que las dades corresponguin a les hores indicades pels -datasets-, però es va realitzar la mateixa avaluació del teletrànsit que en el cas de la xarxa americana, i es va valorar utilitzar la franja horària de les 08:00 a 08:45 indicada pels -datasets-. Un primer fet en l’anàlisi del teletrànsit de les dues xarxes va ser l’evident diferenciació del comportament del teletrànsit en les dues xarxes, però com s’ha explicat amb anterioritat, no es poden extreure conclusions d’aquest fet degut a que les dades de Geant, amb un probabilitat elevada, no corresponen a la franja horària indicada pels -datasets-. Una vegada determinada l’hora d’estudi a cada xarxa es va procedir a realitzar l’anàlisi vist als anteriors punts, amb els paràmetres indicats anteriorment, amb la utilització únicament del mètode quatre i amb un ε= 10 -15 . 56 ANÀLISI ESPAI-TEMPORAL MULTIRESOLUCIÓ DE MATRIUS DE TELETRÀNSIT Els resultats des del punt de vista dels coeficients respecte l’energia són resumits a les taules 5.4 i 5.5 per a cadascuna de les xarxes. Abilene 1 er Dia 2 on Dia 3 er Dia 4 rt Dia 5 è Dia 6 è Dia 7 è Dia 50 % 0,4292 0,4677 0,5401 0,2507 0,5256 0,5353 0,5304 90 % 2,3823 2,5366 2,58 2,1363 2,6475 2,6427 2,7488 99 % 5,0829 5,2951 5,2228 4,6923 5,3337 5,4108 5,488 Taula 5.4. Percentatge de quantitat de coeficients respecte l’energia durant la setmana del 05/07/2004 a 11/07/2004 a la franja horària de 09:00 a 09:55. Geant 1 er Dia 2 on Dia 3 er Dia 4 rt Dia 5 è Dia 6 è Dia 7 è Dia 50 % 1,0633 1,0396 1,0160 1,1932 1,0633 1,0751 1,004 90 % 6,1909 6,0255 6,2854 6,5689 6,3917 5,7065 5,5765 99 % 13,7169 13,6814 13,9886 14,1895 13,5160 13,1498 12,3818 Taula 5.5. Percentatge de quantitat de coeficients respecte l’energia durant la setmana del 10/01/2005 a 16/01/2005, segons -datasetsde Geant, a la franja horària de 08:00 a 08:55. Els resultats que es mostren a las taules 5.4 i 5.5 són pràcticament idèntics als referents a l’estudi realitzant amb anterioritat en un hora aïllada. DADES ANALITZADES 57 CONCLUSIONS En aquest document s’ha mostrat la importància de les matrius de teletrànsit en l’àmbit de la enginyeria de trànsit, la seva rellevància en la gestió i configuració d’aquestes xarxes. Les aplicacions de les matrius de teletrànsit es poden trobar des de la configuració del balanceig de càrrega generat pels nodes de la xarxa, a la configuració de l’encaminament de la xarxa, la detecció de possibles anomalies i predicció d’aquestes. Tot i la utilitat evident de les matrius de teletrànsit existeixen problemes a l’hora d’aconseguir matrius de xarxes reals. Per una banda està la dificultat d’obtenir dades en temps real sense afectar la capacitat computacional dels nodes. El mètode que aporta un compromís acceptable és la captura de les dades amb el protocol SNMP. Un segon problema és degut a las reticències dels ISP comercials a publicar les dades de les seves xarxes, degut a la competència entre empreses. Aquest problema és el que genera un lentitud extraordinària a l’hora de realitzar investigació en el camp de les matrius de teletrànsit. En aquest estudi s’ha treballat amb dades de las xarxes americana, Abilene, i europea, Geant. El model d’anàlisi utilitzat en aquest estudi s’ha basat en la multiresolució de les matrius de teletrànsit. S’ha realitzat una introducció a las diferents eines utilitzades per realitzar la multiresolució. Aquestes eines es basant amb les Wavelets de difusió. Aquest tipus de wavelets ens permet estendre l’anàlisi multiresolució aplicat en altres camps, com per exemple les imatges, al camp dels grafs. Amb les wavelets de difusió i un operador de difusió es pot realitzar l’anàlisi multiresolució. En el nostre cas aquest operador s’ha basat en el model de gravetat. L’anàlisi multiresolució permet, una vegada descomposta la matriu de teletrànsit, pogué reconstruir-la. En el cas que aquests valors acumulin una quantitat d’energia significativa de la matriu original, permet treballar amb una quantitat de valors molt inferior als que conté una matriu de teletrànsit original. L’objectiu ha estat millorar els resultats obtinguts en altres estudis, en quant a la compressibilitat de les TMs. La contribució que s’ha realitzat és la introducció d’un coeficient de correlació a l’estudi de les matrius de teletrànsit en un àmbit temporal. S’ha demostrat que l’aplicació del coeficient de correlació sobre l’operador de difusió ha millorat els resultats respecte estudis anteriors sobre altres operador de difusió. El mode d’aplicació del coeficient de correlació, com s’ha demostrat amb l’estudi realitzat sobre la xarxa Abilene, no és trivial. Durant l’estudi s’han realitzat diferents introduccions del coeficient, mostrant que els resultats milloren o empitjorant segons la seva aplicació.