Towards a Queue Sensitilve Transport Protocol

Towards a Queue Sensitive Transport Protocol Ritesh Kumar, Jasleen Kaur UNC-Chapel Hill

December 9, 2008

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

1 / 33

Why small delays?

Bandwidth is increasing without reduction in end to end latency. Queuing activity aggravates the situation by: Increasing the end to end latency [Armitage:2003]: Hindrance to interactive applications (VoIP, Online Gaming) Increasing buffering demand in routers [Appenzeller:2004]: Costly to build routers with lots of high speed memory Backbone ISPs over-provision to avoid queuing problems – costly!

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

2 / 33

TCP and Router Queues AIMD: maintaining high link utilization necessitates large buffers. I

Loss based congestion detection: fills up all of the queue.

Link fully utilized! buffer=BDP

BDP t

(a) TCP window variation

t

(b) Queue variation

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

3 / 33

TCP and Router Queues AIMD: maintaining high link utilization necessitates large buffers. I

Loss based congestion detection: fills up all of the queue.

Link fully utilized! buffer=BDP

BDP t

(c) TCP window variation

t

(d) Queue variation

The issue is further complicated by: Aggregation of connections: what happens to the sawtooth pattern? Packet arrival process at small timescales with aggregation

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

3 / 33

Solutions and their Scope

1. Reduce queuing activity “as much as possible” Constraint: Retain high (NewReno like) connection throughput Solves the latency problem; queue provisioning still high/uncertain

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

4 / 33

Solutions and their Scope

1. Reduce queuing activity “as much as possible” Constraint: Retain high (NewReno like) connection throughput Solves the latency problem; queue provisioning still high/uncertain 2. Reduce queue provisioning to a much smaller hard limit Solves both the latency and queue provisioning problems What about individual connection throughput?

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

4 / 33

Solutions and their Scope

1. Reduce queuing activity “as much as possible” Constraint: Retain high (NewReno like) connection throughput Solves the latency problem; queue provisioning still high/uncertain 2. Reduce queue provisioning to a much smaller hard limit Solves both the latency and queue provisioning problems What about individual connection throughput? In this paper, we take a look at point 1. only

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

4 / 33

Estimating Queuing Activity for Internet-like traffic Queue behavior with real traffic is not well understood.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

5 / 33

Estimating Queuing Activity for Internet-like traffic Queue behavior with real traffic is not well understood.

Factors which influence TCP’s impact on queuing Connection size: Larger connections ⇒ queue buildup RTTs: Large RTT ⇒ short-timescale burstiness (ack clocking) Socket buffer limits: ⇒ limits queue buildup Number of connections Connection arrival process

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

5 / 33

Estimating Queuing Activity for Internet-like traffic Queue behavior with real traffic is not well understood.

Factors which influence TCP’s impact on queuing Connection size: Larger connections ⇒ queue buildup RTTs: Large RTT ⇒ short-timescale burstiness (ack clocking) Socket buffer limits: ⇒ limits queue buildup Number of connections Connection arrival process

Need to study impact of TCP on queue with realistic traffic mix Keeping the above realistic and invariant across experiments

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

5 / 33

Goals

Evaluate prior proposals for reducing queuing activity Evaluate using realistic Internet-like traffic Propose new techniques learning from prior-work evaluation

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

6 / 33

Outline

1

Prior Work

2

Evaluation Methodology

3

Evaluation of Alternative CC Algorithms

4

Explicit Delay Notification (EDN)

5

Conclusion / Future Work

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

7 / 33

Analysis of burstiness in packet arrivals Methodology: Offline analysis of packet traces. Queue behavior cannot be directly inferred 1

Trace collected at a link is shaped by the link capacity.

input

input

output

output

queue

t

queue

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

t

December 9, 2008

8 / 33

Analysis of burstiness in packet arrivals Methodology: Offline analysis of packet traces. Queue behavior cannot be directly inferred 1

Trace collected at a link is shaped by the link capacity.

input

input

output

output

queue 2

t

queue

t

Publicly available traces are collected from under-utilized links.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

8 / 33

Analysis of burstiness in packet arrivals Methodology: Offline analysis of packet traces. Queue behavior cannot be directly inferred 1

Trace collected at a link is shaped by the link capacity.

input

input

output

output

queue

t

queue

t

2

Publicly available traces are collected from under-utilized links.

3

Close-loop interaction between TCP and router queues.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

8 / 33

Alternate Congestion Control Schemes Congestion Control schemes for reducing queue buildup Alternative CC Schemes

Delay-based CA Vegas [Brakmo:1995] end-to-end

AQM RED + ECN [Floyd:1993] router only

Explicit CC XCP, VCP [Xia:2005] router + end systems

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

9 / 33

Alternate Congestion Control Schemes Congestion Control schemes for reducing queue buildup Alternative CC Schemes

Delay-based CA Vegas [Brakmo:1995] end-to-end

AQM RED + ECN [Floyd:1993] router only

Explicit CC XCP, VCP [Xia:2005] router + end systems

RED+ECN ≤ Explicit CC VCP ≈ XCP; VCP closer to end-to-end CC than XCP

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

9 / 33

Standard NewReno with smaller queue provisioning √ [Appenzeller:2004] argue that BDP/ n queue provisioning suffices Aggregation smoothens the required queue variation to maintain high link utilization / connection throughput Problems: I I

difficult to estimate n or the no. of long-lived connections in a network degradation in throughput of connections due to high loss rates

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

10 / 33

Standard NewReno with smaller queue provisioning √ [Appenzeller:2004] argue that BDP/ n queue provisioning suffices Aggregation smoothens the required queue variation to maintain high link utilization / connection throughput Problems: I I

difficult to estimate n or the no. of long-lived connections in a network degradation in throughput of connections due to high loss rates

Not exactly a congestion control technique; closer to solution type 2. We are looking at limiting queue buildup and not queue provisioning

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

10 / 33

Outline

1

Prior Work

2

Evaluation Methodology

3

Evaluation of Alternative CC Algorithms

4

Explicit Delay Notification (EDN)

5

Conclusion / Future Work

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

11 / 33

Testbed

12 end hosts: Pentium III 800MHz - 1GHz, 1GB RAM, SCSI disks 2 routers: Dual Xeon 1.8GHz, 1.2GB RAM, SCSI disks Gigabit links; Routers have a 100Mbps link between them Hosts and routers run Linux (2.6.20, Feb 4th, 2007) with our changes Collect queuing activity log from the software byte-FIFO queue Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

12 / 33

Tmix Traffic Generator Tmix [Hernandez-Campos:2004] allows us to: replay realistic socket level activity (as observed in Internet traces). control the exact TCP algorithms and queuing schemes. We use very diverse traces as data sources: Trace

Description

cam-acc web-acc isp-peer

short and long flows long flows short flows

Median RTT 80ms 120ms 100ms

Forward Load 79Mbps 54Mbps 73Mbps

Reverse Load 12Mbps 5Mbps 56Mbps

We scale the load up to 75-95Mbps to magnify queue buildups. For brevity, we show only cam-acc results.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

13 / 33

Testbed Experiments

We vary Congestion Control scheme Traffic load

Performance Metrics Queue buildup Probability Distribution Data Transfer durations (= connection duration - total think time). I

both CDFs and CCDFs

Bottleneck link utilization

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

14 / 33

Outline

1

Prior Work

2

Evaluation Methodology

3

Evaluation of Alternative CC Algorithms

4

Explicit Delay Notification (EDN)

5

Conclusion / Future Work

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

15 / 33

Delay based Congestion Avoidance: TCP Vegas

Basic Idea: Impending congestion ⇒ queue buildup ⇒ increasing trend in RTTs. Detecting Queue buildup and Congestion Control: Vegas uses RTT samples to detect impending congestion. I

Uses the min RTT so far as propagation delay estimate.

Vegas uses AIAD for congestion avoidance. I I

Expected to reduce queue buildup. NewReno like slow-start and loss recovery.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

16 / 33

TCP Vegas: Queuing behavior 1e+07

90Mbps NewReno 90Mbps Vegas

Number of packets

1e+06 100000 10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

17 / 33

TCP Vegas: Queuing behavior 1e+07

90Mbps NewReno 90Mbps Vegas

Number of packets

1e+06 100000

large queue buildup

10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

17 / 33

TCP Vegas: “baseRTT” approximation Vegas’s problem: Using RTTs to estimate queue buildup. I

Estimation of “baseRTT” is inaccurate.

We compare tmix emulated min RTT and Vegas’ “baseRTT”. 1 0.9 Cumulative Distribution

0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

90Mbps Vegas (Vegas Base/Tmix Min) 95Mbps Vegas (Vegas Base/Tmix Min) 1

10 Base RTT/Min RTT

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

18 / 33

TCP Vegas: “baseRTT” approximation Vegas’s problem: Using RTTs to estimate queue buildup. I

Estimation of “baseRTT” is inaccurate.

We compare tmix emulated min RTT and Vegas’ “baseRTT”. 1 0.9 Cumulative Distribution

0.8 0.7 0.6

large error

0.5 0.4 0.3 0.2 0.1

90Mbps Vegas (Vegas Base/Tmix Min) 95Mbps Vegas (Vegas Base/Tmix Min) 1

10 Base RTT/Min RTT

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

18 / 33

TCP Vegas: Lessons learnt

Insight 1: Rely on explicit router feedback to detect presence of large queues I

Vegas rarely samples an empty queue; using RTTs can cause estimation errors

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

19 / 33

VCP: Link utilization based feedback

XCP: eXplicit Congestion control Protocol Router calculates per-packet cwnd increments. I

Packets carry congestion window and RTT information.

VCP: Variable-structure Congestion control protocol Router calculates and sends link utilization based metric as feedback. End systems adjust congestion window using – I I I

if feedback < 80%: Multiplicative Increase (MI) if feedback < 100%: Additive Increase (AI) if feedback > 100%: Multiplicative Decrease

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

20 / 33

VCP: Queue behavior 1e+07

90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP

Number of packets

1e+06 100000 10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

21 / 33

VCP: Queue behavior 1e+07

90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP

Number of packets

1e+06 100000

large queue buildup

10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

21 / 33

VCP’s Problem: aggressive MIAIMD congestion control

Does link utilization feedback perform well without aggressive CC?

TCP Util: Vegas like AIAD with link utilization Slow start till feedback < 80%. Vegas like AIAD congestion avoidance outside [80%-100%].

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

22 / 33

TCP Util: Queue behavior 1e+07

90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP 90Mbps Util

Number of packets

1e+06 100000 10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

23 / 33

TCP Util: Queue behavior 1e+07

90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP 90Mbps Util

Number of packets

1e+06 100000

small queue buildup

10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

23 / 33

TCP Util: Data Transfer Durations

1

1 Complementary Cumulative Distribution

0.9

Cumulative Distribution

0.8 0.7 0.6 0.5 0.4 0.3 90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP 90Mbps Util

0.2 0.1 0

0

500

1000

1500 2000 2500 3000 Data Transfer Time (ms)

3500

4000

90Mbps NewReno 90Mbps Vegas 90Mbps RED+ECN 90Mbps VCP 90Mbps Util

0.1

0.01

0.001

0.0001

1e-05

0

500000

1e+06 1.5e+06 Data Transfer Time (ms)

2e+06

Poor response time performance esp. for long connections

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

24 / 33

VCP: Lessons Learnt

Insight 2: No MIMD; use AIAD during congestion avoidance Use something better than link utilization for feedback

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

25 / 33

Outline

1

Prior Work

2

Evaluation Methodology

3

Evaluation of Alternative CC Algorithms

4

Explicit Delay Notification (EDN)

5

Conclusion / Future Work

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

26 / 33

Explicit Delay Notification (EDN)

Use of instantaneous queuing delay as feedback I I I

Packet header contains space for forward and reverse queuing delays End-system uses the round-trip queuing delay for congestion avoidance Feedback smoothing is delegated to end-systems F

End-systems have better knowledge of connection properties

AIAD congestion avoidance algorithm I I

Do slow start till feedback < B AIAD around a given parameter A

Avoids choosing a VCP like “control interval” Aims toward 100% link utilization (unlike link utilization feedback) I

VCP does MI (TCP Util does slow start) till only 80% utilization

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

27 / 33

EDN: Queue behavior 1e+07

90Mbps NewReno 90Mbps Util 90Mbps EDN

Number of packets

1e+06 100000 10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

28 / 33

EDN: Queue behavior 1e+07

90Mbps NewReno 90Mbps Util 90Mbps EDN

Number of packets

1e+06 100000

small queue buildup

10000 1000 100 10 1

0

200K

400K 600K 800K 1M Queue length (bytes)

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

1.2M

1.4M

December 9, 2008

28 / 33

EDN: Data Transfer Durations 1

1 Complementary Cumulative Distribution

0.9

Cumulative Distribution

0.8 0.7 0.6 0.5 0.4 0.3 0.2 90Mbps NewReno 90Mbps Util 90Mbps EDN

0.1 0

0

500

1000

1500 2000 2500 3000 Data Transfer Time (ms)

3500

4000

90Mbps NewReno 90Mbps Util 90Mbps EDN

0.1

0.01

0.001

0.0001

1e-05

0

500000

1e+06 1.5e+06 Data Transfer Time (ms)

2e+06

Good (close to NewReno) response time performance Parameters A and B need to be tuned according to traffic

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

29 / 33

EDN: Impact of load 1e+07

100000

Complementary Cumulative Distribution

Number of packets

0.01

85Mbps NewReno 95Mbps NewReno 85Mbps EDN 95Mbps EDN 85Mbps PEDN 95Mbps PEDN

1e+06

10000 1000 100 10 1

85Mbps NewReno 95Mbps NewReno 85Mbps EDN 95Mbps EDN 85Mbps PEDN 95Mbps PEDN

0.001

0.0001

1e-05 0

200K

400K 600K 800K 1M Queue length (bytes)

1.2M

1.4M

0

500000

1e+06 1.5e+06 Data Transfer Time (ms)

2e+06

EDN may sacrifice throughput for achieving low queue buildup I I

EDN gives queue buildup guarantees EDN parameters A and B control queue buildup

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

30 / 33

PEDN: Favoring connection throughput over queue buildup

Use per-flow number of queued packets for feedback Router uses a simple hash based algorithm for per-flow binning I I

Per packet CPU usage: O(1) Memory usage: O(queue) F

No. of flows whose packets are in the queue = O(queue)

Congestion Avoidance algorithm same as EDN I

Parameters: A = 2 pkts, B = 3 pkts

PEDN favors connection throughput over queue buildup I

PEDN gives throughput guarantees

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

31 / 33

Outline

1

Prior Work

2

Evaluation Methodology

3

Evaluation of Alternative CC Algorithms

4

Explicit Delay Notification (EDN)

5

Conclusion / Future Work

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

32 / 33

Conclusion / Future Work

Use of EDN with a queue provisioning scheme I

solution to problem type 2.

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

33 / 33

Conclusion / Future Work

Use of EDN with a queue provisioning scheme I

solution to problem type 2.

Both EDN and PEDN have the same congestion control algorithm I I

Mixed EDN / PEDN routers; Memory constrained routers can use EDN Need to rethink feedback semantics; can no longer be just delay

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

33 / 33

Conclusion / Future Work

Use of EDN with a queue provisioning scheme I

solution to problem type 2.

Both EDN and PEDN have the same congestion control algorithm I I

Mixed EDN / PEDN routers; Memory constrained routers can use EDN Need to rethink feedback semantics; can no longer be just delay

Thanks! Questions?

Ritesh Kumar, Jasleen Kaur (UNC-Chapel Hill) Towards a Queue Sensitive Transport Protocol

December 9, 2008

33 / 33