Network Bandwidth AllocationProblem StatementAct IA Physical ViewSystem UsageSimplificationAbstractionStochastic BehaviorAct IIAllocation EfficiencyStabilityMaximize Overall ThroughputMax-Min FairnessProportional Fairnessa-Fair AllocationsTCP BiasProperties of a-Fair AllocationsAct IIIFluid ModelsFluid Limit : VisualFluid Limit : MathFluid Model SolutionFluid Analysis is EasierVisualizing Fluid FlowFor StabilityTowards a Formal FrameworkWhy we need a better metric.Skorohod TopologyProhorov MetricFluid Limit TheoremOutline of ProofPapersNetwork Bandwidth Allocation(and Stability)In Three ActsProblem StatementHow to allocate bandwidth to users?How to model the network?What criteria to use?Act IModelingA Physical ViewHost1Host2Host3Host4Host5Router : interconnect, where links meet.Host : multi-user, endpoint of communication.Link / Resource : bottleneck, each has finite capacity Cj.1C2C3C4C5C6C7CSystem UsageHost1Host2Host3Host4Host5)(1tN)(2tN)(3tNRoute : static path through network, supporting Ni(t) flows with i(N(t)) allocated bandwidth.Flows / Users : transfer documents of different sizes, evenly split allocated bandwidth along route. Dynamic. Not directed.))((1tN ))((2tN))((3tNSimplification1C2C3C4C5C6C7C)(1tN)(2tN)(3tN))((1tN ))((2tN))((3tNExtraneous elements have been removed.Abstraction1C2C3C4C5C6C7C)(1tN)(2tN)(3tN))((1tN ))((2tN))((3tNRoutes are just subsets of links / resources.Represented by [Aji] : whether resource j is used by route i.Capacity constraint: 0)(:))((tNijijiiCtA NStochastic Behavior1102201301210201201)220(112)130(223)121(3312)120(11)120(22Model N(t) as a Markov process with countable state space.Poisson user arrivals at rate i.Exponential document sizes with parameter i.Define traffic intensity i = i / i.Act IIPerformanceCriteriaAllocation Efficiency10101010101010535122•An allocation  is feasible if capacity constraint satisfied.•A feasible allocation  is efficient if we don’t have    for any other feasible .•Defined at a point in time, regardless of usage.Stability•Stable  Markov chain positive recurrent.•Returns to each state with probability 1 in finite mean time.•Necessary, but not sufficient condition:•How tight this is gives us an idea of utilization.•Does not uniquely specify allocation.jCAjiiji allfor Maximize Overall Throughput•That is, max•No unique allocation.•Could get unexpected results. 0)(: tNiii10 10 101234Max-Min Fairness•Increase allocation for each user, unless doing so requires a corresponding decrease for a user of equal or lower bandwidth to satisfy the capacity constraints.•Uniquely determined.•Greedy algorithm. Not distributed.12 12123Proportional Fairness•  is proportionally fair if for any other feasible allocation * we have:•Same as maximizing:•Interpret as utility function.•Distributed algorithms known. 0)(*iiiiitNiiitN log)(-Fair Allocations0)(:0)(:11 if log1),,0( if 1)(),(tNiiiitNiiiiiiNtNtGΛ0)(: tNijijiiCA0iMaximizeSubject toWith i=1,    maximize throughput = 1 : proportional fairness max-min fairnessWith i = 1 / RTTi2, = 2 : TCPTCP BiasRTTtimeout•Congestion window based on additive increase / multiplicative decrease mechanism.•Increase for each ACK received, once every Round Trip Time.•Timeouts based on RTT.•Bias against long RTT.Properties of -Fair Allocations•The optimal  exists and is unique.•It’s positive:  > 0.•Scale invariance: (rN) = (N), for r > 0.•Continuity:  is continuous in N.• System is stable whenAssume Ni(t) > 0.Let (N(t)) be a solution to the -fair optimization.jCAjiiji allfor Act IIIFluids &FormalitiesFluid Models))(()()0()( tTStENtNiiiiiNi(0) : initial conditionEi(t) : new arrival processTi(t) : cumulative bandwidth allocatedSi(t) : service processDecompose into non-decreasing processes:tiisstT0d ))(()( NConsider a sequence indexed by r > 0:rrtNtNrr)()( Fluid Limit : Visual0 2 4 6 8 10012345678910E(t)t0 20 40 6 0 8 0 1000102030405060708090100E(t)t0 200 400 600 800 100001002003004005006007008009001000E(t)t1r10r100rFluid Limit : MathtrrtEtrrtEttEttErr )()()()(rtrtrE as )(ttEr)(Look at slope:with probability 1.By strong law of large numbers for renewal processes:ThusFluid Model SolutionA fluid model solution is an absolutely continuous function so that at each regular point t and each route iand for each resource j 0)( if 00)( if )()(tNtNttNiiiiiidtdN)(tN jtNiijitNiijiCAtAii 0)(:0)(:)(NFluid Analysis is EasierA complex function f is absolutely continuous on I=[a,b] if for every  > 0 there is a  > 0 such that for any n and any disjoint collection of segments (1,1),…,(n,n) in I whose lengths satisfy  niii1niiiff1)()(If f is AC on I, the f is differentiable a.e. on I, andxadttfafxf )(')()(DefinitionTheoremVisualizing Fluid Flow123)(11N)(22N)(33NFor Stability•If fluid system empties in finite time, then system is stable.Ttt  allfor 0)(N•Show that 0)( tdtdN•In general, what happens as t when some of the resources are saturated?jiijiCA •We approach the invariant manifold, aka the set of invariant states 0 where allfor )(: iiiNiMNNTowards a Formal Framework•Interested in stochastic processes with samples paths in D[0,, the space of right continuous real functions having left limits.)()(lim txsxts)()(limtxsxts•Well behaved. At most countably many points of discontinuity.t)(txWhy we need a better metric.……tt)(1tx)(2txWhat goes wrong in Lp ? L?Skorohod TopologyLet  be the set of strictly increasing Lipschitz continuous functions  mapping [0,) onto [0,), such that)(log)('t ))((),( sup),,,(~0utyutxruyxdt1rrPut (standard bounded