Transcript XCP

XCP
eXplicit Control Protocol
A Linux implementation and analysis
What is XCP?
• XCP was developed by Dina Katabi from MIT, and
released as a draft RFC on October 17. 2004.
• XCP was conceived as an answer to the question:
“Given our current knowledge of congestion control,
how would we ideally like congestion control to work?”
• XCP is a protocol developed in order to improve
TCP’s congestion control algorithm. Especially in
networks with a high bandwidth-delay product.
• XCP takes a new approach congestion control by
letting the routers in the network return explicit
feedback back to the hosts.
The Master Thesis
• Create a working Linux implementation using the
draft RFC directly.
• Since the XCP protocol was to be implemented as
a separate protocol layer, the implementation
should not change any existing TCP/IP code.
• Using this implementation to test the protocol in a
real network.
• Compare the results from the real Linux
implementation with the original simulations by D.
Katabi and other implementations.
Why develop XCP?
• TCP is 25 years old, and is designed to work in
networks with much lower bandwidth-delay
products than current networks.
• TCP use packet drops to control transmission
speed, and uses an AIMD (Arithmetic Increase,
Multiplicative Decrease) algorithm to adjust the
sending speed.
• The higher the Bandwidth-Delay product, the less
efficient TCP’s congestion control algorithms are.
• Networks with high delays makes TCP react
slower to packet drops. Additionally, bandwidth is
reacquired more slowly in such networks.
XCP’s solution
• XCP allows the routers in the network to
continuously adjust the sending speed of any
participating hosts.
• These adjustments are done by changing the
contents of the packets (XCP header) transferred
between the sender and receiver.
• The feedback from routers are used by the sender
to adjust the transfer speed to fit the routers
current load.
Router
Router
XCP protocol layer
• XCP introduces a 20 byte header
between IP and TCP that carries
information about the sender’s
desired bandwidth and information
about what the routers allow.
• XCP requires all routers and hosts in
the network to use the XCP protocol
in order to work as intended.
• The XCP protocol bases all
adjustments of bandwidth on a per
packet calculation. XCP routers does
not need to separate between
different data-flows, but make
adjustments on each individual
packet.
Application
TCP
XCP
IP
Link
The TCP/XCP/IP stack
The XCP header
0
1
2
3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Format|
Protocol
|
Length
|
unused
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
RTT
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Throughput
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Delta_Throughput
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Reverse_Feedback
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version
Format
Protocol
Length
Unused
:
:
:
:
:
1
1 (Full header), 2 (Minimal header)
Next level protocol (6 for TCP)
20
0
RTT
: Round Trip Time as measured from the sender in milliseconds
Throughput: The current throughput in bytes/ms in use by the sender
Delta_Throughput: The wanted change in throughput wanted by the sender,
measured in bytes/second.
Reverse_Feedback: The contents of the Delta_Throughput field when the
message is returned back to the sender from the
receiver.
The XCP algorithm
• The sender fills in the fields in the XCP header.
The Delta_Throughput field contains the amount
of bandwidth the sender wants to use if no
congestion exist in the network.
• The XCP routers checks incoming requests for
bandwidth and downgrades the Delta_Throughput
field if not enough bandwidth is available.
• The receiver returns the Delta_Throughput back
to the sender in the ACK message in the
Reverse_Feedback field.
• The reverse feedback is then used by the sender
to adjust its sending rate accordingly. So that the
sender will adjust to the available bandwidth in
the network.
An XCP network (simplified)
Network RTT: 100 ms
Router’s capacity: 200.000 B/s
(available 200.000 B/s)
Sender’s capacity: 10.000.000 B/s (available 10.000.000 B/s)
Sender’s current throughput: 0 B/s (or 0 B/ms)
1
1
6 20 0
100
0
10.000.000
0
Sender
1
1
6 20 0
100
RTT
Current Throughput 0
Delta Throughput 200.000
0
Feedback
Router
1
2
6 20 0
100
0
0
200.000
Receiver
An XCP network (simplified)
Network RTT: 100 ms
Router’s capacity: 200.000 B/s
(0 B/s is available)
Sender’s capacity: 10.000.000 B/s (9.800.000 B/s is available)
Sender’s current throughput: 200.000 B/s (or 200 B/ms)
1
1
6 20 0
100
200
9.800.000
0
Sender
1
1
6 20 0
100
RTT
Current Throughput 200
Delta Throughput 0
0
Feedback
Router
1
2
6 20 0
100
0
0
0
Receiver
XCP algorithms at sender
When sending the current throughput is calculated
using the formula:
cwnd
thrp 
RTT
Delta throughput is calculated on a per packet basis
using the following formula:
cap  (thrp *1000)
thrp 
thrp * RTT / MSS
The feedback is calculated using this formula:
cwnd new  max( cwnd old 
fbckrev * RTT
, MSS )
1000
XCP algorithms at router
• The router periodically (each average RTT
milliseconds) calculates the load on itself, and
adjusts how much bandwidth to allow for the
following interval.
• During the previous interval, the router collects
data from the XCP and IP header of all passing
packets (such as their RTT, throughput and size ).
• This data is then used to calculate how
adjustments to each packet’s delta throughput is
done.
• The XCP router basically allows 40% of available
bandwidth to be distributed during the next
interval.
XCP router algorithms
The XCP router uses the following formula to adjust
how much bandwidth to allow for the next interval:
Queue
Fbk 1000 * (0,4 * (Cap  input _ bw)  0,226 *
avr _ RTT
The resulting feedback is then distributed using an
AIMD (Arithmetic Increase, Multiplicative Decrease)
algorithm. In the case where more bandwidth is
available the XCP router will increase the bandwidth
of all flows with the same amount.
If too little bandwidth is available, the reduction for
each XCP flow will be proportional with the flow’s
current bandwidth usage.
XCP router example
Arithmetic Increase:
A router having one flow using 1.000.000 B/s and
ten flows using 10.000 B/s each is to distribute
440.000 B/s. This will give each flow additional
40.000 B/s, so the large flow will get 1.040.000 B/s
and the small ones 50.000 B/s
Multiplicative Decrease:
A router having one flow using 1.000.000 B/s, and
10 flows using 10.000 B/s each, needs to reduce
the throughput by 110.000 B/s (10%). The large
flow will be reduced to 900.000 B/s while the 10
small flows to 9.000 B/s
• The combination of these two algorithms allows
each flow to acquire its fair share of the total
available bandwidth in the network.
XCP Linux implementation issues
• XCP is based on floating point calculations, while
the Linux kernel only allows integer arithmetic.
• XCP needs to change TCP’s congestion window,
thereby invalidating the TCP/IP stack protocol
hierarchy.
• In addition XCP needs to know about different
TCP flows to work. Further invalidating the
protocol hierarchy.
• Hardware checksums in network cards failed,
because of the addition of a new header between
TCP and IP.
XCP Performance
• The throughput = cwnd/RTT formula leads to
invalid XCP feedback during startup
• XCP fails to improve startup speed compared to
TCP, because of TCP’s reliance of the peer’s
“advertised window”.
2000
Packets
1600
Overestimation of congestion window,
due to invalid feedback.
1200
Congestion Window
Advertised Window
800
400
0
0
10000
20000
30000
40000
50000
Milliseconds
60000
70000
80000
90000
XCP Router Queues vs. TCP
• XCP manages to prevent router queues and
packet drops on full duplex network.
XCP router queue and packet drops
Queue
Dropped
80
70
Packets
60
50
40
30
20
10
0
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
Milliseconds
TCP router queue and packet drops
Queue
Dropped
900
800
700
Packets
600
500
400
300
200
100
0
0
10000
20000
30000
40000
50000
Milliseconds
60000
70000
80000
90000
100000
XCP bandwidth distribution
•XCP manages to quickly distribute the available
bandwidth fairly and smoothly between different
flows. The bandwidth usage for each flow stays
constant, and does not oscillate.
Flow 1
Bandwidth Utilization: 4 XCP streams. 30 seconds skew.
Flow 2
Flow 3
Bandwidth Utilization (%)
100
Flow 4
80
60
40
20
0
0
50000
100000
150000
200000
Millisecond
250000
300000
350000
400000
XCP fails in half duplex mode
• On half duplex network, the XCP router fails give
correct feedback to the hosts. This causes queue
buildup, and more oscillatory bandwidth usage.
XCP queue on half duplex network. (1 flow)
Queue
800
Packets
600
400
200
0
0
10000
20000
30000
40000
50000
Milliseconds
60000
70000
80000
90000
100000
XCP fails if sender is bursty
• If the sender transfers data periodically, the XCP
protocol fails to converge. This leads to large
queue buildups, and packet drops.
• Unfortunately for XCP, periodic transfers of data
is very common in the real world.
Cwnd
XCP congestion window and advertised window
Wnd
Inflated congestion window, as XCP
fails to give negative feedback.
3000
Packets
2500
2000
1500
1000
500
0
0
10000
20000
30000
40000
Milliseconds
50000
60000
70000
80000
XCP fails if sender is bursty 2
• As the XCP protocol fails to reduce the
congestion window, queues build up in the router.
• This leads to packet drops, which XCP
supposedly should prevent.
XCP router queue and drops
Queue
Drops
400
Packets
300
200
100
0
0
10000
20000
30000
40000
Milliseconds
50000
60000
70000
80000
Summary
• XCP manages to deliver on its promises in
situations where the XCP router can create a valid
model of the network load.
• When the XCP router fails to correctly predict its
load, the protocol fails. These situations include
half-duplex links, lack of buffer space, periodically
sending applications, and overloaded hosts.
• Implementing XCP as a separate protocol, does
not give enough control over TCP. Using the
congestion window is not exact enough in order
to for XCP to work.
• A feedback mechanism that works in all real life
scenarios must be more advanced than the one
currently in use by XCP.
The Future
• XCP is “revolutionary” in the sense it uses
feedback from the network to improve congestion
control.
• XCP’s design prevents gradual introduction in
Internet.
• XCP has problems working in real life situations.
• Demanding more work to be done by routers is
probably not a good idea for faster networks.
• The XCP routers base their distribution of
bandwidth to all flows, on input from flows that is
not verified.
Questions?