Mathematics for Computer Science
10 Communication Networks Modeling communication networks is an important application of digraphs in com- puter science. In this ...
Chapter 10 Communication Networks374 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 assumeNis a power of two. Which input is suppos ...
10.4. Switch Count 375 path between an input and an output. For example, in the complete binary tree above, the distance from in ...
Chapter 10 Communication Networks376 10.5 Network Latency We’ll sometimes be choosing routings through a network that optimize s ...
10.7. 2-D Array 377 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 switch (and the two ...
Chapter 10 Communication Networks378 in 0 in 1 in 2 in 3 out 0 out 1 out 2 out 3 ...
10.8. Butterfly 379 Proof. First, we show that the congestion is at most 2. Letbe any permutation. Define a solution,P, forto ...
Chapter 10 Communication Networks380 2 inputs 2 outputs À À ND 2 1 Figure 10.1 F 1 , the Butterfly Net switches withND 21. iD1;: ...
10.9. Beneˇs Network 381 ⎧ ⎨ F ⎨ ⎩ 2 n Fn ⎩ 2 n1 tt ⎧ ⎨ F 2 n+^1 outputs ⎨ ⎩ 2 n Fn F newinputs ⎩ Fn+1 Figure 10.2 FnC 1 , the B ...
Chapter 10 Communication Networks382 Bn Bn BnC 1 2 n 2 n 2 nC^1 À À new inputs new outputs Figure 10.3 BnC 1 , the Beneˇs Net sw ...
10.9. Beneˇs Network 383 a clever induction argument that we’ll come to in a moment. Let’s first see how the Benes network stack ...
Chapter 10 Communication Networks384 in 1 out 1 in 0 out 0 in 2 out 2 in 3 out 3 in 4 out 4 in 5 out 5 in 6 out 6 in 7 out 7 Fig ...
10.9. Beneˇs Network 385 1 5 0 4 2 6 7 3 Notice that at most one new edge is incident to each vertex. The two lines drawn betwee ...
Chapter 10 Communication Networks386 blue blue blue blue red red red red 1 5 0 4 2 6 7 3 The solution to this graph-coloring pro ...
10.9. Beneˇs Network 387 in 0 in 1 in 2 out 0 out 1 out 2 (b)Give an input/output permutation, 0 , that forces maximum congesti ...
Chapter 10 Communication Networks388 through the same subnetwork because a collision would occur in the next-to-last column of s ...
10.9. Beneˇs Network 389 in 0 in 1 in 2 in 3 out 0 out 1 out 2 out 3 first layer to the corresponding switch in the second layer ...
Chapter 10 Communication Networks390 in 0 in 2 in 4 out 0 out 1 out 2 out 3 out 4 in 1 in 3 Figure 10.5 5-Path new, better commu ...
10.9. Beneˇs Network 391 Homework Problems Problem 10.7. Louis Reasoner figures that, wonderful as the Beneˇs network may be, th ...
...
«
15
16
17
18
19
20
21
22
23
24
»
Free download pdf