You are previewing OSPF Complete Implementation.
O'Reilly logo
OSPF Complete Implementation

Book Description

Written by the creator of the OSPF (Open Shortest Path First) protocol, this book demonstrates the protocol in action with a complete OSPF implementation. It shows how the protocol's theory is realized in a real-time distributed software system, reveals many of the finer points of OSPF, and offers experienced-based optimization and porting techniques.

The implementation described and examined in this book is written in C++ and designed with porting in mind. The book details the software architecture of the implementation and describes in-depth key OSPF functions, illustrated by numerous code samples. It also includes a guide to porting OSPF software to different environments, with an explanation of the software layer between the OSPF implementation and the operating system. In addition, two sample ports are included–a routing daemon for Linux and an OSPF routing simulator for Linux and Windows.

Key topics covered include:

  • Implementation architecture, including I/O, data flow, and data structures

  • Porting considerations, including handling different types of CPU chips

  • AVL trees, Patricia trees, priority queues, timers, and logging messages

  • The IP routing table

  • Link-state database, including aging LSAs

  • Neighbor discovery and the neighbor state machine

  • Synchronization of link-state databases through the flooding algorithm

  • Hierarchy

  • Routing calculations, including intra-area, inter-area, and external routes

  • An implementation of the Multicast Extensions to OSPF (MOSPF)

  • Configuration and monitoring, including cryptographic authentication

  • Host wiretapping

  • Together, OSPF: Anatomy of an Internet Routing Protocol and OSPF Complete Implementation provide an in-depth view into the theory and inner workings of OSPF, and the knowledge you need to make full use of this important protocol in Internet-based applications.

    Table of Contents

    1. About This eBook
    2. Title Page
    3. Copyright Page
    4. Contents
    5. List of Tables
    6. List of Figures
    7. Preface
      1. Audience
      2. Organization of This Book
      3. Bug Fixes
      4. Source Code Copyright
      5. Acknowledgments
    8. 1. Functional Specifications
      1. 1.1. Feature Set
      2. 1.2. Implementation Mechanics
      3. 1.3. An OSPF Routing Daemon: ospfd
      4. 1.4. An OSPF Routing Simulator
      5. 1.5. Caveats
    9. 2. Installation Instructions
      1. 2.1. Installation of ospfd (Linux Only)
      2. 2.2. Installation of the OSPF Routing Simulator: ospf_sim
      3. 2.3. Installing the OSPF Sources
    10. 3. Software Architecture
      1. 3.1. Data Flow
      2. 3.2. Major Data Structures
      3. 3.3. File Organization
      4. Exercises
    11. 4. Porting Guide
      1. 4.1. Porting Overview
      2. 4.2. System Interface
      3. 4.3. Application Programming Interface
      4. 4.4. Porting Considerations
    12. 5. Building Blocks
      1. Name
      2. Synopsis
      3. Description
      4. Usage
      5. References
      6. Name
      7. Synopsis
      8. Description
      9. Usage
      10. Notes
      11. Name
      12. Synopsis
      13. Description
      14. Usage
      15. Notes
      16. Name
      17. Synopsis
      18. Description
      19. Usage
      20. Implementation
      21. Name
      22. Synopsis
      23. Description
      24. Usage
      25. Notes
      26. Name
      27. Synopsis
      28. Description
      29. Usage
      30. Implementation
      31. Notes
      32. See Also
      33. Name
      34. Synopsis
      35. Description
      36. Usage
      37. Notes
      38. Name
      39. Synopsis
      40. Description
      41. Notes
      42. Name
      43. Synopsis
      44. Description
      45. Usage
      46. Name
      47. Synopsis
      48. Description
      49. Usage
      50. References
      51. Name
      52. Synopsis
      53. Description
      54. Return Values
      55. Implementation
      56. Usage
      57. Notes
    13. 6. The Link-State Database
      1. 6.1. Link-State Database Fundamentals
      2. 6.2. Database Operations
      3. 6.3. LSA Lists
      4. 6.4. Aging LSAs
      5. 6.5. DoNotAge LSAs
      6. Exercises
    14. 7. Originating LSAs
      1. 7.1. Support Routines
      2. 7.2. Router-LSAs
      3. 7.3. Network-LSAs: SpfIfc::nl_orig()
      4. 7.4. Receiving Self-Originated LSAs
      5. 7.5. Deferred Originations
      6. 7.6. Refreshing LSAs
      7. 7.7. LS Sequence Number Rollover
      8. 7.8. Premature Aging
      9. Exercises
    15. 8. Neighbor Maintenance
      1. 8.1. Neighbor State Machine
      2. 8.2. Neighbor Discovery
      3. 8.3. Database Exchange
      4. 8.4. Interface State Changes
      5. Exercises
    16. 9. Flooding
      1. 9.1. Data Structures
      2. 9.2. Receiving Link State Updates: SpfNbr::recv_update()
      3. 9.3. Flooding LSAs: LSA::flood()
      4. 9.4. Receiving Acknowledgments: SpfNbr::recv_ack()
      5. 9.5. Retransmitting LSAs: SpfNbr::rxmt_update()
      6. 9.6. Building Update Packets
      7. Exercises
    17. 10. OSPF Hierarchy
      1. 10.1. Guidelines for Area Boundaries
      2. 10.2. Implementing Area Routing
      3. 10.3. Implementing External Routing
    18. 11. Routing Calculations
      1. 11.1. Triggering the Routing Calculation: OSPF::rtsched()
      2. 11.2. The Intra-AS Routing Calculation: OSPF::full_calculation()
      3. 11.3. Multipath Calculations
      4. 11.4. Preprocessing LSAs
      5. 11.5. Routes to ASBRs
      6. 11.6. External Routes: INrte::run_external()
      7. Exercises
    19. 12. MOSPF Implementation
      1. 12.1. MOSPF Data Structures
      2. 12.2. IGMPv2 Implementation
      3. 12.3. Propagating Group Membership: Group-membership-LSAs
      4. 12.4. Routing Calculations
      5. 12.5. Cache Maintenance and MOSPF–IGMP Interaction
      6. 12.6. Interaction with Other Routing Protocols
      7. Exercises
    20. 13. Configuration and Monitoring
      1. 13.1. Global Parameters
      2. 13.2. Interface Parameters
      3. 13.3. Cryptographic Authentication Keys
      4. 13.4. Area Parameters
      5. 13.5. Area Route Aggregation
      6. 13.6. Virtual Link Parameters
      7. 13.7. Nonbroadcast Neighbors
      8. 13.8. Loopback Addresses and Attached Hosts
      9. 13.9. External Routes
      10. 13.10. Graceful Exit
      11. 13.11. Rereading Entire Configuration
      12. 13.12. Host Wiretapping
      13. 13.13. Monitor Interface
      14. Exercises
    21. 14. A Routing Daemon for Linux
      1. 14.1. The ospfd Configuration
      2. 14.2. Changing Configuration Syntax
      3. 14.3. Dynamic Reconfiguration
      4. 14.4. Graceful Shutdown
      5. 14.5. Monitoring ospfd Operation
      6. 14.6. Caveats
      7. 14.7. Implementation Details
      8. Exercises
    22. 15. An OSPF Simulator
      1. 15.1. Software Architecture
      2. 15.2. The Simulation Controller Process: ospf_sim
      3. 15.3. A Simulated OSPF Router: The ospfd_sim Process
      4. 15.4. Monitoring and Debugging
      5. Exercises
    23. Appendix A. Manual Pages
      1. Name
      2. Synopsis
      3. Description
      4. Files
      5. See Also
      6. Name
      7. Synopsis
      8. Description
      9. Bugs
      10. See Also
      11. Name
      12. Synopsis
      13. Description
      14. Bugs
      15. See Also
      16. Name
      17. Synopsis
      18. Description
      19. Bugs
      20. See Also
      21. Name
      22. Synopsis
      23. Description
      24. Bugs
      25. See Also
    24. Appendix B. OSPFD Logging Messages
      1. B.1. Configuration and Management Messages
      2. B.2. Error Messages
      3. B.3. Informational Messages
      4. B.4. Halt Messages
      5. Exercises
    25. Appendix C. Projects
    26. Appendix D. GNU General Public License
    27. Bibliography
    28. Index