Alternating bit protocol: Difference between revisions

Revision as of 19:57, 12 March 2010

Latest revision as of 17:22, 6 August 2025

(48 intermediate revisions by 22 users not shown)

Line 1:

{{ContextUse American English|date = March 20082019}}

{{Short description|Type of data link layer protocol about transmission fidelity}}

{{NoUse footnotesmdy dates|date = March 20082019}}

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

{{Refimprove|date=March 2008}}

'''Alternating bit protocol''' (ABP) means a simple [[data link layer]] [[network protocol]] that retransmits lost or corrupted messages.

== Design ==

[[Message]]s are sent from [[transmitter]] A to [[receiverReceiver (Informationinformation Theorytheory)|receiver]] B. Assume that the [[Communication channel (communications)|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 character]]scodes that it can send to A: ACK0 and ACK1. We assume that the channel may corrupt a message and that there is a way in which A and B can decide whether or not they have received a correct message. How and to what extent that is possible is the subject of [[coding theory]].

When A sends a message, it sendsresends 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.

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 character]]scodes (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 ===

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

[[Donald Davies|Donald Davies']] 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 ABP was used by the [[ARPANET]] and by the [[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|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==

* [[Acknowledge character]]

* [[Information theory]]

* [[Negative-acknowledge character]]

* [[InformationStop-and-wait TheoryARQ]]

==References==

{{Reflist}}

{{No footnotes|date=March 2008}}

{{FOLDOC}}

{{DEFAULTSORT:Alternating Bit Protocol}}

[[Category:Network protocols]]

[[nl:Alternating bit protocol]]