Scaling laws for line networks: from zero-error to min-cut capacity. Niesen, U., Fragouli, C., & Tuninetti, D. ISIT, 2006.
abstract   bibtex   
We consider communication through a cascade of $L$ identical Discrete Memory less Channels (DMCs).The source and destination node are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of $N$ symbols.It is well known that for any $L$ and $N{\}toınfty$ the relays can use a capacity achieving code and communicate reliably as long as the rate of this code is below the capacity of the underlying DMC. The capacity of the cascade is hence equal to the network \em min-cut capacity.For finite $N$ and $L{\}toınfty$, we showed in previous work that the optimal intermediate processing is the highest rate zero-error code of length $N$ for the underlying DMC.The capacity of the cascade coincides with the rate of this zero-error code, and is always below the \em zero-error capacity.In this work, we characterize how $N$ must scale with $L$ in order to achieve rates in between the zero-error and the min-cut capacity.In particular, we have observed that $N = {\}Theta({\}log L)$ is \em sufficient to achieve any rate below the min-cut capacity. Here, we develop a novel upper bound on the capacity of cascades with optimal intermediate processing that applies for any $(N,L)$ pairs and use it to show that $N = {\}Theta({\}log L)$ is \em necessary to achieve certain rates above the zero-error capacity. Furthermore, we propose a method to evaluate our upper bound by establishing a connection with the Set-Cover Problem in algorithms.
@article{niesen_scaling_2006,
 abstract = {We consider communication through a cascade of \$L\$ identical Discrete Memory less Channels (DMCs).The source and destination node are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of \$N\$ symbols.It is well known that for any \$L\$ and \$N{\textbackslash}toınfty\$ the relays can use a capacity achieving code and communicate reliably as long as the rate of this code is below the capacity of the underlying DMC. The capacity of the cascade is hence equal to the network {\textbackslash}em min-cut capacity.For finite \$N\$ and \$L{\textbackslash}toınfty\$, we showed in previous work that the optimal intermediate processing is the highest rate zero-error code of length \$N\$ for the underlying DMC.The capacity of the cascade coincides with the rate of this zero-error code, and is always below the {\textbackslash}em zero-error capacity.In this work, we characterize how \$N\$ must scale with \$L\$ in order to achieve rates in between the zero-error and the min-cut capacity.In particular, we have observed that \$N = {\textbackslash}Theta({\textbackslash}log L)\$ is {\textbackslash}em sufficient to achieve any rate below the min-cut capacity. Here, we develop a novel upper bound on the capacity of cascades with optimal intermediate processing that applies for any \$(N,L)\$ pairs and use it to show that \$N = {\textbackslash}Theta({\textbackslash}log L)\$ is {\textbackslash}em necessary to achieve certain rates above the zero-error capacity. Furthermore, we propose a method to evaluate our upper bound by establishing a connection with the Set-Cover Problem in algorithms.},
 type={4},
 author = {Niesen, U. and Fragouli, C. and Tuninetti, D.},
 journal = {ISIT},
 tags = {network_coding},
 title = {Scaling laws for line networks: from zero-error to min-cut capacity},
 year = {2006}
}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021