TOBB ET BL 552 Internet Architecture Lecture

Mehmet zdem

Trasport Layer Protokolleri-Part-2

What is Flow/Congestion/Error Control ?

Flow Control: Algorithms to prevent that the sender overruns the receiver with information? Congestion Control: Algorithms to prevent that the sender overloads the network Error Control: Algorithms to recover or conceal the effects from packet losses The goal of each of the control mechanisms are different.

But the implementation is combined

3

TCP Flow Control

TCP implements sliding window flow control
Sending acknowledgements is separated from setting the window size at sender. Acknowledgements do not automatically increase the window size

Acknowledgements are cumulative

Sliding Window: Example

Receiver Buffer Sender sends 2K of data
0 4K

2K SeqNo=0
2K

Sender sends 2K of data

Win=204 AckNo=2048 2K SeqNo=2 048

Sender blocked

4K

AckNo=4096

Win=0
3K

Win= AckNo=4096

1024

TCP Congestion Control

TCP has a mechanism for congestion control. The mechanism is implemented at the sender. The sender has two parameters:

Congestion Window (cwnd) Slow-start threshhold Value (ssthresh)

Initial value is the advertised window size

Congestion control works in two modes:

slow start (cwnd < ssthresh) congestion avoidance (cwnd >= ssthresh
6

Slow Start

Initial value:

Set cwnd = 1
Note: Unit is a segment size. TCP actually is based on bytes and increments by 1 MSS (maximum segment size)

The receiver sends an acknowledgement (ACK) for each packet

Note: Generally, a TCP receiver sends an ACK for every other segment.

Each time an ACK is received by the sender, the congestion window is increased by 1 segment: cwnd = cwnd + 1

If an ACK acknowledges two segments, cwnd is still increased by only 1 segment.

Even if ACK acknowledges a segment that is smaller than MSS bytes long, cwnd is increased by 1.

Does Slow Start increment slowly? Not really. In fact, the increase of cwnd is exponential

Slow Start Example

The congestion window size grows very rapidly

cwnd = 1 cwnd = 2

segment 1

t1 ACK for segmen

segment 2 segment 3

For every ACK, we increase cwnd by 1 irrespective of the number of segments ACKed

cwnd = 4

ts 2 ACK for segmen ts 3 ACK for segmen segment 4 segment 5 segment 6

TCP slows down the increase of cwnd when cwnd > ssthresh

ts 4 ACK for segmen ts 5 ACK for segmen ts 6 ACK for segmen

cwnd = 7

Congestion Avoidance

Congestion avoidance phase is started if cwnd has reached the slow-start threshold value If cwnd >= ssthresh then each time an ACK is received, increment cwnd as follows:

cwnd = cwnd + 1/ [cwnd]

Where [cwnd] is the largest integer smaller than cwnd 9

Slow Start/Congestion Avoidance

Assume that
cwnd = 1 cwnd = 2

ssthresh = 8
14
Cwnd (in segments)

cwnd = 4

12 10 8 6 4 2 0
0 2 4 t= t= t=
Roundtrip times ssthresh

cwnd = 8

cwnd = 9

t=

cwnd = 10

10

Responses to Congestion

So, TCP assumes there is congestion if it detects a packet loss A TCP sender can detect lost packets via: Timeout of a retransmission timer Receipt of a duplicate ACK

TCP interprets a Timeout as a binary congestion signal. When a timeout occurs, the sender performs: cwnd is reset to one: cwnd = 1 ssthresh is set to half the current size of the congestion window: ssthressh = cwnd / 2 and slow-start is entered

11

Summary of TCP congestion control

Initially: cwnd = 1; ssthresh = advertised window size; New Ack received: if (cwnd < ssthresh) /* Slow Start*/ cwnd = cwnd + 1; else /* Congestion Avoidance */ cwnd = cwnd + 1/cwnd; Timeout: /* Multiplicative decrease */ ssthresh = cwnd/2; cwnd = 1;

12

Flavors of TCP Congestion Control

TCP Tahoe (1988, FreeBSD 4.3 Tahoe)

Slow Start Congestion Avoidance Fast Retransmit

Fast Recovery

TCP Reno (1990, FreeBSD 4.3 Reno)

New Reno (1996) SACK (1996)

13

Acknowledgments in TCP

Receiver sends ACK to sender ACK is used for flow control, error control, and congestion control ACK number sent is the next sequence number expected Delayed ACK: TCP receiver normally delays transmission of an ACK (for about 200ms) Why? ACKs are not delayed when packets are received out of sequence Why?

1K SeqNo=0 AckNo=1024

1K SeqNo=1 024 AckNo=2048 1K SeqNo =2048 1K SeqNo=3072

AckNo=2048

Lost segment

14

Acknowledgments in TCP

Receiver sends ACK to sender ACK is used for flow control, error control, and congestion control ACK number sent is the next sequence number expected Delayed ACK: TCP receiver normally delays transmission of an ACK (for about 200ms) Why? ACKs are not delayed when packets are received out of sequence Why?

1K SeqNo=0 AckNo=1024

1K SeqNo=1 024 AckNo=2048

1K SeqNo=204

1K Se q N o =3 0 7 2

AckNo=2048

Out-of-order arrivals

15

Fast Retransmit
1K SeqNo=0

If three or more duplicate ACKs are received in a row, the TCP sender believes that a segment has been lost.

AckNo=1024 1K SeqNo=1 024 1K SeqNo=2 048

duplicate

Then TCP performs a retransmission of what seems to be the missing segment, without waiting for a timeout to happen.
Enter slow start: ssthresh = cwnd/2 cwnd = 1

AckNo=1024 1K SeqNo=3 072

duplicate

AckNo=1024 1K SeqNo=1 024 1K SeqNo=4 096

16

Fast Recovery

cwnd=12 sshtresh=5
AckNo=1024

1K SeqNo=0

Fast recovery avoids slow start after a fast retransmit Intuition: Duplicate ACKs indicate that data is getting through After three duplicate ACKs set: Retransmit lost packet ssthresh = cwnd/2 cwnd = cwnd+3 Enter congestion avoidance Increment cwnd by one for each additional duplicate ACK When ACK arrives that acknowledges new data (here: AckNo=2028), set: cwnd=ssthresh enter congestion avoidance

cwnd=12 sshtresh=5

1K SeqNo=1 024 1K SeqNo=2 048

cwnd=12 sshtresh=5

AckNo=1024 1K SeqNo=3 072

cwnd=12 sshtresh=5

AckNo=1024 1K SeqNo=1 024 1K SeqNo=4 096

cwnd=9 sshtresh=9

AckNo=2048

17

UDP (User Datagram Protocol)

UDP is used to send isolated messages between applications
Data units are referred to as USER DATAGRAMS UDP is connectionless and often used for database lookups
18

Unreliably?

What good is that? Packet loss rate is extremely low (<< 1%) Packets usually dropped by overloaded routers (as well see later) This is good enough for us to build the User Datagram Protocol (UDP)

UDP

For applications where IP guarantees of reliability are good-enough

Streaming multimedia, stock quotes

Extends IP packet with source port, destination port In addition, provides fragmentation (and checksum)

Fragmentation in UDP

Very simple: splits large UDP datagram into multiple IP datagrams, each with a sequence number Marks fragmented bit in the UDP header If one fragment is lost, the whole UDP packet is discarded UDP datagrams are discarded if checksum fails

IP Layer
IP layer routes data between hosts; data may traverse a different layer of hosts. Data is carried in units called datagrams IP layer is connectionless every datagram is routed independently no guarantees to the in sequence delivery of the packets OSI layer 3 corresponds to IP layer

22

IP Header Structure

23

IP Header Fields
Version--Indicates the version of IP currently used. IP header length (IHL)--Indicates the datagram header length in 32-bit words. Type-of-service- Specifies how a particular upper-layer protocol would like the current datagram to be handled. Datagrams can be assigned various levels of importance through this field. Total length--Specifies the length of the entire IP packet, including data and header, in bytes. Identification--Contains an integer that identifies the current datagram. This field is used to help piece together datagram fragments.

24

IP Header Structure
Flags--A 3-bit field of which the low-order 2 bits control fragmentation. One bit specifies whether the packet can be fragmented; the second bit specifies whether the packet is the last fragment in a series of fragmented packets. Time-to-live--Maintains a counter that gradually decrements down to zero, at which point the datagram is discarded. This keeps packets from looping endlessly. Protocol--Indicates which upper-layer protocol receives incoming packets after IP processing is complete.

25

IP Header Structure
Header checksum--Helps ensure IP header integrity. Source address--Specifies the sending node.

Destination address--Specifies the receiving node.

Options--Allows IP to support various options, such as security.

Data--Contains upper-layer information.

Check Related Header Fields from WIRESHARK Capture Program!

26

IP operation

27

MTU, Datagram Size

A datagram is always encapsulated in whatever frame type is used by the LAN it is being sent across Each hardware frame has a limit on the maximum amount of data it may carry - this is the MTU of the network Ethernet uses an MTU of 1500 bytes but other network technologies use a smaller MTU When a large datagram (which fits into one 1500 octet frame) reaches a network with a smaller MTU it must be broken into several smaller datagrams-called fragmentation

fragmentation

28

MTU, Datagram Size

Reassembly - with the FLAGS bits and IDENTIFICATION the final destination has enough information to reassemble the original datagram fragments can be further fragmented if necessary - as long as FRAGMENT OFFSET values are reset appropriately the destination machine has no need to know if a fragment is a whole fragment or a subfragment Fragment Loss/Delay - if a fragment is not present during reassembly - the destination machine holds all subfragments for a max. period while waiting for the missing fragment(s) - after the max time the whole datagram is discarded - remember that this is a "best effort" delivery which is connectionless - higher layers (Transport Layer) must deal with missing datagrams

29

Fragmentation
each fragment has its own IP header which is nearly identical to the original header but the data part of each fragment is smaller each fragment has a bit set in the FLAGS part of the header specifying that it is a fragment, a FRAGMENT OFFSET value which specifies the position of this fragment in the original datagram, and the final fragment has another flag bit set to show it is the final fragment of an original datagram IDENTIFICATION - a unique number placed in each outgoing datagram which is also placed into each fragment

30

Fragmentation
Flags is 3 bits in IP header. Bit 0 is reserved, and is always set to 0. Bit 1 is the DF bit (0 ="may fragment," 1 = "don't fragment"). Bit 2 is the MF bit (0 = "last fragment," 1 = "more fragments").
Value 0 1 Bit 0 0 0 Bit 1 May Dont Bit2 Last More

Fragmentation Offset is 13 bits IP header and indicates where a fragment belongs in the original IP datagram. This value is a multiple of eight bytes.

Fragmentation Example
MTU :1500 byte, Packet Total Length: 2180 byte with IP Header, how can you fragment the packet?
Sequence 0 Identifier 345 Total Length 2180 DF 0 MF 0
Fragment Offset

The first fragment has an offset of 0, the length of this fragment is 1500; this includes 20 bytes for the slightly modified original IP header. The second fragment has an offset of 185 (185 x 8 = 1480), which means that the data portion of this fragment starts 1480 bytes into the original IP datagram. The length of this fragment is 700; this includes the additional IP header created for this fragment.
Sequence
0-0 0-1

Identifier
345 345

Total Length
1500 700

DF
0 0

MF
1 0

Fragment Offset

0 185