CS/ECE 438: Communication Networks Fall 2007Problem Set 3 Due Wednesday, Oct 17NOTE: There will be no automatic extension for this assignment. If you do not hand in the assignmentby the start of class on Oct 17, you will get no credit for the assignment.1. Learning SwitchesRefer to Figure 1 for this question. The octagons with numbers denote learning switches, with p ortslabeled by small numbers, and letters denote hosts (attached to LAN segments).(a) Suppose switching tables for all switches are initially empty, and then the following two transmis-sion occur: A → G, D → A. The following transmission is I → D. Which hosts hear the thirdtransmission?(b) Show the switching table at switch 1 after the three transmissions.124567ABCDEFGHI1233Figure 1: Diagram for Problem 1.12. Virtual CircuitsFigure 2 shows hosts (A–N) connected by virtual circuit routers (1–6). Assume that each VC mayhave a different VCID on each link, and VCIDs are assigned starting at 0 and using the next availableID. Suppose that there are virtual circuits established between: F → I, M → A, C → N , F → B,E → B, in that order.(a) Show the forwarding table at router number 3.(b) Suppose there is an additional virtual circuit formed from D to J . Show the virtual circuit IDsthat a packet will use traveling along that virtual circuit.25 631 4ABCDEFGH IJKLM N12 4123431234123412 431234Figure 2: Diagram for Problem 2.23. (a) Refering to Figure 3, compute the least-cost paths from router A to all the other routers usingDijkstra’s algorithm. Use a table similar to Table 4.9 on p.282 of the textbook to record yourwork (p. 287 of 3rd ed.). You do not need to show the “Comments” column of the table.(b) Now suppose the routers are running a synchronous version of a distance vector algorithm. Everyminute, at exactly the same time, each router sends its current distance vector to its neighbors.Then it updates its own vector based on what it receives, and sends out the updated vector thenext minute.Starting all routers in an initial state where they only know the cost of reaching their neighbors,(i.e.the distance to all other routers is infinity), show the updated distance vector tables at each routerafter the first update.(c) How many minutes will it take for all routers to reach a stable state? (Hint: you do not need tocompute the DV algorithm to answer this question.)ABCD EF GHI8547248359221046Figure 3: Diagram for Problem
View Full Document
Unlocking...