Cover image for OSPF complete implementation
OSPF complete implementation
Personal Author:
Physical Description:
1 computer disc ; 12 cm in pocket enclosure (14 cm


Item Barcode
Call Number
Material Type
Item Category 1
33000000007305 CP 035174 Computer File Accompanies Open Access Book Compact Disc Accompanies Open Access Book

On Order



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 cr

Author Notes

John T. Moy is a Corporate Fellow at Sycamore Networks, Inc. He is the author of the OSPF and MOSPF protocol specifications and chairs the OSPF and MOSPF Working Groups in the Internet Engineering Task Force. Involved in the design and development of router software for nearly two decades, Moy previously worked at Ascend Communications, Proteon, and Bolt, Beranek and Newman. He holds an M.A. in mathematics from Princeton and a B.S. in mathematics from the University of Minnesota.




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. Audience 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. Organization of This Book 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 . 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. Bug Fixes 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 . Bug fixes for problems will be posted on , although possibly not in a very timely fashion. Source Code Copyright The GNU GENERAL PUBLIC LICENSE, Version 2, June 1991, provided in its entirety in Appendix D, covers the OSPF implementation in this book. 0201309661P04062001 Excerpted from OSPF Complete Implementation by John T. Moy All rights reserved by the original copyright owners. Excerpts are provided for display purposes only and may not be reproduced, reprinted or distributed without the written permission of the publisher.

Table of Contents

List of Tablesp. ix
List of Figuresp. xi
Prefacep. xvii
Chapter 1. Functional Specificationsp. 1
1.1 Feature Setp. 1
1.2 Implementation Mechanicsp. 4
1.3 An OSPF Routing Daemon: ospfdp. 5
1.4 An OSPF Routing Simulatorp. 6
1.5 Caveatsp. 6
Chapter 2. Installation Instructionsp. 9
2.1 Installation of ospfd (Linux Only)p. 9
2.2 Installation of the OSPF Routing Simulator: ospf_simp. 11
2.3 Installing the OSPF Sourcesp. 15
Chapter 3. Software Architecturep. 17
3.1 Data Flowp. 17
3.2 Major Data Structuresp. 22
3.3 File Organizationp. 34
Chapter 4. Porting Guidep. 41
4.1 Porting Overviewp. 41
4.2 System Interfacep. 43
4.3 Application Programming Interfacep. 50
4.4 Porting Considerationsp. 54
Chapter 5. Building Blocksp. 59
Chapter 6. The Link-State Databasep. 87
6.1 Link-State Database Fundamentalsp. 87
6.2 Database Operationsp. 93
6.3 LSA Listsp. 102
6.4 Aging LSAsp. 106
6.5 DoNotAge LSAsp. 111
Chapter 7. Originating LSAsp. 119
7.1 Support Routinesp. 120
7.2 Router-LSAsp. 124
7.3 Network-LSAs: SpfIfc::nl_orig ()p. 130
7.4 Receiving Self-Originated LSAsp. 132
7.5 Deferred Originationsp. 134
7.6 Refreshing LSAsp. 136
7.7 LS Sequence Number Rolloverp. 136
7.8 Premature Agingp. 137
Chapter 8. Neighbor Maintenancep. 139
8.1 Neighbor State Machinep. 139
8.2 Neighbor Discoveryp. 146
8.3 Database Exchangep. 149
8.4 Interface State Changesp. 152
Chapter 9. Floodingp. 157
9.1 Data Structuresp. 159
9.2 Receiving Link State Updates: SpfNbr::recv_update ()p. 160
9.3 Flooding LSAs: LSA::flood ()p. 168
9.4 Receiving Acknowledgments: SpfNbr::recv_ack ()p. 172
9.5 Retransmitting LSAs: SpfNbr::rxmt_update ()p. 173
9.6 Building Update Packetsp. 177
Chapter 10. OSPF Hierarchyp. 179
10.1 Guidelines for Area Boundariesp. 179
10.2 Implementing Area Routingp. 182
10.3 Implementing External Routingp. 189
Chapter 11. Routing Calculationsp. 203
11.1 Triggering the Routing Calculation: OSPF::rtsched ()p. 203
11.2 The Intra-AS Routing Calculation: OSPF::full_calculation ()p. 206
11.3 Multipath Calculationsp. 219
11.4 Preprocessing LSAsp. 219
11.5 Routes to ASBRsp. 221
11.6 External Routes: INrte::run_external ()p. 223
Chapter 12. MOSPF Implementationp. 225
12.1 MOSPF Data Structuresp. 226
12.2 IGMPv2 Implementationp. 229
12.3 Propagating Group Membership: Group-membership-LSAsp. 230
12.4 Routing Calculationsp. 234
12.5 Cache Maintenance and MOSPF-IGMP Interactionp. 241
12.6 Interaction with Other Routing Protocolsp. 242
Chapter 13. Configuration and Monitoringp. 245
13.1 Global Parametersp. 246
13.2 Interface Parametersp. 248
13.3 Cryptographic Authentication Keysp. 250
13.4 Area Parametersp. 251
13.5 Area Route Aggregationp. 252
13.6 Virtual Link Parametersp. 252
13.7 Nonbroadcast Neighborsp. 253
13.8 Loopback Addresses and Attached Hostsp. 254
13.9 External Routesp. 254
13.10 Graceful Exitp. 256
13.11 Rereading Entire Configurationp. 259
13.12 Host Wiretappingp. 260
13.13 Monitor Interfacep. 262
Chapter 14. A Routing Daemon for Linuxp. 269
14.1 The ospfd Configurationp. 269
14.2 Changing Configuration Syntaxp. 277
14.3 Dynamic Reconfigurationp. 279
14.4 Graceful Shutdownp. 279
14.5 Monitoring ospfd Operationp. 280
14.6 Caveatsp. 280
14.7 Implementation Detailsp. 282
Chapter 15. An OSPF Simulatorp. 291
15.1 Software Architecturep. 292
15.2 The Simulation Controller Process: ospf_simp. 299
15.3 A Simulated OSPF Router: The ospfd_sim Processp. 302
15.4 Monitoring and Debuggingp. 306
Appendix A. Manual Pagesp. 309
Appendix B. OSPFD Logging Messagesp. 329
B.1 Configuration and Management Messagesp. 330
B.2 Error Messagesp. 331
B.3 Informational Messagesp. 334
B.4 Halt Messagesp. 340
Appendix C. Projectsp. 341
Appendix D. GNU General Public Licensep. 343
Bibliographyp. 351
Indexp. 357