Network Routing: Algorithms, Protocols, and Architectures

Front cover......Page 1
Network Routing: Algorithms, Protocols, and Architectures......Page 4
Copyright page......Page 5
Contents......Page 8
Foreword......Page 24
Preface......Page 26
About the Authors......Page 32
Part I: Network Routing: Basics and Foundations......Page 34
 Chapter 1. Networking and Network Routing: An Introduction......Page 35
  1.1 Addressing and Internet Service: An Overview......Page 37
  1.2 Network Routing: An Overview......Page 38
  1.3 IP Addressing......Page 40
  1.4 On Architectures......Page 44
  1.5 Service Architecture......Page 45
  1.6 Protocol Stack Architecture......Page 46
  1.7 Router Architecture......Page 52
  1.8 Network Topology Architecture......Page 53
  1.10 Public Switched Telephone Network......Page 54
  1.11 Communication Technologies......Page 55
  1.12 Standards Committees......Page 57
  1.13 Last Two Bits......Page 58
  1.14 Summary......Page 59
  Exercises......Page 60
 Chapter 2. Routing Algorithms: Shortest Path and Widest Path......Page 63
  2.1 Background......Page 64
  2.2 Bellman-Ford Algorithm and the Distance Vector Approach......Page 66
  2.3 Dijkstra's Algorithm......Page 71
  2.4 Comparison of the Bellman-Ford Algorithm and Dijkstra's Algorithm......Page 75
  2.5 Shortest Path Computation with Candidate Path Caching......Page 76
  2.6 Widest Path Computation with Candidate Path Caching......Page 78
  2.7 Widest Path Algorithm......Page 80
  2.8 k-Shortest Paths Algorithm......Page 82
  2.9 Summary......Page 84
  Exercises......Page 86
 Chapter 3. Routing Protocols: Framework and Principles......Page 89
  3.1 Routing Protocol, Routing Algorithm, and Routing Table......Page 90
  3.2 Routing Information Representation and Protocol Messages......Page 92
  3.3 Distance Vector Routing Protocol......Page 93
  3.4 Link State Routing Protocol......Page 115
  3.5 Path Vector Routing Protocol......Page 126
  3.6 Link Cost......Page 135
  3.7 Summary......Page 137
  Exercises......Page 138
 Chapter 4. Network Flow Modeling......Page 141
  4.1 Terminologies......Page 142
  4.2 Single-Commodity Network Flow......Page 143
  4.3 Multicommodity Network Flow: Three-Node Example......Page 151
  4.4 Multicommodity Network Flow Problem: General Formulation......Page 161
  4.5 Multicommodity Network Flow Problem: Nonsplittable Flow......Page 170
  Further Lookup......Page 171
  Exercises......Page 172
Part II: Routing in IP Networks......Page 174
 Chapter 5. IP Routing and Distance Vector Protocol Family......Page 175
  5.1 Routers, Networks, and Routing Information: Some Basics......Page 176
  5.2 Static Routes......Page 179
  5.3 Routing Information Protocol, Version 1 (RIPv1)......Page 180
  5.4 Routing Information Protocol, Version 2 (RIPv2)......Page 183
  5.5 Interior Gateway Routing Protocol (IGRP)......Page 186
  5.6 Enhanced Interior Gateway Routing Protocol (EIGRP)......Page 190
  5.7 Route Redistribution......Page 193
  5.8 Summary......Page 194
  Further Lookup......Page 196
  Exercises......Page 197
 Chapter 6. OSPF and Integrated IS-IS......Page 199
  6.1 From a Protocol Family to an Instance of a Protocol......Page 200
  6.2 OSPF: Protocol Features......Page 201
  6.3 OSPF Packet Format......Page 210
  6.4 Examples of Router LSAs and Network LSAs......Page 216
  6.5 Integrated IS-IS......Page 218
  6.6 Similarities and Differences Between IS-IS and OSPF......Page 222
  Exercises......Page 224
 Chapter 7. IP Traffic Engineering......Page 227
  7.1 Traffic, Stochasticity, Delay, and Utilization......Page 228
  7.2 Applications' View......Page 233
  7.3 Traffic Engineering: An Architectural Framework......Page 236
  7.4 Traffic Engineering: A Four-Node Illustration......Page 237
  7.5 Link Weight Determination Problem: Preliminary Discussion......Page 244
  7.6 Duality of the MCNF Problem......Page 246
  7.7 Illustration of Link Weight Determination Through Duality......Page 259
  7.8 Link Weight Determination: Large Networks......Page 265
  7.9 Summary......Page 267
  Exercises......Page 268
 Chapter 8. BGP......Page 271
  8.1 BGP: A Brief Overview......Page 272
  8.2 BGP: Basic Terminology......Page 275
  8.3 BGP Operations......Page 276
  8.4 BGP Configuration Initialization......Page 278
  8.5 Two Faces of BGP: External BGP and Internal BGP......Page 280
  8.6 Path Attributes......Page 283
  8.7 BGP Decision Process......Page 287
  8.8 Internal BGP Scalability......Page 290
  8.9 Route Flap Dampening......Page 295
  8.10 BGP Additional Features......Page 298
  8.11 Finite State Machine of a BGP Connection......Page 299
  8.12 Protocol Message Format......Page 303
  8.13 Summary......Page 310
  Exercises......Page 311
 Chapter 9. Internet Routing Architectures......Page 313
  9.1 Internet Routing Evolution......Page 314
  9.2 Addressing and Routing: Illustrations......Page 316
  9.3 Current Architectural View of the Internet......Page 323
  9.4 Allocation of IP Prefixes and AS Number......Page 334
  9.5 Policy-Based Routing......Page 337
  9.6 Point of Presence......Page 340
  9.7 Traffic Engineering Implications......Page 342
  9.8 Internet Routing Instability......Page 344
  Further Lookup......Page 345
  Exercises......Page 346
Part III: Routing in the PSTN......Page 348
 Chapter 10. Hierarchical and Dynamic Call Routing in the Telephone Network......Page 349
  10.1 Hierarchical Routing......Page 350
  10.2 The Road to Dynamic Routing......Page 355
  10.3 Dynamic Nonhierarchical Routing......Page 361
  10.4 Dynamically Controlled Routing......Page 363
  10.5 Dynamic Alternate Routing......Page 366
  10.6 Real-Time Network Routing......Page 367
  10.7 Classification of Dynamic Call Routing Schemes......Page 369
  10.8 Maximum Allowable Residual Capacity Routing......Page 370
  10.9 Dynamic Routing and Its Relation to Other Routing......Page 372
  10.10 Summary......Page 373
  Further Lookup......Page 374
  Exercises......Page 375
 Chapter 11. Traffic Engineering in the Voice Telephone Network......Page 377
  11.1 Why Traffic Engineering?......Page 378
  11.2 Traffic Load and Blocking......Page 379
  11.3 Grade-of-Service and Trunk Occupancy......Page 383
  11.4 Centi-Call Seconds and Determining Offered Load......Page 385
  11.5 Economic CCS Method......Page 387
  11.6 Network Controls for Traffic Engineering......Page 389
  11.7 State-Dependent Call Routing......Page 395
  11.8 Analysis of Dynamic Routing......Page 396
  Further Lookup......Page 404
  Exercises......Page 405
 Chapter 12. SS7: Signaling Network for Telephony......Page 407
  12.2 SS7 Network Topology......Page 408
  12.3 Routing in the SS7 Network......Page 411
  12.4 Point Codes: Addressing in SS7......Page 413
  12.5 Point Code Usage......Page 415
  12.6 SS7 Protocol Stack......Page 417
  12.7 SS7 Network Management......Page 421
  12.8 ISUP and Call Processing......Page 422
  12.10 ISUP Messages and Dynamic Call Routing......Page 429
  12.11 Transaction Services......Page 433
  12.12 SS7 Link Traffic Engineering......Page 435
  Further Lookup......Page 437
  Exercises......Page 438
 Chapter 13. Public Switched Telephone Network: Architecture and Routing......Page 439
  13.1 Global Telephone Addressing......Page 440
  13.2 Setting Up a Basic Telephone Call and Its Steps......Page 448
  13.5 Call Routing: Single National Provider Environment......Page 450
  13.6 Call Routing: Multiple Long-Distance Provider Case......Page 457
  13.7 Multiple-Provider Environment: Multiple Local Exchange Carriers......Page 465
  13.8 Routing Decision at an Intermediate TDM Switch......Page 466
  13.9 Number Portability......Page 467
  13.10 Nongeographic or Toll-Free Number Portability......Page 469
  13.11 Fixed/Mobile Number Portability......Page 472
  13.12 Multiple-Provider Environment with Local Number Portability......Page 484
  13.13 Summary......Page 486
  Exercises......Page 487
Part IV: Router Architectures......Page 490
 Chapter 14. Router Architectures......Page 491
  14.1 Functions of a Router......Page 492
  14.2 Types of Routers......Page 496
  14.3 Elements of a Router......Page 498
  14.4 Packet Flow......Page 501
  14.5 Packet Processing: Fast Path versus Slow Path......Page 503
  14.6 Router Architectures......Page 508
  Further Lookup......Page 518
  Exercises......Page 519
 Chapter 15. IP Address Lookup Algorithms......Page 521
  15.1 Impact of Addressing on Lookup......Page 522
  15.2 Longest Prefix Matching......Page 525
  15.4 Binary Tries......Page 528
  15.5 Multibit Tries......Page 533
  15.6 Compressing Multibit Tries......Page 540
  15.7 Search by Length Algorithms......Page 552
  15.8 Search by Value Approaches......Page 555
  15.9 Hardware Algorithms......Page 558
  15.10 Comparing Different Approaches......Page 563
  Further Lookup......Page 564
  Exercises......Page 565
 Chapter 16. IP Packet Filtering and Classification......Page 567
  16.1 Importance of Packet Classification......Page 568
  16.2 Packet Classification Problem......Page 570
  16.4 Naive Solutions......Page 573
  16.5 Two-Dimensional Solutions......Page 574
  16.6 Approaches for d Dimensions......Page 581
  16.7 Extending Two-Dimensional Solutions......Page 585
  16.8 Divide and Conquer Approaches......Page 588
  16.9 Tuple Space Approaches......Page 601
  16.10 Decision Tree Approaches......Page 604
  16.11 Hardware-Based Solutions......Page 609
  16.12 Lessons Learned......Page 611
  Further Lookup......Page 612
  Exercises......Page 613
Part V: Toward Next Generation Routing......Page 616
 Chapter 17. Quality of Service Routing......Page 617
  17.1 Background......Page 618
  17.2 QoS Attributes......Page 622
  17.3 Adapting Shortest Path and Widest Path Routing: A Basic Framework......Page 623
  17.4 Update Frequency, Information Inaccuracy, and Impact on Routing......Page 626
  17.5 Lessons from Dynamic Call Routing in the Telephone Network......Page 628
  17.6 Heterogeneous Service, Single-Link Case......Page 629
  17.7 A General Framework for Source-Based QoS Routing with Path Caching......Page 632
  17.8 Routing Protocols for QoS Routing......Page 641
  17.9 Summary......Page 643
  Exercises......Page 644
 Chapter 18. MPLS and GMPLS......Page 645
  18.1 Background......Page 646
  18.3 Multiprotocol Label Switching......Page 647
  18.4 Generalized MPLS......Page 659
  18.5 MPLS Virtual Private Networks......Page 667
  Further Lookup......Page 673
  Exercises......Page 674
 Chapter 19. Routing and Traffic Engineering with MPLS......Page 675
  19.1 Traffic Engineering of IP/MPLS Networks......Page 676
  19.2 VPN Traffic Engineering......Page 680
  19.3 Routing/Traffic Engineering for Voice Over MPLS......Page 691
  Exercises......Page 693
 Chapter 20. VoIP Routing: Interoperability Through IP and PSTN......Page 695
  20.1 Background......Page 696
  20.2 PSTN Call Routing Using the Internet......Page 697
  20.3 PSTN Call Routing: Managed IP Approach......Page 706
  20.4 IP-PSTN Interworking for VoIP......Page 708
  20.5 IP Multimedia Subsystem......Page 717
  20.6 Multiple Heterogeneous Providers Environment......Page 721
  20.7 All-IP Environment of VoIP Services......Page 723
  20.8 Addressing Revisited......Page 724
  20.9 Summary......Page 725
  Further Lookup......Page 726
  Exercises......Page 727
 Appendix A: Notations, Conventions, and Symbols......Page 729
  A.1 On Notations and Conventions......Page 730
  A.2 Symbols......Page 732
 Appendix B: Miscellaneous Topics......Page 733
  B.2 Fixed-Point Equation......Page 734
  B.3 Computational Complexity......Page 735
  B.5 Using CPLEX......Page 737
  B.6 Exponential Weighted Moving Average......Page 739
  B.7 Nonlinear Regression Fit......Page 740
  B.8 Computing Probability of Path Blocking or Loss......Page 741
  B.9 Four Factors in Packet Delay......Page 742
  B.10 Exponential Distribution and Poisson Process......Page 743
  B.11 Self-Similarity and Heavy-Tailed Distributions......Page 745
  B.12 Markov Chain and the Birth-and-Death Process......Page 746
  B.14 Packet Format: IPv4, IPv6, TCP, and UDP......Page 750
Solutions to Selected Exercises......Page 753
Bibliography......Page 757
Index......Page 801
Part VI: Advanced Topics (Bonus Material on CD-ROM)......Page 822
 Chapter 21. Switching Packets......Page 823
  21.1 Generic Switch Architecture......Page 824
  21.2 Requirements and Metrics......Page 825
  21.3 Shared Backplanes......Page 826
  21.5 Shared Memory......Page 828
  21.6 Crossbar......Page 831
  21.7 Head-of-Line Blocking......Page 836
  21.8 Output Queueing......Page 837
  21.9 Virtual Output Queueing......Page 840
  21.10 Input and Output Blocking......Page 853
  21.11 Scaling Switches to a Large Number of Ports......Page 854
  21.12 Clos Networks......Page 855
  21.13 Torus Networks......Page 860
  21.14 Scaling Switches for High-Speed Links......Page 864
  21.15 Conclusions......Page 867
  Further Lookup......Page 868
  Exercises......Page 869
 Chapter 22. Packet Queueing and Scheduling......Page 871
  22.1 Packet Scheduling......Page 872
  22.2 TCP Congestion Control......Page 880
  22.3 Implicit Feedback Schemes......Page 884
  22.4 Random Early Detection (RED)......Page 887
  22.5 Variations of RED......Page 891
  22.6 Explicit Feedback Schemes......Page 895
  22.7 New Class of Algorithms......Page 898
  22.8 Analyzing System Behavior......Page 899
  Further Lookup......Page 900
  Exercises......Page 901
 Chapter 23. Traffic Conditioning......Page 902
  23.1 Service Level Agreements......Page 903
  23.2 Differentiated Services......Page 904
  23.3 Traffic Conditioning Mechanisms......Page 905
  23.4 Traffic Shaping......Page 906
  23.5 Traffic Policing......Page 912
  23.6 Packet Marking......Page 915
  Further Lookup......Page 919
  Exercises......Page 920
 Chapter 24. Transport Network Routing......Page 921
  24.1 Why Transport Network/Service......Page 922
  24.2 Timing of Request and Transport Service Provisioning......Page 924
  24.3 Multi-Time Period Transport Network Routing Design......Page 926
  24.4 Transport Routing with Varied Protection Levels......Page 933
  24.5 Solution Approaches......Page 935
  Exercises......Page 936
 Chapter 25. Optical Network Routing and Multilayer Routing......Page 937
  25.1 SONET/SDH Routing......Page 938
  25.2 WDM Routing......Page 944
  25.3 Multilayer Networking......Page 948
  25.4 Overlay Networks and Overlay Routing......Page 954
  25.5 Summary......Page 955
  Further Lookup......Page 956
  Exercises......Page 957