peter

Emulating low priority transport at the application layer: A Background Transfer Service: 

Emulating low priority transport at the application layer: A Background Transfer Service Laurent Massoulié andamp; Peter Key (Microsoft Research, Cambridge) Bing Wang (U Mass)

Background transfers: 

Background transfers Windows updates www.microsoft.com

Outline : 

Outline Motivation and background Receive window / receive rate relation: Fluid models Control objectives and resulting allocations Algorithms Binary Search Stochastic Approximation Simulation results

Background Transfers: 

Background Transfers Useful for OS updates, P2P file sharing, Prefetching. Requirements: Don’t impact existing foreground flows; Use available capacity efficiently.

Existing Approaches for “worse than best effort”: 

Existing Approaches for 'worse than best effort' Require Transport level changes (to TCP) Delay-based congestion control TCP Nice [Venkataramani, Kokku, Dahlin] TCP-LP [Kuzmanovic, Knightly] Early warning (based on delay, not loss) Aggressive back-off

Our approach: 

Our approach Application-level on top of TCP +ve: easy to deploy -ve: nested control loops No packet level info server client 1000B 400Kbps 100B advertise advertise 40Kbps controls rate by receiver window size max number of bytes allowed at receiver controlled from application-level window = min (congestion window, receiver window)

Inside BaTS: 

Inside BaTS congestion detection rcwnd adaptation goodput measurement Application level Transport level: TCP congestion avoidance

Fluid flow model: 

Fluid flow model Network: links capacity Collection of flows Flow r identifies links (route) Flows: foreground or background … Background flow, b link 1 link 2 link L flow 1 flow 2 server client

Throughput/goodput formulas: 

Throughput/goodput formulas Throughput: propagation delay queueing delay rcwnd loss rate where, e.g., Goodput:

Large buffers case: 

Large buffers case Assume no losses; All flows constrained by receive windows: For given wr, rates xr solution of [M.-Roberts]:

Small buffers case: 

Small buffers case Assume no queueing delays; All flows constrained by losses: For given wr, rates xr solution of [Kelly, Kunnyur-Srikant]: where:

Goodput/receive window relation (single background flow): 

Goodput/receive window relation (single background flow) For both the large and small buffer cases: There is a critical value of the window w*b , w*b=y*bb where y*b is the spare capacity s.t.: Foreground flows affected by b iff wb andgt; w*b Goodput yb(wb) is linear on [0, w*b], slope 1/b yb(wb)/wb andlt;1/b and non-increasing on (w*b,)

Validation: 

Validation background 8 foreground flows 8 Mb/s Window constrained to 6.4 Mb/s Buffer size 20 pkts

Formal control objective: 

Formal control objective Adapt wb so as to force relation: yb wb slope 1/-

Resulting allocations (large buffers): 

Resulting allocations (large buffers) Assume b non-increasing ,s.t. b bandlt;1 Resulting throughputs solve where:

Resulting allocations (small buffers): 

Resulting allocations (small buffers) Assume b non-increasing ,s.t. b bandlt;1; Assume gb decreasing, where Throughputs solve where:

Slide17: 

Window adjustment algorithms control interval: T seconds; unit: k bytes Rn : # of units received (in nth control interval) Wn : receiver window size Estimate Update: where

Method 1: binary search: 

Method 1: binary search Maintain search interval, [wmin,wmax] wn=wmin+a(wmax-wmin) wnandgt;w* ? wmax=wn-1, otherwise wmin=wn [Karp et al.]: Optimality properties for static environment, noiseless measurements, single background flow.

Method 2: stochastic approximation: 

Method 2: stochastic approximation Basic update: Standard Robbins-Monro algorithm. For small gain , behaves as ODE. Flexibility in functional form of updates.

Stability issues (several background flows): 

Stability issues (several background flows) Interaction of window controllers: stable dynamics? For small gains, stochastic approximation dynamics close to differential systems. For delay-constrained case, assuming time-scale separation between TCP and rcwnd control loops, one can design provably stable differential systems.

Stable system (delay constrained case): 

Stable system (delay constrained case) Theorem (adapted from [Moandamp;Walrand]): Window dynamics stable, provided utility functions Ub of background flows are s.t. y U’b decreasing, where:

Slide22: 

performance utilization of spare-bw interference on foreground flows simulation 1000 seconds round-trip propagation delay: 44ms unit: 100 bytes, control interval T=0.2, 0.5 sec Performance evaluation

BaTS & ftp-like TCP: 

BaTS andamp; ftp-like TCP ftp only: 58% ftp only: 100% T=0.5 sec binary search stochastic appr. utilization: 95%, 98% ftp tptr. reduced by: 2%, 6% utilization: 100%, 100% ftp tptr. reduced by: 1%, 3% two approaches achieve design goals, comparable.

BaTS & web traffic: 

BaTS andamp; web traffic Web andamp; ftp Web andamp; BaTS Web only BaTS does not affect web response time much. BaTS uses 21% of capacity, similar for stochastic approx. T=0.5sec Binary search

BaTS & on-off UDP: 

BaTS andamp; on-off UDP Capacity: 10Mbps UDP on/off: 50sec T=0.5sec Binary search BaTS keeps track of spare-bw. BaTS uses 87% of spare-bw, lower for shorter on/off times stochastic approx. uses spare-bw less efficiently. BaTS UDP

Concluding remarks: 

Concluding remarks Designed a low priority service Without network support Using Application level reactions Efficiently utilizes spare bandwidth Future work Investigate stability issues (loss-constrained case) Loss and delay constraints: fluid models? Relation between utility functions and impact on foreground flows.