Scribd
Upload
16 views5 pages

Go-Back-N ARQ Protocol Overview

Go-Back-N ARQ allows up to N outstanding unacknowledged packets to be transmitted continuously without waiting for acknowledgments. The receiver sends cumulative acknowledgments and negatively acknowledges or discards out-of-order packets, while the sender retransmits from the first unacknowledged packet on upon timeout or negative acknowledgment. Selective Repeat ARQ buffers out-of-order packets at the receiver and only retransmits the specific packet requested, improving bandwidth efficiency over Go-Back-N. Checksums like CRC detect errors in packets by adding redundant bits to allow the receiver to identify errors.

Uploaded by

shahid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views5 pages

Go-Back-N ARQ Protocol Overview

Go-Back-N ARQ allows up to N outstanding unacknowledged packets to be transmitted continuously without waiting for acknowledgments. The receiver sends cumulative acknowledgments and negatively acknowledges or discards out-of-order packets, while the sender retransmits from the first unacknowledged packet on upon timeout or negative acknowledgment. Selective Repeat ARQ buffers out-of-order packets at the receiver and only retransmits the specific packet requested, improving bandwidth efficiency over Go-Back-N. Checksums like CRC detect errors in packets by adding redundant bits to allow the receiver to identify errors.

Uploaded by

shahid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Go-Back-N ARQ

packets transmitted continuously (when available) without


waiting for ACK, up to N outstanding, unACKed packets
a logically different sender timer association with each
unACKed packet: extension of AB protocol
Receiver:
ACK packet if correctly received and in-order, pass to
higher layer
NACK or ignore (possibly discard) corrupt or out-of-order
packet
Sender :
if NACK received, or timeout, for packet n, begin resending
from n all over again
cumulative ACK: ACK of n implicitly acknowledges up
through n

Go Back N: Example

Go-Back-N continued

no receiver transport buffering with discard


saves resources at receiver
avoids large bursts of packet delivery to higher layers
simplicity in buffering and protocol processing at sender
and receiver

tradeoff between buffering/processing complexity and


bandwidth

Selective Repeat ARQ


As in go back-N:

packet transmitted when available, up to limit timer


associated with each unACKed packet
receiver NACKs or ignores corrupted packets

Unlike Go-Back-N:

out-of-order (but otherwise correct) packet is ACKed


receiver: buffers out-of-order packets
sender: on timeout or NACK of packet n, just
retransmit n

Selective Repeat ARQ (cont)

Notes:
more receiver buffering than Go back-N
more complicated buffer management by
both sides
saves bandwidth: no need to retransmit
correctly received packets

Selective Repeat ARQ: example

How Big Can a Window Be?


Suppose sequence number space size is N
Q: How big can window be and have SR still
work?
Partial answer: N-1 wont work:
Fundamental problem: sender and receiver
do not have synchronized info
cannot know exact same information

Throughput Comparison
p - loss probability
t_trans - pkt transmission time
rtt - round trip time
tput_SW = (1-p)/(rtt+t_trans)
tput_GB = (1-p)/(p rtt + t_trans)
tput_SR = (1-p)/t_trans

Throughput Comparison

Throughput Comparison
1000

1000
SW

GB(N)

SW

SR

SR

100

100

1GB/sec link
1KB pkt
-> t_trans = 8s
rtt =1ms

GB N

1GB/sec link
1KB pkt
-> t_trans = 8s
rtt =30ms

10

10

0.1
0.1

0.01

0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

loss probability

loss probability, p

Detecting Errors: checksums


Need to detect errors: bits in packet may be flipped
while in transit or stored at intermediate notes.
Approach: add extra bits to packets that will allow us to
detect (possibly correct) bit errors

Simple example: Parity


Given n-1 bit packet, add n-th bit, choosing
value so that total number of 1

bits in packets (including nth bit) is odd (odd parity).


example packet:
error detection
seq
ack
data
(parity bit)
0111 0001 10101011

At receiver:

count # 1s in packet, if even, then error!


what if even number of bit flips?
what if odd number of bit flips?

Simple example: Parity

Forward Error Correction: FEC


ARQ protocols operate by detecting errors and
retransmitting

Note:

many codes with more powerful error detection


capabilities

CRC-16: 16 bit code, detects 2 random bit errors, 16 errors


in sequence.

packet header itself often separately checksummed

checksumming also done at data link layer

hardware support for transport-level checksum: SGI

row parity

d1,1
d2,1

d1,J
d2,J

d1,J+1
d2,J+1

dI,1

dI,J

dI,J+1

column
dI+1,1 dI+1,J
parity

seq #

ACK#

data

d1,j+1

(a) 2-dimensional parity

(b) packet format

10101 0
11110 1
01110 0

10101 0
10110 1
01110 0

11010 0

11010 0

(c) example: no errors

(d) example: single bit error

EDF

retransmission needs round-trip delay to recover


may be too long for deep space, or high-speed, realtime applications
FEC: key idea is to transmit enough redundant data
to allow receiver to recover from errors itself! (no
sender transmission required)

You might also like