Stabilite d'un algorithme distribue de gradient local pour le routage dynamique de paquets

De
Publié par

Stabilite d'un algorithme distribue de gradient local pour le routage dynamique de paquets Florian Huc1 Christelle Molle2 Nicolas Nisse3 Stephane Perennes3 Herve Rivano4 1TCS-sensor lab, Universite de Geneve 2DRAKKAR, LIG, Grenoble 3MASCOTTE, I3S/INRIA, Sophia Antipolis 4SWING, CITI, Lyon JGA 2009 - 05/11/2009 (C. Molle) Stabilite LGG distribue gradient local 1 / 17

  • paquets ?

  • dynamique dans les reseaux

  • file d'attente

  • paquet

  • routage dynamique de proche en proche

  • gradient local

  • taille des files d'attente bornee


Publié le : mardi 19 juin 2012
Lecture(s) : 31
Source : lirmm.fr
Nombre de pages : 25
Voir plus Voir moins
C(loM.S)elirube´rgdaeitnoltabilit´eLGGdist7/1l1ca
JGA 2009 - 05/11/2009
3MASCOTTE, I3S/INRIA, Sophia Antipolis
4SWING, CITI, Lyon
1TCS-sevinUisrerosn,balve`eedt´eneG
2DRAKKAR, LIG, Grenoble
Stabilit´edunalgorithmedistribue´degradientlocalpour le routage dynamique de paquets
Florian Huc1Christelle Molle2Nicolas Nisse3 Ste´phaneP´erennes3eHvr´eRivano4
C(loM.t´liGGeL)Slebita2lacoltn
Notree´tude R´eseau`aledattente Algorithmedistribue´simple Routage dynamique de proche en proche suivant un gradient local Pert ´ entuelles de paquets es ev Stabilite´=tailledeslesdattenteborne´e
Dynamiquedanslesr´eseaux Utilisateurs/Infrastructure bougentr´seacilegoluoat Trafic : flot6= paquetsgestion des files d’attente Medium imparfaitperte de paquets
Introduction
71/buristdiieadgr´e
ilit´eLGlle)Stab´ugeariddGsirtbi173/
MultigrapheG= (V,E) :
S ⊂V: ensemble de sources
S-D-r´ ` file d’attente eseau a
tlenaloc
nœud
le
qt(vkce´psraetqutossrembpadeon:)
D ⊂V\ S: ensemble de destinations
t
l’instant
` a
v
(C.Mo
1
chaquelienpeuttransmettreauplus1paquet,quipeutˆetreperdu sansquel´emetteurnensoitinf´ orme.
chaques∈ Sinjectein(s) paquets dans sa file d’attente.
A chaque etape : ´
S-D-se´r`uaeleaatdnttee
71
3
chaqued∈ Dextrait min{qt(d),out(d)}paquets de sa file d’attente.
2
C.(llMoSte)ilabegradientlocal4/tie´GLdGsirtbi´u
Achaque´etape:
chaques∈ Sinjectein(s) paquets dans sa file d’attente.
chaquelienpeuttransmettreauplus1paquet,quipeuteˆtreperdu sansquelemetteurnensoitinform´e. ’´
1
2
chaqued∈ Dextrait min{qt(d),out(d)}paquets de sa file d’attente.
3
al4/17
S-D-r´esedtaettnae`uael
neidcolt´ubiargeGdLGtrisilab´eit)etSoMll(.C
)Staolle(C.Mcalontieadgr´ebuirtsidGGLe´tilib/1l4
S-Daualedattenter-e´es `
Achaque´etape:
7
1
2
chaques∈ Sinjectein(s) paquets dans sa file d’attente.
chaquelienpeuttransmettreauplus1paquet,quipeuteˆtreperdu sansquele´metteurnensoitinforme´.
chaqued∈ Dextrait min{qt(d),out(d)}paquets de sa file d’attente.
3
Ste)ilabC.(llMo
Aucoursdunee´tapet: 1qt(s) =qt1(s) +in(s),s∈ S 2uV,vΓ(u) : siqt(v)<qt(u),uvoen1pieueaqat`v siunapassasedzeseseia`neovte:sapuq|qt(u)|petits voisins silepaquetestperdu:nonajoute´a`laledev 3qt(d) =qt(d)min{out(d),qt(d)},d∈ D
Hypoth`eses R´eseausynchrone,full-duplex Informations locales : files des voisins Tourneind´ependammentenchaquenœud
17
LGG:algorithmedistribu´edegradientlocal
GdLG´eitu´ibtrisneidarge/5lacolt
atS)elloLe´tilibristdiGGadgr´ebuolaceitn7
Etat duS-D´ eau -res
Introduction`alastabilite´
6l1/
Stabilit´edeLGGsurG Sil´etatdure´seauresteborn´eaucoursdutemps:(Pt)tNboe.rn´e
Etat de l’art Stabilite´sitauxdarriv´ee<flot max [Tassiulas et Ephremides, IEEE Trans. Aut. Con. 1992] Stabilit´esitauxdarriveeflot max pour 1 destination ´ [Awerbuch etal, FOCS 2001]
Pt=Xqt2(v) vV
atSilibe´tuos#esrces/dnationtiesptreetlae´taioredespaquets(C.M
´ugearidneltcola6/17
Introductiona`lastabilit´e
Etat duS-Dese´r-ua
Stabilit´edeLGGsurG Sile´tatdur´eseauresteborne´aucoursdutemps:(Pt)tN.eoern´b
Etat de l’art Stabilite´sitauxdarrive´e<flot max [Tassiulas et Ephremides, IEEE Trans. Aut. Con. 1992] Stabilite´sitauxdarrive´eflot max pour 1 destination [Awerbuch etal, FOCS 2001]
´elititSbatessour#destces/tanisnoiepteaetreal´irtoesedqupa
Pt=Xqt2(v) vV
(.CoMll)etSbailit´eLGGdistrib
,s)=in(s)pourtodΦnaGstleuqΦes(o-´etrisalleabae´rasilelbd-s/17cal7
∪ {(s,s),
E
=
E
Grapheassocie´
G
= (V,E) avec :
V=V∪ {s,d}
e´rgirubtnoldaeit´libitastdiGGeLC(.SstuS)elloM.
d
D}
{(d,d
,s),
s
),
S}
uaese´r-D-S
G= (V,E) avec : V=V∪ {s,d} E=E∪ {(s,s),s∈ S} ∪ {(d,d),
d∈ D}
lacoltne
∈ S.
S-D-r´baellasirue´seae s-dliear´ot-snadΦelbasGtel que Φ(s,s) =in(s) pour touts
Grapheassoci´e
71/7(.CoMitilLG´ee)llabStge´uidarsidGbirt
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi

De j'ai essentiellement travaillé sous la direction du Professeur Günter Lumer sur la théorie des semi groupes dans l'espace des fonctions continues nulles l'infini muni de la norme du suprémum et ses applications aux EDP d'évolution du premier ordre en temps Pour répondre une demande de mathématiques plus appliquées des thésards et de certains collègues chimistes puis suite la disparition soudaine du professeur E Carton F P Ms ayant eu assumer en plus les suppléances d'analyse numérique l'U M H Introduction l'analyse numérique en seconde année C M: 45h T D: 45h Analyse Numérique C M 30h en troisième année puis ayant été nommé chargé de cours temps partiel en analyse numérique l'U M H du au j'ai donné dès une tournure numérique mes recherches méthode des éléments finis frontières extension de la notion du nombre de conditionnement au sens de R Skeel aux opérateurs en dimension infinie recherches sur la propagation des erreurs d'arrondis en arithmétique point flottant normalisé et application du produit scalaire précis un arrondi près l'évaluation précise équations de la thermoconvection de Boussinesq Depuis septembre date laquelle j'ai été nommé professeur des universités attaché l'U V H C je travaille pleinement sur les méthodes de résolutions numériques des EDP essentiellement sur la méthode mixte duale laquelle m'a initié le Professeur Mohamed Farhloul Université de Moncton Canada élève de M Fortin dans l'équipe EDP du laboratoire LAMAV anciennement: MACS et plus anciennement encore LIMAV dirigé par le Professeur Serge Nicaise J'ai aussi étudié récemment la méthode mixte duale pour des EDP d'évolution coefficients stochastiques

de chaeh