Good Ideas So Far : Flow Control

Good Ideas So Far…
• Flow control
• Stop & wait
15-441 Computer Networking • Parallel stop & wait
• Sliding window
Lecture 17 – TCP & Congestion Control • Loss recovery
• Timeouts
• Acknowledgement-driven recovery (selective repeat or
cumulative acknowledgement)
Lecture 17: TCP & Congestion Control 2
Outline Sequence Numbers (reminder)
• How large do sequence numbers need to be?

• Must be able to detect wrap-around
• TCP flow control • Depends on sender/receiver window size
• E.g.
• Max seq = 7, send win=recv win=7
• Congestion sources and collapse • If pkts 0..6 are sent succesfully and all acks lost
• Receiver expects 7,0..5, sender retransmits old 0..6!!!
• Max sequence must be ! send window + recv window
• Congestion control basics
Lecture 17: TCP & Congestion Control 3 Lecture 17: TCP & Congestion Control 4
Sequence Numbers TCP Flow Control
• 32 Bits, Unsigned ! for bytes not packets!

• TCP is a sliding window protocol
• Circular Comparison
b
• For window size n, can send up to n bytes without
receiving an acknowledgement
a
a • When the data is acknowledged then the window
b slides forward
Max 0 Max 0
• Each packet advertises a window size
b<a a<b
• Indicates number of bytes the receiver has space for
• Why So Big?
• Original TCP always sent entire window
• For sliding window, must have
|Sequence Space| > |Sending Window| + |Receiving Window|
• But receiver buffer space != available net. capacity!
• No problem • Congestion control now limits this
• Also, want to guard against stray packets • window = min(receiver window, congestion window)
• With IP, packets have maximum lifetime of 120s
• Sequence number would wrap around in this time at 286MB/s =~ 2.3Gbit/s
(hmm!)
Window Flow Control: Send Side Window Flow Control: Send Side
Packet Sent Packet Received

Source Port Dest. Port Source Port Dest. Port
Sequence Number Sequence Number
window
Acknowledgment Acknowledgment
HL/Flags Window HL/Flags Window
D. Checksum Urgent Pointer D. Checksum Urgent Pointer
Sent and acked Sent but not acked Not yet sent Options… Options...
App write
Next to be sent
acknowledged sent to be sent outside window

Window Flow Control: Receive Side TCP Persist
• What happens if window is 0?

What should receiver do?
• Receiver updates window when application reads data
New • What if this update is lost?
• TCP Persist state
Receive buffer
• Sender periodically sends 1 byte packets
• Receiver responds with ACK even if it can’t store the
packet
Acked but not Not yet
delivered to user acked
window
Performance Considerations Outline
• The window size can be controlled by receiving

application
• Can change the socket buffer size from a default (e.g. • TCP flow control
8-64Kbytes) to some maximum value
• Modern TCPs (linux, bsd, os x) may auto-tune
• Historical source of performance problems on fast nets
• Congestion sources and collapse
• The window size field in the TCP header limits the
window that the receiver can advertise • Congestion control basics
• 16 bits ! 64 KBytes
• 10 msec RTT ! 51 Mbit/second
• 100 msec RTT ! 5 Mbit/second
• TCP options to get around 64KB limit ! increases
above limit
Internet Pipes? Internet Pipes?
• How should you control • How should you control

the faucet? the faucet?
• Too fast – sink overflows!
Internet Pipes? Internet Pipes?
• How should you control • How should you control

the faucet? the faucet?
• Too fast – sink overflows! • Too fast – sink overflows
• Too slow – what happens? • Too slow – what happens?
• Goals
• Fill the bucket as quickly
as possible
• Avoid overflowing the sink
• Solution – watch the sink
Plumbers Gone Wild! Plumbers Gone Wild 2!
• How do we prevent water • Now what?

loss? • Feedback from the bucket or
the funnels?
• Know the size of the
pipes?
Congestion Causes & Costs of Congestion
10 Mbps • Four senders – multihop paths Q: What happens as rate

1.5 Mbps • Timeout/retransmit increases?
100 Mbps
• Different sources compete for resources inside

network
• Why is it a problem?
• Sources are unaware of current state of resource
• Sources are unaware of each other
• Manifestations:
• Lost packets (buffer overflow at routers)
• Long delays (queuing in router buffers)
• Can result in throughput less than bottleneck link (1.5Mbps
for the above topology) ! a.k.a. congestion collapse
Causes & Costs of Congestion Congestion Collapse
• Definition: Increase in network load results in

decrease of useful work done
• Many possible causes
• Spurious retransmissions of packets still in flight
• Classical congestion collapse
• How can this happen with packet conservation? RTT
increases!
• Solution: better timers and TCP congestion control
• When packet dropped, any “upstream transmission • Undelivered packets
capacity used for that packet was wasted! • Packets consume resources and are dropped elsewhere in
network
• Solution: congestion control for ALL traffic
Congestion Control and Avoidance Approaches Towards Congestion

Control
• A mechanism that: • Two broad approaches towards congestion control:
• Uses network resources efficiently
• Preserves fair network resource allocation • End-end congestion • Network-assisted
control: congestion control:
• Prevents or avoids collapse • Routers provide feedback to
• No explicit feedback from
• Congestion collapse is not just a theory network end systems
• Single bit indicating
• Has been frequently observed in many networks • Congestion inferred from congestion (SNA,
end-system observed loss, DECbit, TCP/IP ECN,
delay ATM)
• Approach taken by TCP • Explicit rate sender
should send at
• Problem: makes routers
complicated
Example: TCP Congestion Control Outline
• Very simple mechanisms in network

• FIFO scheduling with shared buffer pool
• Feedback through packet drops • TCP flow control
• TCP interprets packet drops as signs of congestion and
slows down
• This is an assumption: packet drops are not a sign of congestion
• Congestion sources and collapse
in all networks
• E.g. wireless networks
• Periodically probes the network to check whether more • Congestion control basics
bandwidth has become available.
Objectives Phase Plots
• Simple router behavior • What are

• Distributedness desirable
Fairness Line
properties?
• Efficiency: X = "xi(t)
• What if flows are Overload
• Fairness: ("xi)2/n("xi2) not equal?

User 2’s
Allocation
x2 Optimal point
• What are the important properties of this function?
• Convergence: control system must be stable Underutilization
Efficiency Line
User 1’s Allocation x1
Basic Control Model Linear Control
• Reduce speed when congestion is perceived • Many different possibilities for reaction to
• How is congestion signaled? congestion and probing
• Either mark or drop packets • Examine simple linear controls
• Window(t + 1) = a + b Window(t)
• How much to reduce?
• Different ai/bi for increase and ad/bd for decrease
• Increase speed otherwise
• Supports various reaction to signals
• Probe for available bandwidth – how?
• Increase/decrease additively
• Increased/decrease multiplicatively
• Which of the four combinations is optimal?
Phase Plots Additive Increase/Decrease
• Simple way to • Both X1 and X2

visualize behavior increase/ decrease
of competing by the same amount Fairness Line
connections over over time T1

• Additive increase
time User 2’s
Allocation improves fairness and
User 2’s
Allocation T0
x2 x2
additive decrease
reduces fairness
Efficiency Line
User 1’s Allocation x1 User 1’s Allocation x1
Muliplicative Increase/Decrease Convergence to Efficiency
• Both X1 and X2
increase by the
Fairness Line
same factor over T1
time Fairness Line

User 2’s
• Extension from Allocation xH
x2
origin – constant T0
fairness User 2’s

Allocation
x2
Efficiency Line

Efficiency Line
Distributed Convergence to Efficiency Convergence to Fairness
a>0 & b>1

a=0
b=1
Fairness Line
a<0 & b>1
xH
a>0 & b<1 Fairness Line

User 2’s
Allocation x2 xH
User 2’s
Allocation
x2
xH’
a<0 & b<1
Efficiency Line
Efficiency Line

Convergence to Efficiency & Fairness What is the Right Choice?
• Intersection of valid regions • Constraints limit

• For decrease: a=0 & b < 1 us to AIMD Fairness Line
x1
• Can have
Fairness Line
multiplicative x0
User 2’s
term in increase Allocation
xH x2 x2
(MAIMD)
User 2’s
Allocation • AIMD moves
x2
towards optimal Efficiency Line
xH’ point
Efficiency Line
Important Lessons Important Lessons
• Transport service • Why is congestion control needed?

• UDP ! mostly just IP service
• TCP ! congestion controlled, reliable, byte stream
• How to evaluate congestion control algorithms?
• Types of ARQ protocols
• Why is AIMD the right choice for congestion control?
• Stop-and-wait ! slow, simple
• Go-back-n ! can keep link utilized (except w/ losses)
• Selective repeat ! efficient loss recovery • TCP flow control
• Sliding window flow control • Sliding window ! mapping to packet headers
• TCP flow control • 32bit sequence numbers (bytes)
• Sliding window ! mapping to packet headers
• 32bit sequence numbers (bytes)
Pipes…Tubes…Let’s call
Good Ideas So Far…
the whole thing off
• Flow control • An alternate way to look at congestion?
• Stop & wait
• Parallel stop & wait
• Sliding window (e.g., advertised windows)
• Loss recovery
• Timeouts
• Acknowledgement-driven recovery (selective repeat or cumulative
acknowledgement)
• Congestion control
• AIMD ! fairness and efficiency
• Next Lecture: How does TCP actually implement these?

Good Ideas So Far : Flow Control

Uploaded by

Copyright:

Available Formats

Good Ideas So Far : Flow Control

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Good Ideas So Far : Flow Control

Uploaded by

Copyright:

Available Formats

Good Ideas So Far…

Lecture 17: TCP & Congestion Control 2

Outline Sequence Numbers (reminder)

• How large do sequence numbers need to be?

• 32 Bits, Unsigned ! for bytes not packets!

Packet Sent Packet Received

acknowledged sent to be sent outside window

• What happens if window is 0?

Performance Considerations Outline

• The window size can be controlled by receiving

• How should you control • How should you control

Internet Pipes? Internet Pipes?

• How should you control • How should you control

• Solution – watch the sink

• How do we prevent water • Now what?

Congestion Causes & Costs of Congestion

10 Mbps • Four senders – multihop paths Q: What happens as rate

• Different sources compete for resources inside

• Definition: Increase in network load results in

Congestion Control and Avoidance Approaches Towards Congestion

• Very simple mechanisms in network

Objectives Phase Plots

• Simple router behavior • What are

• Fairness: ("xi)2/n("xi2) not equal?

User 1’s Allocation x1

Phase Plots Additive Increase/Decrease

• Simple way to • Both X1 and X2

connections over over time T1

User 1’s Allocation x1 User 1’s Allocation x1

time Fairness Line

fairness User 2’s

User 1’s Allocation x1

User 1’s Allocation x1

Distributed Convergence to Efficiency Convergence to Fairness

a>0 & b>1

a>0 & b<1 Fairness Line

User 1’s Allocation x1

• Intersection of valid regions • Constraints limit

User 1’s Allocation x1

Important Lessons Important Lessons

• Transport service • Why is congestion control needed?

• Next Lecture: How does TCP actually implement these?

You might also like