August 21st, 2001.ppt

1、1,Internet RoutersStochastics Network Seminar February 22nd 2002,Nick McKeown Professor of Electrical Engineering and Computer Science, Stanford University nickmstanford.edu www.stanford.edu/nickm,2,What a Router Looks Like,Cisco GSR 12416,Juniper M160,6ft,19”,2ft,Capacity: 160Gb/s Power: 4.2kW,3ft,

2、2.5ft,19”,Capacity: 80Gb/s Power: 2.6kW,3,Points of Presence (POPs),4,Basic Architectural Components of an IP Router,Control Plane,Datapath per-packet processing,Switching,Forwarding Table,RoutingTable,Routing Protocols,5,Per-packet processing in an IP Router,1. Accept packet arriving on an ingress

3、line. 2. Lookup packet destination address in the forwarding table, to identify outgoing interface(s). 3. Manipulate packet header: e.g., decrement TTL, update header checksum. 4. Send packet to outgoing interface(s). 5. Queue until line is free. 6. Transmit packet onto outgoing line.,6,Generic Rout

4、er Architecture,Lookup IP Address,Update Header,Header Processing,Queue Packet,7,Generic Router Architecture,Buffer Manager,Buffer Memory,Buffer Manager,Buffer Memory,Buffer Manager,Buffer Memory,8,Packet processing is getting harder,CPU Instructions per minimum length packet since 1996,9,Performanc

5、e metrics,Capacity“maximize C, s.t. volume 2m3 and power 5kW” Throughput Operators like to maximize usage of expensive long-haul links. This would be trivial with work-conserving output-queued routersControllable Delay Some users would like predictable delay. This is feasible with output-queueing pl

6、us weighted fair queueing (WFQ).,10,The Problem,Output queued switches are impractical,R,R,R,R,DRAM,NR,NR,data,11,Memory Bandwidth Commercial DRAM,Its hard to keep up with Moores Law: The bottleneck is memory speed. Memory speed is not keeping up with Moores Law.,DRAM 1.1x / 18months,Moores Law 2x /

7、 18 months,Router Capacity 2.2x / 18months,Line Capacity 2x / 7 months,12,Generic Router Architecture,Queue Packet,Buffer Memory,Queue Packet,Buffer Memory,Queue Packet,Buffer Memory,1,2,N,1,2,N,Scheduler,13,Outline of next two talks,Whats known about throughput Today: Survey of ways to achieve 100%

8、 throughput Whats known about controllable delay Next week (Sundar): Controlling delay in routers with a single stage of buffering.,14,Potted history,Karol et al. 1987 Throughput limited to by head-of-line blocking for Bernoulli IID uniform traffic.Tamir 1989 Observed that with “Virtual Output Queue

9、s” (VOQs) Head-of-Line blocking is reduced and throughput goes up.,15,Potted history,Anderson et al. 1993 Observed analogy to maximum size matching in a bipartite graph. M et al. 1995 (a) Maximum size match can not guarantee 100% throughput. (b) But maximum weight match can O(N3).Mekkittikul and M 1

10、998 A carefully picked maximum size match can give 100% throughput.,MatchingO(N2.5),16,Potted history Speedup,5. Chuang, Goel et al. 1997 Precise emulation of a central shared memory switch is possible with a speedup of two and a “stable marriage” scheduling algorithm.Prabhakar and Dai 2000 100% thr

11、oughput possible for maximal matching with a speedup of two.,17,Potted history Newer approaches,Tassiulas 1998 100% throughput possible for simple randomized algorithm with memory. Giaccone et al. 2001 “Apsara” algorithms.Iyer and M 2000 Parallel switches can achieve 100% throughput and emulate an o

12、utput queued switch.Chang et al. 2000 A 2-stage switch with a TDM scheduler can give 100% throughput.Iyer, Zhang and M 2002 Distributed shared memory switches can emulate an output queued switch.,18,Scheduling crossbar switches to achieve 100% throughput,Basic switch model. When traffic is uniform (

13、Many algorithms) When traffic is non-uniform, but traffic matrix is known. Technique: Birkhoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete.

14、 Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,19,Basic Switch Model,A1(n),S(n),N,N,LNN(n),A1N(n),A11(n),L11(n),1,1,AN(n),ANN(n),AN1(n),D1(n),DN(n),20,Some defin

15、itions,3. Queue occupancies:,Occupancy,L11(n),LNN(n),21,Some definitions of throughput,When traffic is admissible,22,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matrix is known Technique: Birk

16、hoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When ther

17、e is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,23,Algorithms that give 100% throughput for uniform traffic,Quite a few algorithms give 100% throughput when traffic is uniform1 For example: Maximum size bipartite match. Maximal size match (e.g. PIM, iS

18、LIP, WFA) Deterministic and a few variants Wait-until-full,1. “Uniform”: the destination of each cell is picked independently and uniformly and at random (uar) from the set of all outputs.,24,Maximum size bipartite match,Intuition: maximizes instantaneous throughputfor uniform traffic.,L11(n)0,LN1(n

19、)0,“Request” Graph,Bipartite Match,Maximum Size Match,25,Aside: Maximal Matching,A maximal matching is one in which each edge is added one at a time, and is not later removed from the matching. i.e. no augmenting paths allowed (they remove edges added earlier). No input and output are left unnecessa

20、rily idle.,26,Aside: Example of Maximal Size Matching,A,1,B,C,D,E,F,2,3,4,5,6,A,1,B,C,D,E,F,2,3,4,5,6,Maximal Matching,Maximum Matching,27,Algorithms that give 100% throughput for uniform traffic,Quite a few algorithms give 100% throughput when traffic is uniform For example: Maximum size bipartite

21、match. Maximal size match (e.g. PIM, iSLIP, WFA) Determinstic and a few variants Wait-until-full,28,Deterministic Scheduling Algorithm,If arriving traffic is i.i.d with destinations picked uar across outputs, then a round-robin schedule gives 100% throughput.,A,1,B,C,D,2,3,4,B,C,D,2,3,4,B,C,D,2,3,4,

22、A,1,A,1,Variation 1: if permutations are picked uar from the set of N! permutations, this too will also give 100% throughput. Variation 2: if permutations are picked uar from the permutations above, this too will give 100% throughput.,29,A Simple wait-until-full algorithm,The following algorithm app

23、ears to be stable for Bernoulli i.i.d. uniform arrivals:If any VOQ is empty, do nothing (i.e. serve no queues). If no VOQ is empty, pick a permutation uar across either (sequence of permutations, or all permutations).,30,Some simple algorithms that achieve 100% throughput,31,Some observations,A maxi

24、mum size match (MSM) maximizes instantaneous throughput. But a MSM is complex O(N2.5). It turns out that there are many simple algorithms that give 100% throughput for uniform traffic. So what happens if the traffic is non-uniform?,32,Why doesnt maximizing instantaneous throughput give 100% throughp

25、ut for non-uniform traffic?,Three possible matches, S(n):,33,Simulation of simple 3x3 example,34,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matrix is known Technique: Birkhoff-von Neumann dec

26、omposition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. T

27、echnique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,35,Example 1: (Trivial) scheduling to achieve 100% throughput,Assume we know the traffic matrix, and the arrival pattern is deterministic:Then we can simply choose:,36,Example 2:With random arrivals, but known traffic matrix

28、,Assume we know the traffic matrix, and the arrival pattern is random:Then we can simply choose:In general, if we know L, can we pick a sequence S(n) to achieve 100% throughput?,37,Birkhoff - von Neumann Decomposition,Any L can be decomposed into a linear (convex) combination of matrices, (M1, , Mr)

29、.,38,In practice,Unfortunately, we usually dont know traffic matrix L a priori, so we can: Measure or estimate L, or Not use L. In what follows, we will assume we dont know or use L.,39,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) Whe

30、n traffic is non-uniform, but traffic matrix is known Technique: Birkhoff-von Neumann decomposition. When traffic matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: R

31、andomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,40,When the traffic matrix is not known,41,Problem,42,Maximum weight matching,A1(n),N,N,LNN(n),A1N(n),A11(n),L11(n),1,1,AN(n),A

32、NN(n),AN1(n),D1(n),DN(n),L11(n),LN1(n),“Request” Graph,Bipartite Match,S*(n),Maximum Weight Match,43,Outline of Proof,44,Choosing the weight,45,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matr

33、ix is known. Technique: Birkhoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Techn

34、ique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,46,100% throughput with pipelining,47,100% throughput with incomplete information,48,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is unifor

35、m (Many algorithms) When traffic is non-uniform, but traffic matrix is known. Technique: Birkhoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not comple

36、te. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel Packet Switch.,49,Achieving 100% when algorithm does not complete,Randomized algorithms: Basic idea (Tassiulas) Reducing delay

37、 (Shah, Giaccone and Prabhakar),50,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matrix is known. Technique: Birkhoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov fun

38、ction. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch. Technique: Parallel

39、Packet Switch.,51,Speedup and Combined Input Output Queueing (CIOQ),A1(n),S(n),N,N,LNN(n),A1N(n),A11(n),L11(n),1,1,AN(n),ANN(n),AN1(n),D1(n),DN(n),With speedup, the matching is performed s times per cell time, and up to s cells are removed from each VOQ. Therefore, output queues are required.,52,Flu

40、id Model Dai and Prabhakar,53,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matrix is known. Technique: Birkhoff-von Neumann decomposition. When matrix is not known. Technique: Lyapunov function

41、. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Technique: 2-stage load-balancing switch.,54,2-stage switch and no

42、scheduler,Motivation: If traffic is uniformly distributed, then even a deterministic schedule gives 100% throughput. So why not force non-uniform traffic to be uniformly distributed?,55,2-stage switch and no scheduler,S2(n),N,N,LNN(n),L11(n),1,1,D1(n),DN(n),N,N,1,1,A1(n),AN(n),S1(n),A1(n),AN(n),Buff

43、erless Load-balancing Stage,Buffered Switching Stage,56,2-stage switch with no scheduler,57,Scheduling algorithms to achieve 100% throughput,Basic switch model. When traffic is uniform (Many algorithms) When traffic is non-uniform, but traffic matrix is known. Technique: Birkhoff-von Neumann decompo

44、sition. When matrix is not known. Technique: Lyapunov function. When algorithm is pipelined, or information is incomplete. Technique: Lyapunov function. When algorithm does not complete. Technique: Randomized algorithm. When there is speedup. Technique: Fluid model. When there is no algorithm. Techn

45、ique: 2-stage load-balancing switch.,58,Throughput results,Theory:,Practice:,Input Queueing (IQ),Input Queueing (IQ),58% Karol, 1987,Various heuristics, distributed algorithms, and amounts of speedup,59,Outline of next talk Sundar Iyer,Whats known about controllable delay Emulation of Output queued switches PIFOs and WFQ Single-buffered switches: Parallel packet switches, and distributed shared memory switches.,