Abstract -Vi presenterar en ny randomiserad nätkodningsmetod för robust, distribuerad överföring och komprimering av information i nätverk, och visar på dess fördelar jämfört med routing-baserade metoder. Vi presenterar en randomiserad nätkodningsmetod för robust, distribuerad överföring och komprimering av information i nätverk. Nätverksnoder överför på varje utgående länk en linjär kombination av inkommande signaler, specificerade av oberoende och slumpmässigt valda kodkoefficienter från vissa ändliga fält F. Den enda information som behövs för att avkoda en t-mottagare är den totala linjära kombinationen av källprocesser som finns i var och en av deras inkommande signaler. Denna information kan behållas, för varje signal i nätverket, som en vektor av koefficienter för var och en av källprocesserna, och uppdateras genom varje kodning nod tillämpa samma linjära kombinationer t o koefficientvektorer som för data. Se [l], [3] för tidigare arbete med nätkodning [4] för arbete med slumpmässig routing och [2] för stödjande resultat som används i våra bevis. Vi ger en lägre gräns på framgångsannolikheten för slumpmässiga nätverkskodning för multicast-anslutningar, baserat på formen av överföringsmatris determinant polynom [3], som är hårdare än Schwartz-Zippel bundet för allmänna polynom av samma totala grad. Motsvarande övre gräns vid felsannolikhet är i storleksordningen omvänt av storleken på det finita fältet, vilket visar att det kan göras godtyckligt litet genom kodning i ett tillräckligt stort ändligt fält, och att det minskar exponentiellt med antalet kodord bitar. Detta tyder på att slumpmässiga koder är potentiellt mycket användbara för nätverk med okända eller föränderliga topologier. Vi modellerar ett nätverk som en delay-free acyklisk graf med enhetskapacitet riktade länkar" och en eller flera diskreta källor.  Randomiserad kodning kan strikt överträffa routing i vissa distribuerade inställningar. För illustration, överväga problemet med att skicka två processer från en källa nod till mottagare noder på slumpmässiga okända platser på ett rektangulärt rutnät, med hjälp av en distribuerad överföringsschema som inte involverar ~ ~ 'Vår modell medger parallella länkar. 2d,d.v.s. Resultatet innehåller för nätverk där inte alla noder utför slumpmässig kodning, eller där signaler lägger till genom superposition på vissa kanaler all kommunikation mellan noder eller routingtillstånd. För att maximera sannolikheten för att någon mottagare nod kommer att få två separata meddelanden, det bästa som en nod med två inkommande länkar kan göra är att försöka bevara meddelandemångfald genom att skicka en inkommande signal på en av sina två utgående länkar med lika stor sannolikhet, och den andra signalen på den återstående länken. Vi härleder kombinatoriskt en övre gräns på routing framgångsannolikheten för en källa-mottagare par i termer av deras relativa rutnät platser, som överträffas av motsvarande lägre gräns för randomiserad kodning i tillräckligt stora ändliga fält. Dessa gränser visas i tabell 1. Vår lägre gräns för kodning framgång sannolikhet gäller för linjärt korrelerade källor, där effekten av randomiserade kodning kan ses som distribuerad kompression sker inom nätverket snarare än en t källorna. För en genomförbar multicast anslutningsproblem och en randomiserad kod av tillräcklig komplexitet, med stor sannolikhet den information som flödar över alla nedskärningar kommer att vara tillräcklig för att rekonstruera de ursprungliga källprocesserna. I själva verket komprimeras källinformationen till kapaciteten hos varje snitt som den passerar igenom. Detta uppnås utan behov av samordning mellan källnoder, vilket är fördelaktigt i distribuerade miljöer där sådan samordning är omöjlig eller dyr. Slutligen noterar vi att detta tillvägagångssätt uppnår stabilitet på ett sätt som skiljer sig helt från traditionella tillvägagångssätt. Traditionellt tillämpas kompression en t-källkod noder för att minimera nödvändig överföringshastighet och lämna reservnätskapacitet, och tillägg av nya källor kan kräva ombokning av befintliga anslutningar. Vår strategi utnyttjar fullt ut tillgänglig eller tilldelad nätverkskapacitet för maximal robusthet, samtidigt som vi behåller full flexibilitet för att hantera förändringar i nätverkstopologi eller tillägg av nya källor.
Ho et al. - Vad är det för fel på dig? REF har varit först med att föreslå begreppet slumpmässig nätkodning med hjälp av slumpmässiga linjära koder, där en mellanliggande nod överför en linjär kombination av inkommande meddelanden på varje utgående länk, som specificeras av oberoende och slumpmässigt valda kodkoefficienter över vissa finita fält.
The benefits of coding over routing in a randomized setting
{'venue': 'IEEE International Symposium on Information Theory, 2003. Proceedings.', 'journal': 'IEEE International Symposium on Information Theory, 2003. Proceedings.', 'mag_field_of_study': ['Computer Science']}