計算機網(wǎng)絡第四章作業(yè)

1、第四章P450-22: Consider the fol lowing network With the indicated link costs, use Di jkstra s shortest-path algorithm to compute the shortest path from x to all network nodes Show hov/ the algor ithm works by computing a tabIeAnswerProb Iem 22StepND (s), p (s)D(t)fp(t)D(u),p( u)D(v),p( v)D(w),p( w)D(y)

2、,p(y )D(z),p(z)0X8OOOO& X6, x6, xOO1xw8OO14, w& X6, xOO2xwyOO15, y14, w7,y3xwyvOO11,v10, v4xwyvu14, u11,vl&y5xwyvut12,t16, t6xwyvuts16, t7xwyvutszRouting Table:DESCOSTNEST HOPX0y6yw6wV7yt11yu10yz16ys12yP451-25: Con sider the net work f ragme nt shown below xhas only two att ached neighbors, w and y.

3、 w has a minimum-cos t path to des tin at i on u of 5, and y has a mini mum-cos t path to u of 6. The comp I e te paths from w and y to tz (and bet wee n w and y) are not shown Al I Iink costs in the network have str ictly positive integer valuesa. Give x* s distance vector for destinations wf y, an

4、d u.b. Gi ve a I ink-cost change for either c(xfw) or c(x, y) such that x wi I I inform i ts neighbors of a new minimum-cost path to as a resuIt of executing the distance-vector algor ithm.c. Gi ve a I i nk-cost change for e i ther c(xfw) or c (x, y) such that “will not i nforin its neighbors of a n

5、ew minimum-cost path to “ as a resuIt of executing the distance-vector algor ithm.AnswerProb Iem 25a. Dx(y) = 5, Dx (w) = 2, Dx(u) = 7b. Fi rst consider what happens if c(x, y) changes If c(x, y) becomesI arger or sma I I er (as long as c (x, y) 0), the leas t cost path from x to u wi I I still have

6、 cos t at I eas t 7. Thus a change in c (x, y) wi I I not cause x to inform its neighbors of any changes Now consider if c (x, w) changesI f c (x, w) =1, then the least-cost path to u cont inues to pass throughw and its cost changes to 5 + ; x wiI I inform its neighbors of this new cost If c(x,w)二 6, then the least cost path now passes through y and has cost 11 ; again x wi I I inform its neighbors of this new costc. Any change