access icon free Delay analysis of network coding nodes and Butterfly network employing stop-and-wait automatic repeat request

The delay characteristics of network coding nodes and Butterfly network are investigated. First, the probability mass function (PMF) of delay and the average delay of general network coding nodes having multiple input links and one output link are analysed. It can be shown that the PMF and average delay can be readily evaluated from the recursive equations derived. Then, the delay performance of the Butterfly network is investigated. Specifically, the authors consider four different scenarios in the context of the packets transmitted over the Butterfly network. The PMFs of delay as well as the average delays of these four scenarios are analysed and, correspondingly, a range of formulae are obtained. Finally, the delay performance of network coding nodes and Butterfly network is investigated based on the numerical results evaluated from the formulae derived. The authors studies demonstrate that network coding nodes embedded in a network generate a big impact on the network's delay performance. Usually, in a network including some network coding nodes, the longest path with some network coding nodes may be chosen for approximately estimating the network's average delay.

Inspec keywords: probability; automatic repeat request; network coding; hypercube networks

Other keywords: recursive equations; network average delay; network coding nodes; butterfly network; one output link; multiple input links; probability mass function; stop-and-wait automatic repeat request; delay analysis

Subjects: Other topics in statistics; Radio links and equipment; Codes; Protocols

References

    1. 1)
      • 1. Ahlswede, R., Cai, N., Li, S.Y.R., Yeung, R.W.: ‘Network information flow’, IEEE Trans. Inf. Theory, 2000, 46, (4), pp. 12041216 (doi: 10.1109/18.850663).
    2. 2)
      • 11. Barros, J., Costa, R., Munaretto, D., Widmer, J.: ‘Effective delay control in online network coding’. Proc. INFOCOM 2009, April 2009, pp. 208216.
    3. 3)
      • 13. Nguyen, D., Tran, T., Nguyen, T., Bose, B.: ‘Hybrid ARQ-random network coding for wireless media streaming’. Proc. Second Int. Conf. Communications and Electronics 2008, 4–6 June 2008, pp. 115120.
    4. 4)
      • 8. Chou, P.A., Wu, Y., Jain, K.: ‘Practical network coding’. Proc. 41st Annual Allerton Conf. Communication, Control, and Computing, 2003.
    5. 5)
      • 14. Sagduyu, Y., Ephremides, A.: ‘On broadcast stability of queue-based dynamic network coding over erasure channels’, IEEE Trans. Inf. Theory, 2009, 55, (12), pp. 54635478 (doi: 10.1109/TIT.2009.2032732).
    6. 6)
      • 5. Qin, Y., Yang, L.-L.: ‘Steady-state throughput analysis of network coding nodes employing stop-and-wait automatic repeat request’, IEEE/ACM Trans. Netw., 2012, 20, (5), pp. 14021411 (doi: 10.1109/TNET.2011.2178860).
    7. 7)
      • 9. Sundararajan, J.K., Shah, D., Médard, M.: ‘ARQ for network coding’. Proc. IEEE Int. Symp. Information Theory 2008, 6–11 July 2008, pp. 16511655.
    8. 8)
      • 4. Lun, D.S., Medard, M., Koetter, R., Effros, M.: ‘Further results on coding for reliable communication over packet networks’. Proc. Int. Symp. on Information Theory' 05, 4–9 September 2005, pp. 18481852.
    9. 9)
      • 2. Lun, D.S., Medard, M., Effros, M.: ‘On coding for reliable communication over packet networks’. Proc. 42nd Annual Allerton Conf. on Communication, Control, and Computing, September/October 2004.
    10. 10)
      • 12. Sundararajan, J.K., Sadeghi, P., Médard, M.: ‘A feedback-based adaptive broadcast coding scheme for reducing in-order delivery delay’. Workshop on Network Coding, Theory, and Applications 2009, June 2009, pp. 16.
    11. 11)
      • 7. Fragouli, C., Lun, D., Medard, M., Pakzad, P.: ‘On feedback for network coding’. Proc. 41st Annual Conf. Information Sciences and Systems 2007, 14–16 March 2007, pp. 248252.
    12. 12)
      • 3. Li, S.Y.R., Yeung, R.W., Cai, N.: ‘Linear network coding’, IEEE Trans. Inf. Theory, 2003, 49, (2), pp. 371381 (doi: 10.1109/TIT.2002.807285).
    13. 13)
      • 10. Sundararajan, J.K., Shah, D., Médard, M.: ‘Online network coding for optimal throughput and delay – the two-receiver case’, Int. Symp. on Information Theory and its Applications, ISITA 2008, Auckland, New Zealand, December 2008, pp. 16.
    14. 14)
      • 6. Lin, S., Costello, D.J.: ‘Error Control Coding’ (Prentice-Hall, Upper Saddle River, New Jersey, 2004, 2nd ed.).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2012.0294
Loading

Related content

content/journals/10.1049/iet-com.2012.0294
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading