ࡱ> ebcd`!t+Z,TL!QN ) ?XjxڕkAgvM&iڤi)E[IĂAh=*ݶ%?JiATO"Z+^(MԒ'  g;ә6!t>ff ADx_C#kpȵZ-<8Ir8;呈5:.@?h n[aIV# ej:*UQ+5}Q^*hErϔ+& +OfF!mn?І3éHF('P>TVV8%@*F`(kbŽ?j9hF-?pqg7\V>2`rZJ#:@0:AOJ?Ja!^ :"%4).0x~v̥ 뢕VDdi2Vk4CE$]MS֌jjU2EUZ}fT\џ6(J%"XuVx"Vam-UT|/I=M4Kk,.QB ,3Q/"gO)͹\VΨbܨ:j|*jUKȮnewe3=Xeb[:ksؙc$IT#wFӭ7 Gq._Q|;dIӒ^MD]}cV\nͳs Z~KYr?DQp7;Ǐg\^xU{6Vg~mOO܂vO4> ںE:Є9M84c$IA@A&wYh&l31ڔ442_2Ɓ,m/ٶF;(< `*j6u haZq`BNмnAzHrM>H5 ,v݀hqpu-TVBwҶVtioc+q[[o!OEJºm8"ŔIi[?rpX`2ƤvY6 ^6 Q0[6J%ܜ^;ݱG8ʣڦNvGla+#!4n/Nr ) S+'xEFLȈë]YX[:XfH Ө=JY/N ^4?{mmM\*Jc4f1XivCi,!I0>'P&Fƻ4Zkx)=D0,iZs~:0H R|mA Kw.LiF!3Jٛ(>qڅ>O?=QW῰u#M"2/@eW{%|׈ 2 !S^ =E`!l Jx& ^ XJ:xeQ=KA}3{1%aD,"0 I K#(xFH@;;{Ghp3IQ xՉ ib4=1)o 9&[}OxnPZceRFo.GWY_ķ6>־#F0Kݎ}f#@հs 4NbCA7' E0`! 07:w5֔2u#@4Q- xڵZ]lWwv$NBp[K!vlҐ!(?lRxwwf6kGPR/<x "@UV }B ȓP^*6sg^nv6?s9wdJK;!S#O<IV Yr?K$ k~o`Y䣫{Lh x~VPk-ŋ-' i}&3eld$u.2@E!۱#ZH^K.dI'x`y#J{jZ&ꙑw@[$27ӻvvʹ #?ַIwFBTKO7w9Ү&UNg9_Ԓ.A/& >SM0[t(2E>тSڹ5ߧ NG6Am"~OGOĻsɭ-do$x;3}T;fxƬui/ѣ''4oD5H݃ d̜x d\=:+K͑^yߜ#w'O>%oQϑw4GNMD{żb[&)[0,CcV-i* wh: p5ެ%;ʩW ܺSyXZXZ<{s$vj4*W/K<[%N=nnQi.ho×xM!=+p ݾGGceB 1wLZ1B-ĥܲ\\Y*?$kٿ2Z ݨo} m#̅"ȝKd6p;7ۙ9<^2׶MNK,%kKܒ6X}CXA9gr;w Z:`=LLϥLٓv8&8kgaՒwQW7UPi.+MTnnQyN:v Hhۋ;v~R>7hߣ~k[_րKΌ%Əkk =c$U 弴GJwhb {#7H~ub g:@ևZ[^?4qvo37ڂGMhjT#@B ^5W dļ 91M_ &)x<I,F7迡~X8ߌ)j0PM-↋PW WXb . ' d2 ZM>/le>]1z%bl$TYn!~[5GhhFʴj7rEP]Z X# ?EܧG*SռN cጎ _ˋfFpZR> ljKr1T"2,{| 95z9%I\PUZ"7^kQ ]`zZ/rb\H>9CP~M1+ 2Ev^lo(%!>z% pPc*@W]MUv%U*iF%nlTjPZΨcTX>YY0 Ǯ"W= ]Yaim50E>|ҊĔ΄aX{yCVYOg Xomc,e E-@N]v\{ȵRjj4ZyzUn\a-Ix;:iq[,ܪW8gz<}mSjZ؂fpSSn{4`!APDH>ZjQ8iXwz X xڵUkA3͇jA,Ik6XHhRqMI5)xxA{ =HOGI00 E yy2a> +gv }<rv  |Х`,2CGXxp:w?I$Ӫ)k'ӇZb g % eRй}b "װ"(5Dž rٸe9䤈Pk#l<*뱱 pN;-m!>q;uo)|XT)i\Wip-M8F~ߓ$O}%U!ifvۊ¯R8T}fִնꞏ6V,Ge®&[G"t,n}d;EWtk+x:tPVŨV/bu:ƳTНZA xdFI KFAEquation Equation.DSMT40*MathType 4.0 Equation0).CEquation Equation.DSMT40*MathType 4.0 Equation0.7DEquation Equation.DSMT40*MathType 4.0 Equation0@cEEquation Equation.30,Microsoft Equation 3.00?gFEquation Equation.30,Microsoft Equation 3.0/ 00DTimes New Roman50Wo 0DComic Sans MSn50Wo 0B DWingdings MSn50Wo 00DWingdings 3Sn50Wo 0 ` .  @n?" dd@  @@``    0)  OFF*e5 [Fo;4\OIFO_dZ_AMI,ej  ECd<"):)>>>@>3#OE7_KK"9s( $`P  U<(@>>A?3&~>" ? D  @ JE5S8@5#:80>$2$t+Z,TL!QN$$$$2$Cv[e 2$ Jxt 2$07:w5֔2u }$$$$$$2$APDH>ZjQ8iXwc $0 33@33 qʚ;2Nʚ;g4VdVd02ppp@ <4!d!d 0L6<4dddd 0L6<4BdBd 0L6z___PPT9\T? -O =X`Scheduling Crossbar Switches =Who do we chose to traverse the switch in the next time slot?>>= dHistory[Karol et al. 1987] Throughput limited to by head-of-line blocking for Bernoulli IID uniform traffic. [Tamir 1989] Observed that with  Virtual Output Queues (VOQs) Head-of-Line blocking is reduced and throughput goes up. " ,3;aBasic Switch ModelbSome definitionseFinding a maximum size match$/How do we find the maximum size (weight) match?00f$Network flows and bipartite matching%%$~Finding a maximum size bipartite matching is equivalent to solving a network flow problem with capacities and flows of size 1.: Network Flows;,A maximum network flow example By inspection -$ <A maximum network flow example$>)Ford-Fulkerson method of augmenting paths**$ fSet f(v,w) = -f(w,v) on all edges. Define a Residual Graph, R, in which res(v,w) = cap(v,w)  f(v,w) Find paths from s to t for which there is positive residue. Increase the flow along the paths to augment them by the minimum residue along the path. Keep augmenting paths until there are no more to augment.B4 " Z( H?Example of Residual Graph@Example of Residual GraphA#Complexity of network flow problemsIn general, it is possible to find a solution by considering at most VE paths, by picking shortest augmenting path first. There are many variations, such as picking most augmenting path first. Best Algorithm based on work by Dinic.TE!*Finding a maximum size match$/How do we find the maximum size (weight) match?00,$Network flows and bipartite matching%%$~Finding a maximum size bipartite matching is equivalent to solving a network flow problem with capacities and flows of size 1.:Network flows and bipartite matching Ford-Fulkerson method ;%$*  $Network flows and bipartite matching%%$  $Network flows and bipartite matching%%$ !$Network flows and bipartite matching%%$ "$Network flows and bipartite matching%%$ #$Network flows and bipartite matching%%$ CComplexity of Maximum Matchings Maximum SizeMatchings: Algorithm by Dinic O(N5/2) Maximum Weight Matchings Algorithm by Kuhn O(N3) In general: Hard to implement in hardware Slooooow. (   ( P  C^Outline'Recap of LQF and proof of stability. OCF: Weight equals the age of a cell. Why do we need a weight to stabilize the switch for non-uniform arrivals? Finding a maximum match. Maximum network flow problems Maximum size/weight matchings as examples of maximum network flows LPF: Another algorithm. za\L  C ?Another algorithm (LPF) /LPF0Properties of LPFqLPF is stable for all admissible Bernoulli traffic. An LPF match is a maximum size match. How can this be stable?  ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@(?vKd@ " d@ ` n?" dd@   @@``PR    @ ` ` p>>   4, (    6s "P  T Click to edit Master title style! !$  0v "  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0| "``  <    0d~ "`   >    0ԁ "@  \* H  0޽h ? ̙33 $Blank Presentation 0 zr  (     0: M(   P*    0<  (  R*  d  c $ ?4h    0P+  ?c  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6tD M   P*    6HJ    R*  H  0Bhy ? ̙33@ (    0W M(   X*   0`\  (  Z*   6K M   X*   6Pc    Z* H  0Bhy ? ̙33     "N (  ~  s *xN:P  : r ! S O:  :   0ؼԔ@   B  2   0,ܼP B  2   0X߼p B  2   0p 0  B  2   0P:p   B  2  0(T:0 p B  2  0V:0 P B  XB  0D3o P XB  0D3o@P@XB  0D3o P XB @ 0D3o ` 0 XB @ 0D3o ` 0   6Z: Q E  7N   6(^:   7N LB  c $D  `LB  c $Dp p LB @ c $D  p LB  c $D0 ` ` P LB  c $D`    64`:V *  71   6c: 71 XB  @ 0D3o@` 0 @H  0޽h ? ̙33  TL077(  B  ZDo?"Y 8B  ZDo?"PY 8PB  ZDo?" ~  s *T:P`  :   c $:0<$ 0 : "p`PpB  <D8csS,$D 0B  0DjB B Z,$D 0XB   0DZ2B Z^B   6D|B  XB   0Dj2B j^B   6D|nK n^   6?jB WR  s *jWB  ZDo?" B  ZDo?" 2  No?" J 2  No?" q 2  No?" q 0dB  <D8cPpPP^  6?` B  ZDo?" n2  No?" J 0^  6?@`  c $A @??@ @B  ZDo?"} }R  s *aB B  ZDo?" A  B  ZDo?"NA NB  <D8c jJ ,$D 0B  <D8c jJ ,$D 0B   0DY 9 9 I ,$D 0XB ! 0DI )9 I ^B " 6D| 9 XB # 0DY )9 Y ^B $ 6D|]B  ]XB % 0D 9 ^ & 6?Y 9 R ' s * 9 F B ( ZDo?" xB ) ZDo?" 2 * No?"  A 2 + No?"  h 2 , No?" h  dB - <D8cjJXB . 0D B B XB / 0D2B XB 0 0D 2B XB 1 0D]B ]^ 2 6? B ]B 3 ZDo?" ]2 4 No?" A  B 5 <D8c~aA~,$D 0LB 6 c $DppPp 7 |BCDEF @P` H  0޽h ? 33v  &@99(  ~  s *:P  : R  s *Ԕ@ ` 0 R  s *ԔP ` LB  c $Do00LB  c $DoLB  c $DoppLB  c $Do  LB   c $Do@ @ LB   c $Do` ` LB   c $Do  LB   c $DoLB   c $Do0LB  c $Do @ LB  c $DopLB  c $Do`  RB  s *DԔ` @@ RB  s *DԔp @@0 RB  s *DԔ@@  6c. _A1(n)>   6`ho@   B    6kP 4p :S(n) 2  0oP B  2  0\rp B  2  0|up 0  B  2  0lyp   B  2  0{0 p B  2  00 P B  RB  s *Do P RB  s *Do@P@RB  s *Do P LB  @ c $Do ` 0 LB !@ c $Do ` 0  " 6 Q E  7N  # 6D   7N  $ 6 P  `LNN(n)>  % 6NN " `A1N(n)>  & 6,r" `A11(n)> LB ' c $D`LB ( c $D` ) 6lZ) . `L11(n)> LB * c $D  `LB + c $Dp p LB ,@ c $D  p LB - c $D0 ` ` P LB . c $D`   / 6jV *  71  0 6X 71 RB 1 s *DԔ 0p  2 6   _AN(n)> RB 3 s *DԔ 0p  4 6 @  `ANN(n)>  5 6쮚N d#"  `AN1(n)> LB 6 c $D Rr LB 7 c $D Rr  8 6ȳp$ _D1(n)>  9 6ظ~ de  _DN(n)> H  0޽h ? ̙33     PH (  ~  s *pP   `  c $A B??f2O  ?  6 9  K3. Queue occupancies: RB  s *Do0 RB  s *Do,FB  S DE FB  S D FB   S D||FB   S DU< < FB   S DU, , FB   S D  FB   S D FB  S D FB  S D5FB  S D FB  S DE lE FB  S D \ FB  S DLFB  S DU l UFB  S DU \ UFB  S D L FB  S D  FB  S D  FB  S D55FB  S D  RB  s *Do \   6>  A Occupancy    6 `L11(n)>   6, `LNN(n)> H  0޽h ? ̙33  0(`//(  x  c $֚   x  c $xך    d  <Gu^ LB  c $DH MLB  c $DS& sLB  c $DM LB  c $DH sLB   c $Dm sLB   c $Ds LB   c $D LB   c $D LB   c $D LB  c $D LB  c $D LB  c $D LB  c $DX LB  c $Ds LB  c $D LB  c $D LB  c $D  F ` >   `>   <TК` 5A  < 5B  < 5C  < : 5D  <:  5E  < >  5FZ2  s *3! Z2  s *3A Z2  s *3a Z2   s *3 Z2 ! s *3  Z2 " s *3 ! F  `/ *  # `  *  $ <,H `  51 % <F /  52 & < D -  53 ' <\B +  54 ( <@ )   55 ) <> ' *  56Z2 * s *3 ` Z2 + s *3 @` Z2 , s *3 `` Z2 - s *3 ` Z2 . s *3 ` Z2 / s *3 ` H  0޽h ? 33  2*p==(  x  c $?   x  c $d#   d  <Gv   <њ` 5A  <Pʚ`H   51X2  0 3  <͚zpZ HSource s$ 3X2   0iv   <\@$ F FSink t$3RB   s *DPFRB   s *DzFRB   s *DFRB  s *DFRB  s *DPb i RB  s *DsK i RB  s *D] i RB  s *D @ iRB  s *DHRB  s *DH RB  s *D 3 hRB  s *D&8 m LB  c $DH" MLB  c $DS> sLB  c $DM" LB  c $DH( sLB  c $Dm" sLB  c $Ds3 LB  c $D( LB  c $D8 LB  c $D8 LB   c $D" LB ! c $D3 LB " c $D8 LB # c $DX LB $ c $Ds" LB % c $D4 LB & c $D LB ' c $D (  ( <@ 5B ) <pD 5C * <G 5D + <LK  5E , <`N >  5F - <RF /  52 . <OD -  53 / <XB +  54 0 <t[@ )   55 1 <^ > ' *  56R2 2 s *3! R2 3 s *3A R2 4 s *3a R2 5 s *3 R2 6 s *3  R2 7 s *3  ! R2 8 s *3  ` R2 9 s *3@ ` R2 : s *3` ` R2 ; s *3 ` R2 < s *3 ` R2 = s *3 ` H  0޽h ? 339  !!y(  x  c $p:P   X2  00@RB  s *D`X2  00-RB  s *D] RB  s *D`RB  s *D] RB   s *D] RB   s *D] RB   s *D] -`RB   s *D`] -   <@t HSource s$ 3  <v FSink t$3  <ǚ  1a  <H~  1c  <  1b  <T  1dz 0Y@  Y0@,$D 0  <0= 810  <0=w 810  <̍ Y @ 810  <\ pE W 71  < i P 71  <$ Y @ 71  <\0 `=G 810  <Ğ}  8100  0  5 Let G = [V,E] be a directed graph with capacity cap(v,w) on edge [v,w]. A flow is an (integer) function, f, that is chosen for each edge so that We wish to maximize the flow allocation. $ &) @`R2  s *3] @R2  s *3] @R2  s *3] @R2   s *3] @` ! c $A .??  @  .H  0޽h ? 33"  !!>>\!(  x  c $o    X2  00@RB  s *D`X2  00-RB  s *D] RB  s *D`RB  s *D] RB   s *D] RB   s *D] -`RB   s *D`] -   <& HSource s$ 3   <l FSink t$3  <  1a  <8  1c  <  1b  <H  1dz 0Y@  Y0@,$D 0  <,0= 810  <0=w 810  < Y @ 810  <| pE W 71  <t i P 71  < Y @ 71  <$0 `=G 810  <L}  810  <*  8Step 1:  R2  s *3] @R2  s *3] @R2  s *3] @R2  s *3] @RB   s *D] z    !  ,$D 0`2 " 0 C0 `B # 0D> `2 $ 00 0 `B % 0D> ` ZB & s *D ZB ' s *D ` ZB ( s *D ` `B ) 0D>` 0 ZB * s *D` 0  + < * 0  HSource s$ 3 , <,* 0  FSink t$3 - <   1a . <   1c / <`  1b 0 < `  1d 1 <07I 0 0  L10, 10*3 2 <D30 @  810 3 <4  L10, 10*3 4 <d  H  71 5 <"  71 6 <,&  71 7 <)3 @  810 8 <, g  L10, 10*3 9 <0}  DFlow is of size 10Z2 : s *3` ZB ; s *D ` Z2 < s *3 ` Z2 = s *3 ` Z2 > s *3` H  0޽h ? 33&  P&H&CC %(   x   c $2`   X2   0pXB   0D>]X2   0p]XB   0D>]- ]XB   0D>PXB   0D>P- PRB   s *D]- PRB   s *D]- PXB   0D>]- XB   0D>- P   <O HSource s$ 3   <T FSink t$3   <Y0i P 1a   <\0 P 1c   <_m  1b   <b  1d   <df L10, 10*3   <xj K10, 1*3   <Z  L10, 10*3   <q`   71   <t u  71   <x 6  J1, 1*3   <0|M -4 K10, 1*3   <   L10, 10*3   <X# 8Step 2:     <d$p UFlow is of size 10+1 = 11 LB   c $DR2   s *3 - R2   s *3 - R2   s *3 - R2 !  s *3 - gz   "   ,$D 0`2 #  0 @C `B $  0D>  `2 %  0- C `B &  0D> ] `B '  0D>  `B (  0D> ] `B )  0D> ] `B *  0D>] - `B +  0D>]  -  ,  <= C  HSource s$ 3 -  <@= C  FSink t$3 .  <  1a /  <x  1c 0  <s  1b 1  < s  1d 2  <p4\ - C  L10, 10*3 3  <0C *  K10, 2*3 4  <  K10, 9*3 5  <P  n  I1,1*3 6  <8     I1,1*3 7  < f  J1, 1*3 8  <, t  K10, 2*3 9  < z  L10, 10*3 :  <h  = Maximum flow: ;  <X!  UFlow is of size 10+2 = 12 L p  <  p ,$D 0 =  <  > Not obvious   >  s BC DE(FԔ PP P 0  @   p Z2 ?  s *3 ] Z2 @  s *3] `B A  0D> ] Z2 B  s *3 ] Z2 C  s *3] H   0޽h ? 33  F(  x  c $4     c $0  "P@08XH  0޽h ? 33"  F">"??!(  x  c $    X2  0pCXB  0D>] X2  0p0XB  0D>] ` ]RB  s *D PRB  s *DP ` PRB   s *D] ` PRB   s *D] ` PXB   0D>]` 0RB   s *D` 0P   < 3s  <(~L 3t  <t"0 P 1a  <&0 P 1c  <<  1b  <;  1d  <:70  L10, 10*3  <TA3@ 810  <C  L10, 10*3  <F H  71  <I  71  <XM  71  <`3 @ 810  <   L10, 10*3  <} z DFlow is of size 10X2  0 C XB  0D1  X2  0 0 XB  0D1 ` ` XB   0DԔ  XB ! 0DԔ ` RB " s *D ` RB # s *D ` XB $ 0D1 0 XB % 0DԔ ` 0 & <` ~L  3t ' <Ī   1a ( <;   1c ) < P  p 1b * <`P  p 1d + <+p -W  810 , <t8 3@ 810 - < s *3p ` R2 ? s *3p` H  0޽h ? 336)  ((IIv((  x  c $`   X2  0pXB  0D>]X2  0p]XB  0D>]- ]XB  0D>PXB  0D>P- PRB   s *D]- PRB   s *D]- PXB   0D>]- XB   0D>- P   < B s$3  <DK B t$3  <0i P 1a  <0 P 1c  <؍m  1b  <|  1d  <\ L10, 10*3  <Й K10, 1*3  <  L10, 10*3  <`   71  < u  71  < 6  J1, 1*3  <M -4 K10, 1*3  <`   L10, 10*3  <<# 8Step 2:    <$p UFlow is of size 10+1 = 11 X2  0 `i XB  0D1 ;( 9 X2  0 Xi XB   0D19 ;( XB ! 0D1 ( XB " 0D1 X9 XB # 0D19 X  $ <c T%i  B s$3 % <c ti  B t$3 & <X   1a ' < B   1c ( <`   1b ) < B '  1d * << -  H10*3 + <Pi @P  G1*3 , <d2 + 8   H10*3 - <x6 { 0   G1*3 . <B  )  G1*3 / <2 H  G1*3 0 <0 e  G1*3 1 < H U  H10*3 2 <`   >Residual GraphLB 3 c $DNF 0 @ 4  0@`B 5 0D1 `B 6 0D1( `B 7 0D1(  8  BCDE(F <x` @   0` 0 8 9  BCDE(F ,X( pH$ @    ` @ : <Y 0@ G9*3 ; <$ l G9*3z 0 @ <  0@,$D 0`B = 0DԔ `B > 0DԔ( `B ? 0DԔ(  @ C BCDE(FԔ <x` @   0` 0 8 A C BCDE(FԔ ,X( pH$ @    ` @R2 B s *3 - R2 C s *3 - R2 D s *3 - R2 E s *3 - R2 F s *3 (  R2 G s *3 ( R2 H s *3  R2 I s *3 H  0޽h ? 33   0(   x   c $    x   c $  H   0޽h ? 33d   /?(  x  c $   x  c $    d  <Gu^ LB  c $DH MLB  c $DS& sLB  c $DM LB  c $DH sLB  c $Dm sLB  c $Ds LB  c $D LB  c $D LB  c $D LB   c $D LB ! c $D LB " c $D LB # c $DX LB $ c $Ds LB % c $D LB & c $D LB ' c $D  8 ` >  >`>   <` 5A ( <\ 5B ) <8^ 5C * <] 5D + <^  5E , <h >  5FZ2 2 s *3! Z2 3 s *3A Z2 4 s *3a Z2 5 s *3 Z2 6 s *3  Z2 7 s *3 ! 8  `/ *  ?`  *   <mH `  51 - <pF /  52 . <D -  53 / <B +  54 0 < @ )   55 1 <> ' *  56Z2 8 s *3 ` Z2 9 s *3 @` Z2 : s *3 `` Z2 ; s *3 ` Z2 < s *3 ` Z2 = s *3 ` H  0޽h ? 33  2*==(  x  c $H>   x  c $?   d  <Gv   < P` 5A  <S`H   51X2  0 3  <@zpZ HSource s$ 3X2   0iv   <(D@$ F FSink t$3RB   s *DPFRB   s *DzFRB   s *DFRB  s *DFRB  s *DPb i RB  s *DsK i RB  s *D] i RB  s *D @ iRB  s *DHRB  s *DH RB  s *D 3 hRB  s *D&8 m LB  c $DH" MLB  c $DS> sLB  c $DM" LB  c $DH( sLB  c $Dm" sLB  c $Ds3 LB  c $D( LB  c $D8 LB  c $D8 LB   c $D" LB ! c $D3 LB " c $D8 LB # c $DX LB $ c $Ds" LB % c $D4 LB & c $D LB ' c $D (  ( <P 5B ) <lS 5C * <V 5D + <HZ  5E , <] >  5F - <`F /  52 . < ' *  56R2 2 s *3! R2 3 s *3A R2 4 s *3a R2 5 s *3 R2 6 s *3  R2 7 s *3  ! R2 8 s *3  ` R2 9 s *3@ ` R2 : s *3` ` R2 ; s *3 ` R2 < s *3 ` R2 = s *3 ` H  0޽h ? 33J  ==(  x  c $(N@   d  <  6   <w\\  5A  <  51X2  0_     <   4 sX2  0U V    <XH  B t$3XB   0DԔ @ XB   0DԔ @ XB   0DԔ ' RB   s *D 4  XB  0DԔ _ XB  0DԔ _ XB  0DԔ _ RB  s *D_  RB  s *D 3 RB  s *D 3 ' RB  s *D_  RB  s *De ' XB  0DԔ RB  s *De RB  s *D` RB  s *DZ XB  0DԔ RB  s *DZ ! XB  0DԔ RB  s *DU RB  s *Dk  RB  s *D e  RB   s *D q  RB ! s *D k , RB " s *Dq RB # s *Dv RB $ s *DZ ! LB % c $D e 2 RB & s *D, Z 2  ' <Ԑ\I  5B ( <d\D  5C ) < \\ 1  5D * <@7 \H W  5E + <] \E }  5F , <  52 - <h   53 . < %  54 / <D' G  55 0 <ԯI i  56R2 1 s *3`- R2 2 s *3- R2 3 s *3- R2 4 s *3 - R2 5 s *3 - @ R2 6 s *3 - ` R2 7 s *3_ R2 8 s *3 R2 9 s *3 R2 : s *3  R2 ; s *3 ? R2 < s *3 _  = <Ķ0 P V&Residual Graph for first three paths: ''H  0޽h ? 33k   ==(  x  c $0P   d  <  6   <h\\  5A  <  51X2  0_     <`   4 sX2  0U V    <}H  B t$3XB   0DԔ @ XB   0DԔ @ XB   0DԔ ' RB   s *D 4  XB  0DԔ _ XB  0DԔ _ XB  0DԔ _ RB  s *D_  XB  0DԔ 3 XB  0DԔ 3 ' XB  0DԔ_  XB  0DԔe ' XB  0DԔ RB  s *De RB  s *D` RB  s *DZ XB  0DԔ RB  s *DZ ! XB  0DԔ RB  s *DU RB  s *Dk  RB  s *D e  XB   0DԔ q  RB ! s *D k , RB " s *Dq RB # s *Dv RB $ s *DZ ! LB % c $D e 2 XB & 0DԔ, Z 2  ' <\I  5B ( <T\D  5C ) < \\ 1  5D * <07 \H W  5E + <|] \E }  5F , <   52 - <d   53 . < %  54 / <|' G  55 0 <I i  56R2 1 s *3`- R2 2 s *3- R2 3 s *3- R2 4 s *3 - R2 5 s *3 - @ R2 6 s *3 - ` R2 7 s *3_ R2 8 s *3 R2 9 s *3 R2 : s *3  R2 ; s *3 ? R2 < s *3 _  = <W? S#Residual Graph for next two paths: $$H  0޽h ? 33  NF0?@(  x  c $5   d  <  6   <`7\\  5A  <:  51X2  0_     <(   4 sX2  0U V    <H  B t$3XB   0DԔ @ XB   0DԔ @ XB   0DԔ ' dB   <D3Ԕ 4  XB  0DԔ _ XB  0DԔ _ XB  0DԔ _ dB  <D3Ԕ_  XB  0DԔ 3 XB  0DԔ 3 ' XB  0DԔ_  XB  0DԔe ' XB  0DԔ RB  s *De dB  <D3Ԕ` RB  s *DZ XB  0DԔ RB  s *DZ ! XB  0DԔ dB  <D3ԔU RB  s *Dk  RB  s *D e  XB   0DԔ q  RB ! s *D k , dB " <D3Ԕq RB # s *Dv RB $ s *DZ ! LB % c $D e 2 XB & 0DԔ, Z 2  ' <(\I  5B ( <!\D  5C ) <% \\ 1  5D * <(7 \H W  5E + <+] \E }  5F , <p/  52 - <2   53 . <L6 %  54 / <9' G  55 0 <(=I i  56R2 1 s *3`- R2 2 s *3- R2 3 s *3- R2 4 s *3 - R2 5 s *3 - @ R2 6 s *3 - ` R2 7 s *3_ R2 8 s *3 R2 9 s *3 R2 : s *3  R2 ; s *3 ? R2 < s *3 _  = <DW T$Residual Graph for augmenting path: %%dB > <D3Ԕip ndB ? <D3Ԕ H  0޽h ? 33  e]@>>(  x  c $   d  <  6   <X\\  5A  <   51X2  0_     <`x   4 sX2  0U V    <yH  B t$3XB   0DԔ @ XB   0DԔ @ XB   0DԔ ' XB   0DԔ 4  XB  0DԔ _ XB  0DԔ _ XB  0DԔ _ XB  0DԔ_  XB  0DԔ 3 XB  0DԔ 3 ' XB  0DԔ_  XB  0DԔe ' RB  s *D RB  s *De XB  0DԔ` RB  s *DZ XB  0DԔ RB  s *DZ ! RB  s *D XB  0DԔU RB  s *Dk  RB  s *D e  XB   0DԔ q  RB ! s *D k , XB " 0DԔq RB # s *Dv RB $ s *DZ ! LB % c $D e 2 XB & 0DԔ, Z 2  ' <`\I  5B ( <`d\D  5C ) <g \\ 1  5D * < <؊ 5J^ pNote that the path augments the match: no input and output is removed from the match during the augmenting step.2qVH  0޽h ? 33  F>P22(  x  c $([0   d  <  6   <\\  5A  <8   51X2  0_     <   4 sX2  0U V    <pH  B t$3XB   0DԔ @ XB   0DԔ @ XB   0DԔ ' XB   0DԔ 4  XB  0DԔ _ XB  0DԔ _ XB  0DԔ _ XB  0DԔ_  XB  0DԔ 3 XB  0DԔ 3 ' XB  0DԔ_  XB  0DԔe ' XB  0DԔ` XB  0DԔ XB  0DԔU XB  0DԔ q  XB  0DԔq XB  0DԔ, Z 2   <h\I  5B  <8"\D  5C  < \\ 1  5D  <X7 \H W  5E   <] \E }  5F ! <4  52 " <d   53 # <l %  54 $ <' G  55 % <\I i  56R2 & s *3`- R2 ' s *3- R2 ( s *3- R2 ) s *3 - R2 * s *3 - @ R2 + s *3 - ` R2 , s *3_ R2 - s *3 R2 . s *3 R2 / s *3  R2 0 s *3 ? R2 1 s *3 _  2 <pWi  DMaximum flow graph: H  0޽h ? 33u  %`#%(  x  c $   d  <  6   <\\  5A  <<  51XB  0DԔ` XB  0DԔ XB  0DԔU XB   0DԔ q  XB   0DԔq XB   0DԔ, Z 2    <\I  5B   <\D  5C  <\ \\ 1  5D  <7 \H W  5E  <8] \E }  5F  <4  52  <   53  << %  54  <' G  55  <$I i  56R2  s *3`- R2  s *3- R2  s *3- R2  s *3 - R2  s *3 - @ R2  s *3 - ` R2  s *3_ R2  s *3 R2  s *3 R2  s *3  R2   s *3 ? R2 ! s *3 _  " <W  GMaximum Size Matching: r % S <   H  0޽h ? 33  p(0(  (x ( c $8]P   x ( c $O  H ( 0޽h ? 33J  (  x  c $@P   x  c $(  R  s *3 `pH  0޽h ? ̙33  z;(  r  S ̕P   `  c $A F??! FH  0޽h ? ̙33  z(  r  S P   `  c $A )?? )H  0޽h ? ̙33  $(  r  S `P   r  S Lb   H  0޽h ? ̙33* 6xZ}lS=;vLPPiq"hFҤLIAMb:K!ЪI eM[1CMG*mӂWMѴUU˘Jہ s{'~^`[5_s߿s=s_#)R>KjT^?XZZҚr >*SO+ ZTTȩ)**U@*r:J=7A_G"`T@=Ogӳ=}'@šLNsWF46?LF^25~ DxY-~мDK:U~K8lR~u՜) @zh Г@[mrx܉S^4-=LPl/t#}F 9z|ԚNϾC]=3??fm'\򃡶mwv'n+FJ&GZCq-/R[ۢaO<ŮCPR\ăp BC'ý)tXݾyܾ"6UAl%ŭ; "g>:z`mi(>utQ"kup  ~xitX}:1c֎YfE1a&c,Y`!F~ Ä́< n>Pʼn#P|8&ҒTڸʖ=hUg}AfK!땊QByɆz<*)OR\?Rx;8g5z:w]s_8r '8)P-u*CTGw,J)F4>v罾vr+|pԯ+|bu˜,b<1mc(;b 4ɉ`X#q18!G$PM9x;"AN><9*2r$gHj^[W]T[ή%O4¥KN"lK:if̓^GxBliգ7^!O0)(US_эY5RW_c7i6Ό&WP*3E٘dGvWU_0pS]LaHPG6$ITw^j8˙ v - =l*#Ly;`4`c7ڀ+%iTf݆BŢ-0YiOrԷOUU%-2V"z3Ծ5r<_}dxmluvac;/llC0m6F=aIk|aL۔p-Z?iUڪnZ"?jQ*AU(rVfvgn{=>ܽ9Y>; %9e/ {g "{w/'Xnp+*TT,a&@X P a%W4X/rBI ~ 2 ,b6ܓ=m\/U @ǧ|$V"͏u'1@FG<ŏv[5b6_Vs?lݳx J_@| `ll@9m Nv] o* 㮲 444 4 imlMH @^G;щ1MnSOU+%jM`x_N2'\T &12ggS6%?_=ٱ+BggsrR&/S>ՌvCZTi&+ғAOMJGITk=H]o"9'H]0rT>e*{mo<x:h/$ss.VmM\`}_;-YS%GdI&PZ8r/V),4 2@ϋa`5'7z}%;:o!FO[`[ i+,-yU;G<]^:C, Wk샖egUq ^,dl˗C'{oT&:؄6VܨkjfpT%GpN֔1DHg2i)^=2%U6VK ־JR-$&=\AfMz |P|}Xi[:(T&()h Ns9^m}RBrqy{Xݭєq-Pg aR},f)7`$ac|pɚO~x jnP*]\|?-$_HJM+0 T|";tz]*7nk9vtQ%{%kwу{ɥEx9ʺ\>(K9F2R#T&*=. ~)tNjfg.'_oVf䐐ѢUЍ2hU*Xa.҈Թsu~ 8YaQSэ=q0&bF8J4I-y2˒o,&m ʠOf]\.X[ >zZ8_%Z a@St,A?X1j;>CbMʧC˚*$FN'瞧٨&^!7Ӝry?p[K8'˖>Ǎ%_/,aލAyqGH1)E\i)}R5JTS +VyMi'UZYMMBCzS;,R O ɮO9ոd Fx W%XXY(*;-]lfaeq6|*$CwA{h6x`+翻XF:Eq:@7' Hhۋys m-[Z|j=ϟ./N-aU~{(V=γפ@+'j7 Te鴟g:=ULiѕq4> ŧ $:&:3Zg.pet@q4|C=G0؂dK2Vgšu\CCPv#V4sՕ5v 'yB =M8Rzb| Wf..|骍R62}^Mbb2̠6395xn#PqZ"6 l^W ݺ[0=xO.j>.ue#V1c<#[+FYxjlk{uʘ&+0/˃zk\02!!{ӸƸǨР^7 prcn3IEXfo|^TMAc4l[u%}[!Gr=Y-3y$h|6qa$M1܅%'\XM DF_TIIksz\!Q9ʅ4=VhnXK^p# \J9q8A8e[w[n^ZsYѧWK@eOI&LKKb/sA|w.;oV Aɑɫ_Q-IX$Nt" 9lNW&!d>PYgR,G]d3t-uKw]O.uݛ}0Kw]tוﺥժXcxXoEͬ6mif4 U M:Xq*.M6?؉\Tjĉ^J*P8X!6GMk7Pj+k;HBo ZAD]+,XpT /jD&mDVKMvcp*CkF@+Js R֤h2pcWX9`N:FFVF+Gl I7VPtYu畐 ʀ;d#}H 3Sw!()d@l3h%K:LJKxa3azJxcgΈ.w%0{l4T})3Mԡ Nܦnql1/]OfRy5j$Ojwq2Z'_mkKr:vU'< ˰mMu; t #77S&2A0ZI"?Nm7vxU=a.Eo1|7%Z61?YУ=6 zw]]I+܈+2V4:ϴN%|<8ه}!¥Rq"N7E1\OF8MO%|^)PI!#w=2ó|rc6[#l]RBM2\ukmQWgLao/V_\eR,3 g\iCsN٦J+8Pɭ~C׾yOwG,Y`D?kw.Ϥ;Hoʭ r@;kwԾq5g('db>OLF:^zX6Nyc#:/Tu:|ax NX/.L^}ر<IXpXףmTJF/5êWkN Z7| }6;^r[yLވMfb5.u#:!h!eV*I=:keXTvTR<&{w4~НY‹d\߶wQ q]VxX_lSUν]u[ױ1pKAtԵD #i]vK4a Of@/% dM|2 O.FL' wwv+ =|m͖;?_#A%h3&G@|qii~xWȥMD1i#Ki_y&WNTgR={+{$/a%/yhm|*Ei-u1=a *O"?*LH7(7=T[foj<]C!` p.}eOVɀ`|:3ogVH8TqI߮'AޡS< ޛz<-""d.bX ΅L'#B{,p#Lt7qI&z:A&RLѤ rqt`vlZ2G^4ͿntFҰxRFS+Yk|5'F_Y2c<4m &gX#L!Gs';:FkbO`U*C{|X[*Qz@ FClC7^9`+Aik{]AN{I`fhOh+'0 hp (4 T ` lx-CS244a: An Introduction to Computer Networksowe Nick McKeowntroGC:\WINDOWS\Application Data\Microsoft\Templates\Blank Presentation.potYuval Shavittli29aMicrosoft PowerPointn D@.@SR@iG^;  '3&@ &&#TNPP2OMi & TNPP &&TNPP   @ --- !@---&9 4&rw@+ UwUw0- & 4& &L4& @BComic Sans MS X UwUw0- . 2 01.--3:-- @BComic Sans MS UwUw0- .32 rRScheduling Crossbar Switches      .--4:-- @BComic Sans MS [ UwUw0- .2 @Who do we chose   . .2 ]to traverse the   . .2 ]switch in the    . .2 ]next time slot?    .--;-- --!-- --!!-- ---- --!-- --!-- ---- &-3- $   $--&&#-3- $   $!--&&-3- $   $--&&>-3- $@@ $--&&>-3- $@@ $--&---- @Times New Roman UwUw0- . 2 N.----  . 2 N.&--$$$$$$$$$$    $      $   $$     --&&--$   ###$%$%((($*)*---$/./222$434777$989<<<$>=>AAA$CBCEFE$HGHJKJ$MLMOPO$QQQTUT$VVVYZY$[[[^_^$```cdc$eeehih$jjjmnm$ooorrr$tttwww$yyy| | |$ ~ ~ ~ $--&&--$$   $     $$     $$$$!!!$%$$'&'*+*$-,-000$222666$888;<;$>=>ABA$DCDGGG$IIIMMM$OOORSR$UTUXYX$[Z[^^^$```ddd$fffiji$lklopo$rqruuu$www{{{$}}}$--&&9b--$:::BBB$EDEMMM$POPXXX$[Z[```--&&?h--$@@@HHH$KJKSSS$VUV^^^$a`afff--&----  . 2 1 .----  . 2 1 .&>#-3- $@@ $!--&-- "System 0-&TNPP &՜.+,0     On-screen ShowStanford Universityق !Times New RomanComic Sans MS Wingdings Wingdings 3Blank PresentationMathType 4.0 EquationMicrosoft Equation 3.0Scheduling Crossbar Switches HistoryBasic Switch ModelSome definitionsFinding a maximum size match%Network flows and bipartite matchingNetwork Flows-A maximum network flow example By inspectionA maximum network flow example*Ford-Fulkerson method of augmenting pathsExample of Residual GraphExample of Residual Graph$Complexity of network flow problemsFinding a maximum size match%Network flows and bipartite matching;Network flows and bipartite matching Ford-Fulkerson method%Network flows and bipartite matching%Network flows and bipartite matching%Network flows and bipartite matching%Network flows and bipartite matching%Network flows and bipartite matching Complexity of Maximum MatchingsOutlineAnother algorithm (LPF)LPFProperties of LPF  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles%_cg Yuval ShavittYuval Shavitt  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ACDEFGHIJKLMNOPQSTUVWXY[\]^_`afRoot EntrydO)PicturesRCurrent UserZSummaryInformation(BPowerPoint Document(gDocumentSummaryInformation8R