Peer-to-Peer Service Model
The communication process can be broken into layers. At each layer, two or more peer processes execute a protocol that delivers the service to the layer above. Peer-to-peer processes executes layer n protocol to provide services to layer n+1.
- Layer n+1 local peer calls layer n local peer and passes Service Data Units (SDUs) for transfer.
- At layer n local peer, SDU is encapsulated into Protocol Data Units (PDUs), which is exchanged to layer n remote peer.
- Layer n remote peer delivers the SDU to destination layer n+1 remote peer.
| Local | Remote | ||
| Layer n+1 | Peer process | Peer process | |
| (1) โ SDU | (3) โ SDU | ||
| Layer n | Peer process | (2) โ PDU | Peer process |
A service model specifies the information transfer service that layer n provides to layer n+1. The most important distinction is whether the service is:
- connection-oriented, or
- connectionless
A service model can also include a Quality-of-Service requirement that specifies a level of performance that can be expected in the transfer of data. Service models differ according to the features of the data transfer they provide. A service offered at a given layer can include some of the following features:
| Message size and structure | Different services impose restrictions on size & structure of data that it will transfer a single bit, a block of bytes or byte streams. |
| Segmentation and reassembly | A layer breaks long messages into smaller blocks and reassembles these at the destination. |
| Blocking and unblocking | A layer combines small messages into bigger blocks prior to transfer. |
| Reliability and sequencing | What transmission is reliable? Are messages or information stream delivered in order? ARQ (Automatic Repeat reQuest) protocols combine error detection, re-transmission, and the sequence numbering to provide reliability. Example: TCP and HDLC |
| Flow control | Messages can get lost (overflow) if receiving system does not have sufficient buffering to store arriving message. Flow control provides back pressure mechanisms that control transfer according to availability of buffers at the destination. Example: TCP and HDLC |
| Timing | Application involving voice and video generate units of information that are temporally related. However network transfer introduces delay and jitters. Timing Recovery protocols use time stamps and sequence numbering to control the delay and jitters in delivered information. Example: RTP and Voice over IP protocols |
| Multiplexing | Enables multiple layer n+1 services to share a service offered by layer n below. A multiplexing tag is required to identify specific users at the destination. Example: IP |
| Privacy, integrity and authentication | Privacy ensures that information transferred can not be read by others. Integrity ensures that information is not altered during transfer. Authentication verifies that sender and/or receiver are who they claim to. Example: IPSec and SSL |
Peer-to-peer protocols usually occur in two basic settings: hop-by-hop, and end-to-end. These two settings can lead to different characteristics about whether messages arrived in order, how long to arrive, whether they arrive at all, and how error detection be performed.
| Hop-by-hop | Initiates error recovery more quickly and may give more reliable service. Processing in each node is more complex. Vulnerable to the errors within switches. Data Link Layer (HDLC) 1. Operates over wire-like, directly-connected systems. 2. Frames can be corrupted or lost, but arrive in order. 3. Performs error-checking and retransmission. 4. Ensures error-free packet transfer between two systems. |
| End-by-end | Simple inside the network. More scalable if complexity at the edge. Transport Layer (TCP) 1. Sends segments across network. 2. Performs end-to-end error checking and retransmission. |
ARQ Protocols
Reliable transfer of information is critical comment in computer communications. Automatic Repeated Requests (ARQ) protocols provide reliable data transfer service. The purpose is to ensure a sequence of information packets is delivered in order without errors or duplication, despite transmission errors and losses. They use a sliding window to specify a set of sequence number corresponding to frames permitted to send or receive.
There are 3 ARQ protocols:
- Stop-and-Wait ARQ
- Go-Back N ARQ
- Selective Repeat ARQ
Basic elements of these ARQ protocols include:
- Error-detecting
- ACKs (positive acknowledgements)
- NAKs (negative acknowledgements)
- Timeout mechanism
All ARQ protocols require the information frame to contain a header which can store information that is needed for it’s proper operation. The transmitter appends CRC check bits that covers the header and information bits to enable the receiver to determine where the errors have occurred during transmission.
Transmitter โน [information frame] โน Receiver
โธ [control frame] โธ
where
[information frame] = [header][information packet][CRC]
[control frame] = [header][CRC]In addition to information frames, control frames are the blocks that consist of a header and CRC. Control frames are used to positive acknowledgement or negative acknowledgement.
Stop-and-Wait ARQ
In Stop-and-Wait ARQ, the transmitter and receiver work on the delivery of one frame at a time. Acknowledgements and time-outs can be used to provide recovery from transmission errors.
- Transmitter sending an information frame to receiver.
- The transmitter then stops and waits for an acknowledgement from the receiver.
- If no acknowledgement is received within some time-out period, the transmitter re-sends the frame and once again stops and waits.
However in the step 3 there are a few possible reasons:
- a) Frame sent by transmitter is lost.
- b) Frame sent by transmitter is received, but the acknowledge sent by receiver is lost. In this case, the receiver will receive the same frame for more than once, there is duplication of frames.
To solve the duplication of frames received by receiver, we need to add information frame sequence number in header of each information frame, in order to let the receiver know whether transmission of a frame is duplicated or not. Then the receiver can discard the duplicate frame and resend acknowledgement for the very first frame (of the duplications).
A more subtle case: a premature time-out (or delayed acknowledgement) combined with loss of information frame, can cause gaps in the delivered packet sequence. It is resolved by providing an acknowledgement sequence number in control frame that enable the transmitter to determine which frames have been received.
The sequence numbers need to be concise because only a finite number of bit are variable in the frame header. One-bit sequence number suffices in Stop-and-Wait ARQ. Using the pair of one-bit information frame sequence number and one-bit acknowledgment sequence number, there are four possible global states.
โน [Slast] โน
Transmitter Receiver
โธ [Rnext] โธ
Global state: (Slast, Rnext)Global states change like this:
| (0, 0) | โ frame 0 arrives at receiver | (0, 1) |
| โ ACK for frame 1 arrives at transmitter | โ ACK for frame 0 arrives at transmitter | |
| (1, 0) | โ frame 1 arrives at receiver | (1, 1) |
The Stop-and-Wait ARQ protocol is initiated with the transmitter in the Ready State to transmit / send sequence number set to 0 and receive a sequence number set to 0. The transmitter can be in Ready State or Wait State. Receiver is always in Ready State.
- The transmitter must keep track of the sequence number of the frame being sent, its associated timer and the frame itself in case re-transmission is required.
- The receiver keeps track only the sequence number of the next frame it is expecting to receive.
Performance
Stop-and-wait ARQ works well on channels that have low propagation delay, but it becomes inefficient when the propagation delay is much greater than the frame transmission time. Because most of the time the channel is just idle, while the transmitter is waiting for acknowledgement.
t0 = 2 tprop + 2 tproc + tframe + tack
= 2 tprop + 2 tproc + nframe / R + nack / R
where
t0 : Total transmit time
tprop : Frame / ACK propagation delay
tframe : Frame transmission time
tack : ACK transmission time
tproc : Processing time for frame (at the receiver) / ACK (at the transmitter)
nframe : Info frame bits
nack : ACK frame bits
R : channel transmission rate The effective information transmission rate (also called transmission bandwidth) of the protocol, in absence of error, is the ratio of the number of information bits delivered to destination over the total time required to deliver the information bits.
Reff = (nframe - n0) / t0
where
n0 : bits for header and CRCThe transmission efficiency is a ratio of the effective transmission rate over the transmission rate.
ฮท0 = Reff / R = (nframe - n0) / (t0 * R)
= (nframe - n0) / [2 ( tprop + tproc ) * R + nframe + nack)]
= (1 - n0 / nframe) / [2 ( tprop + tproc ) * R / nframe + nack / nframe + 1)]
= (1 - Effect of frame overhead) / (Effect of Delay-Bandwidth Product + Effect of ACK frame + 1)The delay-bandwidth product, i.e. 2 ( tprop + tproc ) * R, is a very important concept in analysis of network protocol performance. The delay is indeed the total waiting time (called round-trip time, RTT) during a frame and acknowledgement transmission, that is two propagation delays and two processing time. So delay-bandwidth product is RTT * R.
One may tell that the higher the delay-bandwidth product is, the lower the efficiency of the stop-and-wait protocol is. So the stop-and-wait protocol doesn’t work well for very high-speed networks or very long propagation delay.
Even worse, there is possible transmission error that require a frame be re-transmitted. Let (1 - Pframe) be the probability that frames arrive without errors, the total transmit time is then
t = t0 / (1 - Pframe)The transmission efficiency is now:
ฮท = ฮท0 * (1 - Pframe)If there are further transmission errors, the transmission efficiency would be impacted very significantly.
The inefficiency of the Stop-and-Wait ARQ can be overcome by allowing the transmitter to continue sending enough frames, so that its channel is kept busy while the transmitter waits for acknowledgements.
Go-Back N ARQ
A procedure where the transmission of a new frame begins before the completion time of the previous frame transmission is said to be pipelining. In effect, Go-Back N ARQ pipelines the transmission of frames to keep the channel busy.
Go-Back N ARQ allows a window of up to a number of outstanding frames (the receiver’s window is often 1). This window’s size must be larger than the delay-bandwidth product to ensure that the channel is kept busy.
- If ACK for the oldest frame arrives before the windows is exhausted, continue transmitting.
- If the window is exhausted, pull back and re-transmit all outstanding frames.
A worse situation is, if a frame is lost and transmitter doesn’t have a frame to send, the window will not be exhausted and recovery will not commence. The solution is to use a timeout with each frame. When the timeout expires, resend all outstanding frames.
Given a m-bit sequence number, the maximum allowable window size, i.e. the maximum number of frames that can be outstanding, is 2m - 1. Otherwize, the receiver can not tell the difference between whether a frame is in the old batch or in the new batch.
Piggy-backing
Since in the two-way transmission information frames and control frames are interleaving. Have a free ride of acknowledgement upon a data delivering is a good idea. Receiver can insert acknowledgement in the next departing frame. This is called Piggy-backing. Many of the control frames can be eliminated. The communication becomes bidirectional. Use of piggybacking can result in significant improvement in bandwidth use.
In piggybacking, the time out should cover two propagation delay, two transmission times and a one processing time at least, assuming receiver starts transmission right after receiving.
tpiggy = 2 tprop + 2 tframe + tprocSliding window size should be large enough to keep channel busy.
Go-Back-N ARQ is inefficient in channels that have high error rates, even thought it is bi-directional. Because multiple frames are resent when errors or losses occur, and a correct but out-of-sequence frames would’ve been discarded.
Selective Repeat ARQ
Selective repeat is a more efficient ARQ protocol. It retransmits only an individual frame if there is an error or lost. For this, an active acknowledgement is introduced that causes retransmission of the oldest unacknowledged frame.
Receiver maintains a receive window of sequence numbers that can be accepted. Receiver’s window is larger. Error-free but out-of-sequence frames with sequence numbers within the receive window are buffered.
The sum of the transmitter window size and receiver window size must be equal or smaller than 2m, for m-bit sequence numbering.
We can compare the efficiencies of all three ARQ protocols, the quick take home message is:
- When the transmission error probability is near to 0, Selective Repeat and Go-Back-N are quite the same, both are almost optimal.
- When transmission error probability is near to 100%, Go-Back-N and Stop-and-Wait are quite the same.
My Certificate
For more on Automatic Repeat Request Protocols, please refer to the wonderful course here https://www.coursera.org/learn/peer-to-peer-protocols-local-area-networks
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
