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:
- Sender’s IP address
- Sender’s TCP Port number
- Receiver’s IP Address
- 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 WA.
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 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:
- special control characters
- special bit patterns (flags)
- character counts
- 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
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:
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:
- The size of frames is unpredictable due to byte insertion.
- Malicious users can inflate network bandwidth by inserting
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:
- Initiator and authenticator share a secret key.
- Authenticator sends a challenge (random number and ID).
- Initiator computes a cryptographic checksum of random number and ID using the shared secret key.
- Authenticator calculates its version of cryptographic checksum and compares that to the version from the initiator.
- If the two checksums agree, the authenticator sends an authentication message.
- 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
- makes use of a bit-transport service provided by the physical layer
- transmits frames, and
- provides a communication service to the network layer
Network layer PDU
|⇅ Data link layer SDU|
|⇅ Data link layer SDU|
|Data link layer||⟺|
Data link layer PDU
|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|
|Asynchronous Balance Mode||used in full-duplex point-to-point links|
2. In the reverse direction, one
A frame of HDLC is like this:
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
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.
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
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.
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
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
All of your support will be used for maintenance of this site and more great content. I am humbled and grateful for your generosity. Thank you!
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!Tweet