skip to main content
article

Cycle-logical treatment for "Cyclopathic" networks

Published: 01 June 2006 Publication History

Abstract

This correspondence addresses the problem of finding the network encoding equations for error-free networks with multiple sources and sinks. Previous algorithms could not cope with cyclic networks. Networks that are cyclic in three different senses are considered in this correspondence, and two extensions of the polynomial time Linear Information Flow (LIF) algorithm are presented. The first algorithm will produce the network encoding equations for a network which can be cyclic, unless the actual flow paths form cycles. The second algorithm will work also when the flow paths form simple cycles. Finally an example of a third kind of cyclic network, where the previous algorithms will fail, is given. However, a binary encoding is provided also in this case.

References

[1]
{1} R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
[2]
{2} P. A. Chou, Y.Wu, and K. Jain, "Practical network coding," in Proc. 41st Annu. Allerton Conf. Comunication, Control, and Computing, Monticello, IL, Oct. 2003.
[3]
{3} D. S. Lun, M. Médard, and M. Effros, "On coding for reliable communication over packet networks," in Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, Sep./Oct. 2004.
[4]
{4} P. Sanders, S. Egner, and L. Tolhuizen, "Polynomial time algorithms for network information flow," in Proc. SPAA'03, San Diego, Jun. 7-9, 2003, pp. 286-294.
[5]
{5} S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1973-1983, Jun. 2005.
[6]
{6} C. Fragouli and E. Soljanin, "A connection between network coding and convolutional codes," in Proc. Int. Conf. Communications, Paris, France, Jun. 2004, pp. 661-666.
[7]
{7} S.-Y. R. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371-381, Feb. 2003.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue SI
Special issue on networking and information theory
June 2006
475 pages

Publisher

IEEE Press

Publication History

Published: 01 June 2006
Published in TON Volume 14, Issue SI

Author Tags

  1. cyclic networks
  2. multicasting
  3. network codes
  4. pipelining

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Pruning network coding traffic by network codingIEEE Transactions on Information Theory10.1109/TIT.2010.204085956:4(1909-1929)Online publication date: 21-Nov-2019
  • (2011)Robust network codes for unicast connectionsIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2010.209142419:3(644-656)Online publication date: 1-Jun-2011
  • (2009)Unified construction algorithm of network coding in cyclic networksProceedings of the 15th Asia-Pacific conference on Communications10.5555/1803074.1803242(686-690)Online publication date: 8-Oct-2009
  • (2009)Applying network coding to cyclic networksProceedings of the 28th IEEE international conference on Computer Communications Workshops10.5555/1719850.1719912(321-322)Online publication date: 19-Apr-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media