Alternating bit protocol - Revision history

imported>Whizz40: /* Further reading */ add url to reference

2025-12-28T11:11:29Z

Further reading: add url to reference

← Previous revision		Revision as of 11:11, 28 December 2025
Line 1:		Line 1:
			{{Short description\|Type of data link layer protocol about transmission fidelity}}
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	~~{{Short description\|Type of data link layer protocol about transmission fidelity}}~~
	{{Use mdy dates\|date = March 2019}}		{{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>		'''Alternating bit protocol''' ('''ABP''') is a simple [[network protocol]] operating at the [[data link layer]] ([[OSI model\|OSI]] layer 2){{citation needed\|reason=this looks more like a transport layer protocol\|date=April 2023}} 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.<ref>{{cite book\|last=Tel\|first=Gerard\|title=Introduction to distributed algorithms\|year=2000\|publisher=Cambridge\|isbn=0521794838\|pages=85}}</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 1967 for the proposed [[NPL network]] and published their work in 1968 and 1969.<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><ref>{{Cite web \|title=The Alternating Bit Protocol \|url=https://dspace.library.uu.nl/bitstream/handle/1874/840/c14.pdf \|quote=The protocol, which can be traced back to Bartlett et al. [BSW69]}}</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>

			'''Bounded Retransmission Protocol''' (BRP) is a variant of the alternating bit protocol introduced by [[Philips]] in the mid-1970s.<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 \|url-access=subscription \|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}}</ref>

	== Design ==		== Design ==
Line 17:		Line 22:

	=== Bounded Retransmission Protocol ===		=== 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>~~		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==		==See also==
Line 26:		Line 28:
	* [[Information theory]]		* [[Information theory]]
	* [[Negative-acknowledge character]]		* [[Negative-acknowledge character]]
	* [[Stop-and-wait ARQ]]

	==References==		==References==
	{{Reflist}}		{{Reflist}}

			=== Further reading ===

			* E. Rich, [https://www.cs.utexas.edu/~ear/cs341/automatabook/ 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
			* {{Cite journal \|last=Gildea \|first=K.J. \|last2=Krishnamoorthy \|first2=M.S. \|date=1992 \|title=Modular Protocol Nets: The Alternating Bit Protocol Example \|url=http://ieeexplore.ieee.org/document/638998/ \|journal=Proceedings of the Third International Conference on Computer Integrated Manufacturing \|publisher=IEEE \|pages=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.

			== External links ==

			* [https://kjt.stir.ac.uk/software/comms/jasper/ABP.html Alternating Bit Protocol Simulator] ''University of Sterling''
			* [https://cs.wmich.edu/~elise/courses/cs6800/ABP-Presentation.pdf An Implementation for Alternating Bit Protocol (ABP) as an Application of Theory in Networking] ''Western Michigan University''
			* [http://www.jaist.ac.jp/~ogata/lecture/i636/lectureNote11.pdf Specification and Verification of Distributed Systems: Alternating Bit Protocol] ''Japan Advanced Institute of Science and Technology''
			* [https://asd.cs.mtu.edu/research/tools/examples/abp.pdf Example: Alternating Bit Protocol] ''Michigan Technological University''
			* [https://netherlands.openaire.eu/search/find/research-outcomes?f0=q&fv0=%2522alternating%2520bit%2520protocol%2522 Alternating Bit Protocol]''Dutch Research Outcomes''
	{{DEFAULTSORT:Alternating Bit Protocol}}		{{DEFAULTSORT:Alternating Bit Protocol}}
	[[Category:Network protocols]]		[[Category:Network protocols]]

imported>Kvng: foldoc attribution Template_talk:FOLDOC#It_doesn't_matter_whether_readers_care

2025-08-06T17:22:27Z

foldoc attribution Template_talk:FOLDOC#It_doesn't_matter_whether_readers_care

← Previous revision		Revision as of 17:22, 6 August 2025
Line 8:		Line 8:
	[[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.		[[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.		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.		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.

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-28T15:31:16Z

Open access bot: url-access updated in citation with #oabot.

New page

{{Use American English|date = March 2019}}
{{Short description|Type of data link layer protocol about transmission fidelity}}
{{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.

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 ===
'''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]]
* [[Stop-and-wait ARQ]]

==References==
{{Reflist}}

{{DEFAULTSORT:Alternating Bit Protocol}}
[[Category:Network protocols]]