Contents i 5.2.3 Shortest Path Algorithms,315 The Bellman-Ford Algorithm,318 Dijkstra's Algorithm,322 The Floyd-Warshall Algorithm,323 5.2.4 Distributed Asynchronous Bellman-Ford Algorithm,325 5.2.5 Adaptive Routing Based on Shortest Paths,333 Stability Issues in Datagram Networks,333 Stability Issues in Virtual Circuit Networks,336 5.3 Broadcasting Routing Information-Coping with Link Failures,340 5.3.1 Flooding-The ARPANET Algorithm,343 5.3.2 Flooding without Periodic Updates,345 5.3.3 Topology Broadcast without Sequence Numbers,347 5.4 Flow Models,Optimal Routing,and Topological Design,355 5.4.1 An Overview of Topological Design Problems,360 5.4.2 The Subnet Design Problem,362 Capacity Assignment Problem,362 Heuristic Methods for Capacity Assignment,364 Network Reliability Issues,367 Spanning Tree Topology Design,370 5.4.3 The Local Access Network Design Problem,371 5.5 Characterization of Optimal Routing,374 5.6 Feasible Direction Methods for Optimal Routing,382 5.6.1 The Frank-Wolfe (Flow Deviation)Method,385 5.7 Projection Methods for Optimal Routing,392 Unconstrained Nonlinear Optimization,392 Nonlinear Optimization Over the Positive Orthant,394 Application to Optimal Routing,396 5.8 Routing in the Codex Network,403 5.9 Summary,405 5.10 Notes,Sources,and Suggested Reading,406 PROBLEMS,407Contents xi 5.2.3 Shortest Path Algorithms, 315 The Bellman-Ford Algorithm, 318 Dijkstra's Algorithm, 322 The Floyd-Warshall Algorithm, 323 5.2.4 Distributed Asynchronous Bellman-Ford Algorithm, 325 5.2.5 Adaptive Routing Based on Shortest Paths, 333 Stability Issues in Datagram Networks, 333 Stability Issues in Virtual Circuit Networks, 336 5.3 Broadcasting Routing Information--Coping with Link Failures, 340 5.3.1 Flooding-The ARPANET Algorithm, 343 5.3.2 Flooding without Periodic Updates, 345 5.3.3 Topology Broadcast without Sequence Numbers, 347 5.4 Flow Models, Optimal Routing, and Topological Design, 355 5.4.1 An Overview of Topological Design Problems, 360 5.4.2 The Subnet Design Problem, 362 Capacity Assignment Problem, 362 Heuristic Methods for Capacity Assignment, 364 Network Reliability Issues, 367 Spanning Tree Topology Design, 370 5.4.3 The Local Access Network Design Problem, 371 5.5 Characterization of Optimal Routing, 374 5.6 Feasible Direction Methods for Optimal Routing, 382 5.6.1 The Frank-Wolfe (Flow Deviation) Method, 385 5.7 Projection Methods for Optimal Routing, 392 Unconstrained Nonlinear Optimization, 392 Nonlinear Optimization Over the Positive Orthant, 394 Application to Optimal Routing, 396 5.8 Routing in the Codex Network, 403 5.9 Summary, 405 5.10 Notes, Sources, and Suggested Reading, 406 PROBLEMS, 407