prezo

  • Published on
    13-Aug-2015

  • View
    58

  • Download
    0

DESCRIPTION

1. Introduction Tests Recent advances Future work and contributions Extra slides Implementing CAIA Delay-Gradient in Linux Kenneth Klette Jonassen Department of Informatics…

Transcript

1. Introduction Tests Recent advances Future work and contributions Extra slides Implementing CAIA Delay-Gradient in Linux Kenneth Klette Jonassen Department of Informatics University of Oslo 2. Introduction Tests Recent advances Future work and contributions Extra slides Outline Introduction Thesis subject Thesis outline Tests Recent advances Future work and contributions Future work Linux contributions Early access Extra slides 3. Introduction Tests Recent advances Future work and contributions Extra slides Thesis subject The goal of this thesis is to implement CAIA Delay-Gradient (CDG) in Linux CDG is the result of previous work done at Swinburne University’s Centre for Advanced Internet Architectures CDG is influenced by previous congestion controls Our contribution is to make CDG work for Linux The optimal outcome is to get our CDG implementation accepted into mainline Linux Keep it maintained for future versions of Linux Make CDG available to a broad audience of users See benefits to real-world applications outside academia 4. Introduction Tests Recent advances Future work and contributions Extra slides Thesis outline Internet congestion control Transmission Control Protocol (TCP) CDG is a TCP congestion control Network delays CDG is a delay-based congestion control Why delay works as a congestion signal When delay does not work as a congestion signal Implementing CDG in Linux Preliminaries for congestion control development in Linux Shortcomings of Linux’ RTT measurements ... and how these were addressed. Valid measurements are vital to CDG’s performance Testbed setup Mitigating hidden variables that could distort or bias results Evaluation of homogeneous capacity sharing 5. Introduction Tests Recent advances Future work and contributions Extra slides Experiment testbed Linux router Switch Linux receiver FreeBSD sender Linux sender Gigabit ethernet Management Dedicated gigabit links between the router and hosts Management network runs over seperate network interfaces Using HTB to shape traffic to 10 Mbps Using netem to emulate RTT of 40 ms or 70 ms 84p FIFO queue with Tail drop 6. Introduction Tests Recent advances Future work and contributions Extra slides vs.CDG CUBIC 40 ms RTT 10 Mbps bottleneck 84p FIFO queue with Tail drop 7. Introduction Tests Recent advances Future work and contributions Extra slides flent http://www.flent.org/ (formerly known as netperf-wrapper) 8. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 2 4 6 8 10 12 Mbits/s cdg Upload Ping (ms) 0 20 40 60 80 100 120 140 ms 0 50 100 150 200 250 300 Time (s) 0 2 4 6 8 10 12 Mbits/s cubic Upload Ping (ms) 0 20 40 60 80 100 120 140 ms Single TCP upload stream w/ping Bandwidth and ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:13:44.876320 - Length/step: 300s/0.20s 9. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 2 4 6 8 10 Mbits/s cdg Stream 1 Stream 2 0 50 100 150 200 250 300 Time (s) 0 2 4 6 8 10 Mbits/s cubic Stream 1 Stream 2 Two TCP upload streams; 2nd stream started delayed Bandwidth plot, 5 second smoothed sample size Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:24:46.627611 - Length/step: 300s/0.20s 10. Introduction Tests Recent advances Future work and contributions Extra slides 627611.cdg 523368.cubic 0 1 2 3 4 Meanbandwidth(MBits/s) Stream 1 Stream 2 Two TCP upload streams; 2nd stream started delayed Summarising combined tests Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:24:46.627611 - Length/step: 300s/0.20s 11. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 2 4 6 8 10 Mbits/s cdg Download Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 0 50 100 150 200 250 300 Time (s) 0 2 4 6 8 10 Mbits/s cubic Download Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 8 down - dslreports dsl test equivalent Total bandwidth and average ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:46:42.323957 - Length/step: 300s/0.20s 12. Introduction Tests Recent advances Future work and contributions Extra slides Download Ping (ms) 0 2 4 6 8 10 12 Mbits/s cdg cubic 0 20 40 60 80 100 120 140 Latency(ms) 8 down - dslreports dsl test equivalent Box plot of totals Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:46:42.323957 - Length/step: 300s/0.20s 13. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 2 4 6 8 10 Mbits/s cdg Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 0 50 100 150 200 250 300 Time (s) 0 2 4 6 8 10 Mbits/s cubic Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) Realtime Response Under Load Total bandwidth and average ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:57:46.372348 - Length/step: 300s/0.20s 14. Introduction Tests Recent advances Future work and contributions Extra slides Download Upload Ping (ms) 0 2 4 6 8 10 12 14 16 Mbits/s cdg cubic 0 20 40 60 80 100 120 140 Latency(ms) Realtime Response Under Load Box plot of totals Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:57:46.372348 - Length/step: 300s/0.20s 15. Introduction Tests Recent advances Future work and contributions Extra slides 0 20 40 60 80 100 120 140 ms 0 5 10 15 20 Mbits/s cdg cubic Realtime Response Under Load Ellipsis plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 00:57:46.372348 - Length/step: 300s/0.20s 16. Introduction Tests Recent advances Future work and contributions Extra slides vs.CDG CUBIC 40 ms RTT 100 Mbps bottleneck 840p FIFO queue with Tail drop 17. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 20 40 60 80 100 Mbits/s cdg Upload Ping (ms) 0 10 20 30 40 50 60 70 80 ms 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 100 Mbits/s cubic Upload Ping (ms) 0 10 20 30 40 50 60 70 80 ms Single TCP upload stream w/ping Bandwidth and ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 01:56:42.773456 - Length/step: 300s/0.20s 18. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 20 40 60 80 Mbits/s cdg Stream 1 Stream 2 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 Mbits/s cubic Stream 1 Stream 2 Two TCP upload streams; 2nd stream started delayed Bandwidth plot, 5 second smoothed sample size Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:07:46.457561 - Length/step: 300s/0.20s 19. Introduction Tests Recent advances Future work and contributions Extra slides 457561.cdg 384635.cubic 0 10 20 30 40 Meanbandwidth(MBits/s) Stream 1 Stream 2 Two TCP upload streams; 2nd stream started delayed Summarising combined tests Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:07:46.457561 - Length/step: 300s/0.20s 20. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 20 40 60 80 100 Mbits/s cdg Download Ping (ms) 0 20 40 60 80 100 120 140 Latency(ms) 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 100 Mbits/s cubic Download Ping (ms) 0 20 40 60 80 100 120 140 Latency(ms) 8 down - dslreports dsl test equivalent Total bandwidth and average ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:36:10.066039 - Length/step: 300s/0.20s 21. Introduction Tests Recent advances Future work and contributions Extra slides Download Ping (ms) 0 20 40 60 80 100 120 Mbits/s cdg cubic 0 20 40 60 80 100 120 140 Latency(ms) 8 down - dslreports dsl test equivalent Box plot of totals Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:36:10.066039 - Length/step: 300s/0.20s 22. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 20 40 60 80 100 Mbits/s cdg Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 100 Mbits/s cubic Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) Realtime Response Under Load Total bandwidth and average ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:47:14.909773 - Length/step: 300s/0.20s 23. Introduction Tests Recent advances Future work and contributions Extra slides Download Upload Ping (ms) 0 20 40 60 80 100 120 Mbits/s cdg cubic 0 20 40 60 80 100 120 Latency(ms) Realtime Response Under Load Box plot of totals Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:47:14.909773 - Length/step: 300s/0.20s 24. Introduction Tests Recent advances Future work and contributions Extra slides 0 20 40 60 80 100 120 140 ms 0 50 100 150 200 Mbits/s cdg cubic Realtime Response Under Load Ellipsis plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:47:14.909773 - Length/step: 300s/0.20s 25. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 20 40 60 80 100 120 Mbits/s cdg Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 100 120 Mbits/s cubic Download Upload Ping (ms) 0 20 40 60 80 100 120 Latency(ms) 50 up vs 1 down - exclusively Best Effort Total bandwidth and average ping plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 03:32:07.805839 - Length/step: 300s/0.20s 26. Introduction Tests Recent advances Future work and contributions Extra slides 0 50 100 150 200 250 300 0 10 20 30 40 50 60 70 Mbits/s TCP download CDG BE Cubic BE CDG CS1 Cubic CS1 Avg 0 50 100 150 200 250 300 0 10 20 30 40 50 60 70 Mbits/s TCP upload CDG BE Cubic BE CDG CS1 Cubic CS1 Avg 0 50 100 150 200 250 300 Time (s) 0 20 40 60 80 100 120 Latency(ms) Ping (ms) UDP CS6 UDP CS1 UDP BE ICMP Avg Cubic VS CDG Download, upload, ping (unscaled versions) Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:30:38.827305 - Length/step: 300s/0.20s 27. Introduction Tests Recent advances Future work and contributions Extra slides CDG BE Cubic BE CDG CS1 Cubic CS1 Avg 0 10 20 30 40 50 60 70 Mbits/s Cubic VS CDG Download bandwidth box plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:30:38.827305 - Length/step: 300s/0.20s 28. Introduction Tests Recent advances Future work and contributions Extra slides CDG BE Cubic BE CDG CS1 Cubic CS1 Avg 0 10 20 30 40 50 60 70 Mbits/s Cubic VS CDG Upload bandwidth box plot Local/remote: bestemor/10.0.1.2 - Time: 2015-06-15 02:30:38.827305 - Length/step: 300s/0.20s 29. Introduction Tests Recent advances Future work and contributions Extra slides CDG has parameters to tune its backoff behavior (p.61) HOMOGENEOUS CAPACITY SHARING 61 G = 1 G = 2 G = 3 0.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 0.00 0.25 0.50 0.75 1.00 2◊0msdelay2◊10msdelay2◊20msdelay2◊35msdelay 0 40 80 0 40 80 0 40 80 Queueing delay (msecs) EmpiricalCDF Implementation FreeBSD Linux Homogeneous capacity sharing – CDG G œ {1, 2, 3} Delay œ {0, 10, 20, 35} Figure 4.7: Queueing delay distributions, as measured by the sender and the receiver in cooperation. 30. Introduction Tests Recent advances Future work and contributions Extra slides Recent advances 31. Introduction Tests Recent advances Future work and contributions Extra slides CDG is now a part of net-next 32. Introduction Tests Recent advances Future work and contributions Extra slides CDG was featured on lwn.net ... 33. Introduction Tests Recent advances Future work and contributions Extra slides Future work Hybrid Slow start (HyStart) Avoiding slow start overshoot avoids loss and delay CDG can exit slow start using its probabilistic backoff HyStart can exit slow start deterministically RTT independent congestion avoidance Faster rate increase to help CDG level with CUBIC Possibly a new algorithm that refines CUBIC Parameters for using CDG in different environments Defaults are magic numbers One-way delay measurements Avoid conflating delay in forward and reverse paths, e.g., simultaneous download and upload Hardware RTT measurements Possible with some recent adapters 34. Introduction Tests Recent advances Future work and contributions Extra slides Hybrid Slow start tcp_cubic has HyStart Important to avoid slow start overshoot Alleviates an issue that could be caused by Proportional Rate Reduction (PRR) “Linux TCP/Reno behavior with large DropTail Queue” (rite-research e-mail) Should we add a global PRR on/off knob in Linux? ... and tcp_cdg now has HyStart! Previous HyStart code is tightly tangled into tcp_cubic We have an opportunity to improve HyStart tcp_cubic is the default, and is sensitive to change tcp_cdg is a new module CDG’s HyStart uses Hayes’ Delayed ACK filter Helps avoid spurious slow start exits CDG’s HyStart uses a microsecond clock Increases accuracy for high speeds 35. Introduction Tests Recent advances Future work and contributions Extra slides Contributions (patches) to Linux Commit Description Linux 3725a26 pkt_sched: fq: avoid hang when ... 3.19 – pkt_sched: fq: avoid artificial bursts ... – 932eb76 tcp: use RTT from SACK for CC 4.0 3d0d26c tcp: fix bogus RTT when retrans... 4.1 196da97 tcp: move struct tcp_sacktag_state to ... (4.2) 31231a8 tcp: improve RTT from SACK for CC (4.2) 138998f tcp: invoke pkts_acked hook on every ACK (4.2) 7782ad8 tcp: export tcp_enter_cwr() (4.2) 2b0a8c9 tcp: add CDG congestion control (4.2) 758f0d4 tcp: cdg: use div_u64() (4.2) Patches for Linux 4.2 are in net-next, where they remain until Linux 4.1 is released and the merge window for Linux 4.2 opens. 36. Introduction Tests Recent advances Future work and contributions Extra slides Early access Clone Linux’ net-next git tree: git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git Select to compile tcp_cdg, e.g., using make menuconfig: . . . 37. Introduction Tests Recent advances Future work and contributions Extra slides Hybrid Slow start with pacing Hybrid Slow start consists of two algorithms to help probe the slow start threshold: ACK train detection Delay threshold detection Setups using pacing must disable ACK train detection The ACK train algorithm probes the Bandwidth Delay Product by guessing the sum of inter-packet arrival times It assumes that packets are sent in bursts Pacing spaces the inter-packet transmission times Can still use the delay threshold algorithm Set parameter hystart_detect=2 for tcp_cubic and tcp_cdg to selectively enable the delay threshold algorithm.