Monarch: A Tool to Emulate Transport Protocol Flows over the ...
Monarch: A Tool to Emulate Transport Protocol Flows over the Internet at Large Andreas Haeberlen Marcel DischingerKrishna Gummadi Stefan Saroiu MPI-SWS MPI-SWS University of Toronto MPI-SWS / Rice University 2006 Andreas Haeberlen, MPI-SWS 1 Motivation New protocol design is an active research area State of the art for protocol evaluation:
PCP [NSDI 2006], TCP BIC [Infocom 2004], TCP Vegas, TCP Nice [OSDI 2002], TFRC [Sigcomm 2000] Analysis Simulation/emulation Testbeds But: We still do not understand protocol performance over the real, heterogeneous Internet Fiber, cable, DSL, cellular, wireless, ... 2006 Andreas Haeberlen, MPI-SWS 2 The Monarch tool Monarch emulates transport protocols over the Internet at large Scale: Can use millions of live Internet paths
Realism: Captures the Internet's heterogeneity Accuracy: Emulation is accurate 2006 Andreas Haeberlen, MPI-SWS 3 Outline Overview How Monarch works Evaluation Applications Summary 2006 Andreas Haeberlen, MPI-SWS 4 How Monarch works TCP
Sender Data packet (1500 bytes) Internet Internet TCP Sender Host under our control Internet Internet ACK packet (40 bytes) Host under our control TCP Receiver TCP Receiver Standard TCP 2006 Andreas Haeberlen, MPI-SWS
5 How Monarch works TCP Sender Internet Internet TCP Receiver Standard TCP 2006 Andreas Haeberlen, MPI-SWS Host under our control TCP Sender TCP Receiver Data packet, 1500 bytes Probe packet, 1500 bytes (e.g. TCP ACK) Internet
Internet Response packet, 40 bytes (e.g. TCP RST) Internet host (not under our control) Monarch 6 How Monarch works Internet Internet Response packets Probe packets Path is stressed in the same way TCP Receiver Similar throughput, delay, loss, reordering Standard TCP 2006 Andreas Haeberlen, MPI-SWS
Small packets Data packets TCP Receiver Big packets Internet Internet TCP Sender Small packets Big packets TCP Sender ? Monarch 7 What are the limitations?
How many hosts will respond? Which protocols can it emulate? What are sources of inaccuracy? 2006 Andreas Haeberlen, MPI-SWS 8 How many hosts will respond? s t s Broadband Academico Router h 0 % ry 69.6 % TCP ACK 7.2 % 13.4 0 a 0
, s s% ICMP TsReq 18.0 %10 4.9 63.0 % e c d e n %f n 8.9 % ICMP EchoReq 25.0 89.3 % fi i o t e% UDP Packet 7.4 4.1 % 7.3 % r y o s a Any probe 18.1 %
90.3 % E or m28.4 % Probe packet Host type At least 18% of the hosts respond 2006 Andreas Haeberlen, MPI-SWS 9 Which protocols can it emulate? Monarch works with many protocols TCP BIC, TCP Nice, TCP Westwood, TCP Vegas, Highspeed TCP, Scalable TCP, Fast TCP SACK, FACK, Window Congestio scaling n PCP, RAP, TFRC experience d!
Some protocols cannot be used ECN, XCP 2006 Andreas Haeberlen, MPI-SWS 10 What are sources of inaccuracy? Monarch interprets upstream packet loss as downstream packet loss Upstream losses cause additional retransmissions Paper discusses other challenges Delayed ACKs, middleboxes, upstream reordering 2006 Andreas Haeberlen, MPI-SWS 11 Monarch knows when it made a mistake
ID 17 ID 17 ID 18 ID 19 Monarch uses IPIDs to find potential inaccuracies When a flow has completed, it is classified as: Confirmed: No upstream loss or upstream reordering Inaccurate: Upstream loss or upstream reordering Indeterminate: Not enough information to self-diagnose 2006 Andreas Haeberlen, MPI-SWS 12 Outline
Overview How Monarch works Evaluation Applications Summary 2006 Andreas Haeberlen, MPI-SWS 13 Methodology Run real and emulated TCP transfers over the same links, compare the results Endpoints: 4 hosts under our control: Seattle, Houston, Boston, Saarbrcken (Germany) 356 PlanetLab nodes Each flow transfers 500kB
12,166 flow pairs total 2006 Andreas Haeberlen, MPI-SWS 14 CWND (packets) RTO (milliseconds) Monarch and TCP are very close Time (seconds) Monarch and TCP flow go through the same states Look at aggregate statistics Throughput, latency, loss 2006 Andreas Haeberlen, MPI-SWS 15 Why? Throughput is similar Fraction of flows
100% 80% Ideal result 60% 40% Monarch vs. TCP 20% TCP vs. TCP 0% 25% 50% -100% -75% -50% -25% 0% Relative error (Monarch/TCP) 75% 100% Compare average throughput of Monarch/TCP flows Half of the Monarch flows have <5% relative error 2006 Andreas Haeberlen, MPI-SWS 16
How often does it make mistakes? Earlier: Inaccuracies if upstream losses are present Monarch can detect upstream losses How often does that actually happen? Datasets: Broadband: 4,805 cable and DSL hosts in 11 ISPs Router: 697 Internet routers 2006 Andreas Haeberlen, MPI-SWS 17 Monarch is accurate for many Internet paths Result Router
Traces total Broadband 15,642 100.0 % 2,776 100.0 % Most flows were not affected by upstream loss or upstream reordering 2006 Andreas Haeberlen, MPI-SWS 18 Outline Overview How Monarch works Evaluation Applications Summary
2006 Andreas Haeberlen, MPI-SWS 19 Monarch is useful in many ways Evaluating transport protcols Inferring network properties Example: How well do different congestion control algorithms work for DSL and cable? Example: Characterize networks that researchers do not have access to Other examples are in the paper 2006 Andreas Haeberlen, MPI-SWS 20
Congestion control over broadband 400 300 200 100 0 0 1 2 3 4 Time (seconds) Reno 1 2 3 4 Time (seconds) BIC 100 0 1 2 3 4 Time (seconds) 80 60 40
20 0 Vegas Results: 0 Low RTT! CWND (packets) RTT (ms) RTT >400ms! RTT >300ms! Slow start Congestion avoidance 500 Long last-mile queues are prevalent Reno and BIC do not keep RTT under control; Vegas does Linux default setting caused highest queueing delay! But it still does not achieve a higher throughput
2006 Andreas Haeberlen, MPI-SWS 21 Fraction of flows Fraction of flows TCP throughput over DSL and cable ISP #4 ISP #5 ISP #2 ISP #6 ISP #3 ISP #1 ISP #7 ISP #8 ISP #9 ISP #10 ISP #11 DSL ISPs: Ameritech BellSouth
BTOpenWorld PacBell Qwest SWBell Cable ISPs: Charter Chello Comcast Roadrunner Rogers Throughput (kbps) 2006 Andreas Haeberlen, MPI-SWS 22 Summary Monarch emulates transport protocols over the Internet at large Monarch enables designers to evaluate their protocols in a realistic environment Monarch is accurate over a variety of Internet paths
Examples: DSL and cable 2006 Andreas Haeberlen, MPI-SWS 23 Thank you! Source code and data sets are available at: http://monarch.mpi-sws.org/ Questions? 2006 Andreas Haeberlen, MPI-SWS 24
Warm-up Title:1/25 "Allusion" Copy the definition: Allusion: referring to a well-known place, person, event, or story. Write the following phrase: "I was not born in a manger. I was actually born on Krypton and sent here by my father, Jor-el,...
"Quod qui bene (non) intelligit... "Szemantikai megjegyzések Anselmus ontológiai argumentumához Ferencz Sándor 2006_05_15 Anselmus Cantuariensis (1033-1109) Proslogion 2 Így hát, Uram, aki a hit számára megadod az értést, add meg nekem - amennyire helyesnek ítéled -, hogy meg is értsem,...
Title: Cell Probe Complexity Last modified by: Haim Kaplan Document presentation format: On-screen Show Other titles: Times New Roman Comic Sans MS Arial Symbol Arial Unicode MS Standarddesign MathType 5.0 Equation Abstract Data Types Stack, Queue Amortized analysis Queue The...
Times New Roman Symbol Comic Sans MS Blank Presentation MathType 4.0 Equation Microsoft Equation 3.0 PowerPoint Presentation Homework #7 Exam #2 Results Second Moments of Area Moments of Area Moments of Basic Shapes Polar Moment Parallel Axis Theorem Radius of...
Lines 223-239: Which sentence states the main idea in this passage? Cite one detail from the passage that supports the main idea. from Flesh & Blood So Cheap. 8. Lines 254-265: What details describe Chief Croker? Why does the author...
HOW CAN NEUROIMAGING HELP UNDERSTAND, DIAGNOSE, AND DEVELOP TREATMENTS FOR ALZHEIMER'S DISEASE? Part C - AD brain scans - anatomical NUCLEAR MEDICINE GRAND ROUNDS Stanford University J. Wesson Ashford, M.D., Ph.D. Clinical Professor (affiliated), Department of Psychiatry and Behavioral Sciences