Reliable Services and Data Link Controls

Tweet

TCP Reliable Stream and Flow Control

TCP Reliable Stream Service applies Automatic Repeat Request (ARQ) flow control. TCP provides a reliable service that is in order, error free, and duplication free. It uses Selective Repeat ARQ protocol, but varies in several key aspects.

In TCP, application layer writes bytes into a sender buffer through a socket, but boundaries between multiple writes are not preserved. TCP may decide to break a stream into multiple ones or merge multiple small bytes into a single larger one.

---

---

TCP was designed to deliver a connection-oriented service over IP which offers connectionless packet transfer service. In IP network, each packet that is transmitted between a sender and receiver can traverse a different path and packets can arrive with errors or loss, or even out-of-order. Receiver accepts segments within a small window, the likelihood of accepting an old message is very low.

TCP uses Three-Way Handshake to set up connection and establish the initial sequence number (32-bits). Each connection is uniquely identified by:

1. Sender’s IP address
2. Sender’s TCP Port number
3. Receiver’s IP Address
4. Receiver’s TCP Port number

TCP uses a sliding window mechanism (an enhancement of Selective Repeat ARQ) using acknowledged messages and a timer mechanism. The sender’s window contains 4 pointers:

                                                 ↓Slast + WA - 1
-------------------------------------------------------------------→
          ↑Slast      ↑Srecent                           ↑Slast + WS - 1

where
Slast : the oldest byte unacknowledged
Srecent : the last byte transmitted (not acknowledged yet)
Slast + WA - 1 : the highest-number of byte that can be transmitted
Slast + WS - 1 : the highest-number of byte that can be accepted from an application

WA : advertised window size
WS : sender's window size

The receiver’s window contains 4 pointers too:

         ↓Rlast                                     ↓Rlast + WR - 1
-------------------------------------------------------------------→
                       ↑Rnext      ↑Rnew

where
Rlast : the oldest byte not yet read by the application
Rnext : next expected byte (not yet received correctly)
Rnew : the highest-number of byte that has been received correctly
Slast + WR - 1 : the highest-numbered byte that can be accommodated in receiver's buffer

WR : receiver's windows size

During data exchange, application writes data into sender’s buffer. TCP sender arranges a consecutive string of bytes into segments. TCP receiver performs Selective Repeat ARQ function and writes bytes into receiver’s buffer. The segment contains a sequence number that corresponds to the number of the first byte in the string that is being transmitted. This is very different from the conventional ARQ protocols.

TCP separates the flow control function from the acknowledgement function. TCP receiver controls rate at which sender transmits to prevent buffer overflow, by advertising a window size which specifies the number of bytes that can be accommodated by receiver.

WA = WR - (Rnew - Rlast)

---

---

TCP sender is obliged to keep the number of outstanding bytes below W_A.

Srecent - Slast ≤ WA

In TCP, the sender sets a timer each time a segment is transmitted. The timeout cannot be too long (recovery too slow) nor be too short (excessive number of transmissions). Indeed, it depends on the round trip time, RTT. However RTT on the Internet varies a lot. In practice, TCP uses adaptive estimation of RTT. Each time an acknowledgement is received, TCP measures RTT τ_n, and compute the estimation based on it, continuously.

tRTT_new = α tRTT_old + (1 - α) τn

typically α = 7/8

The variance of RTT σ_RTT is also approximately estimated.

σRTT_new = β σRTT_old + (1 - β) | τn - tRTT |

Finally the estimated timeout is given by:

timeout = tRTT + k σRTT

where
k : a suitable constant 

Data Link Layer Services and Control

The assumption is that Data Link is directly connected (wire-like), there might be losses and errors, but no out-of-sequence frames. Data Link offers services like framing, error control, flow control, multiplexing, etc. Example of protocols are PPP, HDLC, Ethernet LAN, IEEE 802.11 LAN (WiFi), etc.

Framing

Framing involves identifying the beginning and end of a block of information within a digital stream. Framing maps stream of physical layer bits into frames, and then maps frames into a bit stream.

Stream of physical layer bits ⟹ Frames ⟹ Bit stream

The length of frames is variable, the boundaries of frames can be determined using:

1. special control characters
2. special bit patterns (flags)
3. character counts
4. CRC checks

Character-Based Framing (Byte Stuffing)

Character based of framing are used when information in a frame consists of an integer number of characters. Special eight-bit codes that are not printable characters are used as control characters. This is called byte stuffing.

A special control character DLE (data link escape) with hexadecimal value 0x10 is introduced. The sequence DLE STX is used to indicate the beginning of a frame, and DLE ETX denodes the end of a frame. The receiver looks for them to identify a frame.

To deal with the potential occurrence of DLE in the data contained in the frame, an extra DLE is inserted or stuffed before each occurrence of a DLE inside of the frame. Consequently, every legitimate DLE in the data is replaced by two DLEs.

Data:
A DLE B ETX DLE STX E

Frame:
DLE STX A DLE DLE B ETX DLE DLE STX E DLE ETX

Therefore, the only occurrence of DLE STX or DLE ETX will identify beginning and end of frame.

---

---

Flag-Based Framing (Bit Stuffing)

Flag-based bit stuffing framing is for transferring an arbitrary number of bits within a frame. It is used in HDLC. A frame is delineated by flag character that it is in hexadecimal 0x7E. It use bit stuffing to prevent occurrence of flag inside frame data.

• Transmitter inserts extra 0 after each consecutive five 1s inside a frame.
• Receiver checks for five consecutive 1s:
  • If next bit is 0, then remove it.
  • If next bits are 10, then flag is detected.
  • If next bits are 11, then the frame is broken.

Point-to-Point Protocol (PPP)

Point-to-Point Protocol (PPP) provides a method for encapsulating IP packets over point-to-point links. It can be used as a data link control to connect two routers or to connect a personal computer to an Internet service provider (ISP) using a telephone line or modem. A frame of PPP is like this:

Flag

Address

Control

Protocol

Information

CRC

Flag

PPP provides framing and error-detection. It was designed to support multiple network protocols simultaneously. That is, PPP can transfer packets that are produced by different network layer protocols. PPP is used in many point-to-point applications, also over shared links such as Ethernet to provide:

• Link Control Protocol (LCP, used to setup, configure, test, maintain and terminate a link connection)
• Network Control Protocol (NCP, works with layer 3 or the network layer)
• Authentication features

PPP is character-based version of HDLC, its flag is 0x7E and control escape is 0x7D. It uses an HDLC-like frame format and the same flag to encapsulate the datagrams. However it uses byte stuffing as its frames consist of an integer number of bytes, which cause two problems:

1. The size of frames is unpredictable due to byte insertion.
2. Malicious users can inflate network bandwidth by inserting 0x7D and 0x7E.

PPP authentication is a password-based protocol. so ID and password are transmitted unencrypted. The Challenge Handshake Authentication Protocol (CHAP) provides greater security by having the initiator and responder (authenticator) to go through a challenge response sequence:

1. Initiator and authenticator share a secret key.
2. Authenticator sends a challenge (random number and ID).
3. Initiator computes a cryptographic checksum of random number and ID using the shared secret key.
4. Authenticator calculates its version of cryptographic checksum and compares that to the version from the initiator.
5. If the two checksums agree, the authenticator sends an authentication message.
6. Authenticator can reissue challenge during a session.

HDLC and Multiplexing

Derived from IBM SDLC (Synchronous Data Link Control), the HDLC is flag-based data link protocol, providing a rich set of standards for operating data link over bit-synchronous physical layers. So data link control

1. makes use of a bit-transport service provided by the physical layer
2. transmits frames, and
3. provides a communication service to the network layer

Network layer	⟺ Network layer PDU “Packet”	Network layer
⇅ Data link layer SDU ⇅ DLSAP		⇅ Data link layer SDU ⇅ DLSAP
Data link layer	⟺ Data link layer PDU “Frame”	Data link layer
⇅		⇅
Physical layer	⟺	Physical layer

---

---

Data link layer can be configured to provide several types of services: connection-oriented or connectionless. HDLC has two data transfer modes (selected during connection establishment):

Normal Response Mode	used in polling multi-drop lines 1. One Primary commands. 2. Multiple Secondary responses. ⟺ Secondary Primary ⟺ Secondary ⟺ Secondary
Asynchronous Balance Mode	used in full-duplex point-to-point links 1. One Primary commands, one Secondary responses. 2. In the reverse direction, one Secondary responses, one Primary commands. Primary ⟺ Secondary Secondary ⟺ Primary

A frame of HDLC is like this:

Flag

Address

Control

Information

FCS

Flag

The function of a protocol depends on the Control fields that are defined in the header. HDLC and PPP use the same Flag byte in framing. The frame has a Address field which always contains the address of the Secondary.

Frames may get lost due to the loss of synchronization or receiver’s buffer overflow. Frames may also undergo errors in transmission. CRCs are used to detect error and such frames are treated as lost, then recovery is done through acknowledgements, timeouts and retransmission. Again sequence numbers are used to identify out-of-sequence and duplicates. HDLC provides options for implementing several ARQ methods.

Statistical Multiplexing

Computer applications generate data for transmission in a bursty manner. Dedicating a transmission line to a computer is inefficient. This is solved by a technique called statistical multiplexing for sharing a digital transmission line among multiple computers, which achieves greater efficiency and lower cost.

Note that the generation times of packets overlap, so the multiplexer must “buffer and delay” some of the packets. Nevertheless, all packets get transmitted in the order in which they were generated. Typically, packets are transmitted in First-In, First-Out fashion. But increasingly, multiplexers use priorities in scheduling to determine the order of packet transmission.

Packets are buffered in the queue. Consequently, it is a tradeoff between packet delay and the utilization of the transmission line. If the buffer overflows, packets may get lost. End-to-end the protocols are responsible for recovering them.

Important factors include:

• Packet arrival pattern
• Packet service time (how long are the packets?)
• Service discipline (the order of transmission)
• Buffer discipline (if buffer is full, which packet will be dropped?)

The performance measures are:

• average delay distribution
• packet loss probability
• line utilization

The behavior of statistical multiplexer is characterized by the number of packets in the multiplexer at a given time. A famous arrival pattern is described as Poisson Arrivals, in which the time between consecutive packet arrivals is an exponential random variable.

Arrivals are equally-likely to occur at any point in time, the time between consecutive arrivals is an exponential random variable with mean 1 / λ. The number of arrivals in internal of time t is a Possion random variable with mean λt.

P[ k arrives in t seconds ] = (λt)k e-λt / k!

where
λ : average arrival rate (packets per seconds)

Queuing Theory is very important to measure the delay and loss statistics.

---

---

My Certificate

For more on Reliable Services and Data Link Controls, please refer to the wonderful course here https://www.coursera.org/learn/peer-to-peer-protocols-local-area-networks

My #119 certificate from Coursera

---

Related Quick Recap

Automatic Repeat Request Protocols

---

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