Network Routing, 2nd Edition

Network Routing, 2nd Edition

by Deep Medhi, Karthik Ramasamy
Released September 2017
Publisher(s): Morgan Kaufmann
ISBN: 9780128008294

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Network Routing: Algorithms, Protocols, and Architectures, Second Edition, explores network routing and how it can be broadly categorized into Internet routing, circuit-switched routing, and telecommunication transport network routing.

The book systematically considers these routing paradigms, as well as their interoperability, discussing how algorithms, protocols, analysis, and operational deployment impact these approaches and addressing both macro-state and micro-state in routing.

Readers will learn about the evolution of network routing, the role of IP and E.164 addressing and traffic engineering in routing, the impact on router and switching architectures and their design, deployment of network routing protocols, and lessons learned from implementation and operational experience. Numerous real-world examples bring the material alive.

  • Extensive coverage of routing in the Internet, from protocols (such as OSPF, BGP), to traffic engineering, to security issues
  • A detailed coverage of various router and switch architectures, IP lookup and packet classification methods
  • A comprehensive treatment of circuit-switched routing and optical network routing
  • New topics such as software-defined networks, data center networks, multicast routing
  • Bridges the gap between theory and practice in routing, including the fine points of implementation and operational experience
  • Accessible to a wide audience due to its vendor-neutral approach

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright
  5. Dedication
  6. Foreword (1st Edition)
  7. Preface (2nd Edition)
    1. Acknowledgments
  8. Preface (1st Edition)
    1. Audience
    2. Organization and Approach
    3. Bonus Materials and Online Resources
    4. Acknowledgments
    5. References
  9. About the Authors
  10. Part 1: Routing: Basics and Foundations
    1. Chapter 1: Networking and Network Routing: An Introduction
      1. Abstract
      2. 1.1. Addressing and Internet Service: An Overview
      3. 1.2. Network Routing: An Overview
      4. 1.3. IPv4 Addressing
      5. 1.4. IPv6 Addressing
      6. 1.5. On Architectures
      7. 1.6. Service Architecture
      8. 1.7. Protocol Stack Architecture
      9. 1.8. Router Architecture
      10. 1.9. Network Topology Architecture
      11. 1.10. Network Management Architecture
      12. 1.11. Global Telephone Network
      13. 1.12. Communication Technologies
      14. 1.13. Standards Committees
      15. 1.14. Last Two Bits
      16. 1.15. Summary
      17. Further Lookup
      18. Exercises
      19. References
    2. Chapter 2: Routing Algorithms: Shortest Path, Widest Path, and Spanning Tree
      1. Abstract
      2. 2.1. Background
      3. 2.2. Bellman–Ford Algorithm and the Distance Vector Approach
      4. 2.3. Dijkstra's Algorithm
      5. 2.4. Comparison of the Bellman–Ford Algorithm and Dijkstra's Algorithm
      6. 2.5. Shortest Path Computation with Candidate Path Caching
      7. 2.6. Widest Path Computation with Candidate Path Caching
      8. 2.7. Widest Path Algorithm
      9. 2.8. Shortest Widest Path and Widest Shortest Path
      10. 2.9. Tree, Spanning Tree, and Steiner Tree Algorithms
      11. 2.10. k-Shortest Paths Algorithm
      12. 2.11. Summary
      13. Further Lookup
      14. Exercises
      15. References
    3. Chapter 3: Routing Protocols: Framework and Principles
      1. Abstract
      2. 3.1. Routing Protocol, Routing Algorithm, and Routing Table
      3. 3.2. Routing Information Representation and Protocol Messages
      4. 3.3. Distance Vector Routing Protocol
      5. 3.4. Link State Routing Protocol
      6. 3.5. Path Vector Routing Protocol
      7. 3.6. Link Cost
      8. 3.7. Threats to Routing Protocols
      9. 3.8. Summary
      10. Further Lookup
      11. Exercises
      12. References
    4. Chapter 4: Network Flow Models
      1. Abstract
      2. 4.1. Terminologies
      3. 4.2. Single-Commodity Network Flow
      4. 4.3. Multicommodity Network Flow: Three-Node Example
      5. 4.4. Multicommodity Network Flow: General Link-Path Formulation
      6. 4.5. Multicommodity Network Flow Problem: Non-Splittable Flow
      7. 4.6. Node-Link Formulation
      8. 4.7. Generating Traffic Matrix
      9. 4.8. Summary
      10. Further Lookup
      11. Exercises
      12. References
  11. Part 2: Internet Routing
    1. Chapter 5: IP Routing and Distance Vector Protocol Family
      1. Abstract
      2. 5.1. Routers, Networks, and Routing Information: Some Basics
      3. 5.2. Static Routes
      4. 5.3. Routing Information Protocol, Version 1 (RIPv1)
      5. 5.4. Routing Information Protocol, Version 2 (RIPv2)
      6. 5.5. Interior Gateway Routing Protocol (IGRP)
      7. 5.6. Enhanced Interior Gateway Routing Protocol (EIGRP)
      8. 5.7. Route Redistribution
      9. 5.8. Summary
      10. Further Lookup
      11. Exercises
      12. References
    2. Chapter 6: OSPF and Integrated IS–IS
      1. Abstract
      2. 6.1. From a Protocol Family to an Instance of a Protocol
      3. 6.2. OSPF: Protocol Features
      4. 6.3. Multitopology Routing in OSPF
      5. 6.4. OSPF Packet Format
      6. 6.5. Examples of Router LSA and Network LSA
      7. 6.6. Integrated IS–IS
      8. 6.7. Similarities and Differences Between IS–IS and OSPF
      9. 6.8. OSPFv3 and IS–IS for IPv6
      10. 6.9. Additional Extensions to OSPF and IS–IS
      11. 6.10. Summary
      12. Further Lookup
      13. Exercises
      14. References
    3. Chapter 7: IP Traffic Engineering
      1. Abstract
      2. 7.1. Traffic, Stochasticity, Delay, and Utilization
      3. 7.2. Applications' View
      4. 7.3. Traffic Engineering: An Architectural Framework
      5. 7.4. Traffic Engineering: A Four-Node Illustration
      6. 7.5. IGP Metric (Link Weight) Determination Problem for the Load Balancing Objective: Preliminary Discussion
      7. 7.6. Determining IGP Link Weights via duality of MCNF Problems
      8. 7.7. Illustration of Link Weight Determination through Duality
      9. 7.8. Link Weight Determination: Large Networks
      10. 7.9. IP Traffic Engineering of PoP-to-DataCenter Networks
      11. 7.10. Summary
      12. Further Lookup
      13. Exercises
      14. References
    4. Chapter 8: Multicast Routing
      1. Abstract
      2. 8.1. Multicast IP Addressing
      3. 8.2. Internet Group Management Protocol (IGMP)
      4. 8.3. Multicast Listener Discovery Protocol (MLD)
      5. 8.4. Reverse Path Forwarding (RPF)
      6. 8.5. Distance Vector Multicast Routing Protocol (DVMRP)
      7. 8.6. Multicast OSPF
      8. 8.7. Core Based Trees
      9. 8.8. Protocol Independent Multicast (PIM)
      10. 8.9. Inter-Domain Multicast Routing
      11. 8.10. Internet Protocol Television (IPTV) Multicasting
      12. 8.11. Summary
      13. Further Lookup
      14. Exercises
      15. References
    5. Chapter 9: BGP
      1. Abstract
      2. 9.1. BGP: A Brief Overview
      3. 9.2. BGP: Basic Terminology
      4. 9.3. BGP Operations
      5. 9.4. BGP Configuration Initialization
      6. 9.5. Two Faces of BGP: External BGP (eBGP) and Internal BGP (iBGP)
      7. 9.6. Path Attributes
      8. 9.7. BGP Decision Process
      9. 9.8. Internal BGP Scalability
      10. 9.9. Route Flap Damping
      11. 9.10. BGP Additional Features and Extensions
      12. 9.11. BGP Vulnerabilities
      13. 9.12. Securing BGP
      14. 9.13. Finite State Machine of A BGP Connection
      15. 9.14. BGP4 Protocol Message Format
      16. 9.15. Summary
      17. Further Lookup
      18. Exercises
      19. References
    6. Chapter 10: Routing in the Global Internet
      1. Abstract
      2. 10.1. Internet Routing Evolution
      3. 10.2. Addressing and Routing: Illustrations
      4. 10.3. Allocation of IP Prefixes and AS Numbers
      5. 10.4. Current Architectural View of the Internet
      6. 10.5. Traffic Engineering Implications
      7. 10.6. Point of Presence (PoP) for Large ISPs
      8. 10.7. Policy-Based Routing
      9. 10.8. IP Prefix Hijacking
      10. 10.9. Detecting and Preventing IP Prefix Hijacking
      11. 10.10. Internet Routing Instability
      12. 10.11. Size and Growth of the Internet Routing Architecture
      13. 10.12. Addressing the Growth: Locator/ID Separation Protocol (LISP)
      14. 10.13. Summary
      15. Further Lookup
      16. Exercises
      17. References
    7. Chapter 11: Routing and Traffic Engineering in Software Defined Networks
      1. Abstract
      2. 11.1. Software Defined Networks: An Overview
      3. 11.2. OpenFlow
      4. 11.3. Routing Decisions
      5. 11.4. Traffic Engineering for Aggregated Flow Routing
      6. 11.5. Flow Management Approaches
      7. 11.6. Summary
      8. Further Lookup
      9. Exercises
      10. References
    8. Chapter 12: Routing and Traffic Engineering in Data Center Networks
      1. Abstract
      2. 12.1. Cloud Services and Data Center Applications
      3. 12.2. Data Center Network: A Simple Illustration
      4. 12.3. Data Center Network: Routing/Forwarding Requirements
      5. 12.4. Fat-Tree Data Center Topology
      6. 12.5. PortLand Approach for the Fat-Tree Topology
      7. 12.6. Multipath Routing and Traffic Engineering for Fat-Tree Topology
      8. 12.7. BCube
      9. 12.8. Multipath Routing and Traffic Engineering for BCube Architecture
      10. 12.9. Border Gateway Protocol (BGP) in Ultra Large Data Center Networks
      11. 12.10. Software-Defined Networking for Data Center Networks
      12. 12.11. Convergence Time and Performance
      13. 12.12. Summary
      14. Further Lookup
      15. Exercises
      16. References
  12. Part 3: Router Architecture & Design
    1. Chapter 13: Router Architectures
      1. Abstract
      2. 13.1. Functions of a Router
      3. 13.2. Types of Routers
      4. 13.3. Elements of a Router
      5. 13.4. Packet Flow
      6. 13.5. Packet Processing: Fast Path Versus Slow Path
      7. 13.6. Router Architectures
      8. 13.7. Summary
      9. Further Lookup
      10. Exercises
      11. References
    2. Chapter 14: IP Address Lookup Algorithms
      1. Abstract
      2. 14.1. Impact of Addressing on Lookup
      3. 14.2. Longest Prefix Matching
      4. 14.3. Naïve Algorithms
      5. 14.4. Binary Tries
      6. 14.5. Multibit Tries
      7. 14.6. Compressing Multibit Tries
      8. 14.7. Search by Length Algorithms
      9. 14.8. Search by Value Approaches
      10. 14.9. Hardware Algorithms
      11. 14.10. Comparing Different Approaches
      12. 14.11. Summary
      13. Further Lookup
      14. Exercises
      15. References
    3. Chapter 15: IP Packet Filtering and Classification
      1. Abstract
      2. 15.1. Importance of Packet Classification
      3. 15.2. Packet Classification Problem
      4. 15.3. Packet Classification Algorithms
      5. 15.4. Naïve Solutions
      6. 15.5. Two-Dimensional Solutions
      7. 15.6. Approaches for d Dimensions
      8. 15.7. Extending Two-Dimensional Solutions
      9. 15.8. Divide and Conquer Approaches
      10. 15.9. Tuple Space Approaches
      11. 15.10. Decision Tree Approaches
      12. 15.11. Hardware-Based Solutions
      13. 15.12. Lessons Learned
      14. 15.13. Summary
      15. Further Lookup
      16. Exercises
      17. References
    4. Chapter 16: Switch Fabric
      1. Abstract
      2. 16.1. Generic Switch Architecture
      3. 16.2. Requirements and Metrics
      4. 16.3. Shared Backplane
      5. 16.4. Switched Backplane
      6. 16.5. Shared Memory
      7. 16.6. Crossbar
      8. 16.7. Head-of-Line (HOL) Blocking
      9. 16.8. Output Queueing
      10. 16.9. Virtual Output Queueing
      11. 16.10. Input and Output Blocking
      12. 16.11. Scaling Switches to a Large Number of Ports
      13. 16.12. Clos Networks
      14. 16.13. Torus Networks
      15. 16.14. Scaling Switches for High-Speed Links
      16. 16.15. Conclusions
      17. 16.16. Summary
      18. Further Lookup
      19. Exercises
      20. References
    5. Chapter 17: Packet Queueing and Scheduling
      1. Abstract
      2. 17.1. Packet Scheduling
      3. 17.2. TCP Congestion Control
      4. 17.3. Implicit Feedback Schemes
      5. 17.4. Random Early Detection (RED)
      6. 17.5. Variations of RED
      7. 17.6. Explicit Feedback Schemes
      8. 17.7. New Class of Algorithms
      9. 17.8. Analyzing System Behavior
      10. 17.9. Summary
      11. Further Lookup
      12. Exercises
      13. References
    6. Chapter 18: Traffic Conditioning
      1. Abstract
      2. 18.1. Service Level Agreements
      3. 18.2. Differentiated Services
      4. 18.3. Traffic Conditioning Mechanisms
      5. 18.4. Traffic Shaping
      6. 18.5. Traffic Policing
      7. 18.6. Packet Marking
      8. 18.7. Summary
      9. Further Lookup
      10. Exercises
      11. References
  13. Part 4: Routing in Reservation-Oriented Networks
    1. Chapter 19: Circuit-Switching: Hierarchical and Dynamic Call Routing
      1. Abstract
      2. 19.1. Circuit Switching
      3. 19.2. Hierarchical Call Routing
      4. 19.3. The Road to Dynamic Routing
      5. 19.4. Dynamic Non-Hierarchical Routing (DNHR)
      6. 19.5. Dynamically Controlled Routing (DCR)
      7. 19.6. Dynamic Alternate Routing (DAR)
      8. 19.7. Real-Time Network Routing (RTNR)
      9. 19.8. Classification of Dynamic Call Routing Schemes
      10. 19.9. Maximum Allowable Residual Capacity Routing
      11. 19.10. Dynamic Routing and Its Relation to Other Routing
      12. 19.11. Summary
      13. Further Lookup
      14. Exercises
      15. References
    2. Chapter 20: Traffic Engineering for Circuit-Switched Networks
      1. Abstract
      2. 20.1. Why Traffic Engineering
      3. 20.2. Traffic Load and Blocking
      4. 20.3. Grade-of-Service (GoS)
      5. 20.4. Centi-Call Seconds (CCS) and Determining Offered Load
      6. 20.5. Economic CCS (ECCS) Method
      7. 20.6. Network Controls for Traffic Engineering
      8. 20.7. State-Dependent Call Routing
      9. 20.8. Analysis of Dynamic Routing
      10. 20.9. Performance for Heterogeneous Services
      11. 20.10. Summary
      12. Further Lookup
      13. Exercises
      14. References
    3. Chapter 21: Quality of Service Routing
      1. Abstract
      2. 21.1. Background
      3. 21.2. QoS Attributes
      4. 21.3. Adapting Shortest Path and Widest Path Routing: A Basic Framework
      5. 21.4. Update Frequency, Information Inaccuracy, and Impact on Routing
      6. 21.5. Lessons from Dynamic Call Routing in the Telephone Network
      7. 21.6. A General Framework for Source-Based QoS Routing with Path Caching
      8. 21.7. Routing Protocols for QoS Routing
      9. 21.8. Summary
      10. Further Lookup
      11. Exercises
      12. References
    4. Chapter 22: MultiProtocol Label Switching (MPLS)
      1. Abstract
      2. 22.1. Background
      3. 22.2. Traffic Engineering Extension to Routing Protocols
      4. 22.3. Multiprotocol Label Switching (MPLS)
      5. 22.4. Generalized MPLS (GMPLS)
      6. 22.5. MPLS Virtual Private Networks
      7. 22.6. Multicast VPN with MPLS
      8. 22.7. Summary
      9. Further Lookup
      10. Exercises
      11. References
    5. Chapter 23: Routing and Traffic Engineering using MPLS
      1. Abstract
      2. 23.1. Traffic Engineering of IP/MPLS Networks
      3. 23.2. VPN Traffic Engineering
      4. 23.3. Multicast VPN Traffic Engineering
      5. 23.4. Routing/Traffic Engineering for Voice over MPLS
      6. 23.5. Summary
      7. Further Lookup
      8. Exercises
      9. References
    6. Chapter 24: Routing in Optical Networks, Multilayer Networks, and Overlay Networks
      1. Abstract
      2. 24.1. Optical Technology: Overview
      3. 24.2. How is Optical Routing Different?
      4. 24.3. SONET/SDH and OTN Routing
      5. 24.4. WDM Routing and Wavelength Assignment
      6. 24.5. Protection Routing
      7. 24.6. Routing in Multilayer Networks
      8. 24.7. Overlay Networks and Overlay Routing
      9. 24.8. Summary
      10. Further Lookup
      11. Exercises
      12. References
    7. Chapter 25: Call Routing in GSTN
      1. Abstract
      2. 25.1. E.164 Addressing for GSTN
      3. 25.2. National Numbering Plan
      4. 25.3. Provider Identifier: Carrier Identification Code, Mobile Country Code, and Mobile Network Code
      5. 25.4. Signaling System: SS7 and Point Code
      6. 25.5. SS7 Protocol Stack
      7. 25.6. SS7 ISUP and Call Processing
      8. 25.7. Call Routing: Single Provider Case
      9. 25.8. Call Routing With Multiple Service Providers
      10. 25.9. Number Portability
      11. 25.10. Non-Geographic or Toll-Free Number Portability
      12. 25.11. Fixed/Mobile Number Portability
      13. 25.12. Multiple Provider Environment With Local Number Portability
      14. 25.13. Summary
      15. Further Lookup
      16. Exercises
      17. References
    8. Chapter 26: VoIP Call Routing
      1. Abstract
      2. 26.1. Background
      3. 26.2. GSTN Call Routing Using Internet
      4. 26.3. GSTN Call Routing: Managed IP Approach
      5. 26.4. IP-GSTN Interworking for VoIP
      6. 26.5. IP Multimedia Subsystem (IMS)
      7. 26.6. Multiple Heterogeneous Providers Environment
      8. 26.7. All-IP Environment for VoIP Services
      9. 26.8. Addressing Revisited
      10. 26.9. Summary
      11. Further Lookup
      12. Exercises
      13. References
  14. Part 5: Appendices, Bibliography, and Index
    1. Appendix A: Notations, Conventions, and Symbols
      1. A.1. On Notations and Conventions
      2. A.2. Symbols
    2. Appendix B: Miscellaneous Topics
      1. B.1. Binary and Hexadecimal Numbers
      2. B.2. Functions: Logarithm and Modulo
      3. B.3. Fixed-Point Equation
      4. B.4. Computational Complexity
      5. B.5. Equivalence Classes
      6. B.6. Solving Linear Programming Problems
      7. B.7. Exponential Weighted Moving Average (EWMA)
      8. B.8. Linear Regression Fit
      9. B.9. Non-Linear Regression Fit
      10. B.10. Computing Probability of Path Blocking or Loss
      11. B.11. Four Factors in Packet Delay
      12. B.12. Exponential Distribution and Poisson Process
      13. B.13. Generating Normal and Lognormal Distributions
      14. B.14. Self-Similarity and Heavy-Tailed Distributions
      15. B.15. Markov Chain and the Birth-and-Death Process
      16. B.16. Average Network Delay
      17. B.17. Packet Format: IPv4, IPv6, TCP, and UDP
      18. References
    3. Appendix C: Solutions to Selected Exercises
    4. Bibliography
    5. Index

Product information

  • Title: Network Routing, 2nd Edition
  • Author(s): Deep Medhi, Karthik Ramasamy
  • Release date: September 2017
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780128008294