Network Routing (eBook)

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