Alternating bit protocol: Difference between revisions

Revision as of 22:32, 22 August 2020

Latest revision as of 17:22, 6 August 2025

(15 intermediate revisions by 7 users not shown)

Line 3:

{{Use mdy dates|date = March 2019}}

'''Alternating bit protocol''' ('''ABP''') is a simple [[network protocol]] operating at the [[data link layer]] ([[OSI model|OSI]] layer 2){{cn|reason=this looks more like a transport layer protocol|date=April 2023}} that retransmits lost or corrupted messages using FIFO semantics. It can be seen as a special case 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.<ref>{{cite book|last=Tel|first=Gerard|title=Introduction to distributed algorithms|year=2000|publisher=Cambridge|isbn=0521794838|pages=85}}</ref>

== Design ==

[[Message]]s are sent from [[transmitter]] A to [[Receiver (information theory)|receiver]] B. Assume that the [[Communication channel|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 [[Negation|complements]] (flips) the sequence number and starts transmitting the next message.<ref name="foldoc">{{foldoc|Alternating+bit+protocol}}</ref>

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.

Line 16:

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 ===

A variant of this protocol, introduced by [[Philips]], is called [[Bounded Retransmission Protocol]] (BRP). Unlike ABP, BRP deals with sequence numbers of datum in the file and interrupts transfer after fixed number of retransmissions for a datum.<ref>{{cite web|url=https://www.irif.fr/~sighirea//trex/demos/brp.html|title=TreX's Examples -- Bounded Retransmission Protocol|website=www.irif.fr}}</ref>

'''Bounded Retransmission Protocol''' (BRP) is a variant of the alternating bit protocol introduced by [[Philips]].<ref>{{cite journal |last=Burnett |first=D.J. |author2=Sethi, H.R. |year=1977 |title=Packet Switching at Philips Research Laboratories |url=http://rogerdmoore.ca/PS/NPLPh/PhilipsA.html |url-status=dead |journal=Computer Networks |volume=1 |issue=6 |pages=341–348 |doi=10.1016/0376-5075(77)90010-1 |archive-url=https://web.archive.org/web/20131020142510/http://rogerdmoore.ca/PS/NPLPh/PhilipsA.html |archive-date=2013-10-20 |access-date=2013-08-30|url-access=subscription }}</ref> 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.<ref>{{cite web|url=https://www.irif.fr/~sighirea//trex/demos/brp.html|title=TreX's Examples -- Bounded Retransmission Protocol|website=www.irif.fr}}</ref>

== History ==

An[[Donald AlternatingDavies|Donald BitDavies']] team at the [[National Physical Laboratory (United Kingdom)|National Physical Laboratory]] introduced the concept of an alternating bit protocol in 1968 for the [[NPL network]].<ref name=":3">{{Cite journal |last=Cambell-Kelly |first=Martin |date=1987 |title=Data Communications at the National Physical Laboratory (1965-1975) |url=https://archive.org/details/DataCommunicationsAtTheNationalPhysicalLaboratory |journal=Annals of the History of Computing |language=en |volume=9 |issue=3/4 |pages=221–247 |doi=10.1109/MAHC.1987.10023 |s2cid=8172150}}</ref> An ProtocolABP was used by the [[ARPANET]] and by the [[Packet switching#EIN|European Informatics Network]].<ref>{{Cite book|last=Davies|first=Donald Watts|url=https://archive.org/details/computernetworks00davi|title=Computer networks and their protocols|date=1979|publisher=Chichester, [Eng.] ; New York : Wiley|others=Internet Archive|isbn=|___location=|pages=[https://archive.org/details/computernetworks00davi/page/206 206]|url-access=registration}}</ref><ref>{{Cite web |title=ARPANET is now 50 years old {{!}} Inria |url=https://www.inria.fr/en/arpanet-now-50-years-old |access-date=2022-11-10 |website=www.inria.fr |language=en}}</ref><ref>{{Cite book |last1=Brügger |first1=Niels |url=https://books.google.com/books?id=kqyJEAAAQBAJ&dq=gerard+le+lann+%22sliding+window%22+scheme&pg=PT82 |title=Oral Histories of the Internet and the Web |last2=Goggin |first2=Gerard |date=2022-10-25 |publisher=Taylor & Francis |isbn=978-1-000-79781-7 |language=en}}</ref>

==See also==

Line 29 ⟶ 30:

==References==

{{Reflist}}

{{refbegin}}

* {{FOLDOC}}

{{refend}}

{{DEFAULTSORT:Alternating Bit Protocol}}

[[Category:Network protocols]]

{{Telecomm-stub}}