DOC PREVIEW
MIT 6 042J - Problems for Recitation 10

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.042/18.062J Mathematics for Computer Science October 13, 2010 Tom Leighton and Marten van Dijk Problems for Recitation 10 Analysis of Two Networks Two communication networks are shown below. Complete the table of properties and be prepared to justify your answers. IN0IN1IN2IN3IN4OUT0OUT1OUT2OUT3OUT4IN ININ INOUT OUTOUTOUT0 122330 15-Path 4-Cycle network # switches switch size diameter max congestion 5-path 4-cycle Recall that the diameter of a communication network is the number of edges on the shortest path between the input and output that are farthest apart. The max congestion of a network is the largest number of packets that pass through any switch in the best solution to the hardest permutation routing problem. You might imagine that your enemy picks a permutation and then you pick the path taken by each packet. (Her goal is to cause congestion, and yours is to eliminate it.) Assuming you both do your best, the max congestion is then equal to the largest number of packets passing through a single switch.2 Recitation 10 Routing in a Bene˘s Network In lecture, we saw that the Bene˘s network has a max congestion of 1; that is, every permu-tation can be routed in such a way that a single packet passes through each switch. Let’s work through an example. A Bene˘s network of size N = 8 is attached. 1. Within the Bene˘s network of size N = 8, there are two subnetworks of size N = 4. Put boxes around these. Hereafter, we’ll refer to these as the upper and lower subnetworks. 2. Now consider the following permutation routing problem: π(0) = 3 π(4) = 2 π(1) = 1 π(5) = 0 π(2) = 6 π(6) = 7 π(3) = 5 π(7) = 4 Each packet must be routed through either the upper subnetwork or the lower subnet-work. Construct a graph with vertices 0, 1, . . . , 7 and draw a dashed edge between each pair of packets that can not go through the same subnetwork because a collision would occur in the second column of switches. 3. Add a solid edge in your graph between each pair of packets that can not go through the same subnetwork because a collision would occur in the next-to-last column of switches. 4. Color (i.e., label) the vertices of your graph red and blue so that adjacent vertices get different colors. Why must this be possible, regardless of the permutation π? 5. Suppose that red vertices correspond to packets routed through the upper subnetwork and blue vertices correspond to packets routed through the lower subnetwork. On the attached copy of the Bene˘s network, highlight the first and last edge traversed by each packet. 6. All that remains is to route packets through the upper and lower subnetworks. One way to do this is by applying the procedure described above recursively on each subnetwork. However, since the remaining problems are small, see if you can complete all the paths on your own.3 Recitation 10 OUTOUTOUTOUTOUTOUT01OUT32OUT4567ININININININININ01234567MIT OpenCourseWarehttp://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Fall 2010 For information about citing these materials or our Terms of Use, visit:


View Full Document

MIT 6 042J - Problems for Recitation 10

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Problems for Recitation 10
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problems for Recitation 10 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problems for Recitation 10 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?