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

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

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    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)
      • 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.
    3. 3)
      • 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).
    4. 4)
      • 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.
    5. 5)
      • 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).
    6. 6)
      • 6. Lin, S., Costello, D.J.: ‘Error Control Coding’ (Prentice-Hall, Upper Saddle River, New Jersey, 2004, 2nd ed.).
    7. 7)
      • 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.
    8. 8)
      • 8. Chou, P.A., Wu, Y., Jain, K.: ‘Practical network coding’. Proc. 41st Annual Allerton Conf. Communication, Control, and Computing, 2003.
    9. 9)
      • 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.
    10. 10)
      • 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.
    11. 11)
      • 11. Barros, J., Costa, R., Munaretto, D., Widmer, J.: ‘Effective delay control in online network coding’. Proc. INFOCOM 2009, April 2009, pp. 208216.
    12. 12)
      • 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.
    13. 13)
      • 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.
    14. 14)
      • 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).

Related content

This is a required field
Please enter a valid email address