DZ
DefZone.Net

Kien thuc cong nghe & giai tri

  1. Home
  2. Wiki

Alternating bit protocol (ABP) is a simple network protocol operating at the data link layer (OSI layer 2)[citation needed] that retransmits lost or corrupted messages using FIFO semantics. It is the foundational form of a stop-and-wait ARQ, which is the simplest possible implementation of a sliding window protocol, where a simple timer restricts the order of messages to ensure receivers send messages in turn while using a window of 1 bit.[1]

History

[edit]

Donald Davies' team at the National Physical Laboratory introduced the concept of an alternating bit protocol in 1967 for the proposed NPL network and published their work in 1968 and 1969.[2][3] An ABP was used by the ARPANET and by the European Informatics Network.[4][5][6]

Bounded Retransmission Protocol (BRP) is a variant of the alternating bit protocol introduced by Philips in the mid-1970s.[7]

Design

[edit]

Messages are sent from transmitter A to receiver B. Assume that the channel from A to B is initialized and that there are no messages in transit. Each message from A to B contains a data part and a one-bit sequence number, i.e., a value that is 0 or 1. B has two acknowledge codes that it can send to A: ACK0 and ACK1.

When A sends a message, it resends it continuously, with the same sequence number, until it receives an acknowledgment from B that contains the same sequence number. When that happens, A complements (flips) the sequence number and starts transmitting the next message.[8]

When B receives a message that is not corrupted and has sequence number 0, it starts sending ACK0 and keeps doing so until it receives a valid message with number 1. Then it starts sending ACK1, etc.

This means that A may still receive ACK0 when it is already transmitting messages with sequence number one. (And vice versa.) It treats such messages as negative-acknowledge codes (NAKs). The simplest behaviour is to ignore them all and continue transmitting.

The protocol may be initialized by sending bogus messages and acks with sequence number 1. The first message with sequence number 0 is a real message.

Bounded Retransmission Protocol

[edit]

The service it delivers is to transfer in a reliable manner, if possible, large files (sequence of data of arbitrary length) from a sender to a receiver. Unlike ABP, BRP deals with sequence numbers of datum in the file and interrupts transfer after fixed number of retransmissions for a datum.[9]

See also

[edit]

References

[edit]
  1. ^ Tel, Gerard (2000). Introduction to distributed algorithms. Cambridge. p. 85. ISBN 0521794838.
  2. ^ Cambell-Kelly, Martin (1987). "Data Communications at the National Physical Laboratory (1965-1975)". Annals of the History of Computing. 9 (3/4): 221–247. doi:10.1109/MAHC.1987.10023. S2CID 8172150.
  3. ^ "The Alternating Bit Protocol" (PDF). The protocol, which can be traced back to Bartlett et al. [BSW69]
  4. ^ Davies, Donald Watts (1979). Computer networks and their protocols. Internet Archive. Chichester, [Eng.]; New York : Wiley. pp. 206.
  5. ^ "ARPANET is now 50 years old | Inria". www.inria.fr. Retrieved November 10, 2022.
  6. ^ Brügger, Niels; Goggin, Gerard (October 25, 2022). Oral Histories of the Internet and the Web. Taylor & Francis. ISBN 978-1-000-79781-7.
  7. ^ Burnett, D.J.; Sethi, H.R. (1977). "Packet Switching at Philips Research Laboratories". Computer Networks. 1 (6): 341–348. doi:10.1016/0376-5075(77)90010-1. Archived from the original on October 20, 2013. Retrieved August 30, 2013.
  8. ^ This article is based on material taken from Alternating+bit+protocol at the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.
  9. ^ "TreX's Examples -- Bounded Retransmission Protocol". www.irif.fr.

Further reading

[edit]
  • E. Rich, Automata, computability and complexity: theory and applications. Upper Saddle River, NJ: Pearson Prentice Hall, 2008.
  • K. A. Bartlett, R. A. Scantlebury, and P. T. Wilkinson, “A note on reliable full-duplex transmission over half-duplex links,” Commun. ACM, vol. 12, no. 5, pp. 260-261, May 1969
  • W. C. Lynch, “Reliable full-duplex file transmission over halfduplex telephone lines,” Commun. ACM, vol. 11, no. 6, pp. 407 410, June 1968.
  • I. Suzuki, "Formal analysis of the alternating bit protocol by temporal Petri nets," in IEEE Transactions on Software Engineering, vol. 16, no. 11, pp. 1273-1281, Nov 1990. doi: 10.1109/32.60315
  • Gildea, K.J.; Krishnamoorthy, M.S. (1992). "Modular Protocol Nets: The Alternating Bit Protocol Example". Proceedings of the Third International Conference on Computer Integrated Manufacturing. IEEE: 86–95. doi:10.1109/CIM.1992.638998. ISBN 978-0-8186-2615-9.
  • Berthomieu, B., Diaz, M., “Modeling slid Verification of Time Dependent Systems Using Time Petri Nets,” IEEE Transactions on Software Engineering, March 1991.
[edit]