Packet Transmission in a Noisy-Channel Ring Network
Victor C. Pestien, Subramanian Ramakrishnan, Dilip Sarkar · SIAM Journal on Computing · 1994
Assume that n stations, each with a buffer to hold only one packet at a time, are connected as a ring and that data packets are transmitted counterclockwise. A station will attempt to transmit a packet to the next station only if (i) it has a packet to send and (ii) the next station’s buffer is empty. The communication cannels connecting the stations are noisy, and there is a fixed probability $p(0 < p < 1)$ of error-free transmission of a packet from one station to the next in one attempt. An exact expression for the long-run average time for a packet to go around the ring is derived. (A special case of this answers a question raised by Berman and Simon in [Proc. 20th ACM Symp. on Theory of Computing, ACM Press, 1988, pp. 66–77].) For fixed n and p, the throughput of the system is maximum when the number of packets is an integer closest to ${n / 2}$.