CS2105: Introduction to Computer Networks

L2: Principles of Reliable Data Transfer (Data Link Control)

Framing Flow and Error Control Concepts Stop-and-Wait ARQ Protocol Go-Back-N Protocol Selective-Repeat Protocol
Anand Bhojan
COM2-02-46, School of Computing banand@comp.nus.edu.sg ph: 651-67351

Data Link Layer

Data Transfer between two directly connected nodes. (Hop-toHop communication, Point-to-point communication) Data link layer divided into two functionality-oriented sublayers

application transport network link physical

Data Link Layer

Data Link Control Multiple Access Resolution

47

CS2105/2011-12 Sem 2/AaBee

Data Link Layer - Framing

Bits

must be framed into discernible blocks of information. Message/Data is broken up into recoverable chunks that can easily be checked for corruption. Frames have Source and Destination addresses Separates/identifies frames from different sources at the destination.

48

CS2105/2011-12 Sem 2/AaBee

Data Link Control Protocols - Simple Protocol

Assumes noiseless channel and infinite buffer

Note:- Shown as Link layer Protocol. It is also applicable for Transport Layer.
49 CS2105/2011-12 Sem 2/AaBee

Flow control - concept

What happens if the channel is noiseless but the receiver has finite buffer?

Receiver processes data at its own speed. Sender cannot overwhelm the receiver with large amount of data.

Flow Control is required! How?

51

CS2105/2011-12 Sem 2/AaBee

Stop-and-Wait Protocol

What happens if the channel is noiseless but the Flow Control is required receiver has finite buffer?
Flow control refers to a set of procedures used to restrict the amount of data that a sender can send before waiting for an acknowledgment (ACK).

52

CS2105/2011-12 Sem 2/AaBee

Error Control - concept

Channel

is noisy (errors, losses and delay) with finite buffer. Error Control is required! How?

53

CS2105/2011-12 Sem 2/AaBee

Most Common Error Control - concept

Generally frames have some error detection mechanism (will be discussed in next Lecture) If received frame is in error, receiver requests for retransmission Automatic Repeat Request (ARQ)

54

CS2105/2011-12 Sem 2/AaBee

Stop and Wait ARQ - Design

Case 1: Lost or Corrupt Frame. How to find and retransmit?

55

CS2105/2011-12 Sem 2/AaBee

Stop and Wait ARQ - Design

Case 2: Lost or Corrupt ACK.

Side effect?
56 CS2105/2011-12 Sem 2/AaBee

Stop and Wait ARQ - Design

Case 3: Delayed Frame/ACK

Duplicate ACK

57

CS2105/2011-12 Sem 2/AaBee

Sender

maintains a timer for each transmitted frame maintains a copy of each transmitted frame and retransmits when required numbers the frames Numbers the ACKs (next expected frame number)
58

Stop and Wait ARQ

Summary

CS2105/2011-12 Sem 2/AaBee

Performance of Stop and Wait ARQ

Stop-and-wait ARQ works, but performance stinks example: 1 Gbps link, 15 ms end-to-end Prop Delay from east coast to west coast of US (RTT=30 ms; approx speed of light), 1KB packet:
Ttransmit = L (packet length in bits) 8kb/pkt = = 8 microsec R (transmission rate, bps) 10**9 b/sec

U sender: utilization of sender or utilization of the channel (time sender busy sending / total time) 1 Gbps link is underutilized
59 CS2105/2011-12 Sem 2/AaBee

Performance of Stop and Wait ARQ

sender first packet bit transmitted, t = 0 last packet bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK receiver

RTT

ACK arrives, send next packet, t = RTT + L / R

Effect of increasing Distance (or RTT)? Effect of increasing digital BW? == BDP

As BDP increases we need to transmit more bits or frames (before waiting for ACK) to improve the utilisation
60 CS2105/2011-12 Sem 2/AaBee

Pipelined protocols
Pipelining: sender allows multiple, in-flight, yetto-be-acknowledged pkts
range

of sequence numbers must be increased buffering at sender and/or receiver

Two generic forms of pipelined protocols: goBack-N, selective repeat

61 CS2105/2011-12 Sem 2/AaBee

Analogy:
Current:

Pipe-lined:

An Analogy: Talking on a Cell Phone. Bob says a sentences and waits for ACK (uh huh) before saying next sentence.

An Analogy: Talking on a Cell Phone.

Bob is allowed to say N sentences and waits for ACK (uh huh) before saying next sentence.

Questions:

How much is N?

Can N be infinite?

Cumulative ACK

62

CS2105/2011-12 Sem 2/AaBee

Go-back-N ARQ (GBN)

How many in-flight packets? N Packets (sliding window of size N on sequence numbers) --- [Flow Control]

Out-of-order packets are discarded. Because of this, Receive window size of GBN is 1 and acknowledgement in GBN is cumulative. Packet losses uses timer; retransmit on timeout

63

CS2105/2011-12 Sem 2/AaBee

Some examples follows

64

CS2105/2011-12 Sem 2/AaBee

Eg 1:

Send 1 Packet

65

CS2105/2011-12 Sem 2/AaBee

Eg 2:

Receive ACK 4

66

CS2105/2011-12 Sem 2/AaBee

Eg 3: Cumulative ACK

Receive ACK 6

67

CS2105/2011-12 Sem 2/AaBee

Eg 4:

Full Window

68

CS2105/2011-12 Sem 2/AaBee

Eg 5:

Empty Window

69

CS2105/2011-12 Sem 2/AaBee

Go-back-N ARQ

Why it is called Go-back-N?

When a timer expires all frames starting from the frame in error are retransmitted.
Sender Receiver

Example:
Frame 3 Frame 4 Frame 5

Frame 6 Go back and retransmit all frames starting from frame 3! Timer Expired Frame 3 Frame 4 Stop-and-Wait ARQ is a special case of Go-Back-N ARQ in which the size of the send window is 1.
70

Frame 5 Frame 6
CS2105/2011-12 Sem 2/AaBee

GBN eg1: Lost ACKs

71

CS2105/2011-12 Sem 2/AaBee

GBN eg2: Lost Frame

The size of the receive window is always 1 in Go-back-N

72 CS2105/2011-12 Sem 2/AaBee

Go-back-N ARQ window SIZE

If the size of sequence number field is m bits, then we can transmit a maximum of 2m-1 frames. Example: 2 bit sequence number

73

CS2105/2011-12 Sem 2/AaBee

Selective-Repeat ARQ (SR)

GBN leads to unnecessary retransmission since out of order packets are discarded. SR sender retransmits only the lost (or invalid; error) packets. (Improvement over GBN).

Requirements at receiver side

Receiver should buffer out of order packets. Receiver needs a receiver-window of size of size equal to send window.

74

CS2105/2011-12 Sem 2/AaBee

Selective-Repeat ARQ (SR)

75

CS2105/2011-12 Sem 2/AaBee

SR eg1: Lost Frame

Instead NAK one can use Duplicate ACK to tell the expected frame to the sender What happens if NAK 1 is lost?
76 CS2105/2011-12 Sem 2/AaBee

Selective Repeat ARQ

In Selective Repeat ARQ, the size of the sender and receiver window must be at most one-half of 2m.

77

CS2105/2011-12 Sem 2/AaBee

Piggybacking
Sender
Frame 0
1 Frame 0 ACK Frame 1 ACK 1

Communication is generally full-duplex acknowledgement can be piggybacked on data in the opposite direction.

Receiver

Frame 1, ACK 2
Frame 2, ACK 2

78

CS2105/2011-12 Sem 2/AaBee

Summary
Flow control and Error control Simple Protocol (No flow and error control) Stop and Wait (for flow control) Stop and Wait ARQ (adds error control to SW) Pipelined Protocols (improves efficiency of SW-ARQ) GBN : receive window size = 1 SR : receiver window = send window size

READ THE TEXT BOOK. (Slides alone are not enough)

79 CS2105/2011-12 Sem 2/AaBee