Resumen de Stability in communication networks under adversarial models
Maria J. Blesa Aguilera
El treball de Borodin, et al. [Universal stability results for greedy contention-resolution protocols, JACM 48:39-69 2001], juntament amb la seva continuació per Andrews, et al. [Adversarial queueing theory, JACM 48:13-38 2001] fóra el punt de partida d'aquesta tesi. En aquests treballs es va presentar la Teoria Adversarial de Cues (AQT en anglès), per a l'estudi de la dinàmica de xarxes de commutació de paquets sota proveïdors de tràfic malèvols. Aquest fou un treball pioner en l'estudi de propietats de xarxes via l'anàlisi de cas pitjor. Els models previs utilitzaven assumpcions probabilistes per l'arribada de tràfic. L'AQT va reemplaçar aquestes assumpcions per escenaris de cas pitjor, apropant-se així a entorns de xarxa més realistes. L'AQT considera que un sistema es composa de tres components bàsics: la xarxa de commutació de paquets, el proveïdor adversarial de tràfic i un protocol que planifica la congestió als nodes.
Estabilitat és la propietat que garanteix que la quantitat de paquets que hi ha en el sistema està sempre afitada. Indirectament això també fa referència al tamany limitat de les cues intermèdies que guarden els paquets en circulació, així com a l'arribada a destí dels paquets. Més forta és la noció d'estabilitat universal de xarxes, que implica l'estabilitat de tot sistema composat per una determinada xarxa contra tot possible proveïdor de tràfic i protocol.
L'AQT s'ha aplicat a l'estudi de condicions que assegurin l'estabilitat de xarxes de commutació de paquets sota assumpcions de tràfic adversarial. L'objectiu d'aquesta tesi era aprofundir en el coneixement i compressió d'aquestes condicions. Quan vàrem començar al març de 2001 no es coneixien encara gaires resultats. Una de les nostres contribucions principals ha estat la caracterització de la propietat de l'estabilitat universal de xarxes. Hem trobat que diferents assumpcions pel que fa a la trajectòria que segueixen els paquets donen lloc a diferents caracteritzacions. En qualsevol cas, però, la propietat és decidible en temps polinòmic. Apart de la importància de la pròpia caracterització, aquests resultats ajudaren a aclarir algunes confusions existents en la literatura inicial sobre el tema.
Hem caracteritzat la propietat de l'estabilitat d'una xarxa sota alguns protocols coneguts. És interessant el fet que per alguns protocols aquesta caracterització coincideix amb la caracterització de l'estabilitat universal de xarxes. Això, apart d'assegurar la decidibilitat en temps polinòmic, estableix una forta relació entre totes dues propietats.
Per tal d'estudiar entorns més realistes hem incorporat fluxos de tràfic prioritzats, connexions susceptibles a fallada i asincronisme al model AQT original. Pel que fa a fluxos prioritzats hem proposat extensions del model per tractar tràfic amb paquets de diferents prioritats. Inspirats per la creixent importància de xarxes mòbils sense fils, hem introduït models adversarials per xarxes dinàmiques en les quals les connexions poden fallar. En aquests models l'adversari controla, a més de les injeccions de paquets, la fallada dels enllaços. Depenent de com restringim l'adversari en produir aquestes fallades i de com gestionem els paquets implicats en aquestes fallades, la estabilitat del sistema pot ser més o menys difícil d'assegurar. També hem estudiat models adversarials més generals que inclouen característiques tecnològiques específiques com ara amplades de banda, retards de propagació i paquets de tamany no unitari. Addicionalment, hem prescindit del sincronisme inherent a l'AQT i hem considerat sistemes asíncrons. Tot i que un model així és més general, el seu poder efectiu no és significativament diferent a l'AQT. Això fa que ens qüestionem com de complex ha de ser un model per tal de representar entorns reals de xarxes. Després de tot, potser un model relativament simple és suficient.
