A Trellis Connectivity Analysis of Random Linear Network Coding with Buffering

Author

Wu, Yunnan

Author_Institution

Microsoft Res., Redmond, WA

fYear

2006

fDate

9-14 July 2006

Firstpage

768

Lastpage

772

Abstract

Previous studies have proposed a practical network coding scheme for multicasting information in packet networks, which buffers received packets and outputs random linear mixtures of packets in the buffer. To analyze the performance of such a scheme, this paper introduces a continuous-time trellis, which models the packet transmissions in a practical asynchronous network. The continuous-time trellis represents an extension of a discrete-time trellis that was used in prior theoretical studies to model a synchronized network. The asymptotic throughput of the practical network coding scheme is characterized via an analysis of the asymptotic s-T connectivity in the trellis

Keywords

linear codes; multicast communication; random codes; trellis codes; asymptotic s-T connectivity; asynchronous network; continuous-time trellis; discrete-time trellis; information multicasting; packet networks; packet transmissions; random linear mixtures; random linear network coding; synchronized network; trellis connectivity analysis; Buffer storage; Delay; Galois fields; H infinity control; Network coding; Network topology; Performance analysis; Queueing analysis; Throughput; Web and internet services;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory, 2006 IEEE International Symposium on

Conference_Location

Seattle, WA

Print_ISBN

1-4244-0505-X

Electronic_ISBN

1-4244-0504-1

Type

conf

DOI

10.1109/ISIT.2006.261636

Filename

4036067