CS 31204: Computer Networks – Transport Layer Services

INDIAN INSTITUTE OF TECHNOLOGY

KHARAGPUR

Department of Computer Science and Engineering

Sandip Chakraborty

sandipc@cse.iitkgp.ac.in

​

Abhijnan Chakraborty

abhijnan@cse.iitkgp.ac.in

Protocol Stack Implementation in a Host

Software, Kernel

Firmware, Device Driver

Hardware

Indian Institute of Technology Kharagpur

How Application Data Passes Through Different Layers

HTTP Data

HTTP Header

Transport Layer Data

TCP Header

Network Layer Data

IP Header

Data Link Layer Data

MAC Header

HTTP Data

HTTP Header

TCP Header

IP Header

MAC Header

PHY Header

PHY Trailer

Indian Institute of Technology Kharagpur

Transport Layer Services

​

​

​

​

​

​

UDP

End to end packet delivery

​

​

​

​

​

​

TCP

Connection Establishment

Reliable Data Delivery

Flow and Congestion Control

Ordered Packet Delivery

Transport

Data Link

Datagram delivery (unreliable)

Network

Indian Institute of Technology Kharagpur

Transport Layer – Interfacing with Application and Network

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Port Number

IP Address

Indian Institute of Technology Kharagpur

Transport Layer – Interfacing with Application and Network

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Create a logical pipe between the sender and the receiver and monitor the data transmission through this pipe

Indian Institute of Technology Kharagpur

Transport Service Primitives

• To allow users to access transport service, the transport layer must provide some operations to the application programs.
• Let us look into a hypothetical transport service primitives, that are provided to the application layer

The transport layer needs to remember the state of the pipe, so that appropriate actions can be taken. We need a stateful protocol for transport layer.

Indian Institute of Technology Kharagpur

Transport Service Primitive – Connection Establishment

Client

Server

LISTEN

CONNECT

CONNECTION REQ

CONNECTION ACK

ESTABLISHED

ESTABLISHED

SEND

DATA

RECEIVE

DISCONNECT

DISCONNECTION REQ

DISCONNECTION ACK

The client and server needs to remember the state

Indian Institute of Technology Kharagpur

Transport Layer Protocol – State Diagram

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

SERVER

Indian Institute of Technology Kharagpur

Transport Layer Protocol – State Diagram

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

CLIENT

Indian Institute of Technology Kharagpur

Segment, Packet (or Datagram) and Frame

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Establishment

• This is a simple primitive for connection establishment – but does this work?

Client

Server

LISTEN

CONNECT

CONNECTION REQ

CONNECTION ACK

Indian Institute of Technology Kharagpur

Connection Establishment

• Consider a scenario when the network can lose, delay, corrupt and duplicate packets (the underline network layer uses unreliable data delivery)

​

• Consider retransmission for ensuring reliability – every packet uses different paths to reach the destination

​

• Packets may be delayed and got struck in the network congestion, after the timeout, the sender assumes that the packets have been dropped, and retransmits the packets

Indian Institute of Technology Kharagpur

Connection Establishment

• How will the server differentiate whether CONNECTION REQ-1 is a new connection request or a duplicate of the CONNECTION REQ-2?

Client

Server

LISTEN

CONNECT

CONNECTION REQ - 1

CONNECTION REQ - 2

It may happen that the server has crashed and the client reinitiated the connection (with same ports). So distinguishing between these two is essential

Indian Institute of Technology Kharagpur

Connection Establishment

• Protocol correctness versus Protocol performance – an eternal debate in computer networks …

​

• Delayed duplicates create a huge confusion in the packet switching network. A major challenge in packet switching network is to develop correct or at least acceptable protocols for handling delayed duplicates

​

Indian Institute of Technology Kharagpur

Connection Establishment – Handling Delayed Duplicates

• Solution 1: Use Throwaway Transport Address (Port Numbers)
• Do not use a port number if it has been used once already – Delayed duplicate packets will never find their way to a transport process
• Is this solution feasible?

​

• Solution 2: Give each connection a unique identifier chosen by the initiating party and put in each segment
• Can you see any problem in this approach?

Indian Institute of Technology Kharagpur

Connection Establishment – Handling Delayed Duplicates

• Solution 3: Devise a mechanism to kill off aged packets that are still hobbling about (Restrict the packet lifetime) – Makes it possible to design a feasible solution
• Three ways to restrict packet lifetime
• Restricted Network Design – Prevents packets from looping (bound the maximum delay including congestion)
• Putting a hop count in each packet – initialize to a maximum value and decrement each time the packet traverses a single hop (most feasible implementation)
• Timestamping each packet – define the lifetime of a packet in the network, need time synchronization across each router.

​

• Design Challenge: We need to guarantee not only that a packet is dead, but also that all acknowledgements to it are also dead

Indian Institute of Technology Kharagpur

Connection Establishment – Handling Delayed Duplicates

• Let us define a maximum packet lifetime T – If we wait a time T secs after a packet has been sent, we can be sure that all traces of it (packet and its acknowledgement) are now gone

​

• Rather than a physical clock (clock synchronization in the Internet is difficult to achieve), let us use a virtual clock – sequence number generated based on the clock ticks

​

• Label segments with sequence numbers that will not be reused within T secs.

​

• The period T and the rate of packets per second determine the size of the sequence number – at most one packet with a given sequence number may be outstanding at any given time

Indian Institute of Technology Kharagpur

Sequence Number Adjustment

• Two important requirements (Tomlinson 1975, Selecting Sequence Numbers)

​

• Sequence numbers must be chosen such that a particular sequence number never refers to more than one byte (for byte sequence numbers) at any one time (how to choose the initial sequence number)

​

• The valid range of sequence numbers must be positively synchronized between the sender and the receiver, whenever a connection is used (three way handshaking followed by the flow control mechanism – once connection is established, only send the data with expected sequence numbers)

Indian Institute of Technology Kharagpur

Why Initial Sequence Number is Important

• A Delayed duplicate packet of connection 1 can create a confusion for connection 2

Packet Lifetime T

Time

Sequence Numbers

Connection 1

Connection 2

Conn 1 crashed

Conn 2 initialized

Indian Institute of Technology Kharagpur

What We Ideally Want? Either …

Packet Lifetime T

Time

Sequence Numbers

Connection 1

Connection 2

Conn 1 crashed

Conn 2 initialized

Indian Institute of Technology Kharagpur

What We Ideally Want? Or …

Packet Lifetime T

Time

Sequence Numbers

Connection 1

Connection 2

Conn 1 crashed

Conn 2 initialized

Indian Institute of Technology Kharagpur

Connection Establishment – Handling Delayed Duplicates

• If a receiver receives two segments having the same sequence number within a duration T, then one packet must be the duplicate. The receiver then discards the duplicate packets.

​

• For a crashed device, the transport entity remains idle for a duration T after recovery, to ensure that all packets from the previous connection are dead – not a good solution

• Adjust the initial sequence numbers properly - A host does not restart with a sequence number in the forbidden region, based on the sequence number it used before crash and the time duration T.

Indian Institute of Technology Kharagpur

How do We Ensure that Packet Sequence Numbers are �Out of the Forbidden Region

• Two possible source of problems
• A host sends too much data too fast on a newly opened connection

​

​

​

​

• The data rate is too slow that the sequence number for a previous connection enters the forbidden region for the next connection

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Adjusting the Sending Rate based on Sequence Numbers

• The maximum data rate on any connection is one segment per clock tick
• Clock ticks (inter-packet transmission duration) is adjusted based on the sequences acknowledged – ensure that no two packets are there in the network with same sequence number
• We call this mechanism as self-clocking (used in TCP)
• Ensures that the sequence numbers do not warp around too quickly (RFC 1323)

​

• We do not remember sequence number at the receiver: Use a three way handshake to ensure that the connection request is not a repetition of an old connection request
• The individual peers validate their own sequence number by looking at the acknowledgement (ACK)
• Positive synchronization among the sender and the receiver

Indian Institute of Technology Kharagpur

Three Way Handshake

• By looking at the ACK, Host 1 ensures that Sequence number x does not belong to the forbidden region of any previously established connection

​

• By looking at the ACK in DATA, Host 2 ensures that sequence number y does not belong to the forbidden region of any previously established connection

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Three Way Handshake – CONNECTION REQUEST is a Delayed Duplicate

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Three Way Handshake – CONNECTION REQUEST and ACKNOWLEDGEMENT both are Delayed Duplicates

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release – Asymmetric Release

• When one party hangs up, the connection is broken

​

• This may results in data loss

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release – Symmetric Release

• Treats the connection as two separate unidirectional connections and requires each one to be released separately

​

• Does the job when each process has a fixed amount of data to send and clearly knows when it has sent it.

​

• What can be a protocol for this?
• Host 1: "I am done. Are you done?"
• Host 2: "I am done too. Goodbye."
• Each side disconnects.

​

• Does this protocol always work well?

Indian Institute of Technology Kharagpur

The Two Army Problem

No protocol exists to solve this

Let every party take independent decisions

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release – Final ACK Lost

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release – Response Lost

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Connection Release – Response Lost and Subsequent DRs Lost

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Ensure Reliability at the Transport Layer

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Error Control and Flow Control

• These features are used in both Data Link Layer and Transport Layer – Why?

​

• Flow control and error control at the transport layer is essential

​

• Flow control and error control at the data link layer improves performance

Indian Institute of Technology Kharagpur

Flow Control Algorithms

• Stop and Wait Flow Control (Error Free Channel):

Indian Institute of Technology Kharagpur

Flow Control Algorithms

• Stop and Wait (Noisy Channel):

​

• Use sequence numbers to individually identify each frame and the corresponding acknowledgement

Note: acknowledgement contains sequence no. of next expected frame in TCP actually

​

• What can be a minimum size of the sequence number in Stop and Wait?

​

• Automatic Repeat Request (ARQ)

0

1

0

1

1

Indian Institute of Technology Kharagpur

Stop and Wait ARQ – Sender Implementation

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Problem with Stop and Wait

• Every packet needs to wait for the acknowledgement of the previous packet.

​

• For bidirectional connections – use two instances of the stop and wait protocol at both directions – further waste of resources

​

• A possible solution: Piggyback data and acknowledgement from both the directions

​

• Reduce resource waste based on sliding window protocols (a pipelined protocol)

Indian Institute of Technology Kharagpur

Stop and Wait versus Sliding Window (Pipelined)

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Sliding Window Protocols

• Each outbound segment contains a sequence number – from 0 to some maximum (2ⁿ-1 for a n bit sequence number)

​

• The sender maintains a set of sequence numbers corresponding to frames it is permitted to send (sending window)

​

• The receiver maintains a set of frames it is permitted to accept (receiving window)

Indian Institute of Technology Kharagpur

Sliding Window Protocols – Sending Window and Receiving Window

Indian Institute of Technology Kharagpur

Sliding Window for a 3 bit Sequence Number

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Sliding Window Protocols in Noisy Channels

• A timeout occurs if a segment (or the acknowledgment) gets lost

​

• How does the flow and error control protocol handle a timeout?

​

• Go Back N ARQ: If segment N is lost, all the segments from segment 0

(start of the sliding window) to segment N are retransmitted

​

• Selective Repeat (SR) ARQ: Only the lost packets are selectively retransmitted
• Negative Acknowledgement (NAK) or Selective Acknowledgements (SACK): Informs the sender about which packets need to be retransmitted (not received by the receiver)

Indian Institute of Technology Kharagpur

Go Back N ARQ – Sender Window Control

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Go Back N ARQ

Source https://www.tutorialspoint.com/data_communication_computer_network/data_link_control_and_protocols.htm

Indian Institute of Technology Kharagpur

Go Back N ARQ – Sender

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Go Back N ARQ – Receiver

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Go Back N ARQ – A Bound on Window Size

• Outstanding Frames – Frames that have been transmitted, but not yet acknowledged

​

• Maximum Sequence Number (MAX_SEQ): MAX_SEQ+1 distinct sequence numbers are there
• 0,1,…,MAX_SEQ

​

• Maximum Number of Outstanding Frames (=Window Size): MAX_SEQ

​

• Example: Sequence Numbers (0,1,2,…,7) – 3 bit sequence numbers, number of outstanding frames = 7 (Not 8)

Indian Institute of Technology Kharagpur

Go Back N ARQ – A Bound on Window Size

• Let MAX_SEQ = 3, Window Size = 4

​

0

1

2

3

0

Timeout

Indian Institute of Technology Kharagpur

Go Back N ARQ – A Bound on Window Size

• Let MAX_SEQ = 3, Window Size = 3

​

0

1

2

0

Timeout

Discards the wrong frame correctly

Indian Institute of Technology Kharagpur

Selective Repeat (SR) – Window Control

Source: Computer Networks, Kurose, Ross

Indian Institute of Technology Kharagpur

Selective Repeat ARQ

Indian Institute of Technology Kharagpur

Selective Repeat – A Bound on Window Size

• Maximum Sequence Number (MAX_SEQ): MAX_SEQ+1 distinct sequence numbers are there
• 0,1,…,MAX_SEQ

​

• Maximum Number of Outstanding Frames ( =Window Size ): (MAX_SEQ+1)/2

​

• Example: Sequence Numbers (0,1,2,…,7) – 3-bit sequence numbers, number of outstanding frames (window size) = 4

Indian Institute of Technology Kharagpur

Selective Repeat – A Bound on Window Size

• Let MAX_SEQ = 3, Window Size = 3 [(MAX_SEQ+1)/2+1]

​

0

1

2

0

Timeout

1

2

1

2

1

2

1

2

Indian Institute of Technology Kharagpur

Selective Repeat – A Bound on Window Size

• Let MAX_SEQ = 3, Window Size = 2

​

0

1

0

Timeout

1

2

1

2

1

2

Discards the wrong frame correctly

Indian Institute of Technology Kharagpur

Bandwidth Delay Product

• Bandwidth Delay Product (BDP) = Link Bandwidth x Link Delay – an important metric for flow control

​

• Consider Bandwidth = 50 Kbps, one way transit time (delay) = 250 msec
• BDP 12.5 Kbit
• Assume 1000 bit segment size; BDP = 12.5 segments

​

• Consider the event of a segment transmission and the corresponding ACK reception – this takes a round trip time (RTT) – twice the one way latency.

​

• Maximum number of segments that can be outstanding during this duration = 12.5 x 2 = 25 segments

Indian Institute of Technology Kharagpur

Bandwidth Delay Product – Implication on Window Size

• Maximum number of segments that can be outstanding within this duration = 25 + 1 (as the ACK is sent only when the first segment is received) = 26
• This gives the maximum link utilization – the link will always be busy in transmitting data segments

​

• Let BD denotes the number of frames equivalent to the BDP, w is the maximum window size

​

• So, w = 2BD + 1 gives the maximum link utilization – this is an important concept to decide the window size for a window based flow control mechanism

Indian Institute of Technology Kharagpur

Implication of BDP on Protocol Design Choice

• Consider the link bandwidth = 1Mbps, Delay = 1ms
• Consider a network, where segment size is 1 KB (1024 bytes)
• Which protocol is better for flow control?
• (a) stop and wait,
• (b) Go back N,
• (c) Selective Repeat

​

• BDP = 1 Mbps x 1ms = 1 Kb (1024 bits)
• The segment size is eight times larger than the BDP -> the link can not hold an entire segment completely
• Sliding window protocols do not improve performance
• Stop and Wait is better – less complexity

Indian Institute of Technology Kharagpur

Application Transport Interfacing – Sender Side

APPLICATION

write(), send()

TportSend()

Send Data to IP

Transmission Rate Control

USER

KERNEL

Trigger Periodically

Function names are hypothetical

Indian Institute of Technology Kharagpur

Application Transport Interfacing – Sender Side

APPLICATION

write(), send()

TportSend()

Send Data to IP

Transmission Rate Control

USER

KERNEL

Trigger Periodically

Transport Buffer - Sender

Different connections are treated differently, so we need connection specific source buffering

write() call blocks the port until the complete data is written in the transport buffer

Function names are hypothetical

Indian Institute of Technology Kharagpur

Application Transport Interfacing – Receiver Side

APPLICATION

read(), recv()

CheckBuffer()

USER

KERNEL

Transport Buffer - Receiver

Interrupt

Data from IP

TportRecv()

read() call blocks the port until the data is received and the complete data is read from the transport buffer

Function names are hypothetical

Indian Institute of Technology Kharagpur

Application Transport Interfacing – Receiver Side (Alternate Implementation)

APPLICATION

read(), recv()

PollBuffer()

Data from IP

USER

KERNEL

Transport Buffer - Receiver

poll()

get()

TportRecv()

Function names are hypothetical

Indian Institute of Technology Kharagpur

Organizing Transport Buffer Pool

• If most segments are nearly the same size, organize the buffer as a pool of identically sized buffers (one segment per buffer)

​

• For variable segment size – chained fixed sized buffer (buffer size = maximum segment size)

​

​

​

• Space would be wasted if segment sizes are widely varied
• Small buffer size – multiple buffers to store a single segment – added complexity in implementation

​

Indian Institute of Technology Kharagpur

Organizing Transport Buffer Pool

• Variable size buffers (b)
• Advantage: better memory utilization
• Disadvantage: Complicated implementation

​

​

• Single large circular buffer for every connection (c)
• Good use of memory only when connections are heavily loaded

​

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Dynamic Buffer Management for Window Based Flow Control

• Sender and receiver needs to dynamically adjust buffer allocations

​

• Based on the rate difference between the receive rate by the transport entity and the receive rate by the application, the available size of the receiver buffer changes

​

​

​

​

• Sender should not send more data compared to receiver buffer space – dynamically adjust the window size based on availability of receiver buffer space

Free Space at Receiver Buffer

Segments awaiting at the buffer

Segments read by the application

Indian Institute of Technology Kharagpur

Dynamic Buffer Management for Window Based Flow Control

• Receiver forwards available buffer space through ACK

Ensure that the ACKs are flowing in the network continously

Indian Institute of Technology Kharagpur

Congestion Control in the Network

• Consider a centralized network scenario – how can you maintain optimal flow rates?

10

20

5

2

6

4

2

11

18

S

D

50

50

Apply Max Flow Min Cut Theorem !

But this is hard in a real network …

Indian Institute of Technology Kharagpur

Congestion Control in the Network

Changing Bandwidth Allocation over Time

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Congestion Control in the Network

• Flows enter and exit network dynamically – so applying an algorithm for congestion control is difficult

​

• Congestion avoidance: Regulate the sending rate based on what the network can support

Sending Rate = minimum (network rate, Receiver rate)

Gradually increase the network rate and observe the effect on flow rates (packet loss)

Comes from flow control – receiver advertised window size for a sliding window flow control

Indian Institute of Technology Kharagpur

Principles of congestion control

Congestion:

• Informally: “too many sources sending too much data too fast for network to handle”
• Manifestations:
• Long delays (queueing in router buffers)
• Packet loss (buffer overflow at routers)
• Different from flow control!

​

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 1

Simplest scenario:

​

maximum per-connection throughput: R/2

Host A

Host B

large delays as arrival rate λ_in approaches capacity

R

• One router, infinite buffers
• Input, output link capacity: R
• Two flows
• No retransmission needed

​

R

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Q: What happens as the arrival rate λ_in approaches R/2?

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

• One router, finite buffers

​

​

​

Host A

Host B

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

Host A

Host B

copy

free buffer space!

Idealization: Perfect knowledge

• Sender sends only when router buffers available

​

​

λ_out

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

Host A

Host B

copy

no buffer space!

Idealization: Some perfect knowledge

• Packets can be lost (dropped at router) due to full buffers
• Sender knows when packet has been dropped: only resends if packet known to be lost

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

Host A

Host B

free buffer space!

Idealization: Some perfect knowledge

• Packets can be lost (dropped at router) due to full buffers
• Sender knows when packet has been dropped: only resends if packet known to be lost

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

Host A

Host B

copy

Realistic scenario: Un-needed duplicates

• Packets can be lost, dropped at router due to full buffers – requiring retransmissions
• But sender timers can time out prematurely, sending two copies, both of which are delivered

​

free buffer space!

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 2

“costs” of congestion:

• More work (retransmission) for given receiver throughput
• Unneeded retransmissions: link carries multiple copies of a packet
• decreasing maximum achievable throughput

​

Realistic scenario: un-needed duplicates

• Packets can be lost, dropped at router due to full buffers – requiring retransmissions
• But sender times can time out prematurely, sending two copies, both of which are delivered

​

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 3

• Four senders
• Multi-hop paths
• Timeout/retransmit

​

finite shared output link buffers

Host A

Host B

Host C

Host D

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Q: What happens when λ_in and λ'_in increase?

A: As red λ'_in increases, all arriving blue packets at upper queue are dropped, blue throughput -> 0

Indian Institute of Technology Kharagpur

Causes/Costs of Congestion: Scenario 3

Another “cost” of congestion:

• When packet dropped, any upstream transmission capacity and buffering used for that packet was wasted!

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Congestion Control and Fairness

• Ensure that the rate of all the flows in the network is controlled in a fair way

​

• A bad congestion control algorithm may affect fairness - some flows can get starved

​

• Hard fairness in a decentralized network is difficult to implement

​

• Max-Min Fairness: An allocation is max-min fair if the bandwidth given to one flow cannot be increased without decreasing the bandwidth given to another flow with an allocation.

​

​

Indian Institute of Technology Kharagpur

Max-Min Fairness – An Example

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

AIMD – Efficient and Fair Operating Point for Congestion Control

• Additive Increase Multiplicative Decrease (AIMD) – Chiu and Jain (1989)

​

• Let w(t) be the sending rate. a (a > 0) is the additive increase factor, and b (0<b<1) is the multiplicative decrease factor

Indian Institute of Technology Kharagpur

AIMD – Design Rationale (Two Flows Example)

​

​

​

​

​

​

​

​

• AIAD – Oscillate across the efficiency line
• MIMD – Oscillate across the efficiency line (different slope from AIAD)

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

AIMD – Design Rationale (Two Flows Example)

​

​

​

​

​

​

​

​

• The path converges towards the optimal point
• Used by TCP - Adjust the size of the sliding window to control the rates

Source: Computer Networks (5^th Edition) by Tanenbaum, Wetherell

Indian Institute of Technology Kharagpur

Let us look TCP design details …

Indian Institute of Technology Kharagpur