Transport Layer & Transport Layer Congestion Control

What are the two generic forms of pipelined protocols?

go back N

selective repeat

How does pipelining work for rdt 3.0?

we send a bunch of things back to back without receiving an acknowledgement

How is the utilization equation changed with pipelining?

packet number * (L/R)/(RTT + L/R))

L = length in bits

Rate = bits/second

What must happen to the sequence numbers if we are pipelining?

Range of sequence numbers must be increased

Originally we used one bit for the sequence number (remember FSM), but with pipelining we need to increase the number of bits b/c we’re sending multiple packets

Besides adding bits for the sequence numbers, what other changes does pipelining cause?

buffering at sender and/or receiver (to receive multiple packets, buffer lets us send data back)

Go Back N is a pipeling protocol.

explain how it works.

Go Back N contains a window from the sender side with unACKed packets

As we receive acknowledgements in order, we shift the window

How does the window work in the Go Back N sender?

if the window is full, we cannot send

If it isn’t then we can send more packets

How do cumulative acknowledgements work for Go Back N?

Acks all packets up to, including sequence number n

• on receiving ack(N)< move window forward to begin at n + 1

What is the timer on for the Go-Back-N sender?

timer for oldest in-flight packet

How does the time out work for Go Back N sender?

retransmit packet n and all higher sequence number packets in the window

Within Go Back N sender, what does send-base represent?

the smallest sequence number for the oldest unack packet

Give the ranges for all colors of the window

already ack’ed

sent, not yet ack’ed

usable, not sent

not usable

green = [0, send_base - 1]

sent, not yet ack’ed = [send_base, ns-1]

usable, not yet sent = [ns, send_base + n - 1]

Not usable range = [ >= send_base + n]

Oh no, what if timer times out?

sender will resend all packets sent since the oldest unacknowledged packet

Go-Back-N: receiver

What happens if the packets come out of order?

we just let it time out and ask for retransmit

Disadvantage of go back n receiver

extra time retransmitting packets, better to buffer out of order packets

What is MSS?

Maximum segment size

(Sequence number on both sizes. Have buffer to determine receiving window as well for sender)

MSS is just how much data we can take

An alternate Ack mechanism would be for the receiver to individually acknowledge specific packets as they are received. What is this called?

selective repeat protocol

How does the selective repeat protocol work?

• receiver individually acknowledges all correctly received packets

• buffers packets as needed

• sender times out and retransmits individually for unAcked packets

  • timer for each unAcked packet

• sender window has N consecutive seqeunce numbers

• limits sequence #s of sent for unAcked packets

range for ack(n) packets for sender side

range for packet n in receiver side (window)

range for packet n, to acknowledge

range for ack(n) packets for sender side: [sendbase, sendbase + N]

range for packet n in receiver side = [rcvbase, rcvbase + n - 1]

Packet n in = [rcvBase - N, rcvbase - 1]

For selective repeat in action, what happens if a packet is lost?

it times out and the sender ONLY sends the missing packet, waiting for the matching acknowledgement

In TCP, what happens after a three way handshake?

sender and receiver establish parameters.

Sender establishes its own sequence number, receiver also sends sequence number

Sender and receiver decide buffer

When sender wants to send the data, data goes through send buffer. TCP does not specify when TCP will fetch/send data from buffer. It’s based off of TCP availability. TCP grabs the MSS. (Max transferable unit that the link layer can send. Link layer will send max size of frame it can send, and based off of that MSS is decided)

MSS is only application data, it is not transport header layer involved

Number of pacekts generated based off of MSS and filesize

size/MSS

(sequence number of first byte is zero)

TCP sequence numbers with telnet scenario (echoes back)

How to set TCP timeout value?

longer than RTT but RTT varies

If too short → premature timeout → unneessary retransmissions

if too long → slow reaction to segment lost

How to estimate RTT?

Sample RTT (measured time from segment transmission until ACK receipt)
- average of multiple measurements not just sampleRTT

How does TCP recompute the estimated RTT each time a new sampleRTT is taken

-

Given this value of the estimated RTT, TCP computes the timeout interval to vbe the estimated RTT plus a safety margin.

So, if we see a large variation in SampleRTT, the RTT estimates are fluctuation a lot, so we’ll want what type of safety margin?

a larger safety margin

The segment number is what number?

byte stream number of first data byte in the segment

Scenario, what does TCP receiver do?

Event:

arrival of in-order segment with

expected seq #. All data up to

expected seq # already ACKed

delayed ACK. Wait up to 500ms

for next segment. If no next segment,

send ACK

Scenario, what does TCP receiver do?

Event:

arrival of in-order segment with

expected seq #. One other 

segment has ACK pending

immediately send single cumulative

ACK, ACKing both in-order segments

Scenario, what does TCP receiver do?

Event:
arrival of out-of-order segment

higher-than-expect seq. # .

Gap detected

immediately send duplicate ACK,

indicating seq. # of next expected byte

Scenario, what does TCP receiver do?

Event:
arrival of segment that 

partially or completely fills gap

immediate send ACK, provided that

segment starts at lower end of gap

What is TCP fast retransmit and why is it needed?

Time-out period is often really long before packet is resent, so we detect the lost segments via duplicate ACKs

- if sender sends many segments back to back, then resent b/c if segment lost, there will be a lot of duplicate ACKs

• If sender receives 3 additional ACKs for the same data, resend unACKed segment with smallest sequence number

  • no need to wait for timeout if we have those duplicates

What is flow control?

– it allows the RECEIVER to explictly control the SENDER so sender won’t overflow receiver’s buffer by transmitting too much, too fast

(network layer delivers data faster than application layer removes data from socket buffers)

rcvBuffer stands for…

number of bytes associated with the buffer

Rwnd stands for…

receive window

Last Byte read stands for…

sequence number of last byte read from receiver buffer

Last byte received

sequence number of last byte placed in receiver buffer

How to tell how much received buffer is occupied?

last byte received - last byte read

How much of the received buffer is empty?

rcvBuffer - |LBrcved - LBread|

How to find the rwnd?

rwnd = RcvBuffer – [LastByteRcvd – LastByteRead]

In TCP flow control, what happens when Receiver advertise rwnd = 0 and no data to send?

Sender will not send data and will know when buffer opens up again if rwnd = 0 and no new data to send. No way to tell A the new capacity b/c A still thinks B is still full

Solution: even tho B send rwnd = 0, A will still send 1 byte of data to B. If the buffer has capacity available, it will read data and send packet back, so we have new capacity available to A (that A knows about).

flow control

number of bytes receiver willing to accept

(how much buffer space is available at receiver side)

On the sender side, what does the sender consistently have to run?

§LastByteSent – LastByteAcked <=rwnd

How can congestions occur?

1. Lost packets

   1. buffer overflow at routers

2. Long delays

   1. queuing in router buffers

Two approaches to congestion control

end-end congestion control

network-assisted congestion control

Describe end-end congestion control

• no explicit feedback from network

• conegestion inferred from end-system observed loss, delay

• approach taken by TCP

• router will enable bit from one router to another router, before being received by receiver. Receiver understands router is congested and sends back to sender that router is ocongestion

Describe network-assisted congestion control

routers provide feedback to end systems

• single bit indicating congestion (SNA,DECbit, ATM)

• explicit rate for sender to send at (sophisticated info, send at Mbps to solve congestion)

• choke packet + sophisticated

Explain TCP Congestion control:

1. Additive increase

2. Multiplicative decrease

TCP Congestion Control

1. Sender increases transmission rate (window size), probing for usable bandwith until loss occurs

• Additive increase

  • increase cwnd by 1 MSS every RTT until loss detective

• Multiplicative decrease

  • cut cwnd in half after loss

True or false: does sender have rwnd?

NO, sender has congestion window (cwnd)

is NOT part of TCP header

What does the cwnd do?

impose a constraint on the rate at which a TCP sender can send traffic into the network

the amount of unacknolwedged data at a sender may not exceed the minimum of cwnd and rwnd, show equation

TCP sending rate

• send cwnd bytes, wait RTT for ACKs, then send more bytes

How does TCP sender determine which rate data should be sent?

1. Lost segment indicates congestion → sender’s rate should be decreased

   1. time out or 4 additional duplicate ack

2. Acknowledgement segment indicates network is delivering data and sender’s rate can be increased

3. Bandwidth probing

   1. TCP strat to incrase rate in response to arriving ACK until loss event occurs, then decrease sender’s rate

Stages to TCP congestion Control Algorithm

1. Slow start

2. Congestion avoidance

3. Fast recovery (optional)

Describe TCP slow start

1. when connection begins, increase rate exponentially until first loss event

   1. initially cwnd = 1 MSS

      1. double cwnd every RTT

      2. done by incrementing cwnd for every ACK received

2. grows exponentially (slow start) then we slash it once congestion occurs, then half it

WHen do we go from slow start to fast recovery state?

when the loss indiciated by 3 duplicate acknolwdgement comes

when should the exponential increase switch to linear?

(slow start)

when cwnd gets to ½ its value before timeout

IMplementatino of switching slow start to contro lalgorithm

on loss event, ssthresh is set to ½ of cwnd just before loss event

TCP Tahoe vs TCP Reno

• when loss occurs with slow start, TCP Tahoe has CWND set to 1 MSS

• TCP Reno slashes it in half

What’s the point of ssthreshold?

it kind of acts as our constraint.

CWND just turns consistent, does not surpass ssthresh and we continue to send data linearly