6 - Congestion control & streaming

Question 1

Congestion Collapse

Answer 1

Increase in load -> Decrease in useful work

Cause of congestion collapse

• Spurious retransmission (solution is to have better timers and TCP congestion control)
• Undelivered packets (solution is to apply congestion control to all traffic)

Question 2

Goals of Congestion Control

Answer 2

• User network resources efficiently
• Preserve fair allocation of resources
• Avoid congestion collapse

Question 3

End-to-end (one approach to congestion control)

Answer 3

• No Feedback from network
• Congestion inferred by loss and delay
• Approach taken by TCP congestion control

Question 4

Network-assisted (one approach to congestion control)

Answer 4

• Routers provide feedback
  
  • > single bit
  • > explicit rates

Question 5

TCP Congestion Control

Answer 5

• Senders increase rate until packets are dropped
• TCP interprets packet loss as congestion and slows down.
• Congestion control has 2 parts:
  
  1. Increase algorithm - The sender must test the network to determine whether the network can sustain a higher sending rate
     2. Decrease algorithm - the senders react to congestion to achieve optimal loss rates, delays in sending rates

Question 6

Window-based aka AIMD (Approach to adjusting rates)

Answer 6

A sender can only have a certain number of packets outstanding or in flight

Sender uses acks from the receiver to clock the retransmission of new data

If sender wants to increase rate, they must increase the window size

In TCP, every time a sender receives an acknowledgement, it increases the window size

Success: one packet increased window per round trip (“additive increase”)

Failure: window size reduced by half (“multiplicative decrease”)

common way of performing congestion control

Question 7

Rate-based (Approach to adjusting rates)

Answer 7

• monitor loss rate

- uses timer to modulate

Question 8

What does AIMD converge to?

Answer 8

Fairness and efficiency

Question 9

Additive increase is applied

Answer 9

Increases efficiency

Question 10

Multiplicative decrease is applied

Answer 10

Increases fairness

Question 11

AIMD algorithm (TCP Congestion Control)

Answer 11

• Distributed, fair, efficient

- sawtooth behavior (rate vs time)

Question 12

Data Center & TCP “Incast”

Answer 12

racks connected to switches

• High “fan-in”
• High bandwidth, low latency
• lots of parallel requests each with small amount of data
• small switch buffers

The throughput collapse that results from this phenomenon is called TCP Incast

Incast is a drastic reduction in application throughput that results when servers using TCP all simultaneously request data, leading to a gross underutilization of network capacity in many-to-one communication networks like a data center.

The filling up of the buffers here at the switches result in bursty retransmissions that overfill the switch buffers. These bursting retransmissions are caused by TCP timeouts

TCP timeouts can last hundreds of milliseconds.

Roundtrip time in a data center network is typically less than a millisecond, often microseconds.

Because the roundtrip times are so much less than TCP timeouts the centers will have to wait for the TCP timeout before they retransmit

An application throughput can be reduced as much as 90% as a result of link idle time

Question 13

Barrier Synchronization & Idle Time

Answer 13

common request pattern

Whereby a client or an application might have many parallel threads and no forward progress can be made until all the responses for those threads are satisfied

The addition of more servers in the network induces an overflow of the switch buffer causing severe packet loss and inducing throughput collapse

Solution 1: Use fine grained TCP retransmission timers on the order of microseconds , rather than on the order of milliseconds , reducing the retransmission timeout for TCP, thus improves system throughput

Basic idea is that the timers need to operate on a granularity that’s close to the round-trip time of the network.

Solution 2: Have the client acknowledge every other packet rather than every packet, thus reducing the overall network load

Question 14

Challenges for Media Streaming

Answer 14

• Large volume of data
• Data volume varies over time
• Low tolerance for delay variation
• Low tolerance for delay, period
  (some loss is acceptable)

Question 15

Video Compression

Answer 15

• Image compression -> spatial redundancy
• Compression across images -> temporal redundancy

Video compression uses a combo of static image compression on reference frames (or anchor frames or I frames) and derived frames (P)

MPEG

Question 16

Streaming Video

Answer 16

• Server stores audio/video
• Client requests
  
  • > Playout at the “right time”

Server can divide data into segments, label each segment with a timestamp indicating the time at which that particular segment should be played so that client knows when to play that data.

The data must arrive to client quickly

Solution: Playout Buffer
Client stores data as it arrives from the server and plays the data for the user in a continuous fashion, thus data may arrive more slowly or quickly from the server, but as long as the client is playing data out of the buffer at a continuous rate, the user sees a smooth playout.

A client may typically wait a few seconds before it starts playing a stream to allow data to be built up in this buffer to account for cases when the server might have times where it is not sending at a rate that’s sufficient to satisfy the client’s playout rate

Question 17

Playout Delay

Answer 17

We might see packets generated at a particular rate and the packets might be received at slightly different times, depending on network delay.

We want to avoid these delays when we playout.

Playout delay allows client to achieve a smooth playout.

Some delay at the beginning of the playout is acceptable

Question 18

Pathologies streaming audio/video tolerate

Answer 18

Loss and Delay

Question 19

TCP is not a good fit for congestion control for streaming video or audio.

Answer 19

• Reliable Delivery
• Slowing down upon loss
• Protocol overhead

Consider using UDP 
- No Transmission
- No sending rate adaptations
Higher layers must solve the above problems
"TCP Friendly"

Question 20

Skype

Answer 20

• Central Login Server
• P2P data exchange
• Compression
• Encryption
• Delays
• Congestion
• Disruption

Question 21

Commonly used QoS for streaming audio/video

Answer 21

• Marking packets (by priority)

- Scheduling