Selective Repeat ARQ
Encyclopedia
Selective Repeat ARQ / Selective Reject ARQ is a specific instance of the Automatic Repeat-Request (ARQ) protocol used for communications.
When used as the protocol for the delivery of messages, the sending process continues to send a number of frames
specified by a window size even after a frame loss. Unlike Go-Back-N ARQ
, the receiving process will continue to accept and acknowledge
frames sent after an initial error; this is the general case of the sliding window protocol
with both transmit and receive window sizes greater than 1.
The receiver process keeps track of the sequence number of the earliest frame it has not received, and sends that number with every acknowledgement
(ACK) it sends. If a frame from the sender does not reach the receiver, the sender continues to send subsequent frames until it has emptied its window. The receiver continues to fill its receiving window with the subsequent frames, replying each time with an ACK containing the sequence number of the earliest missing frame
. Once the sender has sent all the frames in its window, it re-sends the frame number given by the ACKs, and then continues where it left off.
The size of the sending and receiving windows must be equal, and half the maximum sequence number (assuming that sequence numbers are numbered from 0 to n−1) to avoid miscommunication in all cases of packets being dropped. To understand this, consider the case when all ACKs are destroyed. If the receiving window is larger than half the maximum sequence number, some, possibly even all, of the packages that are resent after timeouts are duplicates that are not recognized as such. The sender moves its window for every packet that is acknowledged.
When used as the protocol for the delivery of subdivided messages it works somewhat differently. In non-continuous channels where messages may be variable in length, standard ARQ or Hybrid ARQ protocols may treat the message as a single unit. Alternately selective retransmission may be employed in conjunction with the basic ARQ mechanism where the message is first subdivided into sub-blocks (typically of fixed length) in a process called packet segmentation
. The original variable length message is thus represented as a concatenation of a variable number of sub-blocks. While in standard ARQ the message as a whole is either acknowledged (ACKed) or negatively acknowledged (NAKed), in ARQ with selective transmission the NAKed response would additionally carry a bit flag indicating the identity of each sub-block successfully received. In ARQ with selective retransmission of sub-divided messages each retransmission diminishes in length, needing to only contain the sub-blocks that were NAKed.
In most channel models with variable length messages, the probability of error-free reception diminishes in inverse proportion with increasing message length. In other words it's easier to receive a short message than a longer message. Therefore standard ARQ techniques involving variable length messages have increased difficulty delivering longer messages, as each repeat is the full length. Selective retransmission applied to variable length messages completely eliminates the difficulty in delivering longer messages, as successfully delivered sub-blocks are retained after each transmission, and the number of outstanding sub-blocks in following transmissions diminishes.
uses a variant of Go-Back-N ARQ
to ensure reliable transmission of data over the Internet Protocol
, which does not provide guaranteed delivery of packets; with Selective Acknowledgement (SACK), it uses Selective Repeat ARQ.
The ITU-T
G.hn
standard, which provides a way to create a high-speed (up to 1 Gigabit/s) Local area network
using existing home wiring (power lines
, phone lines and coaxial cables
), uses Selective Repeat ARQ to ensure reliable transmission over noisy media. G.hn
employs packet segmentation
to sub-divide messages into smaller units, to increase the probability that each one is received correctly.
Concept
It may be used as a protocol for the delivery and acknowledgement of message units, or it may be used as a protocol for the delivery of subdivided message sub-units.When used as the protocol for the delivery of messages, the sending process continues to send a number of frames
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
specified by a window size even after a frame loss. Unlike Go-Back-N ARQ
Go-Back-N ARQ
Go-Back-N ARQ is a specific instance of the automatic repeat request protocol, in which the sending process continues to send a number of frames specified by a window size even without receiving an acknowledgement packet from the receiver...
, the receiving process will continue to accept and acknowledge
Acknowledgement (data networks)
In data networking, an acknowledgment is a signal passed between communicating processes or computers to signify acknowledgment, or receipt of response, as part of a communications protocol...
frames sent after an initial error; this is the general case of the sliding window protocol
Sliding Window Protocol
A sliding window protocol is a feature of packet-based data transmission protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the Data Link Layer as well as in the Transmission Control Protocol .Conceptually, each portion of the...
with both transmit and receive window sizes greater than 1.
The receiver process keeps track of the sequence number of the earliest frame it has not received, and sends that number with every acknowledgement
Acknowledgement (data networks)
In data networking, an acknowledgment is a signal passed between communicating processes or computers to signify acknowledgment, or receipt of response, as part of a communications protocol...
(ACK) it sends. If a frame from the sender does not reach the receiver, the sender continues to send subsequent frames until it has emptied its window. The receiver continues to fill its receiving window with the subsequent frames, replying each time with an ACK containing the sequence number of the earliest missing frame
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
. Once the sender has sent all the frames in its window, it re-sends the frame number given by the ACKs, and then continues where it left off.
The size of the sending and receiving windows must be equal, and half the maximum sequence number (assuming that sequence numbers are numbered from 0 to n−1) to avoid miscommunication in all cases of packets being dropped. To understand this, consider the case when all ACKs are destroyed. If the receiving window is larger than half the maximum sequence number, some, possibly even all, of the packages that are resent after timeouts are duplicates that are not recognized as such. The sender moves its window for every packet that is acknowledged.
When used as the protocol for the delivery of subdivided messages it works somewhat differently. In non-continuous channels where messages may be variable in length, standard ARQ or Hybrid ARQ protocols may treat the message as a single unit. Alternately selective retransmission may be employed in conjunction with the basic ARQ mechanism where the message is first subdivided into sub-blocks (typically of fixed length) in a process called packet segmentation
Packet segmentation
In a data communications networks, packet segmentation is the process of dividing a data packet into smaller units for transmission over the network...
. The original variable length message is thus represented as a concatenation of a variable number of sub-blocks. While in standard ARQ the message as a whole is either acknowledged (ACKed) or negatively acknowledged (NAKed), in ARQ with selective transmission the NAKed response would additionally carry a bit flag indicating the identity of each sub-block successfully received. In ARQ with selective retransmission of sub-divided messages each retransmission diminishes in length, needing to only contain the sub-blocks that were NAKed.
In most channel models with variable length messages, the probability of error-free reception diminishes in inverse proportion with increasing message length. In other words it's easier to receive a short message than a longer message. Therefore standard ARQ techniques involving variable length messages have increased difficulty delivering longer messages, as each repeat is the full length. Selective retransmission applied to variable length messages completely eliminates the difficulty in delivering longer messages, as successfully delivered sub-blocks are retained after each transmission, and the number of outstanding sub-blocks in following transmissions diminishes.
Examples
The Transmission Control ProtocolTransmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
uses a variant of Go-Back-N ARQ
Go-Back-N ARQ
Go-Back-N ARQ is a specific instance of the automatic repeat request protocol, in which the sending process continues to send a number of frames specified by a window size even without receiving an acknowledgement packet from the receiver...
to ensure reliable transmission of data over the Internet Protocol
Internet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
, which does not provide guaranteed delivery of packets; with Selective Acknowledgement (SACK), it uses Selective Repeat ARQ.
The ITU-T
ITU-T
The ITU Telecommunication Standardization Sector is one of the three sectors of the International Telecommunication Union ; it coordinates standards for telecommunications....
G.hn
G.hn
G.hn is the common name for a home network technology family of standards developed under the International Telecommunication Union's Standardization arm and promoted by the HomeGrid Forum...
standard, which provides a way to create a high-speed (up to 1 Gigabit/s) Local area network
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...
using existing home wiring (power lines
Power line communication
Power line communication or power line carrier , also known as power line digital subscriber line , mains communication, power line telecom , power line networking , or broadband over power lines are systems for carrying data on a conductor also used for electric power transmission.A wide range...
, phone lines and coaxial cables
Ethernet over coax
Ethernet over Coax is a family of technologies that supports the transmission of Ethernet frames over coaxial cable.- History :The first Ethernet standard, known as 10BASE5 in the family of IEEE 802.3, specified baseband operation over coaxial cable...
), uses Selective Repeat ARQ to ensure reliable transmission over noisy media. G.hn
G.hn
G.hn is the common name for a home network technology family of standards developed under the International Telecommunication Union's Standardization arm and promoted by the HomeGrid Forum...
employs packet segmentation
Packet segmentation
In a data communications networks, packet segmentation is the process of dividing a data packet into smaller units for transmission over the network...
to sub-divide messages into smaller units, to increase the probability that each one is received correctly.