Question? Leave a message!




Successive shortest path algorithm

Successive shortest path algorithm
7. NETWORK FLOW III assignment problem ‣ inputqueued switching ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Sep 8, 2013 6:40 AM7. NETWORK FLOW III assignment problem ‣ inputqueued switching ‣ SECTION 7.13Assignment problem Input. Weighted, complete bipartite graph G = (X ∪ Y, E) with X = Y . Goal. Find a perfect matching of min weight. 15 0' 0 7 3 5 1 1' 6 2 9 4 2 1 2' X Y 3Assignment problem Input. Weighted, complete bipartite graph G = (X ∪ Y, E) with X = Y . Goal. Find a perfect matching of min weight. 15 0' 0 7 3 mincost perfect matching 5 M = 02', 10', 21' 1 1' 6 cost(M) = 3 + 5 + 4 = 12 2 9 4 2 1 2' X Y 4Princeton writing seminars Goal. Given m seminars and n = 12m students who rank their top 8 choices, assign each student to one seminar so that: Each seminar is assigned exactly 12 students. Students tend to be "happy" with their assigned seminar. Solution. Create one node for each student i and 12 nodes for each seminar j. Solve assignment problem where c is some function of the ranks: ij f(rank(i,j))B7 i`MFb j c = ij B7 i/Q2bMQi`MF j 5Locating objects in space Goal. Given n objects in 3d space, locate them with 2 sensors. Solution. Each sensor computes line from it to each particle. Let c = distance between line i from censor 1 and line j from sensor 2. ij Due to measurement errors, we might have c 0. ij Solve assignment problem to locate n objects. 6Kidney exchange If a donor and recipient have a different blood type, they can exchange their kidneys with another donor and recipient pair in a similar situation. Can also be done among multiple pairs (or starting with an altruistic donor). 7Kidney exchange 1 3 2 8 3 1 3 2 8 3 6 2 5 9 4 6 2 5 9 4 4 7 5 1 6 4 7 5 1 6 weight = 3 + 5 + 7 + 8 + 4 = 27 weight = 2 + 5 + 8 + 6 + 1 + 9 = 31 8Applications Natural applications. Match jobs to machines. Match personnel to tasks. Match PU students to writing seminars. Nonobvious applications. Vehicle routing. Kidney exchange. Signal processing. Multiple object tracking. Virtual output queueing. Handwriting recognition. Locating objects in space. Approximate string matching. Enhance accuracy of solving linear systems of equations. 9Bipartite matching Bipartite matching. Can solve via reduction to maximum flow. Flow. During FordFulkerson, all residual capacities and flows are 01; flow corresponds to edges in a matching M. 1 Residual graph G simplifies to: M 1 1 If (x, y) ∉ M, then (x, y) is in G . M t s If (x, y) ∈ M, then (y, x) is in G . M X Y Augmenting path simplifies to: Edge from s to an unmatched node x ∈ X, Alternating sequence of unmatched and matched edges, Edge from unmatched node y ∈ Y to t. 10Alternating path Def. An alternating path P with respect to a matching M is an alternating sequence of unmatched and matched edges, starting from an unmatched node x ∈ X and going to an unmatched node y ∈ Y. Key property. Can use P to increase by one the cardinality of the matching. Pf. Set M ' = M ⊕ P. symmetric difference y y y x x x matching M alternating path P matching M' 11Assignment problem: successive shortest path algorithm Cost of alternating path. Pay c(x, y) to match xy; receive c(x, y) to unmatch. 1 10 1' 6 P = 2 → 2' → 1 → 1' cost(P) = 2 6 + 10 = 6 7 2 2 2' Shortest alternating path. Alternating path from any unmatched node x ∈ X to any unmatched node y ∈ Y with smallest cost. Successive shortest path algorithm. Start with empty matching. Repeatedly augment along a shortest alternating path. 12Finding the shortest alternating path Shortest alternating path. Corresponds to minimum cost s↝t path in G . M 10 1 1' 0 6 s t 7 0 2 2 2' Concern. Edge costs can be negative. Fact. If always choose shortest alternating path, then G contains no M negative cycles ⇒ can compute using BellmanFord. Our plan. Use duality to avoid negative edge costs (and negative cycles) ⇒ can compute using Dijkstra. 13Equivalent assignment problem Duality intuition. Adding a constant p(x) to the cost of every edge incident to node x ∈ X does not change the mincost perfect matching(s). Pf. Every perfect matching uses exactly one edge incident to node x. ▪ original costs c(x, y) modified costs c'(x, y) 15 0' 18 0' 0 0 p(0) = 3 7 10 3 6 add 3 to all edges incident to node 0 5 5 6 1' 1 6 1' 1 2 2 9 9 4 4 2 1 2' 2 1 2' X Y X Y 14Equivalent assignment problem Duality intuition. Subtracting a constant p(y) to the cost of every edge incident to node y ∈ Y does not change the mincost perfect matching(s). Pf. Every perfect matching uses exactly one edge incident to node y. ▪ original costs c(x, y) modified costs c'(x, y) 15 0' 10 0' 0 p(0') = 5 0 7 7 3 3 subtract 5 from all edges incident to node 0' 5 0 6 1' 1 6 1' 1 2 2 9 4 4 4 2 1 2' 2 1 2' X Y X Y 15Reduced costs p Reduced costs. For x ∈ X, y ∈ Y, define c (x, y) = p(x) + c(x, y) – p(y). Observation 1. Finding a mincost perfect matching with reduced costs is equivalent to finding a mincost perfect matching with original costs. p original costs c(x, y) reduced costs c (x, y) 15 0' 4 0' 0 p(0') = 11 0 p(0) = 0 7 1 3 0 5 0 6 1' p(1') = 6 1 6 1' p(1) = 6 1 2 5 p 9 0 c (1, 2') = p(1) + 2 – p(2') 4 0 2 1 2' 2 0 2' p(2') = 3 p(2) = 2 X Y X Y 16Compatible prices Compatible prices. For each node v ∈ X ∪ Y, maintain prices p(v) such that: p c (x, y) ≥ 0 for all (x, y) ∉ M. p c (x, y) = 0 for all (x, y) ∈ M. Observation 2. If prices p are compatible with a perfect matching M, then M is a mincost perfect matching. p reduced costs c (x, y) Pf. Matching M has 0 cost. ▪ 4 0' 0 1 0 0 1 6 1' 5 0 0 2 0 2' X Y 17Successive shortest path algorithm SUCCESSIVESHORTESTPATH (X, Y, c) prices p are M ← ∅. compatible with M p FOREACH v ∈ X ∪ Y : p(v) ← 0. c (x, y) = c(x, y) ≥ 0 WHILE (M is not a perfect matching) p d ← shortest path distances using costs c . p P ← shortest alternating path using costs c . M ← updated matching after augmenting along P. FOREACH v ∈ X ∪ Y : p(v) ← p(v) + d(v). RETURN M. 18Successive shortest path algorithm Initialization. M = ∅. For each v ∈ X ∪ Y : p(v) ← 0. original costs c(x, y) p(0) = 0 p(0') = 0 15 0 0' 7 3 p(1) = 0 p(1') = 0 5 s t 1 6 1' 2 9 4 2 1 2' p(2) = 0 p(2') = 0 19Successive shortest path algorithm Initialization. M = ∅. For each v ∈ X ∪ Y : p(v) ← 0. p reduced costs c (x, y) p(0) = 0 p(0') = 0 15 0 0' 7 3 p(1) = 0 p(1') = 0 5 s t 1 6 1' 2 9 4 2 1 2' p(2) = 0 p(2') = 0 20Successive shortest path algorithm Step 1. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). shortest path distances d(v) d(0) = 0 d(0') = 5 15 0 0' 7 3 d(s) = 0 d(t) = 1 d(1) = 0 d(1') = 4 5 s t 1 6 1' 2 9 4 2 1 2' d(2) = 0 d(2') = 1 21Successive shortest path algorithm Step 1. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). alternating path d(0) = 0 d(0') = 5 15 0 0' 7 3 d(s) = 0 d(t) = 1 d(1) = 0 d(1') = 4 5 s t 1 6 1' 2 9 matching 4 22' 2 1 2' d(2) = 0 d(2') = 1 22Successive shortest path algorithm Step 1. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). p reduced costs c (x, y) p(0) = 0 p(0') = 5 10 0 0' 3 2 p(1) = 0 p(1') = 4 0 s t 1 2 1' 1 4 matching 0 22' 2 0 2' p(2) = 0 p(2') = 1 23Successive shortest path algorithm Step 2. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). shortest path distances d(v) d(0) = 0 d(0') = 0 10 0 0' 3 2 d(s) = 0 d(t) = 0 d(1) = 0 d(1') = 1 0 s t 1 2 1' 1 4 matching 0 22' 2 0 2' d(2) = 1 d(2') = 1 24Successive shortest path algorithm Step 2. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). shortest path distances d(v) d(0) = 0 d(0') = 0 10 0 0' 3 2 d(s) = 0 d(t) = 0 d(1) = 0 d(1') = 1 0 s t 1 2 1' 1 4 matching 0 22' 10' 2 0 2' d(2) = 1 d(2') = 1 25Successive shortest path algorithm Step 2. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). p reduced costs c (x, y) p(0) = 0 p(0') = 5 10 0 0' 2 1 p(1) = 0 p(1') = 5 0 s t 1 1 1' 0 5 matching 0 22' 10' 2 0 2' p(2) = 1 p(2') = 2 26Successive shortest path algorithm Step 3. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). shortest path distances d(v) d(0) = 0 d(0') = 6 10 0 0' 2 1 d(s) = 0 d(t) = 1 d(1) = 6 d(1') = 1 0 s t 1 1 1' 0 5 matching 0 22' 10' 2 0 2' d(2) = 1 d(2') = 1 27Successive shortest path algorithm Step 3. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). shortest path distances d(v) d(0) = 0 d(0') = 6 10 0 0' 2 1 d(s) = 0 d(t) = 1 d(1) = 6 d(1') = 1 0 s t 1 1 1' 0 5 matching 0 10' 02' 21' 2 0 2' d(2) = 1 d(2') = 1 28Successive shortest path algorithm Step 3. p Compute shortest path distances d(v) from s to v using c (x, y). Update matching M via shortest path from s to t. For each v ∈ X ∪ Y: p(v) ← p(v) + d(v). p reduced costs c (x, y) p(0) = 0 p(0') = 11 4 0 0' 1 0 p(1) = 6 p(1') = 6 0 s t 1 6 1' 5 0 matching 0 10' 02' 21' 2 0 2' p(2) = 2 p(2') = 3 29Successive shortest path algorithm Termination. M is a perfect matching. Prices p are compatible with M. p reduced costs c (x, y) p(0) = 0 p(0') = 11 4 0 0' 1 0 p(1) = 6 p(1') = 6 0 1 6 1' 5 0 matching 0 10' 02' 21' 2 0 2' p(2) = 2 p(2') = 3 30Maintaining compatible prices Lemma 1. Let p be compatible prices for M. Let d be shortest path distances p p+d in G with costs c . All edges (x, y) on shortest path have c (x, y) = 0. M forward or reverse edges Pf. Let (x, y) be some edge on shortest path. p If (x, y) ∈ M, then (y, x) on shortest path and d(x) = d(y) – c (x, y); p If (x, y) ∉ M, then (x, y) on shortest path and d(y) = d(x) + c (x, y). p In either case, d(x) + c (x, y) – d(y) = 0. p By definition, c (x, y) = p(x) + c(x, y) – p(y). p Substituting for c (x, y) yields (p(x) + d(x)) + c(x, y) – (p(y) + d(y)) = 0. p+d In other words, c (x, y) = 0. ▪ Given prices p, the reduced cost of edge (x, y) is p c (x, y) = p(x) + c(x, y) – p(y). 31Maintaining compatible prices Lemma 2. Let p be compatible prices for M. Let d be shortest path distances p in G with costs c . Then p' = p + d are also compatible prices for M. M Pf. (x, y) ∈ M (y, x) is the only edge entering x in G . Thus, (y, x) on shortest path. M p+d By LEMMA 1, c (x, y) = 0. Pf. (x, y) ∉ M p (x, y) is an edge in G ⇒ d(y) ≤ d(x) + c (x, y). M p Substituting c (x, y) = p(x) + c(x, y) – p(y) ≥ 0 yields (p(x) + d(x)) + c(x, y) – (p(y) + d(y)) ≥ 0. p+d In other words, c (x, y) ≥ 0. ▪ Prices p are compatible with matching M: p c (x, y) ≥ 0 for all (x, y) ∉ M. p c (x, y) = 0 for all (x, y) ∈ M. 32Maintaining compatible prices Lemma 3. Let p be compatible prices for M and let M ' be matching obtained p+d by augmenting along a min cost path with respect to c . Then p' = p + d are compatible prices for M'. Pf. By LEMMA 2, the prices p + d are compatible for M. Since we augment along a mincost path, the only edges (x, y) that swap into or out of the matching are on the mincost path. p+d By LEMMA 1, these edges satisfy c (x, y) = 0. Thus, compatibility is maintained. ▪ Prices p are compatible with matching M: p c (x, y) ≥ 0 for all (x, y) ∉ M. p c (x, y) = 0 for all (x, y) ∈ M. 33Successive shortest path algorithm: analysis Invariant. The algorithm maintains a matching M and compatible prices p. Pf. Follows from LEMMA 2 and LEMMA 3 and initial choice of prices. ▪ Theorem. The algorithm returns a mincost perfect matching. Pf. Upon termination M is a perfect matching, and p are compatible prices. Optimality follows from OBSERVATION 2. ▪ 3 Theorem. The algorithm can be implemented in O(n ) time. Pf. Each iteration increases the cardinality of M by 1 ⇒ n iterations. Bottleneck operation is computing shortest path distances d. 2 Since all costs are nonnegative, each iteration takes O(n ) time using (dense) Dijkstra. ▪ 34Weighted bipartite matching Weighted bipartite matching. Given a weighted bipartite graph with n nodes and m edges, find a maximum cardinality matching of minimum weight. Theorem. FredmanTarjan 1987 The successive shortest path algorithm 2 solves the problem in O(n + m n log n) time using Fibonacci heaps. 1/2 Theorem. GabowTarjan 1989 There exists an O(m n log(nC)) time algorithm for the problem when the costs are integers between 0 and C. J. COMPUT. SIAM ()1989 Society for Industrial and Applied Mathematics No. Vol. 18, 5, pp. 10131036, October 1989 011 FASTER SCALING ALGORITHMS FORNETWORK PROBLEMS HAROLD N. AND ROBERT E. TARJAN GABOW Abstract. This paper presents algorithms for the problem, the assignment transportation and the minimumcost flow of research. The find a minimum problem, problem operations algorithms cost run in time close to the bestknown bounds for the without solution, yet corresponding problems costs. For the example, assignment problem (equivalently, minimumcost matching in a bipartite can solved graph) be in O(v/’rnlog(nN)) time, where n, m, and N denote the number of vertices, number of and of be edges, largest magnitude a cost; costs are assumed to integral. The algorithms work by scaling. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum. Key words, graph theory, networks, assignment problem, matching, scaling subject classifications. 68Q20, 68Q25, 05C70 AMS(MOS) 68R10, 35 1. Introduction. Many problems in operations research involve minimizing a cost function defined on a bipartite or directed graph. A simple but fundamental example is the assignment problem. This paper gives algorithms for such problems that run almost as fast as the bestknown algorithms for the problems corresponding without costs. For the problem, the problem without costs assignment corresponding is maximum bipartite cardinality matching. The results are achieved by the costs. This requires the costs to be scaling for the to be costs should be polynomi integralvalued. Further, algorithms efficient, n(1). bounded in the number of at most These are ally vertices, i.e., requirements satisfied a number of in both theoretical and by large problems practical applications. Table 1 summarizes the results of the paper. The parameters the input describing are in the and defined more below. The first column specified caption precisely gives and bestknown Such a the problem the strongly polynomial time bound. bound from time of the of numbers comes an algorithm with running independent size the (assuming the uniform cost model of computation The second column gives AHU). the time bounds achieved in this paper by scaling. The table shows that significant speedups can be achieved through scaling. Further, it will be seen that the scaling algorithms are simple to program. Now we discuss the specific results. The is to a a assignment problem find minimumcost perfect matching in bipartite is graph. The strongly polynomial algorithm the Hungarian algorithm K55, K56 implemented with Fibonacci heaps This algorithm can be improved significantly FT. when all costs are zero. Then the problem amounts to finding a perfect matching in a bipartite graph. The bestknown cardinality matching algorithm, due to Hopcroft and Sarp, runs in time The new time bound for the problem is O(v/m) HK. assignment Received by the editors August 18, 1987; accepted for publication revised November (in form) 4, 1988. Department of Computer University of Colorado, Boulder, Colorado 80309. The Science, research of this author was supported in part by National Science Foundation grant DCR851191 and ATT Bell Laboratories. Department, Princeton New Jersey 08544 and ATT ::Computer Science University, Princeton, New The of this was in Bell Laboratories, Murray Hill, Jersey 07974. research author supported of contract part by National Science Foundation grant DCR8605962 and Office Naval Research N0001487K0467. 1013History Thorndike 1950. Formulated in a modern way by a psychologist. Assign individuals to jobs to maximize average success of all individuals. 36History Thorndike 1950. Formulated in a modern way by a psychologist. anticipated theory of computational complexity 37History Kuhn 1955. First polytime algorithm; named "Hungarian" algorithm to honor two Hungarian mathematicians (Kőnig and Egerváry). 4 Munkres 1957. Reviewed algorithm; observed O(n ) implementation. 3 EdmondsKarp, Tomizawa 1971. Improved to O(n ). anticipated development of combinatorial optimization 38History Jacobi (18041851). Introduces a bound on the order of a system of m ordinary differential equations in m unknowns and reduces it to…. Looking for the order of a system of arbitrary ordinary differential equations 3916 C.G.J. Jacobi §.3. History About the resolution of the problem of inequalities on which the research of the order of the system of arbi 4 trary di↵ erential equations is supported . Considering a table, we define a canon. An arbitrary canon being given, we find a simplest one. Jacobi (18041851). The assignment problem Moreover, he provides a polynomialtime algorithm. ywhatprecedes, the research of the order of a system of ordinary di↵ erentialequationsisreducedtothefollowingproblemofinequalities, B which is also worth to be considered for itself: Problem. (i) We dispose nn arbitrary quantities h in a square table in such a k way that we have n horizontal series and n vertical series having each one n terms. Among these quantities, to chose n being transversal, that is all disposed in di↵ erent horizontal and vertical series, which may be done in 1.2...n ways; and among these ways, to research one Looking for the order of a system of arbitrary ordinary di↵ erential equations 17 that gives the maximum of the sum of the n chosen numbers. 0 0 0 ...it may occur that all combinatih ons lead h to.. th.e sam h e sum. For example if, as it 1 2 n 00 00 00 happens for the isoperimetrical prob hlem,hthis t..ab.le h 1 2 n ................. 2m m +m ... m +m 1 1 2 1 n (n) (n) (n) h h ... h , m +m 2m 1 2 ... m n+m 2 1 2 2 n ................................. we can add to each term of the same horizontal series a same quantity, and (i) m +m m +m ... 2m , th n 1 n 2 n we call ` the quantity added to the terms of the i horizontal series. This being done, each of the 1.2...n transversal sums among which we need to is given. If m is the greatest of the quantities m , m ,..., m , the terms of each 1 1 2 n find a maximum is increased by the same quantity verticals will be made equal by increasing respectively the lines of the horizontal 5 series by the positive values 0, m 0 m 00,..., m ( n)m ,... 1 2 1 n ` + ` +···+ ` = L, because, in order(it)o form these sums, we need to pick a term in each hori 6 The quantities h being disposed in a square figure k zontal series. Hence, if we pose 4 (i) (i) This was a § 23 in the manuscript. (i) h + ` = p k k 5 The remaining of II/13 b) fo 2200 has been ruled out by Jacobi. I extract this part (i) which shows how the ideas developped in the last section of the paper could have arisen and that the maximal transversal sum of the terms h is k from his work on the isoperimetrical problem. T.N. 6 (i ) (i ) 1 2 (i ) n Cohn’s transcription continues here with a second fragment of a § 19 entitled by Jacobi h +h +···+h = H, 1 2 n About the di↵ erentiations and eliminations by which the shortest reduction (see Jacobi 2) (i) to canonical form is done. A problem of inequalities that must be solved to perform this this makes that the value of the maximal sum formed with the p is k reduction. T.N. (i ) (i ) 1 2 (i ) n p +p +···+p = H +L, 1 2 n and reciprocally. So that finding the proposed maximum for the quanti (i) (i) ties h or p is equivalent. k k Jacobi formulated the assignment problem; proposed and analyzed the Hungarian algorithm 0 00 (n) Let us bring it about that the quantities `, `,..., ` be determined in (i) such a way that, the quantities p being disposed in square in the same 40 k (i) way as the quantities h and chosing a maximum in each vertical series, k (i ) k these maxima be placed in all di↵ erent horizontal series. If we call p the k maximum of terms (n) 0 00 p ,p ,...,p , k k k the sum (i ) (i ) 1 2 (i ) n p +p +···+p 1 2 n will be the maximum among all the transversal sums formed with the quan (i) tities p . ... Indeed, in this case, we have without trouble the maximal k (i) transversal sum formed with the proposed quantities h k (i ) (i ) 1 2 (i ) n h +h +···+h . 1 2 n 0 00 (n) So that we solve the proposed problem when we find quantities `,` ,...,` satisfying the given condition.7. NETWORK FLOW III assignment problem ‣ inputqueued switching ‣Inputqueued switching Inputqueued switch. n input ports and n output ports in an nbyn crossbar layout. At most one cell can depart an input at a time. At most one cell can arrive at an output at a time. Cell arrives at input x and must be routed to output y. Application. Highbandwidth switches. x 1 inputs x 2 x 3 y y y 1 2 3 outputs 42FIFO queuing FIFO queueing. Each input x maintains one queue of cells to be routed. Headofline blocking (HOL). A cell can be blocked by a cell queued ahead of it that is destined for a different output. x 1 y y y 2 1 2 x y 2 2 FIFO x y y y 3 1 3 3 y y y 1 2 3 outputs 43FIFO queuing FIFO queueing. Each input x maintains one queue of cells to be routed. Headofline blocking (HOL). A cell can be blocked by a cell queued ahead of it that is destined for a different output. Fact. FIFO can limit throughput to 58 even when arrivals are uniform i.i.d. Input Versus Output Queueing on a SpaceDivision Input Versus Output Queueing on a SpaceDivision Pack Switch Pack Switch AbstractTwo simple models of queueing on an N X N spacedivision fi connections may be contending for use of the same center fi connections may be contending for use of the same center AbstractTwo simple models of queueing on an N X N spacedivision packet switch are examined. The switch operates synchronously with link. The use of a blocking network as a packet switch is link. The use of a blocking network as a packet switch is packet switch are examined. The switch operates synchronously with fixedlength packets; during each time slot, packets may arrive on any feasible only under light loads or, alternatively, if it is possible to run the switch substantially faster than the input and output inputs addressed to any outputs. Because packet arrivals to the switch are fixedlength packets; during each time slot, packets may arrive on any feasible only under light loads or, alternatively, if it is possible unscheduled, more than one packet may arrive for the same output trunks. inputs addressed to any outputs. Because packet arrivals to the switch are to run the switch substantially faster than the input and output during the same time slot, making queueing unavoidable. Mean queue In this .paper, we consider only nonblocking networks. A unscheduled, more than one packet simple may example arrive of for a nonblocking the same switch output fabric trunks. is the crossbar lengths are always greater for queueing on inputs than for queueing on interconnect with switch points (Fig. 1). Here it is always outputs, and the output queues saturate only as the utilization approaches In this .paper, we consider only nonblocking networks. A during the same time slot, making queueing unavoidable. Mean queue unity. Input queues, on the other hand, saturate at a utilization that possible to establish a connection between any idle input simple example of a nonblocking switch fabric is the crossbar lengths are always greater for queueing on inputs than for queueing on output pair. Examples of other nonblocking switch fabrics are depends on N, but is approximately (2 ) = 0.586 when Nis large. If given in 3. Even with a nonblocking interconnect, interconnect some with switch points (Fig. 1). Here it is always output trunk utilization is outputs, the primary and consideration, the output it is queues possible saturate to only as the utilization approaches queueing in a packet switch is unavoidable, simply because the slightly increase utilization of the output trunksup to (1 e’) = 0.632 possible to establish a connection between any idle input unity. Input queues, on the other hand, saturate at a utilization that as N t by dropping interfering packets at the end of each time slot, switch acts as a statistical multiplexor; that is, packet arrivals output pair. Examples of other nonblocking switch fabrics are depends on N, but is approximately (2 ) = 0.586 when Nis large. If rather than storing them in the input queues. This improvement is to the switch are unscheduled. If more than one packet arrives for the same output at a given time, queueing given is required. in 3. Even with a nonblocking interconnect, some possible, however, only when the utilization of the input trunks exceeds a output trunk utilization is the primary consideration, it is possible to Depending on the speed of the switch fabric and its particular second critical thresholdapproximately In (1 + A) = 0.881 for large queueing in a packet switch is unavoidable, simply because the slightly increase utilization of the output trunksup to (1 e’) = 0.632 architecture, there may be a choice as twhere o the queueing is N. switch acts as a statistical multiplexor; that is, packet arrivals as N t by dropping interfering packets at the end of each time slot, done: for example, on the input trunk, on the output trunk, or at an internal node. to the switch are unscheduled. If more than one packet arrives rather than storing them in the input queues. This improvement is I. INTRODUCTION We assume that the switch operates synchronously with for the same output at a given time, queueing is required. possible, however, only when the utilization of the input trunks exceeds a PACEDIVISION packet switching is emerging as a key fixedlength packets, and that during each time s1ot;packets component in the trend toward highperformance S Depending on the speed of the switch fabric and its particular second critical thresholdapproximately may arrive In (1 on + any A) inputs = 0.881 addressed for to large any outputs (Fig. 2). If integrated communication networks for data, voice, image, the switch fabric runs N times as fast as the input and output architecture, there may be a choice as twhere o the queueing is N. and video l, 121 and multiprocessor interconnects for trunks, all the packets that arrive during a particular input time done: for example, on the input trunk, on the output trunk, or building highly parallel computer systems 3, 4. Unlike slot can traverse the switch before the next input slot, but there presentday packet switch architectures with throughputs will still be queueing at the outputs Fig. l(a). at This an queueing internal node. I. INTRODUCTION measured in 1’s or at most 10’s of Mbits/s, a spacedivision really has nothing to do with the switch architecture, but is due We assume that the switch operates synchronously with 44 packet switch can have throughputs measured in l’s, lo’s, or to the simultaneous arrival of more than one input packet for PACEDIVISION packet switching is emerging as a key fixedlength packets, and that during each time s1ot;packets even 100’s of Gbitsls. These capacities are attained through the same output. If, on the other hand, the switch fabric runs at the use of a highly parallel S component switch fabric coupled in with the trend toward simple highperformance the same speed as the inputs and outputs, only may one packet arrive can on any inputs addressed to any outputs (Fig. 2). If per packet processing distributed among many highspeed integrated communication networks be accepted for by data, any given voice, output image, line during a time slot, and the switch fabric runs N times as fast as the input and output VLSI circuits. other packets addressed to the same output must queue on the and video l, 121 and multiprocessor interconnects for Conceptually, a spacedivision packet switch is a box with trunks, all the packets that arrive during a particular input time input lines Fig. l(b). For simplicity, we do not consider the N inputs and N outputs building that routes the highly packets parallel arriving computer on its systems 3, 4. Unlike intermediate case where some packets can be slot queued can traverse at the switch before the next input slot, but there inputs to the appropriate outputs. At any given time, internal presentday packet switch architectures internal nodes, as with in the Banyan throughputs topology. will still be queueing at the outputs Fig. l(a). This queueing switch points can be set to establish certain paths from inputs It seems intuitively reasonable that the mean queue lengths, measured in 1’s or at most 10’s of Mbits/s, a spacedivision to outputs; the routing information used to establish input really has nothing to do with the switch architecture, but is due and hence the mean waiting times, will be greater for queueing output paths is often contained in the header of each arriving packet switch can have throughputs measured in l’s, lo’s, or on inputs than for queueing on outputs. When queueing is done to the simultaneous arrival of more than one input packet for packet. Packets may have to be buffered within the switch on inputs, a packet that could traverse the .switch to an idle even 100’s of Gbitsls. These capacities are attained through the same output. If, on the other hand, the switch fabric runs at until appropriate connections are available; the location of the output during the current time slot may have to wait in queue the use of a highly parallel switch fabric coupled with simple buffers and the amount of buffering required depend on the the same speed as the inputs and outputs, only one packet can behind a packet whose output is currently busy. The intuition switch architecture and the statistics of the offered traffic. per packet processing distributed among many highspeed that, if possible, it is better to queue on the outputs than the be accepted by any given output line during a time slot, and Clearly, congestion can occur if the switch is a blocking inputs of a spacedivision packet switch also pertains to the VLSI circuits. other packets addressed to the same output must queue on the network, that is, if there are not enough switch points to following situation. Consider a single road leading to both a Conceptually, a spacedivision packet switch is a box with provide simultaneous, independent paths between arbitrary input lines Fig. l(b). For simplicity, we do not consider the spot arena and a store Fig. 3(a). Even if there are no pairs of inputs and outputs. A Banyan switch 35, for N inputs and N outputs that routes customers the waiting packets for arriving service in on the store, its some shoppers intermediate case where some packets can be queued at example, is a blocking network. In a Banyan switch, even might be stuck in stadium traffic. A simple bypass road around inputs to the appropriate outputs. At any given time, internal internal nodes, as in the Banyan topology. when every input is assigned to a different output, as many as the stadium is the obvious solution Fig. 3(b). switch points can be set to establish certain paths from inputs This paper quantifies the performance improvements It seems pro intuitively reasonable that the mean queue lengths, Paper approved by the Editor to outputs; for Local Area the Networks routing of information the IEEE vided used by output queueing to establish for the input following simple model. and hence the mean waiting times, will be greater for queueing Communications Society. Manuscript received August 8, 1986; revised May Independent, statistically identical traffic arrives on each input output paths is often contained in the header of each arriving 14, 1987. This paper was presented at GLOBECOM’86, Houston, TX, on inputs than for queueing on outputs. When queueing is done trunk. In any given time slot, the probability that a packet will December 1986. packet. Packets may have to be buffered within the switch arrive on a particular input ip. s Thus, p represents the average on inputs, a packet that could traverse the .switch to an idle M. J. Karol is with ATLT Bell Laboratories, Holmdel, NJ 07733. until appropriate connections are utilization available; of each the input. location Each packet of the has equal probability 1/ M. G. Hluchyj was with ATT Bell Laboratories, Holmdel, NJ 07733. He output during the current time slot may have to wait in queue N of being addressed to any given output, and successive is now with the Codex Corporation, Canton, MA 02021. buffers and the amount of buffering required depend on the packets are independent. behind a packet whose output is currently busy. The intuition S. P. Morgan is with ATT Bell Laboratories, Murray Hill, NJ 07974. switch architecture and the statistics of the offered traffic. With output queueing, all arriving packets in a time slot are IEEE Log Number 8717486. that, if possible, it is better to queue on the outputs than the Clearly, congestion can occur if the switch is a blocking inputs of a spacedivision packet switch also pertains to the 00906778/87/1200134701.00 0 1987 IEEE network, that is, if there are not enough switch points to following situation. Consider a single road leading to both a provide simultaneous, independent paths between arbitrary spot arena and a store Fig. 3(a). Even if there are no pairs of inputs and outputs. A Banyan switch 35, for customers waiting for service in the store, some shoppers example, is a blocking network. In a Banyan switch, even might be stuck in stadium traffic. A simple bypass road around when every input is assigned to a different output, as many as the stadium is the obvious solution Fig. 3(b). This paper quantifies the performance improvements pro Paper approved by the Editor for Local Area Networks of the IEEE vided by output queueing for the following simple model. Communications Society. Manuscript received August 8, 1986; revised May Independent, statistically identical traffic arrives on each input 14, 1987. This paper was presented at GLOBECOM’86, Houston, TX, trunk. In any given time slot, the probability that a packet will December 1986. arrive on a particular input ip. s Thus, p represents the average M. J. Karol is with ATLT Bell Laboratories, Holmdel, NJ 07733. utilization of each input. Each packet has equal probability 1/ M. G. Hluchyj was with ATT Bell Laboratories, Holmdel, NJ 07733. He N of being addressed to any given output, and successive is now with the Codex Corporation, Canton, MA 02021. packets are independent. S. P. Morgan is with ATT Bell Laboratories, Murray Hill, NJ 07974. With output queueing, all arriving packets in a time slot are IEEE Log Number 8717486. 00906778/87/1200134701.00 0 1987 IEEE Virtual output queueing Virtual output queueing (VOQ). Each input x maintains n queues of cells, one for each output y. Maximum size matching. Find a max cardinality matching. Fact. VOQ achieves 100 throughput when arrivals are uniform i.i.d. but can starve inputqueues when arrivals are nonuniform. y 1 y y y 2 2 2 x 1 y y 3 3 x 2 VOQ y y y 2 2 2 y y y y 3 3 3 3 x 3 y y y 2 2 2 y 3 y y y 1 2 3 outputs 45Inputqueued switching Max weight matching. Find a min cost perfect matching between inputs x and outputs y, where c(x, y) equals: LQF The number of cells waiting to go from input x to output y. OCF The waiting time of the cell at the head of VOQ from x to y. Theorem. LQF and OCF achieve 100 throughput if arrivals are independent (even if not uniform). 1260 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 8, AUGUST 1999 1260 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 47, NO. 8, AUGUST 1999 Achieving 100 Throughput Achieving 100 Throughput in an InputQueued Switch in an InputQueued Switch Nick McKeown, Senior Member, IEEE, Adisak Mekkittikul, Member, IEEE, Nick McKeown, Senior Member, IEEE, Adisak Mekkittikul, Member, IEEE, Practice. Venkat Anantharam, Fellow, IEEE, and Jean Walrand, Fellow, IEEE Venkat Anantharam, Fellow, IEEE, and Jean Walrand, Fellow, IEEE Assignment problem too slow in practice. Abstract—It is well known that headofline blocking limits Abstract—It is well known that headofline blocking limits the throughput of an inputqueued switch with firstin–firstout the throughput of an inputqueued switch with firstin–firstout (FIFO) queues. Under certain conditions, the throughput can be (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6. It is also known shown to be limited to approximately 58.6. It is also known Difficult to implement in hardware. that if nonFIFO queueing policies are used, the throughput can that if nonFIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100 throughput for all independent it is possible to achieve 100 throughput for all independent arrival processes. In this paper we prove this to be the case using arrival processes. In this paper we prove this to be the case using Provides theoretical framework: a simple linear programming argument and quadratic Lyapunov a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is a separate FIFO queue for each output and that the switch is scheduledusingamaximumweightbipartitematchingalgorithm. scheduledusingamaximumweightbipartitematchingalgorithm. Weintroduce twomaximumweightmatchingalgorithms:longest use maximal (weighted) matching. Weintroducetwomaximumweightmatchingalgorithms:longest queue first (LQF) and oldest cell first (OCF). Both algorithms queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100 throughput for all independent arrival processes. achieve 100 throughput for all independent arrival processes. Fig. 1. Components of an inputqueued cellswitch. Fig. 1. Components of an inputqueued cellswitch. LQF favors queues with larger occupancy, ensuring that larger LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can queues will eventually be served. However, we find that LQF can leadtothepermanentstarvationofshortqueues.OCFovercomes leadtothepermanentstarvationofshortqueues.OCFovercomes 4) arriving packets are of fixed and equal length, called 4) arriving packets are of fixed and equal length, called this limitation by favoring cells with large waiting times. this limitation by favoring cells with large waiting times. cells; cells; Index Terms—Arbitration, ATM, inputqueued switch, input 5) is large. Index Terms—Arbitration, ATM, inputqueued switch, input 5) is large. queueing, packet switch, queueing networks, scheduling algo queueing, packet switch, queueing networks, scheduling algo When conditions1) and 2)are truewe shall say thatarrivals When conditions1) and 2)are truewe shall say thatarrivals rithm. rithm. are independent, and when condition 3) is true we shall say are independent, and when condition 3) is true we shall say that arrivals are uniform. that arrivals are uniform. I. INTRODUCTION I. INTRODUCTION The throughput is limited because a cell can be held up by The throughput is limited because a cell can be held up by another cell ahead of it in line that is destined for a different INCE Karol et al.’s paperanother was published cell aheadinof 1986 it in11, lineitthat is destined for a different INCE Karol et al.’s paper was published in 1986 11, it output. This phenomenon is known as headofline (HOL) has become well known that output. an This phenomenon port inputqueued is known as headofline (HOL) has become well known that anS port inputqueued S 46 blocking. switch with firstinput–firstoutput blocking. (FIFO) queues can have a switch with firstinput–firstoutput (FIFO) queues can have a It is well documented that this result applies only to input throughput limited to just It is well documented . The conditions that this result applies only to input throughput limited to just . The conditions queued switches with FIFO queues. And so many techniques for this to be true are that: queued switches with FIFO queues. And so many techniques for this to be true are that: have been suggested for reducing HOL blocking using non have been suggested for reducing HOL blocking using non 1) arrivals at each input are independent and identically 1) arrivals at each input are independent and identically FIFO queues, for example, by examining the first cells FIFO queues, for example, by examining the first cells distributed (i.i.d.); distributed (i.i.d.); in a FIFO queue, where 5, 8, 10. In fact, HOL in a FIFO queue, where 5, 8, 10. In fact, HOL 2) arrival processes at each input are independent of ar 2) arrival processes at each input are independent of ar blockingcanbeeliminatedentirelybyusingasimplebuffering blockingcanbeeliminatedentirelybyusingasimplebuffering rivals at other inputs; rivals at other inputs; strategy at each input port. Rather than maintain a single FIFO strategy at each input port. Rather than maintain a single FIFO 3) all arrival processes have the same arrival rate and 3) all arrival processes have the same arrival rate and queue for all cells, each input maintains a separate queue queue for all cells, each input maintains a separate queue destinations are uniformly distributed over all outputs; destinations are uniformly distributed over all outputs; for each output 1, 9, 16–19, as shown in Fig. 1. This for each output 1, 9, 16–19, as shown in Fig. 1. This Paper approved by P. E. Rynes, the Editor for Switching Systems of the Paper approved by P. E. Rynes, the Editor for Switching Systems of the queuingdisciplineisoftenreferredtoasvirtualoutputqueuing queuingdisciplineisoftenreferredtoasvirtualoutputqueuing IEEE Communications Society. Manuscript received July 29, 1997; revised IEEE Communications Society. Manuscript received July 29, 1997; revised (VOQ). HOL blocking is eliminated because a cell cannot be (VOQ). HOL blocking is eliminated because a cell cannot be October 5, 1998. This paper was presented in part at INFOCOM’96, San October 5, 1998. This paper was presented in part at INFOCOM’96, San Francisco, CA. held up by a cell queued ahead of it that is destined for a Francisco, CA. held up by a cell queued ahead of it that is destined for a N. McKeown is with the Department of Electrical Engineering, Stanford N. McKeown is with the Department of Electrical Engineering, Stanford different output. The implementation of VOQ is slightly more different output. The implementation of VOQ is slightly more University, Stanford, CA 943059030 USA (email: nickmstanford.edu). University, Stanford, CA 943059030 USA (email: nickmstanford.edu). complex, requiring FIFO’s to be maintained by each input complex, requiring FIFO’s to be maintained by each input A. Mekkittikul was with the Department of Electrical Engineering, A. Mekkittikul was with the Department of Electrical Engineering, Stanford University, Stanford, CA 943059030 USA. He is now with buffer. But no additional speedup is required; at most one cell Stanford University, Stanford, CA 943059030 USA. He is now with buffer. But no additional speedup is required; at most one cell Berkeley Concept Research Corporation, Berkeley, CA 94704 USA (email: Berkeley Concept Research Corporation, Berkeley, CA 94704 USA (email: can arrive and depart from each input in a slot. During each can arrive and depart from each input in a slot. During each adisakbcrcorp.com). adisakbcrcorp.com). slot, a scheduling algorithm decides the configuration of the slot, a scheduling algorithm decides the configuration of the V. Anantharam is with the Department of Electrical Engineering and V. Anantharam is with the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA switch by finding a matching on a bipartite graph (described Computer Sciences, University of California at Berkeley, Berkeley, CA switch by finding a matching on a bipartite graph (described 94720 USA (email: anantheecs.berkeley.edu). 94720 USA (email: anantheecs.berkeley.edu). below). A number of different techniques have been used for below). A number of different techniques have been used for J. Walrand is with Odyssia Systems, Berkeley, CA 94710 USA (email: J. Walrand is with Odyssia Systems, Berkeley, CA 94710 USA (email: finding such a matching, for example, using neural networks finding such a matching, for example, using neural networks jeanodyssiasystems.com). jeanodyssiasystems.com). Publisher Item Identifier S 00906778(99)063059. 2, 4,22 or iterative algorithms 1, 14,15. These algo Publisher Item Identifier S 00906778(99)063059. 2, 4,22 or iterative algorithms 1, 14,15. These algo 0090–6778/9910.00 © 1999 IEEE 0090–6778/9910.00 © 1999 IEEE
Website URL
Comment