Achieving Stability in a Network of IQ SwitchesOutlineThe ProblemLQF is Unstable [AZ ‘01]Prior WorkSlide 6Max-Min FairnessFair-LQF [KPS ‘04]Fair-MWM [KPS ‘04]Slide 10Our Model: TrafficOur Model: FlowsOur Model: StabilitySingle-Server SwitchesProof (1)Proof (2)Proof (3)Proof (4)Fair-LQF on CounterexampleN x N SwitchesSimulation ResultsFair-LQF vs LQF (1)Fair-LQF vs LQF (2)Fair-MWM vs MWM (1)Fair-MWM vs MWM (2)Fair-MWM is MMFAchieving Stability in a Network of IQ SwitchesAchieving Stability in a Network of IQ SwitchesNeha KumarShubha U. NabarOutline•The Problem–Instability of LQF–Prior Work •Fairness in Scheduling–Fair-LQF–Fair-MWM•Stability of Networks–Single-Server Switches–AZ Counterexample–N x N SwitchesThe ProblemCan we ensure stability in networks of IQ switches using a simple local and online scheduling policy?LQF is Unstable [AZ ‘01]1/301/301/301/30Prior Work•Longest-In-Network [AZ ‘01]–Frame-based, not local•BvN based scheduling [MGLN ’03] –Requires prior knowledge of rates•Approximate-OCF [MGLN ’03]–Involves rate estimationOutline•The Problem–Instability of LQF–Prior Work •Fairness in Scheduling–Fair-LQF–Fair-MWM•Stability of Networks–Single-Server Switches–AZ Counterexample–N x N SwitchesMax-Min FairnessGiven server capacity C and n flows with rates 1  n , rate allocation R = (r1  rn) is max-min fair if1. n ri · C , ri · i 2. any ri can be increased only by reducing rj s.t. rj · riFair-LQF [KPS ‘04]if (q_size > threshold)add q to congested list;m = # congested queues;while (m != 0) round-robin on congested;m--;m = # non-empty uncongested queues;while (m != 0)lqf on uncongested;m--;Fair-MWM [KPS ‘04]if (voq_size > threshold)add voq to congested list;MWM-schedule unblocked voqs;for all i-jif (voqij is matched & congested)n = # non-empty voqxjs;block voqij for n cycles; else if (cyclesij > 0)cyclesij--;Outline•The Problem–Instability of LQF–Prior Work •Fairness in Scheduling–Fair-LQF–Fair-MWM•Stability of Networks–Single-Server Switches–AZ Counterexample–N x N SwitchesOur Model: Traffic•Arrivals for each flow satisfy SLLNlimn ! 1 Ai(n)/n = i 8 i•Arrivals are admissibleIf fx is the set of flows that go through port x, then i 2 fx i < 1Our Model: FlowsA flow is a set of packets that traverse the same path within the network•Per-Flow Queueing•Deterministic RoutingOur Model: StabilityA network of switches is rate stable if limn ! 1 Xn/n = limn ! 1 1/n i(Ai – Di) = 0 w.p.1Xn – queue lengths vector at time nDi – departure vector at time iAi - arrival vector at time iSingle-Server Switches Claim: Fair-LQF is stableProof (1)Lemma 1:For flow i at switch S,if limn ! 1 Ai(n)/n = i and i < 1/Nthen Fair-LQF ensures that limn ! 1 Di(n)/n exists and is iregardless of other arrivals at S .Work in ProgressProof (2)•Consider flow i with smallest injection rate, that passes through switches S1 Sk•From traffic model and Lemma 1, limn ! 1 DiS1(n)/n exists and is iProof (3)•Observe that limn ! 1 AiS2(n)/n = limn ! 1 DiS1(n)/n = i •Repeatedly applying Lemma 1, limn ! 1 AiSj(n)/n = limn ! 1 DiSj(n)/n = i 8j · kProof (4)•Remove flow i from consideration•Reduce service rates for S1  Sk accordingly•Repeat above for reduced network while flows exist ▪Fair-LQF on Counterexample1/31/31/31/3N x N Switches Claim: Fair-MWM is stableWork in ProgressSimulation ResultsFair-LQF vs LQF (1)LQF causes packets to grow unboundedly in systemNumber of packets stays bounded under Fair-LQFFair-LQF vs LQF (2)LQF causes packets to grow unboundedly in systemNumber of packets stays bounded under Fair-LQFFair-MWM vs MWM (1)Bad guys are punishedAs they ask for higher ratesFair-MWM vs MWM (2)Good guys continue to get their fair share As bad guys grow in rateFair-MWM is MMFIntuition:Consider a frame-based algorithm where VOQs collect packets for T time slots. Each output independently does a MMF rate allocation. The VOQs drop all packets that cannot be scheduled. The rest of the packets are sent through. We believe that Fair-MWM does this