Random linjära nätkoder kan utformas och genomföras på ett distribuerat sätt, med låg beräknings komplexitet. Dessa koder tillämpas dock klassiskt [1] över ändliga fält vars storlek beror på vissa globala nätverksparametrar (nätets storlek, antalet sänkor) som kan vara okända före kodkonstruktionen. Dessutom kan hela nätverkskoden behöva omformas när en ny nod ansluter sig. I detta arbete presenterar vi de första universella och robusta distribuerade linjära nätverkskodningssystemen. Våra system är universella eftersom de är oberoende av alla nätverksparametrar. De är robusta eftersom om noder går eller lämnar, de återstående noderna behöver inte ändra sin kodning verksamhet och mottagarna kan fortfarande avkoda. De distribueras eftersom noder behöver endast ha topologisk information om den del av nätverket uppströms av dem, som naturligt kan strömmas som en del av kommunikationsprotokollet. Vi presenterar både probabilistiska och deterministiska system som alla är asymptotiskt hastighetsoptimala i kodblockets längd, och har garantier för korrekthet. Våra probabilistiska konstruktioner är beräkningseffektiva, med ordningsoptimal komplexitet. Våra deterministiska konstruktioner garanterar noll felavkodning, om än via koder med hög beräknings komplexitet i allmänhet. Våra kodningssystem bygger på nätkoder över "skalbara fält". I stället för att välja kodningskoefficienter från ett fält vid varje nod som i [1] använder varje nod linjär kodningsverksamhet över en "effektiv fältstorlek" som beror på nodens avstånd från källnoden. Analysen av våra system kräver tekniska verktyg som kan vara av oberoende intresse. I synnerhet generaliserar vi Schwartz-Zippel lemma [2] genom att bevisa en icke enhetlig version, vari variabler väljs från uppsättningar av möjligen olika storlekar. Vi tillhandahåller också en ny robust distribuerad algoritm för att tilldela unika ID till nätverksnoder. Paradigmet för nätkodning gör det möjligt för varje nod i ett nätverk att bearbeta information på ett icke-trivialt sätt. Som visas i [3], [4], [5], Om mellanliggande noder helt enkelt utföra linjära operationer över vissa ändliga fält, kan de resulterande nätkoder vara hastighetsoptimal för en stor klass av kommunikationsproblem. I synnerhet algoritmer som genererar koder för multicast kommunikationsproblem, där var och en av flera sänkor kräver samma information från en källa nod, har varit välstuderade. Beräkningsmässigt effektiv deterministisk [6], [7] och probabilistisk [1], [8] utformning av sådana koder finns. För alla nuvarande nätföreskrifter krävs dock viss information om nätverksparametrar för att bestämma storleken på upphovsmännen är listade i alfabetisk ordning.
Referensreferensreferensen diskuterade påverkan av att ansluta noder i nätverket.
Universal and robust distributed network codes
{'venue': '2011 Proceedings IEEE INFOCOM', 'journal': '2011 Proceedings IEEE INFOCOM', 'mag_field_of_study': ['Mathematics', 'Computer Science']}