Abstract-CSMA-baserad schemaläggning är en nyligen föreslagna distribuerad schemaläggningsalgoritm som visas för att uppnå maximal genomströmning. Centralt för denna algoritm är en Markov kedja som producerar prover från en önskad distribution. I detta arbete diskuterar vi relationen mellan den uppnåeliga genomströmningen, köförseningen och blandningstiden för Markovkedjan i en variant av algoritmen. Detta resultat tyder på att en liten blandningstid är önskvärd för låg fördröjning. Vi diskuterar sedan hur en generisk gräns på blandningstiden kan stramas åt i specifika topologier. Som i [1], beskriver vi grundmodellen. Anta att det finns K-länkar i nätverket, där varje länk är ett (beställd) transmitter-mottagarpar. Nätverket är associerat med en konfliktgraf (eller "CG") G = {V, E}, där V är uppsättningen hörn (var och en av dem representerar en länk) och E är uppsättningen av kanter. Två länkar k 1 och k 2 kan inte överföra samtidigt (dvs. "konflikt") iff det finns en kant mellan dem, dvs. (k 1, k 2 ) E. Antag att G har N oberoende uppsättningar ("IS"). Observera att i'th är av en vektor Packets anländer till länk k med en hastighet λ k > 0. Låt λ  på R K vara vektorn för ankomsthastigheter. Vi säger att λ är genomförbar om och endast om λ = ip i x i för viss sannolikhet distributionp R N + uppfyller p i ≥ 0 och ip i = 1. Det vill säga, λ är en konvex kombination av de invaderande arterna, så att det är möjligt att betjäna den ankommande trafiken med ett visst sändningsschema. Ange vilken uppsättning av möjliga λ byC. Länkarna följer ett kontinuerligt CSMA-protokoll liknande det i [1]. Innan en sändning försöker, väntar sändaren av länk k (eller backs-off) under en slumpmässig tidsperiod som är exponentiellt fördelade med medel 1/R k och sedan känner av mediet. Om någon motstridande länk (dvs. någon länk m sådan att (k, m) E) sänder, sedan länk k startar en annan väntetid med samma distribution, men oberoende av föregående väntetider. Annars, länk k startar överföringen, vars varaktighet är exponentiellt distribueras med Detta arbete stöds av MURI anslag BAA 07-036.18. genomsnitt 1. Definiera r k := log(R k ) att vara "överföring aggressivitet" (TA) av länk k. Detta CSMA-protokoll leder till en Markov kedja bland den oberoende uppsättningen som kallas CSMA Markov kedjan. Eftersom r = (r k ) har den följande stationär distribution: där K är tillståndet för Markov-kedjan vid (kontinuerlig) tid t. Därefter anger x k (t) {0, 1} om länken k sänder vid tiden t. Tiden är uppdelad i slots, där varje kortplats har en varaktighet på en tidsenhet. Antag att ankomstpriserna λ är genomförbara, dvs. λ  på C. Betrakta följande schemaläggningsalgoritm som uppdaterar TA-parametrarna r. Algoritm 1: Schemaläggningsalgoritm med avgränsade kölängder 1) Inledningsvis, r k (0) = 0,  skak. Den verkliga kölängden Q k (0) = 0,  och k. Algoritmen uppdaterar r(j) varje T-tidsenhet (eller slots) där T är ett heltal. Inledningsvis j = 0. Rätta en konstant β > 0. (Vi hänvisar till intervallet mellan tiden jT och (j + 1)T som ram j där j = 0, 1,... ) 2) Använd r(j) i CSMA-operationen för T-tidsenheter. 3) Efter T-tidsenheter (dvs. i den (j + 1)-th uppdateringen), låt
Jiang m.fl. REF visar sambandet mellan den lilla blandningstiden och en låg fördröjning, och undersöker hur man kan strama åt den generiska gränsen för blandningstid för specifika topologier.
Performance bounds of distributed CSMA scheduling
{'venue': '2010 Information Theory and Applications Workshop (ITA)', 'journal': '2010 Information Theory and Applications Workshop (ITA)', 'mag_field_of_study': ['Computer Science']}