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:
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.
Click below for Source Code related to this title:
List of Tables.
List of Figures.
1. Functional Specifications.
An OSPF Routing Daemon: OSPFD.
An OSPF Routing Simulator.
Installation of OSPFD (Linux Only).
Installation of the OSPF Routing Simulator: OSPF_SIM.
Installing the OSPF Sources.
Major Data Structures.
Application Programming Interface.
Link-State Database Fundamentals.
Receiving Self-Originated LSAs.
LS Sequence Number Rollover.
Neighbor State Machine.
Interface State Changes.
Receiving Link State Updates: SpfNbr::recv_update().
Flooding LSAs: LSA::flood().
Receiving Acknowledgments: SpfNbr::recv_ack().
Retransmitting LSAs: SpfNbr::rxmt_update().
Building Update Packets.
Guidelines for Area Boundaries.
Implementing Area Routing.
Implementing External Routing.
Triggering the Routing Calculation: OSPF::rtsched().
The Intra-AS Routing Calculation: OSPF::full_calculation().
Routes to ASBRs.
External Routes: INrte::run_external().
MOSPF Data Structures.
Propagating Group Membership: Group-Membership-LSAs.
Cache Maintenance and MOSPF IGMP Interaction.
Interaction with Other Routing Protocols.
Cryptographic Authentication Keys.
Area Route Aggregation.
Virtual Link Parameters.
Loopback Addresses and Attached Hosts.
Rereading Entire Configuration.
The OSPFD Configuration.
Changing Configuration Syntax.
Monitoring OSPFD Operation.
The Simulation Controller Process: OSPF_SIM.
A Simulated OSPF Router: The OSPFD_SIM Process.
Monitoring and Debugging.
Configuration and Management Messages.
This book is the companion to OSPF: Anatomy of an Internet Routing Protocol. In keeping with the Internet tradition of valuing "rough consensus and working code," this book provides a complete OSPF implementation to go with the previous description of the OSPF protocol. The implementation is written in C++ and has been designed for portability. Two sample ports are included: (1) an OSPF routing daemon, called ospfd, for the Linux operating system and (2) an OSPF routing simulator, ospf_sim, that can be run under Linux or Windows.
The text of this book provides design documentation for the implementation, a porting guide, and user manuals for the two sample ports. The data flow and major data structures are explained, using code fragments when necessary. The complete implementation is contained in an attached CD-ROM.
Examination of an OSPF implementation allows us to explore all the nooks and crannies of the protocol. Methods to optimize an OSPF implementation are also explained. Exercises are included for readers interested in gaining experience with modifying a fairly large, real-time distributed software system.
One thing that I have learned through many years of writing networking software is that there is always more than one way of doing anything. In no way should the reader assume that this book presents the only right way to implement OSPF functionality. However, the reader should learn from this book new techniques of implementing networking software and some fine points of the OSPF routing protocol.
Like OSPF: Anatomy of an Internet Routing Protocol, this book is for people interested in the practical aspects of Internet routing: students of data communications, TCP/IP network administrators, protocol designers, developers of routing protocol software, and other professionals involved in the design, development, and management of TCP/IP networks. Through the exercises included in the book, software engineers can also gain experience with modifying and enhancing a fairly large and complicated real-time software system.
Because the book contains a working OSPF implementation that can be used to turn a Linux workstation into a router or as an OSPF network simulator, the book will also be of interest to nonprogrammers involved in administering, designing, and monitoring OSPF networks.
This book assumes a basic knowledge of OSPF, which can be obtained either by reading the companion book, OSPF: Anatomy of an Internet Routing Protocol, or from the OSPF protocol specifications themselves.
This book can be read in several ways. Those people interested only in using the ospfd implementation or the OSPF simulator can restrict their attention to Chapters 1, 2, 13, 14, and 15. Those people interested mainly in porting the OSPF software to other environments can concentrate on Chapter 4 and the two sample ports described in Chapters 14 and 15.
The rest of the book—in Chapters 3 and 5n12—describes an implementation of OSPF and some of its extensions in great detail. For these chapters, familiarity with the basics of the C++ programming language is assumed. Each of these chapters discusses an OSPF function, such as flooding LSAs. The chapters begin with any required elucidations of the OSPF specifications and descriptions of any novel efficiency provisions provided by the implementation and then illustrate the function through examination of code samples. The network diagram on the flyleaf, a reproduction of Figure 6.6 in OSPF: Anatomy of an Internet Routing Protocol, is used throughout the text in examples. Exercises at the end of each chapter are used to reinforce ideas presented and to allow readers to add features to the implementation. Answers to the exercises are not provided; however, answers to those exercises marked as bug fixes can be found in the source code on http://www.ospf.org/software/ospfd.
Chapter 1, Functional Specifications, describes those OSPF features and extensions that are implemented by the enclosed software and those that are not. An overview of the two sample ports—the ospfd routing daemon for Linux and an OSPF routing simulator named ospf_sim—are also given.
Chapter 2, Installation Instructions, explains how to install the OSPF routing daemon ospfd under Linux and the OSPF routing simulator ospf_sim under Linux and Windows.
Chapter 3, Software Architecture, details the software architecture of the implementation, including inputs, outputs, and the data flow through the implementation. A brief description of the major data structures and their interrelationships is provided. This chapter also explains the source file organization of the CD-ROM.
Chapter 4, Porting Guide, shows how to port the OSPF software to various enviroments. The layer of software between the OSPF implementation and the operating system is explained. Special porting considerations, such as how to handle various types of CPU chips, are also covered.
Chapter 5, Building Blocks, describes various utility functions that the OSPF software uses. These utility functions are provided with the software and include AVL and Patricia trees and priority queues. The implementation of timers, logging messages, and the IP routing table are also explained.
Chapter 6, The Link-State Database, describes the organization of the implementation's OSPF link-state database. Various operations on the link-state database, including the aging of LSAs, are also covered.
Chapter 7, Originating LSAs, explains how the implementation originates LSAs, including the building of each particular OSPF LSA type. This chapter also discusses rate-limiting LSA originations, refreshing LSAs, and flushing LSAs from the link-state database.
Chapter 8, Neighbor Maintenance, describes the process of discovering and maintaining OSPF neighbor relationships. This chapter also covers the initial synchronization of link-state databases between neighbors and the handling of interface state changes.
Chapter 9, Flooding, details the continuing synchronization of OSPF link-state databases through the reliable-flooding algorithm.
Chapter 10, OSPF Hierarchy, begins with a discussion of the restrictions on configuration of OSPF area boundaries. The method for distributing routing information across area boundaries and the importation of external routes into an OSPF routing domain are also explained.
Chapter 11, Routing Calculations, describes the basic OSPF routing calculations, which yield IP routing table entries. Also included in this discussion are the various events that trigger the routing table calculation, and link-state database manipulations to enable the routing calculations to run faster. Calculation of intra-area, inter-area, and external routes are covered.
Chapter 12, MOSPF Implementation, describes an implementation of the Multicast Extensions to OSPF, or MOSPF. Topics covered include the interactions between MOSPF and IGMP, the generation of group-membership-LSAs, and the MOSPF routing calculation.
Chapter 13, Configuration and Monitoring, explains how the OSPF implementation is configured. The complete list of configuration parameters is explained, together with any consequences when a given parameter is changed dynamically. The mechanism for processing configuration requests is described, as well as the graceful-exit procedure used when shutting down the OSPF software.
Chapter 14, A Routing Daemon for Linux, describes the first sample port of the OSPF software: an OSPF routing daemon called ospfd for the Linux operating system. This daemon is an analog for the standard routed RIP routing daemon provided with most UNIX-based operating systems; ospfd would be used by those people wanting to run OSPF instead of RIP. The method for configuring, monitoring, and debugging ospfd is also provided.
Chapter 15, An OSPF Simulator, describes another port of the OSPF implementation: an OSPF routing simulator called ospf_sim running under Linux and Windows. The method to configure and run the simulation, which is a window-based Tk/Tcl application, is given.
A number of appendices have also been provided. Manual pages for the programs contained in the OSPF software distribution are included in Appendix A. The logging messages produced by the OSPF software are explained in Appendix B. A list of projects for people interested in extending the OSPF software appears in Appendix C. The last appendix, Appendix D, reproduces the GNU General Public license covering the implementation.
Following the appendices is an extensive bibliography arranged and numbered in alphabetical order. Within the text, the citation 75, for example, refers to item 75 in the bibliography.
The OSPF software provided is labeled Release 0.1. Although I have tried to test as many functions as possible, doubtless many bugs are in the software. Bug reports can be sent to email@example.com. Bug fixes for problems will be posted on http://www.ospf.org/software/ospfd, although possibly not in a very timely fashion.
The GNU GENERAL PUBLIC LICENSE, Version 2, June 1991, provided in its entirety in Appendix D, covers the OSPF implementation in this book.