Criticalitat autoorganitzada en xarxes d’interconnexió

Francesc Comellas Javier Ozón Departament de Matemàtica Aplicada i Telemàtica

E.T.S.E. Telecomunicació, Universitat Politècnica de Catalunya Campus Nord C-3, Gran Capitán s/n, Barcelona

       comellas@mat.upc.es    matjog@mat.upc.es

26 d’Agost de 1995 Butll. Soc. Cat. Ciènc., Sotmés (1995)

Abstract

En aquest treball presentem una aplicació concreta de les teories de la complexitat i de la criticalitat autoorganitzada a l’estudi del comportament de les grans xarxes d’interconnexió. Un dels trets principals dels sistemes complexos adaptatius, la presència d’un gran nombre d’unitats amb un comportament individual normalment ben definit i interrelacionades les unes amb les altres, és també un tret fonamental de qualsevol xarxa de comunicació. En aquest treball s’ha aplicat a diverses xarxes de comunicació un model caracterísitic de estructura autoorganitzada, el model biològic de Bak i Sneppen. Així s’ha comprovat com en les grans xarxes de comunicació és també possible l’aparició d’estructures autoorganitzades, tal com passa en alguns sistemes evolutius de la natura.

1 Sistemes complexos adaptatius

Un sistema complex adaptatiu està format per un gran nombre d’unitats que interaccionen les unes amb les altres, i on s’esdevenen processos d’adaptació, aprenentatge i selecció, tots tres relacionats normalment amb l’obtenció i processament d’informació de l’entorn on es troba el sistema complex. Un sistema complex adaptatiu és, en un sentit ampli, un sistema evolutiu en el qual el comportament global no depèn únicament del comportament individual de cadascuna de les parts, sinó també de la seva estructura i dels diferents tipus d’interacció entre les diferents unitats que el componen. Així, per exemple, un formiguer, un grup d’ocells volant en bandada, o el conjunt de companyies que distribueixen un determinat producte en una gran ciutat, són sistemes complexos on de la interacció de grans nombres d’unitats emergeixen pautes globals de comportament que permeten l’assoliment d’algun objectiu determinat; tot això sense la presència de cap autoritat central de govern o control.

Així mateix, les grans xarxes d’interconnexió són un altre exemple característic de sistema complex adaptatiu. Qualsevol xarxa, per definició, està formada per una sèrie d’unitats que processen i s’intercanvien informació a través d’algun tipus de connexió física. Encara ara, una gran majoria de les xarxes existents d’interconnexió estan controlades per alguna autoritat central, circumstància que pot provocar grans reaccions en cadena de caràcter descontrolat. Així, per exemple, en 1991 sis de les set milions de trucades telefòniques en servei en la ciutat de Washington van caure en produir-se un allau a partir d’un dígit incorrecte en una de les rutines de control. Aquest fet ha dut a una experiència pilot en la qual l’autoritat central ha estat substituïda per un conjunt de petits algorismes locals de control, que actuant simultàniament i en paral.lel sobre diferents zones de la xarxa poden obtenir un control global sobre el conjunt total de la xarxa.

2 Criticalitat autoorganitzada

Una de les hipòtesis fonamentals de la teoria de la complexitat diu que la selecció natural porta els sistemes complexos adaptatius cap a la frontera entre l’ordre i el caos, allà on la capacitat de produir-se canvis és gran, però on també és present, d’alguna manera, l’ordre. En aquets casos la dinàmica dels sistemes pot estudiar-se en termes d’un estat d’equilibri trencat per esdeveniments de petita magnitud. Durant aquests últims anys s’ha començat a comprendre com aquests sistemes que se situen en el límit entre l’ordre i el caos, denominada criticalitat autoorganitzada, poden generar un comportament complex que els permet adaptar-se de la forma més convenient als seus diferents entorns. El que es busca és una mena de contrapunt a la segona llei de la termodinàmica (que afirma que l’entropia de l’univers augmenta), una llei matemàtica que indiqui sota quines condicions poden aparèixer pautes de comportament autoorganitzat, una teoria que expliqui què és exactament la complexitat, per què apareix espontàniament i per què els sistemes naturals adaptatius semblen evolucionar cap a aquesta frontera entre l’ordre i el caos.

Molts sistemes complexos adaptatius poden patir grans catàstrofes no només sota l’efecte de forces externes de gran magnitud, sinó també a causa de fenòmens insignificants però que són capaços de provocar allaus de qualsevol mida entre els elements que formen el sistema. D’aquesta manera, dins dels grans sistemes complexos adaptatius poden produir-se reaccions en cadena de qualsevol mida. Aquestes reaccions en cadena normalment no produeixen catàstrofes, però de vegades poden afectar a un gran nombre d’elements del sistema, originant aleshores allaus de caràcter global i que encara que poden alterar l’aspecte extern del sistema, no influeixen per norma general en la descripció de les seves propietats fonamentals. En molts d’aquests sistemes, a més, s’ha vist que el nombre de grans esdeveniments augmenta, normalment de forma potencial, amb el nombre de petits allaus. En aquests sistemes complexos adaptatius els mecanismes que governen els petits esdeveniments són, així, els mateixos que guien els grans fenòmens. Aquests mecanismes són deguts, a més, a la mateixa estructura del sistema i no depenen de cap tipus de factor extern al sistema. Tampoc aquests sistemes no assoleixen mai cap estat d’equilibri, sinó que evolucionen des de determinats estats metaestables (on els allaus són de petita magnitud) cap a d’altres estats metaestables, tot això, com ja hem esmentat, sense la necessitat de cap força externa que actuï sobre el sistema complex adaptatiu.

Glenn A. Hell i els seus col.laboradors han dissenyat un sistema, la pila de sorra, que representa perfectament el comportament essencial de la criticalitat autoorganitzada (veieu [8, 9]). En la pila de sorra s’afegeix de forma uniforme, gra per gra, sorra sobre una superfície plana. Quan els grans comencen a caure es distribueixen primer sobre la superfície, però a mesura que es van afegint més grans, aquests es van amuntegant els uns a sobre dels altres, generant un munt el pendent del qual augmenta a poc a poc, fins a assolir un pendent final d’equilibri. Quan el pendent supera aquest punt s’originen allaus de diverses mides que retornen la pila al seu estat d’equilibri, mentre que quan és més petit que el pendent d’equilibri deixen de produir-se esllavissaments fins que el pendent retorna de nou al seu punt crític.

Tal com hem vist en la introducció, l’objectiu d’aquest treball ha estat el reconeixement, sota unes condicions determinades, de la possible aparició de la criticalitat autoorganitzada en les grans xarxes d’interconnexió. Amb aquest objectiu hem considerat diverses xarxes i hi hem aplicat un model, ideat per Bak i d’altres [7], emprat per estudiar sistemes biològics i que ha demostrat generar estructures amb criticalitat autoorganitzada.

3 El model de Per Bak

És possible establir connexions i analogies entre els sistemes biològics evolutius i les grans xarxes d’interconnexió, bàsicament referents a que tots dos estan formats per un determinat nombre d’elements interrelacionats, el comportament dels quals pot alterar el desenvolupament dels elements veïns. D’aquesta manera es podria suposar, tal com s’esdevé en molt sistemes complexos de la natura, i sota circumstàncies determinades, l’evolució d’algunes grans xarxes d’interconnexió vers estats de criticalitat autoorganitzada. Un bon exemple d’això que acabem de dir és el fet que ja hem esmentat abans que va passar a Washington, on un únic error en un dígit d’un algorisme rutinari va causar la fallida de gran part de la xarxa. Així, per tal d’estudiar la hipotètica aparició de criticalitat autoorganitzada en les grans xarxes d’interconnexió, que aquí presentem modelades com a grafs, hem pres el model evolutiu de Per Bak i l’hem aplicat sobre diferents tipus de grafs, comprovant com efectivament és possible l’aparició de la criticalitat autoorganitzada en les grans xarxes d’interconnexió. Evidentment, el model de Bak no recrea exactament el comportament de qualsevol xarxa de comunicació, però sí que recull alguns dels seus trets més importants (i bàsicament la interacció entre les diferents unitats interconnectades). Així, el que hem fet ha estat aplicar el següent algorisme a diferents xarxes.

1. Es considera un graf concret, que modela una xarxa donada, amb N vèrtexs etiquetats.

2. A cadascun dels vèrtexs se li assigna un nombre aleatori distribuït uniformement entre 0 i 1.

3. D’entre tots els vèrtex, es determina el de valor més petit, i a continuació s’actualitzen aquest vèrtex i els seus adjacents, assignant-los-hi nous valors aleatoris distribuïts uniformement entre el 0 i el 1.

4. El pas anterior es repeteix successivament, fins que el sistema convergeix cap a un estat de criticalitat autoorganitzada.

Figure 1: Graf de doble pas fix de vuit vèrtexs

En el nostre cas, i per analogia amb el model biològic de Per Bak, hem estudiat primer l’evolució d’aquest algorisme sobre grafs de doble pas fix, com el que mostra la figura 1. Més endavant hem aplicat el nostre model a xarxes amb estructura d’hipercub i a xarxes generades aleatòriament. En tots els casos han emergit pautes de comportament complex i de criticalitat autoorganitzada, tal com passava en el model biològic de Per Bak.

Els nombres aleatoris assignats als vèrtexs poden representar d’aquesta manera l’aptitud de cadascun dels sistemes que formen la xarxa. Cada pas o interacció del model representa, d’altra banda, la detecció del vèrtex amb pitjor funcionament i la seva modificació i la dels seus veïns.

4 Resultats

S’han realitzat en aquest treball diferents simulacions en màquines SUN i HP Apollo; principalment sobre grafs grans de, típicament, 1000 a 10000 vèrtexs. S’han estudiat de forma exhaustiva grafs de doble pas fix de 1000 vèrtexs. Així mateix s’han realitzat estadístiques sobre hipercubs H_{10} i sobre grafs regulars generats aleatòriament d’ordre 1000 i grau 10 (és a dir, de 1000 vèrtexs, cadascun d’ells connectats a 10 vèrtexs veïns). En l’estudi dels diferents paràmetres s’han realitzat estadístiques sobre diferents grafs i execucions, de tal manera que els resultats experimentals s’han tret bàsicament de poblacions d’uns cent individus. El temps total equivalent de CPU ha estat d’aproximadament uns tres messos.

La xarxa d’interconnexió concreta que hem pres al començament d’aquest estudi és, així, una xarxa de doble pas fix amb 1000 vèrtexs. El que hem fet ha estat aplicar sobre aquest graf l’algorisme de Per Bak i determinar la possible emergència de criticalitat autoorganitzada. Tres pautes típiques que indiquen l’aparició de criticalitat autoorganitzada en un sistema complex determinat són la fractalitat espaial, la distribució potencial dels esdeveniments i el soroll flicker del senyal temporal que estudia l’evolució del sistema.

Així, la figura 2 mostra l’evolució temporal de la situació del pitjor vèrtex. Es pot observar en ella com, un cop ha convergit el sistema, el pitjor vèrtex se situa durant períodes més o menys llargs de temps en les mateixes zones del graf, però que en determinats moments poden haver-hi salts de gran amplada, desplaçant-se en aquests casos el pitjor a zones llunyanes. D’això en diem formació de clusters: un cluster és la zona de l’espai on durant aquests períodes es concentren els vèrtexs pitjors de la xarxa. Un canvi de l’escala temporal ens indica que els clusters es distribueixen en l’espai amb una geometria fractal (és a dir, podem trobar formacions de clusters dins de clusters de major rang, i així successivament fins a arribar a una escala determinada que depèn del graf estudiat en cada moment).

A més, l’anàlisi espectral d’aquest senyal ha resultat tenir una característica 1/f, coneguda com soroll flicker, i que és un dels patrons típics de reconeixement de la criticalitat autoorganitzada. El soroll flicker és també indicatiu d’una correlació molt forta entre els esdeveniments passats i l’estat actual del sistema (al contrari del soroll blanc). Aquest és un tret caracterísitc del nostre model ja que per estudiar l’estadística del sistema en

Figure 2: Evolució de la situació del pitjor a dins del graf

un moment determinat cal conèixer tots els estats passats dels sistema. D’altra banda, el soroll flicker també es pot entendre com indicador de la presència d’esdeveniments de totes mides, que, com ja hem dit abans, és un altre dels paràmetres propis de la criticalitat autoorganitzada.

Un altre aspecte important ha estat l’estudi de l’evolució temporal del valor mig dels vèrtexs del graf. Per a això hem considerat tots els vèrtexs i hem promitjat els seus valors en cada instant, estudiant com variaven al llarg del temps. Com es pot observar en la gràfica 2, el valor mig de la població va augmentant fins assolir un valor de convergència, on el sistema va patint petites fluctuacions que, no obstant, sempre retornen tard o d’hora al valor d’equilibri. Així, quan la xarxa ha convergit i de forma aleatòria supera, o empitjora, el seu valor d’equilibri, es produeix un reajustament que la retorna sempre a la seva posició de convergència, tal com succeeix en la pila de sorra quan el pendent es desvia del punt crític.

Aquest comportament es pot entendre si es pensa en el mecanisme que hem aplicat sobre cadascun dels grafs. A cada instant hem pres el pitjor vèrtex i li hem assignat un nou valor. En aquest cas és de suposar que la major part de les vegades s’haurà introduït una millora. D’altra banada, però, també canviarem els valors dels vèrtexs adjacents al pitjor. En un començament de vegades els millorarem i d’altres els empitjorarem. Però a mesura que avança el temps s’anirà produint una millora en aquests vèrtexs que farà que al final, quan els assignem nous valors, aquests siguin normalment més baixos que els

Figure 3: Evolució de la mitjana de la població

antics. D’aquesta forma, arribarà un punt en el qual la millora introduïda en el vèrtex pitjor quedarà contrarrestada per l’empitjorament dels vèrtexs adjacents. En aquest cas el model haurà convergit.

Figure 4: Distribució estadística de la longitud dels clusters

D’altra banda hem estudiat també la distribució estadística dels clusters. Els dos aspectes més importants eren la longitud temporal dels diferents clusters i la seva amplitud (la distància entre els dos vèrtexs més allunyats dins d’un mateix cluster). De la representació en eixos logarítmics es dedueix que la distribució de la longitud segueix una llei potencial (un altre dels patrons de la criticalitat autoorganitzada) mentre que l’amplitud segueix també una distribució potencial decreixent fins a un cert punt on presenta un màxim local, per després tornar a decréixer. D’aquesta forma, tal com era d’esperar en un model amb criticalitat autoorganitzada, el nombre de clusters de petita longitud és molt més gran que el nombre de clusters amb longitud superior, i a més ambdues magnituds estan relacionades per una llei potencial.

Hem estudiat també d’altres estadístiques que el nostre model ha generat. Així hem mesurat la distribució del valor del pitjor (amb forma lineal i decreixent) i la de la població (totalment plana entre un valor determinat i 1). Hem estudiat així mateix el temps de convergència que, com era d’esperar, és directament proporcional al nombre de vèrtexs del graf, i el valor de convergència final en funció del nombre de vèrtexs del graf i del grau (que és el nombre de veïns de cada vèrtex). Les xarxes d’interconnexió amb pocs vèrtexs evolucionen cap a estats d’adaptabilitat més baixos que les xarxes molt poblades. D’altra banda, en augmentar el nombre de veïns de cada node, el valor de convergència també disminueix, en aquest cas d’una manera dràstica. Això, com ja hem dit, és degut a que un cop el model ha convergit, quan assignem nous valors als veïns del pitjor normalment els estarem empitjorant. De tal manera que quan més veïns hi hagi més gran serà l’empitjorament i més petit, per tant, el valor final de convergència.

Tots aquests resultats no han variat substancialment quan hem canviat l’estructura dels grafs estudiats o la distribució dels nombres generats aleatòriament. Un punt important, no obstant, ha estat la comprovació de que en l’hipercub el valor final de convergència de la població ha estat més baix que en el graf de doble pas fix. Això és degut a que en aquests últims els vèrtexs adjacents comparteixen molts dels seus veïns, la qual cosa no passa en l’hipercub. D’aquesta manera normalment, quan s’assignaven nous valors als veïns del pitjor, aquests vèrtexs ja havien estat veïns del pitjor en les anteriors iteracions, amb la qual cosa l’empitjorament global quedava esmorteït, ja que estàvem assignant valors baixos a vèrtexs amb valors baixos (perquè anteriorment ja els havíem modificat).

5 Conclusions

En primer lloc, el nostre model és un exemple característic de com a partir d’un algorisme tan senzill com el considerat, es pot produir un comportament complex, amb un conjunt de lleis que expliquen diferents aspectes de l’evolució del sistema. Aquesta és una pauta que es repeteix contínuament a la natura, on a partir de regles no gaire complicades es Figure 5: Distribucions estadístiques del valor del pitjor i de la mitjana de la població

poden produir comportaments extremadament complexos (i hom podria pensar també en el propi univers, la riquesa i complexitat del qual deriva, teòricament, d’unes poques equacions que es poden expressar sense grans complicacions). El fet, que potser semblarà trivial, és important per comprendre el veritable abast i la importància real de la teoria de la complexitat i els sistemes que estudia.

D’altra banda, en aquest treball s’ha fet una primera aproximació a l’aparició d’estructures amb criticalitat autoorganitzada en les grans xarxes d’interconnexió. Per això ens hem basat en un model biològic que ha estat aplicat sobre diferents tipus de grafs i que ha produït pautes de comportament autoorganitzatiu. Això fa pensar que possiblement per a models més realistes que no pas el nostre també poden aparèixer pautes d’aquest tipus, la qual cosa seria d’interès ja que permetria una primera aproximació a l’estudi de les grans xarxes de comunicació des del punt de vista de la teoria de la complexitat; això no només significaria un estudi més exacte, sinó que a més permetria el disseny de controladors de xarxes basats en la distribució de responsabilitats i en el paral.lelisme algorísmic.

Dels nostres resultats hem pogut, a més, extreure algunes conclusions que permeten obtenir diferents criteris a l’hora d’avaluar i fins i tot dissenyar diferents xarxes de comunicació. Evidentment els resultats només són qualitatius i a més, degut a que el nostre model no era totalment realista, orientatius. D’aquesta manera hem vist com en un moment determinat, i quan el grau dels grafs és baix l’augment del grau del graf (és a dir, la inclusió de noves branques o connexions entre vèrtexs) pot provocar un empitjorament dràstic de l’efectivitat global del sistema (si mesurem aquesta efectivitat a partir del valor mig de la població). Tanmateix, quan el grau dels vèrtexs és gran, l’augment del nombre de connexions no afecta pràcticament l’efectivitat global. D’altra banda hem vist com el sistema resultant posseïa la propietat de tenir una forta correlació amb els esdeveniments passats, la qual cosa, com ja hem dit, dificulta d’una manera especial un estudi purament teòric del model. Alguns teòrics de l’evolució diuen que qualsevol ésser viu recull, a través del seu codi genètic i mitjançant la selecció natural, l’aprenentatge útil que els seus avantpassats han recollit durant segles. Una cosa semblant passaria en el nostre model, on un esdeveniment actual incidirà de forma infinita (encara que cada cop més feble) sobre tots els instants futurs.

Un altre aspecte important ha estat la comprovació de com en estructures anàlogues a les nostres un criteri necessari de disseny faria fomentar la transitivitat en les xarxes. És a dir, des del punt de vista del nostre estudi, seria convenient que dos vèrtexs adjacents compartissin veïnatge. D’aquesta manera l’empitjorament que patirien a cada iteració els nodes veïns al pitjor es concentraria, per a una època determinada, en un nombre més reduït de vèrtexs, la qual cosa permetria un millor comportament global del sistema. Finalment també hem comprovat com les falles en una xarxa poden concentrar-se en àrees locals durant períodes relativament llargs per moure’s de sobte cap a zones llunyanes, on possiblement s’establiran nous clusters i d’on també, tard o d’hora, escaparà el vèrtex pitjor per establir-se en noves zones de la xarxa.

S’han descrit, així mateix, d’altres lleis i expressions matemàtiques que relacionen diferents aspectes del model presentat. Tot això, però, no és més que un punt de partença. El que cal fer a partir d’aquí és aprofundir en l’estudi d’aquestes pautes i aconseguir reconèixer les estructures autoorganitzades que poden sorgir en les xarxes reals de comunicació; trobar algun tipus de llei que expliqui sota quines condicions exactes emergeixen pautes de criticalitat autoorganitzada, i saber preveure-les i fins i tot treure’n profit.

References

[1] Per Bak. Catastrophes and self-organized criticality. Comput. Phys., 5(4):430–433, 1991.

[2] Per Bak and Kan Chen. Self-organized criticality. Scientific American, 264(1):26–33, January 1991.

[3] Per Bak and Kim Sneppen. Punctuated equilibrium and criticality in a simple model of evolution. Phys. Rev. Lett., 71(24):4083–4086, December 1993.

[4] Per Bak and Chao Tang. Self-organized criticality. Phys. Today, 42:S27–S28, January 1989.

[5] Per Bak and Chao Tang. Self-organized criticality in the ‘game of life’. Nature, 342:780–782, December 1989.

[6] Kim Sneppen Henrik Flyvbjerg and Per Bak. Mean field theory for a simple model of evolution. Phys. Rev. Lett., 71(24):4087–4090, December 1993.

[7] Henrik Flyvbjerg Per Bak and Kim Sneppen. Can we model Darwin? New Scientist, 141(1916):36–39, March 1994.

[8] Russell Ruthen. Adapting to complexity. Scientific American, 268(1):110–117, January 1993.

[9] Douglas A. Halverson D.T. Jacobs Sara K. Grumbacher, Karen M. McEwen and John Lindner. Self-organized criticality: An experiment with sandpiles. Am. J. Phys., 61(4):329–335, April 1993.