CS 118 Spring 2011 : Homework 6Figure 1: Network with edge weightsStep N’ D(A),p(A) D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(G),p(G) D(H),p(H)0 F ∞ ∞ ∞ 3,F 1,F 6,F ∞1 FE ∞ ∞ 4,E 2,E 6,F ∞2 FED ∞ 11,D 3,D 3,D ∞3 FEDC 7,C 5,C 3,D ∞4 FEDCG 7,C 5,C 17,G5 FEDCGB 6,B 7,B6 FEDCGBA 7,BTable 1: Solution tableProblem 1In this problem we’ll explore the impact of NATs on P2P applications. Suppose a peer with username Alicediscovers through querying that a peer with username Bob has a file it wants to download. Also supposethat Bob and Alice are both behind a NAT. Is it possible to devise a technique that will allow Alice toestablish a TCP connection with Bob without application-specific NAT configuration? Why or why not?It is not possible to devise such a technique. In order to establish a direct TCP connection between Aliceand Bob, either Alice or Bob must initiate a connection to the other. But the NATs covering Alice and Bobdrop SYN packets arriving from the WAN side. Thus neither Alice nor Bob can initiate a TCP connectionto the other if they are both behind NATs.Problem 2If you have a network that looks like Figure 1 and you use the link weights shown, use Dijkstra’s shortest-path algorithm to compute the shortest path from F to all network nodes. Show how the algorithm worksby computing a table like Table 4.3 (4th:page 373, 5th: page 379) in your book.See Table 1.Problem 3Using the network in Figure 2, x has only 2 attached neighbors, w and y. w has a minimum-cost path todestination u (not shown) of 5, and y has a minimum-cost path to u of 6. The complete paths from w andProblem 3 continued on next page. . . Page 1 of 2CS 118 Spring 2011 : Homework 6Figure 2: Fragment of network.y to u (and between w and y) are not shown. All link costs in the network have strictly positive integervalues.a. Find x’s distance vector for destinations w, y, and u.b. Find a case of link-cost change (if any) for either c(x, w) or c(x, y) such that x will inform its neighborsof a new minimum-cost path to u as a result of executing the distance vector algorithm.c. Find a case of link-cost change (if any) for either c(x, w) or c(x, y) such that x will not inform itsneighbors of a new minimum-cost path to u as a result of executing the distance vector algorithm.a. Dx(y) = 4, Dx(w) = 1, Dx(u) = 6b. First consider what happens if c(x,y) changes. If c(x,y) becomes larger or smaller (as long as c(x,y) >0), the least cost path from x to u will still have cost 6 and pass through w. Thus a change in c(x, y)will not cause x to inform its neighbors of any changes. Now consider if c(x,w) changes. If c(x,w) = ≤ 1, then the least-cost path to u continues to pass through w and its cost changes to 5 + ; x willinform its neighbors of this new cost. If c(x,y) = δ > 5, then the least cost path now passes through yand has cost 10; again x will inform its neighbors of this new cost.c. Any change in link cost c(x,y) will not cause x to inform its neighbors of a new minimum-cost path tou.Page 2 of
View Full Document
Unlocking...