Internet Draft August 2007 Network Working Group Matthew R Thomas Internet Draft David K Hunter Expires: 3 March 2008 Martin J Reed OSPF-lite draft-thomas-hunter-reed-ospf-lite-00.txt Status of this Memo Distribution of this memo is unlimited. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. OSPF-lite Abstract This memo documents OSPF-lite. OSPF-lite is a link state routing protocol, and a branch version of Internet Standard 54 OSPF [ref1]. It is designed to be run internal to a single Autonomous System. Each OSPF-lite router maintains an identical database describing the Autonomous System's topology. From this database, a routing table is calculated by constructing a shortest-path tree. OSPF-lite has been designed to provide a simpler version of the OSPF protocol. A router running ospf-lite requires little configuration. Areas are not implemented and all designated Router functionality has been removed from the protocol. OSPF-lite will run over non fully meshed clouds with no special OSPF configuration commands required. Thomas et al [Page 1] Internet Draft August 2007 Many of the Protocol complexities have been removed, and processor overhead utilised in a different way. This work is intended to keep pace with the vast increases in processor performance, memory size and link capacity since OSPF was originally designed in 1989, with the resulting benefits of simpler network design, configuration and maintenance. The differences between this memo and RFC 2328 are highlighted throughout the document, but special attention should be placed on Sections 2, 7, 16, and Appendix A; the latter describes detailed packet structures. Many of the differences are backward compatible in nature, but it is not envisioned that OSPF Version 2 will interoperate with OSPF-lite, unless multiple instances are running and route redistribution is employed. The protocol has been designed with backward consistency in mind, as far has been possible, to allow code modules developed for OSPF Version 2 to be re-utilised. This Internet Draft has been written within the same structure as RFC 2328, to enable a section-by-section comparison with previous versions of the main OSPF protocol. It is recommended that the sections are directly compared. The authors’ thanks in turn go the developers of all of the features in RFC 2328, and associated RFCs, and Standards. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [KEYWORDS]. Implementations of this memo and of RFCs 2328, 1583, and 1247 will not directly interoperate. Please send comments to mrthom@essex.ac.uk Table of Contents 1 Introduction ............................................ 6 1.1 Protocol Overview ....................................... 8 1.2 Definitions of commonly used terms ...................... 9 1.3 link-state routing technology and OSPF-lite... ......... 12 1.4 Organization of this document .......................... 12 1.5 Acknowledgments ........................................ 13 2 The link-state database: organization and calculations.. 13 2.1 Representation of routers and networks ................. 13 Thomas et al [Page 2] Internet Draft August 2007 2.1.0.1 Removal of Network LSAs............................... 14 2.1.0.2 Some new ospf-lite LSA terms.......................... 14 2.1.0.3 A recommendation for an 'implied network vertex'...... 14 2.1.0.4 neighbor relationships on an implied vertex network... 14 2.1.0.5 The operation of OSPF-lite-stub and OSPF-lite-transit. 15 2.1.0.6 Safety feature introduced by ospf-lite-transit........ 15 2.1.0.7 Point-to-point networks............................... 15 2.1.0.8 OSPF-lite network types independent of physical type.. 16 2.1.0.9 Introduction example graphs........................... 16 2.1.0.10 Point-to-point representation and IP unnumbered...... 18 2.1.0.11 OSPF-lite-stub example............................... 18 2.1.0.12 Implied transit Vertex example....................... 18 2.1.1. Representation of non-broadcast networks ............. 18 2.1.1.1 OSPF-lite allows Vendors to implement manual type..... 19 2.1.2.0 An OSPF-lite link-state database ..................... 19 2.1.2.1 Options for creating the network graph: two stage..... 22 2.1.2.2 Building stub vertices for all networks: two stage.... 22 2.1.2.3 Summary of protocol specific graphing terms........... 22 2.1.2.4 Information graph resulting from Router LSAs.......... 23 2.1.2.5 Network graph for first pass SPF calcuation........... 24 2.2 The shortest-path tree in OSPF-lite................... 26 2.2.1 NBMA network example with LSA and graph............... 29 2.2.1.1 Neighbors Adjacencies are fully meshed on NBMA........ 30 2.3 External routing information Supported in OSPF-lite..... 30 2.4 Equal-cost multipath ................................... 32 3.0 How OSPF-lite doesn't support areas..................... 33 3.1 The Autonomous System with OSPF-lite.................... 33 3.2 Not applicable.......................................... 33 3.3 Classification of routers .............................. 33 3.4 Not applicable.......................................... 33 3.5 IP subnetting support .................................. 33 3.6 Not applicable.......................................... 33 3.7 Not applicable.......................................... 33 4 Functional Summary ..................................... 34 4.1 Not applicable.......................................... 35 4.2 AS external routes ..................................... 35 4.3 Routing protocol packets ............................... 35 4.4 Basic implementation requirements ...................... 36 4.5 Optional OSPF-lite capabilities ........................ 38 5 Protocol data structures ............................... 39 6 Areas not supported in OSPF-lite........................ 40 7 Modified Adjacencies in OSPF-lite....................... 40 7.1 The Hello Protocol ..................................... 40 7.1.1 ospf-lite Hello protocol differences.................... 40 7.2 The Synchronization of Databases ....................... 41 7.3 Removal of Designated Router ........................... 42 7.4 Not applicable.......................................... 42 7.5 The Modified graph of adjacencies ...................... 42 Thomas et al [Page 3] Internet Draft August 2007 8 Protocol Packet Processing ............................. 43 8.1 Sending protocol packets ............................... 43 8.2 Receiving protocol packets ............................. 44 9 The Modified Interface Data Structure .................. 46 9.1 Interface states ....................................... 48 9.2 Events causing interface state changes ................. 49 9.3 OSPF-lite Interface state machine ...................... 50 9.4 Not applicable.......................................... 52 9.5 Sending Hello packets .................................. 52 9.5.1 OSPF-lite modified NBMA networks........................ 52 10 The Neighbor Data Structure ............................ 52 10.1 Neighbor states ........................................ 54 10.2 Events causing neighbor state changes .................. 57 10.3 The Neighbor state machine ............................. 59 10.4 OSPF-lite All neighbors become adjacent................. 63 10.5 Receiving Hello Packets ................................ 63 10.6 Receiving Database Description Packets ................. 65 10.7 Receiving Link State Request Packets ................... 68 10.8 Sending Database Description Packets ................... 68 10.9 Sending Link State Request Packets ..................... 69 10.10 An OSPF-lite modified Example .......................... 70 11 The Routing Table Structure ............................ 72 11.1 Routing tables ......................................... 72 11.2 Sample OSPF-lite routing table (see Section 2).......... 72 11.3 Not applicable................... .................... 72 12 Link State Advertisements (LSAs) .................... 72 12.1 The LSA Header ...................................... 73 12.1.1 LS age .............................................. 73 12.1.2 Options ............................................. 74 12.1.3 OSPF-lite modified LSA Types......................... 74 12.1.3.1 Opaque LSAs supported................................ 75 12.1.4 Link State ID ....................................... 75 12.1.5 Advertising Router .................................. 76 12.1.6 LS sequence number .................................. 76 12.1.7 LS checksum ......................................... 76 12.2 The link state database ............................. 77 12.3 Representation of TOS ............................... 78 12.4 Originating LSAs .................................... 78 12.4.1 Router-LSAs ......................................... 81 12.4.1.1. Point-to-point interfaces; ospf-lite-stub/transit.. 84 12.4.1.1.1 IP unnumbered issues with Router LSA generation... 84 12.4.1.1.2 Hello protocol assistance with IP unnumbered...... 84 12.4.1.2 OSPF-lite broadcast and NBMA interfaces ............ 84 12.4.1.3 Not applicable............. ......................... 85 12.4.1.4 OSPF-lite and Point-to-MultiPoint interfaces ........ 85 12.4.1.5 Examples of router-LSAs ............................. 86 12.4.2 Network-LSAs not supported in OSPF-lite ............. 88 12.4.2.1 Not applicable............. ......................... 88 12.4.3 Summary-LSAs not supported in OSPF-lite.............. 88 12.4.3.1 Not applicable............. ......................... 88 12.4.3.2 Not applicable............. ......................... 88 12.4.4 AS-external-LSAs .................................... 88 Thomas et al [Page 4] Internet Draft August 2007 12.4.4.1 Examples of AS-external-LSAs support................. 89 12.4.4.2 Example of Router LSA with NBMA interface............ 91 13 Flooding Procedure .................................. 92 13.1 Determining which LSA is newer ........................ 95 13.2 Installing LSAs in the database ....................... 92 13.3 Next step in the flooding procedure ................... 96 13.4 Receiving self-originated LSAs ........................ 98 13.5 Sending Link State Acknowledgment packets ............. 99 13.6 Retransmitting LSAs .................................. 101 13.7 Receiving link state acknowledgments ................. 101 14 Aging The Link State Database ........................ 102 14.1 Premature aging of LSAs .............................. 102 15 OSPF-lite and Virtual Links ...........................103 16 Calculation of the routing table ..................... 103 16.0.1 Introduction to Calculations (see also 2.1.2.4)....... 103 16.0.2 Connecting router transit vertices with implied arcs.. 104 16.0.3 Create implied transit vertices if desired............ 105 16.0.4 Adding Stub Vertices.................................. 106 16.0.5 External networks and implied arcs.................... 106 16.0.6 Full graph (see Section 2.1.2.4)...................... 106 16.0.7 Calculating the SPF tree and resulting table.......... 108 16.0.7.1 Preloading Main device routing table................ 108 16.1 Calculating the shortest-path tree for OSPF-lite AS... 110 16.1.1 The next hop calculation ............................. 115 16.2 Not applicable........................................ 116 16.3 Not applicable........................................ 116 16.4 Calculating AS external routes ....................... 116 16.4.1 Not applicable........................................ 117 16.5 Not applicable........................................ 117 16.6 Incremental updates -- AS-external-LSAs .............. 117 16.7 Not applicable........................................ 117 16.8 Equal-cost multipath ................................. 118 Footnotes ................................................... 119 Normative References......................................... 120 Informative References....................................... 120 A OSPF-lite data formats ............................... 121 A.1 Encapsulation of OSPF-lite packets ................... 121 A.2 The Options field ................................. 122 A.3 OSPF-lite Packet Formats ............................. 123 A.3.1 The OSPF-lite packet header .......................... 124 A.3.2 The Hello packet ..................................... 125 A.3.3 The Database Description packet ...................... 127 A.3.4 The Link State Request packet ........................ 129 A.3.5 The Link State Update packet ......................... 130 A.3.6 The Link State Acknowledgment packet ................. 131 A.4 OSPF-lite Modified LSA formats ....................... 132 A.4.1 The LSA header ....................................... 133 A.4.2 Router-LSAs Modified Link types....................... 134 A.4.3 Not applicable ....................................... 137 Thomas et al [Page 5] Internet Draft August 2007 A.4.4 Not applicable ....................................... 137 A.4.5 AS-external-LSAs ..................................... 137 B Architectural Constants .............................. 139 C Configurable Constants ............................... 140 C.1 Global parameters .................................... 141 C.2 AS parameters ........................................ 141 C.3 Router interface parameters .......................... 141 C.4 Not applicable ....................................... 143 C.5 NBMA network Modifications............................ 143 C.6 Point-to-MultiPoint support replaced ................. 144 C.7 Host route parameters ................................ 144 D Authentication ...................................... 144 D.1 Null authentication ................................. 144 D.2 Simple password authentication ...................... 145 D.3 Cryptographic authentication ........................ 145 D.4 Message generation .................................. 148 D.4.1 Generating Null authentication ...................... 148 D.4.2 Generating Simple password authentication ........... 148 D.4.3 Generating Cryptographic authentication ............. 149 D.5 Message verification ................................ 150 D.5.1 Verifying Null authentication ....................... 150 D.5.2 Verifying Simple password authentication ............ 150 D.5.3 Verifying Cryptographic authentication .............. 150 E An algorithm for assigning Link State IDs ........... 151 F Multiple interfaces to the same network/subnet ...... 153 Security Considerations ..................................... 153 Author's Addresses........................................... 154 Full Copyright Statement..................................... 155 1. Introduction This document outlines OSPF-lite. It is assumed that the reader will be familiar with OSPF Version 2 (RFC 2328), and if not it is suggested that the reader should have an understanding of the protocol from such a source first. There are some major differences between OSPF and OSPF-lite. One of the most major of these concerns the Link type in Type 1 Router-LSAs. Over broadcast media OSPF Version 2 elects Designated Routers and Backup Designated Routers. This design is less necessary with today's more powerful processors and memory allocations. OSPF-lite removes the Designated Router function, and the Type 2 Network-LSAs from the protocol. Thomas et al [Page 6] Internet Draft August 2007 Two of the original OSPF design goals were to restrict the number of Adjacencies that routers on shared media had to support. There was also a second goal of keeping routing traffic low. This was done by electing a router on a shared Medium, to perform operations on behalf of that media. Given the speed of today's transmission media, and the increase in performance of today's processors, it was felt that the Design goals of adjacency reduction on the protocol could be removed. Processor load graphs will follow in future documents. The removal of the complexities introduced by the desire to keep adjacencies and packets low, is the goal of this Draft. In some cases the protocol can be made more scalable, and will be able to run on simpler devices. It is worth noting that this design moves the emphasis on the processor cycles spend. Load is saved from protocolcomplexities, and then spent on state describing Database adjacencies. Looking at the new ExampleRouter LSA in Section 12.4.1.5, you can see the simpler layout of the structure. There are economic savings to be made in the re-use of established protocols and code modules with unused fields zeroed. It is hoped that further simplifications can be applied over successive rewrites of this protocol. There are also some secondary benefits to the removal of the DR and associated processes. With no DR Election, the Hello process is simplified. Another major benefit is the lack of reliance on the Network LSAs Type 2. These were identified by the Designated Router, and if the router failed, the LSA needed re-flooding. The Hello protocol has also been re-worked, in order to overcome non fully meshed NBMA networks (see Section 7.1.1.) Finally and most importantly, OSPF-lite employs a unified way to handle today's differing Network Types. The handling of Point-to-Point networks, Broadcast networks and more specifically NBMA networks has been re-evaluated, with the protocol reading the physical network type, but then applying the rules set down in the Router LSA Type 1 Structures. There is the Introduction of the two new Link Types for use within the Router LSA Type 1's. OSPF-lite-stub (Type 8) and OSPF-lite-transit (Type 9) replace all of the previously defined network linkTypes. This has meant that point-to-point interfaces have been completely re-worked, along with all of the other Interface types. Thomas et al [Page 7] Internet Draft August 2007 There has been the removal of multiple area support. LSA Type 5's are supported for External Networks, and full tagging, but the LSA-3's and 4's have been removed. This has been done as it is felt that modern routers are able to process much larger graphs than today’s networks can build. In the case of requiring 'areas' multiple instances of ospf-lite can be run with redistribution between the instances. This is recommended while shielding an internal network from Internet routes for example . The concept of an implied (transit) network vertex has been introduced (Section 2.1.0.3.) There is a distinction in ospf-lite between the Adjacency graph on an individual network, which is always fully meshed between neighbors, and the graph used for router calculation (See Section 2), which operates in a similar way to OSPF Version 2 with vertices (implied) for each network. There is a similar distinction with the information sent in the LSAs. The presence of a vertex in the SPF graph does not always coincide with the presence of a sepcific LSA as in OSPF Version 2. we would like to recommend that all interfaces on an OSPF-lite network have an IP address, however unnumbered functionality is supported. routing protocol traffic . 1.1. Protocol overview OSPF-lite is a link state protocol based upon OSPF Version 2. In a link-state routing protocol, each router maintains a database describing the Autonomous System's topology. This database is referred to as the link-state database. Each participating router has an identical database. Each individual piece of this database is a particular router's local state (e.g., the router's usable interfaces and reachable neighbors). The router distributes its local state throughout the Autonomous System by flooding. Thomas et al [Page 8] Internet Draft August 2007 Both OSPF-lite and OSPF Version 2 involve a minimum of misrouting during convergence time. This is a feature of all link State protocols. All routers run the same algorithm, in parallel. From the link-state database, each router constructs a tree of shortest paths with itself as root. This shortest-path tree gives the route to each destination in the Autonomous System. Externally derived routing information appears on the tree as leaves. When several equal-cost routes to a destination exist, traffic is distributed equally among them. The cost of a route is described by a single dimensionless metric. Unlike OSPF V2, OSPF-lite does not support multiple areas. However it does support External tagged routes as in OSPF V2, Hence it supports LSA types 1 and 5. This is intentional, as the protocol is designed for ease of implementation, configuration and management, with possible applications in mobile applications where areas could be restrictive. OSPF-lite supports VLSM, and supernet routes, but does NOT support non-contiguous network masks. All OSPF-lite protocol exchanges are authenticated. A variety of authentication schemes can be used. These are taken entirely from the work on OSPF V2. Externally derived routing data (e.g., routes learned from an Exterior Gateway Protocol such as BGP) can be advertised throughout the Autonomous System. Each external route can also be tagged by the advertising router, enabling the passing of additional information between routers on the boundary of the Autonomous System. This is accomplished in the same way as in OSPF Version 2. 1.2. Definitions of commonly used terms This section provides definitions for terms that have a specific meaning in the context of the OSPF-lite protocol and that are used throughout the text. The reader unfamiliar with the Internet Protocol Suite is referred to [ref2] for an introduction to IP. Router A layer 3 Internet Protocol packet switch, formerly called a gateway in much of the IP literature. Autonomous System A group of routers exchanging routing information via a common routing protocol. Abbreviated as AS. Thomas et al [Page 9] Internet Draft August 2007 Interior Gateway Protocol The routing protocol spoken by the routers belonging to an Autonomous system. Abbreviated as IGP. Each Autonomous System has a single IGP. Separate Autonomous Systems may be running different IGPs. Router ID A 32-bit number assigned to each router running the OSPF-lite protocol, which uniquely identifies the router within an Autonomous System. Network In this memo, an IP network/subnet/supernet. It is possible for one physical network to be assigned multiple IP network/subnet numbers. We consider these to be separate networks. OSPF-lite supports many logical networks on a physical Network. Network mask A 32-bit number indicating the range of IP addresses residing on a single IP network/subnet/supernet. This specification displays network masks as hexadecimal numbers. For example, the network mask for a class C IP network is displayed as 0xffffff00. Such a mask is often displayed elsewhere in the literature as 255.255.255.0. Point-to-point networks A network that joins a single pair of routers. Broadcast networks Networks that can support many attached routers, and can address a single physical message to all of the attached routers (broadcast). Each pair of routers on a broadcast network is assumed to be able to communicate directly. An Ethernet is an example of a broadcast network. Non-broadcast networks Networks supporting many (more than two) routers, but having no broadcast capability. Neighboring routers are maintained on these nets (as on all networks) using OSPF-lite's Hello Protocol. OSPF-lite achieves neighbor discovery even on non fully meshed non-broadcast networks automatically. An X.25 Public Data Network (PDN) is an example of a non-broadcast network. Thomas et al [Page 10] Internet Draft August 2007 Interface The connection between a router and one of its attached networks. An interface has state information associated with it, which is obtained from the underlying lower level protocols and the routing protocol itself. Neighboring routers Two routers that have interfaces to a common network. Neighbor relationships are maintained and dynamically discovered by OSPF-lite's Hello Protocol. With ospf-lite ALL neighbors become adjacent. Adjacency A relationship formed between neighboring routers for the purpose of exchanging routing information. In OSPF-lite, all pairs of neighboring routers become Fully adjacent. Link state advertisement Unit of data describing the local state of a router or network. For a router, this includes the state of the router's interfaces and adjacencies. Each link state advertisement is flooded throughout the routing domain. The collected link state advertisements of all routers (describing the networks they are connected to), forms the protocol's link state database. Throughout this memo, link state advertisement is abbreviated as LSA. Hello Protocol The part of the OSPF-lite protocol used to establish and maintain neighbor relationships. The Hello Protocol dynamically discovers neighboring routers even on non fully meshed networks and operates on ALL network types. Flooding The part of the OSPF-lite protocol that distributes and synchronizes the link-state database between OSPF-lite enabled routers. Designated Router Unlike OSPF Version 2, Designated Routers and Backup Designated Routers are not used in any way or supported in OSPF-lite. There are also no LSA Type 2 Network LSA's in OSPF-lite. Lower-level protocols The underlying network access protocols that provide services to the Internet Protocol and in turn the OSPF-lite protocol. Examples of these are the X.25 packet and frame levels for X.25 PDNs, and the Ethernet data link layer for Ethernets. Thomas et al [Page 11] Internet Draft August 2007 1.3. link-state routing technology and OSPF-lite OSPF-lite is purely a link state routing protocol. Such protocols are also referred to in the literature as SPF-based or distributed-database protocols. The first link-state routing protocol was developed for use in the ARPANET packet switching network. This protocol is described in [ref16], and has formed the starting point for all other link-state protocols. The homogeneous ARPANET environment, i.e., single-vendor packet switches connected by synchronous serial lines, simplified the design and implementation of the original protocol. Modifications to this protocol were proposed in [ref21], which dealt with increasing its fault tolerance through, amongst other things, adding a checksum to the LSAs (thereby detecting database corruption). The paper also included means for reducing the routing traffic overhead in a link-state protocol. This was accomplished by introducing mechanisms which enabled the interval between LSA originations to be increased by an order of magnitude. The OSPF Working Group of the IETF extended this work in developing the OSPF Version 2 protocol. OSPF-lite is a Branch from much of the work that has gone into the OSPF Version 1 and 2 protocols. OSPF-lite builds on and utilises most of OSPF Version 2. 1.4. Organization of this document As previously stated, this document is organised along the same lines as RFC 2328 OSPF Version 2 [ref1], to facilitate cross-referencing from section to section of the different features and characteristics of the two protocols. It is envisioned that implementers of OSPF-lite will probably already be familiar with OSPF V2, and so this has been done so that the features changed can be seen at a glance. The authors are grateful therefore to John Moy and his colleagues for much of his prose and text. The authors are especially indebted to the work on Appendix D which is taken almost directly from OSPF V2. The first three sections of this specification give a general overview of the protocol's capabilities and functions. Sections 4-16 explain the protocol's mechanisms in detail. Packet formats, protocol constants and configuration items are specified in the appendices, including the new LS link Types introduced with OSPF-lite. Thomas et al [Page 12] Internet Draft August 2007 Labels such as HelloInterval encountered in the text refer to protocol constants. They may or may not be configurable. Architectural constants are summarized in Appendix B. Configurable constants are summarized in Appendix C. The detailed specification of the protocol is presented in terms of data structures and algorithms, in order to make the explanation more precise. Implementations of the protocol are required to support the functionality described, but need not use the same data structures and algorihtms as those that appear here. 1.5. Acknowledgments from RFC2328 The authors would like to thank firstly John Moy, and also acknowledge the original OSPF Version 2 protocol, from which most of this structure has been taken. It needn't be said that without the seminal work on OSPF by J.Moy, this document would not have happened. The extra 'OSPF-lite-stub' host route induced by a NBMA Network Type in OSPF-lite is based in principle and operation on work done on the OSPF Version 2, Point-to-MultiPoint interface, which was in turn based on work done by Fred Baker. This work inspired the writing of this memo. The OSPF-lite Cryptographic Authentication option Appendix D is resued from RFC2328 in entirety and all credit goes to the original authors. As stated previously, this work uses the formatting of RFC 2328, to give a familiar feel, and enable paragraph by paragraph comparison, not to mention it made our lives a lot easier. In Summary, much of the credit for the basis of this protocol lies with the creators and designers of the original OSPF version 2 protocol. 2. The Link-state Database: organization and calculations The following subsections describe the organization of OSPF-lite's link state database, and the routing calculations that are performed on the database in order to produce a router's routing table. 2.1. Representation of routers and networks The Autonomous System's link-state can be described by a structure known as a directed graph. Such a graph consists of vertices connected by directed arcs. A number of methods of representing the network topology using graphs is possible. One such representation is given as an example in Section 2.1.2.4 Both the LSAs generated by the routers to produce the graph, and the SPF tree calculated from the graph are independent of these different graph representations. Thomas et al [Page 13] Internet Draft August 2007 2.1.0.1 In OSPF-lite There are no network LSAs. Unlike OSPF V2, OSPF-lite does not generate network LSAs, only Router LSAs. The information in the Router LSAs is used to connect the vertices in order to describe the database as a directed graph. In terms of the Router LSAs there are the following formal OSPF-lite network types: 2.1.0.2 Some new LSA terms OSPF-lite-stub; representing a router on its own on a network. OSPF-lite-transit; representing a network with more than one OSPF-lite router. 2.1.0.3 A recommendation for an 'Implied network vertex' in the graph Networks are not normally represented as transit vertices in the network graph representation in OSPF-lite, but an OSPF-lite-transit network with more than two routers attached could be represented by an implied transit vertex. Section 2.1.2.1 outlines a recommendation for building the directed graph. In this recommendation we are suggesting that for a network with more than two routers attached, an 'implied transit vertex' could be created to represent the network. This may facilitate faster SPF processing. There is no LSA generated for this 'Implied transit Vertex', and its presence is not reported to other routers. This is merely an implementation suggestion and is not reflected in the operation of the protocol. When graphed, an OSPF-lite implied transit vertex only has a cost on incomming edges. All networks, namely OSPF-lite-stub, OSPF-lite-transit (with no more than two routers) and external networks, end up being represented by vertices in the graph. These vertices can be implied STUB vertices and do NOT have to be implied TRANSIT vertices. The reader's attention is drawn to the fact that OSPF-lite-stub and OSPF-lite-transit are network types, but implied Stub vertices and implied transit Vertices are graph representations of the LSAs. Stub and Transit vertices are related to the OSPF-lite types but are not the same term and do not always coincide with one another. For example, OSPF-lite-transit networks are often added to a graph as only Stub Vertices as described in Section 2.1.2.2 2.1.0.4 neighbor relationships on an 'implied vertex' network It is important to realise that the neighbor relationships of the routers are not affected by whether implied vertices are used in the graph representation which is suggested here. The routers on a broadcast NBMA network are fully meshed as far as these neighbor relationships are concerned. The implied transit vertex merely seeks to simplifiy the SPF processing. This implementation of O(N^2) message passing Thomas et al [Page 14] Internet Draft August 2007 complexity over the broadcast network is deliberate. The ability to use an implied vertex for SPF processing is a vendor specific issue but allows the advantage of a transit network vertex where required for SPF processing without the complexity overhead of flooding Network LSAs within the OSPF-lite protocol. 2.1.0.5 The operation of OSPF-lite-stub and OSPF-lite-transit The description of the networks in the AS topology, (held in the routers link state database, and subsequesntly graphed), is based solely on information from Router LSA's. Networks can be described as OSPF-lite-stub or OSPF-lite-transit. When a Router LSA (from Router1) is first sent on a network, the network is described as OSPF-lite-stub. This can be seen throughout the AS and another AS router (Router3) can calculate that the router1 is alone on the network. If router1 receives a router LSA from another router (Router 2) and receives it on the network concerned, then Router1 resends the Router LSA with the network type changed to OSPF-lite-transit. All networks begin being advertised as stub networks in the router LSA, and migrate to OSPF-lite-transit networks if another OSPF-lite router is operating and advertising on the same network. There must also be an adjacency in place for this change from OSPF-lite-stub to OSPF-lite-transit to take place. The reason for this mechanism are as follows: 2.1.0.6 Safety introduced by OSPF-lite-stub and OSPF-lite-transit If Router1 has advertised a connected network as a stub network, and a second remote router2 has been misconfigured to advertise that it is attached to the same network as Router1, then Router1 will not receive the LSA about the network directly over the network. Router1 will then not migrate the network type in the Router LSA from stub to transit type. A third remote router3 can see that both routers 1 and 2 are advertising the same stub network, and know that there is a misconfiguration. The other routers in the AS therefore do not connect the routers 1 and 2 together on the graph with an implied arc, and an error condition is identified. 2.1.0.7 Point-to-point networks All neworks are treated in the same way. In OSPF-lite this means that a point-to-point network will being advertised as an ospf-lite-stub network in the router LSA, and migrate to an OSPF-lite-transit network. This is a much simpler implementation than in OSPF V2. Thomas et al [Page 15] Internet Draft August 2007 In general all networks are OSPF-lite-transit, unless they are either loopbacks, extra stubs added for the purpose of NBMA networks, or networks on which there is no other router running OSPF-lite. In OSPF-lite, the network takes a Link Type of 8 initially, namely OSPF-lite-stub. The link becomes OSPF-lite-transit, if a neighbour appears on the link, with matching Hellos, and the router LSA from the neighbor contains the same network received on the network. The Database must match both OSPF-lite-transit connections together in the associated graph. It is assumed that the link has an IP address. IP un-numbered is supported but the vendor must ensure that the MIB 2 If-value is copied correctly into the Link ID field of the Router LSA, and the link is reflected as one that does not have its own native IP subnet. The subnet in the Link Data field is replaced by the value 0.0.0.1. Hellos generated on these links place 0.0.0.1 in the mask field also to indicate to ignore the mask. IP unnumbered is considered an unusual case. For standard point-to-point lines with IP addressing, the Local IP address and mask are listed in the LS Link type ID, and Data fields. See Appendix A for details. This differs from operation in OSPF Version 2, which adds an extra stub network to the Router LSA. 2.1.0.8 OSPF-lite network types are independent of physical type The network's type in OSPF-lite does NOT depend on the physical network type. Point-to-point, broadcast, NBMA meshed or non-fully meshed, all have the same OSPF-lite type, that of; OSPF-lite-stub if they are the only router on that network, or OSPF-lite-transit if there are more than one OSPF-lite router functioning on the network. The only 'exception' to this is a special route introduced for NBMA networks, where the fact that an network is NBMA is understood by OSPF-lite and a special case is introduced. This operation is default. See Section 2.1.1 for details, and Section 2.2.1 for a specific NBMA non fully meshed network example. 2.1.0.9 Introduction example graphs Both OSPF-lite-stub and OSPF-lite-transit, and the implied vertex (if used) are depicted in Figure 1. Rectangles indicate routers. Circles and oblongs indicate networks. Router names are prefixed with the letters RT and network names with the letter N. Lines between routers indicate connecting networks. The left side of the figure shows networks with their connected routers, with the resulting graphs shown on the right. Thomas et al [Page 16] Internet Draft August 2007 **FROM** |RT1| +---+ N1 -------- |RT1|------ **TO** (OSPF-lite-stub) N1| 3 | +---+ cost3 Physical point-to-point networks (OSPF-lite-stub) figure 1.1 **FROM** 3 4 |RT1|RT2| +---+ N1 +---+ ------------ |RT1|------|RT2| **TO** RT1| | 4 | +---+ +---+ RT2| 3 | | (OSPF-lite-transit) N1| 3 | 4 | Physical point-to-point networks (OSPF-lite-transit) figure 1.2 **FROM** +---+ |RT7| |RT7| +---+ **TO** -------- | 4 N1 | 4 | +----------------------+ N1 Single Router on Ethernet (OSPF-lite-stub) figure 1.3 **FROM** +---+ +---+ |RT3| |RT4| |RT3|RT4|RT5|RT6|N1 | +---+ +---+ ------------------------- 5 | N1 5 | **TO** RT3| - | | | | 0 | +----------------------+ RT4| | - | | | 0 | 5 | 5 | RT5| | | - | | 0 | +---+ +---+ suggested RT6| | | | - | 0 | |RT5| |RT6| (implied vertex) N1¦ 5 | 5 | 5 | 5 | - | +---+ +---+ Broadcast or NBMA networks (implied vertex) figure 1.4 Thomas et al [Page 17] Internet Draft August 2007 Routers are represented by vertices. An edge connects Vertex A to Vertex B if the intersection of Column A and Row B is marked with a cost. 2.1.0.10 Point-to-point representation and IP unnumbered. Figure 1.1 shows two routers connected by a point-to-point link. 2.1.0.11 OSPF-lite-stub example Figures 1.1 and 1.3 show an example of an OSPF-lite-stub network. This is a network with only one attached router. In this case, the network appears on the end of a stub connection in the link-state database's graph. This is link type OSPF-lite-stub (link type 8). If a directly connected router appears sending a router LSA 1 with this network advertised, then this link type would change to OSPF-lite-transit (Link type 9). Note: Eventually even stub networks would be represented by implied stub vertices in the graph. Section 2.1.2.1 outlines one such possible graph representation. 2.1.0.12 Implied transit Vertex example When more than two routers are attached to a broadcast network, then the graph can be represented with an implied network transit vertex. The graph shows all routers bidirectionally/fully connected to the implied transit network vertex. This is represented in Figure 1.4. This graph does not reflect the routers' neighbor status, which is fully meshed among the routers on the 'implied transit vertex' network. 2.1.1.0 OSPF-lite operation on non-broadcast multi-access networks As mentioned previously, OSPF-lite runs over non-broadcast networks in one of two modes: OSPF-lite-stub or OSPF-lite-transit depending on whether another router is present and sending Router LSAs and Hellos. There is however a slight difference with NBMA networks; OSPF-lite sees that the network is NBMA, from inspection of the MIB If database and operates in the following way: In the router LSA, the IP NBMA network is represented as a standard OSPF-lite-stub or OSPF-lite-transit network as normal. However an extra link of type OSPF-lite-stub is also introduced into the router LSA. This link includes the full 32-bit IP address of the interface on the network. This leads eventually to a 32-bit host route to the interface, which facilitates routing of packets to non fully meshed Thomas et al [Page 18] Internet Draft August 2007 nodes over the NBMA network. See Section 2.2.1 for a graph example. This accomplishes routing over a non fully meshed NBMA network in a similar way to the operation of a point-to-multipoint interface in OSPF V2. Unlike OSPF point-to-multipoint networks, all the routers on an NBMA network have fully meshed adjacencies. They all have FULL neighbor relationships with each other. The additional 32-bit route introduced into the Router LSA ensures that non fully meshed neighbors can communicate via routing. As the packets are sourced from and destined to the same network, the neighbor relationships can be formed even if the packets are forwarded via a third party. Section 16.0.7.1, outlines a recommendation that these 32-bit host routes are added to the routing table before the remainder of the processing. It is worth remembering that lower layers may need static Layer 2 to layer 3 mapping, including broadcast or static neighbors in some circumstances, to ensure that the packets can be transmitted on the medium. This is a medium issue and not a protocol issue. 2.1.1.1 OSPF-lite allows Vendors to implement a manual network type If the router's vendor has enabled the interface to be seen as 'point-to-point' in some manual way, then this is supported also. An NBMA network masquerading as a point-to-point link type, is treated like a real point-to-point type, i.e. the 32-bit mask is not added. In any case OSPF-lite treats all networks as firstly OSPF-lite-stub, and then OSPF-lite-transit. Concerning again the Layer 2 layer 3 issues of mapping multicasts and broascasts (used by the OSPF-lite Hello protocol), some non-broadcast networks' data-link protocols such as Frame Relay Inverse ARP will allow automatic mapping of IP addresses to the lower layer2 identifiers. This can allow broadcast facilities on the medium. 2.1.2. An example link-state database Figure 2 shows a sample map of an Autonomous System. Lines between routers indicate physical point-to-point networks. All point-to-point networks have interface addresses. Routers RT5 and RT7 have BGP connections to other Autonomous Systems. A set of BGP-learned routes are indicated by N12, N13, N14, and N15. These are displayed as connected to these routers. Notice that N12 is accessable through both RT5 and RT7. Thomas et al [Page 19] Internet Draft August 2007 A cost is associated with the output side of each router interface. This cost is configurable by the system administrator. The lower the cost, the more likely the interface is to be used to forward data traffic. Costs are also associated with the externally derived routing data (e.g., the BGP-learned routes N12, N13, N14, and N15). The link-state database is pieced together from LSAs generated by the routers. Only the Routers have LSAs. The information for the graph for the networks is embedded in the Router LSAs. Router RT12 for example has an interface to two broadcast networks. All of the link types in the LSAs and associated graph are described in the Router LSAs as either OSPF-lite-stub, or OSPF-lite-transit. Thomas et al [Page 20] Internet Draft August 2007 + | 3+---+ external; N12 N13 N14 N1|--|RT1|\ 1 \ | / | +---+ \ 8\ |8/8 + \ ____ \|/ / \ 1+---+8 8+---+6 * N3 *---|RT4|------|RT5|--------+ \____/ +---+ N19 +---+ | + / | |7 | | 3+---+ / | N18| | N2|--|RT2|/1 |1 |6 N17| | +---+ +---+8 6+---+ | + |RT3|--------------|RT6| | +---+ N5 +---+ | |2 |7 | | | | +---------+ | | N4 | | | | N16 | | N11 | |external; +---------+ | | | | | N12 |3 | |6 2/ +---+ | +---+/ |RT9| | |RT7|---N15 +---+ | +---+ 9 |1 + | |1 _|__ | |5 __|_ / \ 1+----+2 | 3+----+1 / \ * N9 *------|RT11|----|---|RT10|---* N6 * \____/ +----+ | +----+ \____/ | | | |1 + |1 +----+ N8 +---+ |RT12| |RT8| +----+ +---+ |2 |4 | | +---------+ +--------+ N10 N7 Figure 2: A sample Autonomous System Thomas et al [Page 21] Internet Draft August 2007 2.1.2.1 Options for creating the network graph: Two Pass SPF Routers are always considered as transit vertices in OSPF-lite. A Router vertex is represented by a transit vertex having both incoming and outgoing edge costs. All of the data to represent the network graph is located in the Router LSAs, and can be extracted in any way to produce the graph. One suggestion already made was that of an implied transit vertex. A further suggestion is the implementation of a two-stage calcuation. OSPF version 2 recommends two stages of calculation. In the first stage the main processing is achieved, and in the second stage stub vertices are added to the first calculation. The following sections discuss implementation of this procedure, if it is required: 2.1.2.2 Building stub vertices for all networks: Two stages system For the purposes of running an SPF calculation it is sometimes preferable to have vertices for all networks. The vertices do not have to be transit vertices. OSPF version 2 recommends running a first SPF stage with only the transit vertices. The stub vertices are then added after a table look-up or a 'second pass' of calculations. To achieve this second stage, the OSPF-lite-stub networks, and also the OSPF-lite-transit networks that did are not represented by an implied vertex, gain an implied STUB vertex. The vertices they gain are NOT transit, and can be processed as 'stub vertices'. 2.1.2.3 Summary of protocol specific graphing terms: Two Stage Implied arc: The connection between routers (in the network graph) from information gleaned from the Router LSAs. Vertex: Vertices can be transit or stub. Transit vertex: A vertex that is a full part of the SPF iteration. Implied Transit vertex: these vertices are also fully transit, but are built from information in the database with no corresponding dedicated LSA. Implied Stub vertex: this is a vertex that is not transit, and is added in the second stage of processing. They represent all of the ospf-lite stub networks, and some of the ospf-lite-transit networks. Stub and Transit vertices are related to the OSPF-lite types but are not the same term and do not always co-incide. OSPF-lite-stub and OSPF-lite-transit are network types. Stub and Transit vertices are graph representations of the LSAs. Thomas et al [Page 22] Internet Draft August 2007 2.1.2.4 Information graph resulting from the Router LSAs TRANSIT VERTICES (pass 1) ------------------------- Implied |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|T Vertex |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N9| ----- ------------------------------------------- RT1| | | | | | | | | | | | |0 | | | RT2| | | | | | | | | | | | |0 | | | RT3| | | | | |6 | | | | | | |0 | | | RT4| | | | |8 | | | | | | | |0 | | | RT5| | | |8 | |6 |6 | | | | | | | | | RT6| | |8 | |7 | | | | |5 | | | | | | RT7| | | | |6 | | | | | | | | |0 | | RT8| | | | | | | | | | | | | |0 | | RT9| | | | | | | | | | | | | | |0 | RT10| | | | | |7 | | | | |2 | | |0 | | RT11| | | | | | | | | |3 | | | | |0 | RT12| | | | | | | | | | | | | | |0 | Implied T Vertex N3|1 |1 |1 |1 | | | | | | | | | | | | Implied T Vertex N6| | | | | | |1 |1 | |1 | | | | | | Implied T Vertex N9| | | | | | | | |1 | |1 |1 | | | | ---------------------------------------------------------------- STUB VERTICES (pass 2) ---------------------------------------------------------------- o-lite-stub N1|3 | | | | | | | | | | | | | | | o-lite-stub N2| |3 | | | | | | | | | | | | | | o-lite-stub N4| | |2 | | | | | | | | | | | | | o-lite-stub N7| | | | | | | |4 | | | | | | | | o-lite-stub N10| | | | | | | | | | | |2 | | | | o-lite-stub N11| | | | | | | | |3 | | | | | | | ---------------------------------------------------------------- STUB VERTICES (pass 2) cont... ---------------------------------------------------------------- o-lite-transit N5| | |8 | | |6 | | | | | | | | | | o-lite-transit N8| | | | | | | | | |3 |2 | | | | | o-lite-transit N16| | | | | |7 | | | |5 | | | | | | o-lite-transit N17| | | | |6 | |6 | | | | | | | | | o-lite-transit N18| | | | |7 |6 | | | | | | | | | | o-lite-transit N19| | | |8 |8 | | | | | | | | | | | ---------------------------------------------------------------- STUB VERTICES (pass 2) cont... ---------------------------------------------------------------- external lsa5 N12| | | | |8 | |2 | | | | | | | | | external lsa5 N13| | | | |8 | | | | | | | | | | | external lsa5 N14| | | | |8 | | | | | | | | | | | external lsa5 N15| | | | | | |9 | | | | | | | | | Figure 3 Data stored from the Router LSAs Thomas et al [Page 23] Internet Draft August 2007 The information resulting from the map in Figure 2 is depicted in Figure 3. Arcs are labelled with the cost of the corresponding router output interface. Arcs having no labelled cost have a cost of 0. Arcs leading from network 'Implied Vertices' (if used) always have a cost of 0. Networks N3, N6 and N9 are candidates for network 'Implied transit vertices' as they have more than two routers present on the OSPF-lite-transit networks. Network N6 for example is a broadcast network with three attached routers. As there are more than two routers, this could be represented by an implied transit vertex. The cost of all links from Network N6 (if using an implied transit vertex) to its attached routers is 0. The externally derived routing data appears on the graph as stub vertices in the second stage of the calculation. Externally derived networks have their own LSA type, Type 5. These are implemented as in OSPF Version 2. See Section 2.3. 2.1.2.5 Network graph for first pass SPF calcuation: Two Stage The graph for the primary SPF calculation if the two pass system is used is shown below in Figure 4: |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|Implied vertex |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N9| ----- ------------------------------------------- RT1| | | | | | | | | | | | |0 | | | RT2| | | | | | | | | | | | |0 | | | RT3| | | | | |6 | | | | | | |0 | | | RT4| | | | |8 | | | | | | | |0 | | | RT5| | | |8 | |6 |6 | | | | | | | | | RT6| | |8 | |7 | | | | |5 | | | | | | RT7| | | | |6 | | | | | | | | |0 | | RT8| | | | | | | | | | | | | |0 | | RT9| | | | | | | | | | | | | | |0 | RT10| | | | | |7 | | | | |2 | | |0 | | RT11| | | | | | | | | |3 | | | | |0 | RT12| | | | | | | | | | | | | | |0 | Implied Vertex N3|1 |1 |1 |1 | | | | | | | | | | | | Implied Vertex N6| | | | | | |1 |1 | |1 | | | | | | Implied Vertex N9| | | | | | | | |1 | |1 |1 | | | | Figure 4 The resulting primary directed graph Thomas et al [Page 24] Internet Draft August 2007 **FROM |N9|N10| ------------ **TO** RT12|1 | 2 ¦ RT12's router-LSA Router LSA Type 1 contains: Network 9 link type is OSPF-lite-transit Network 10 link type is OSPF-lite-stub Figure 4.1 This leads to the following first pass SPF tree: RT6(origin) RT5 o-----------o 6 |\ 7 | \ 6| \ | \ | \ 2| \ N4 o-----o RT3 \ /1 \ / RT10 o / |\1 RT4 o-----o N3 3| \ /| | \ N6 RT7 / | | o---------o / | | | RT2 o o RT1 | | | |RT8 RT11 o o 1| | | N9 o /| / | RT9 / |RT12 o o Figure 5: First pass SPF tree for RT6 Thomas et al [Page 25] Internet Draft August 2007 The second pass then adds the other networks as stub vertices to the SPF tree although this is a matter of implementation. Note also that in the router LSA the point-to-point networks are seen as OSPF-lite-transit networks. When using this two-pass method, the point-to-point networks are not included in the first pass. They are then added as 'stub vertices' in the second pass. The information from the router LSA has been used already to connect the two routers attached to the point-to-point network together as an implied arc in the database. 2.2. The full resulting shortest-path tree Each OSPF-lite router in the Autonomous System has an identical link-state database, implying an identical graphical representation. A router generates its routing table from this graph by calculating a tree of shortest paths with the router itself as root. Obviously, the shortest-path tree depends on which router is doing the calculation, and is therefore acting as the root of the SPF tree. The shortest-path tree for Router RT6 in our example is depicted in Figure 5. The tree can look as in Figure 5. This can vary slightly, depending on how the implied vertices are implemented, but the resulting routes and costs will be the same. The tree gives the entire path to any destination network. However, only the next hop to the destination is used in the forwarding process. Note also that the best route to any router has also been calculated. For the processing of external data, we note the next hop and distance to any router advertising external routes. The resulting routing table for Router RT6 is shown in Table 2. Thomas et al [Page 26] Internet Draft August 2007 RT6(origin) N17 o \ \6 N18 o 6 8 \RT5 6 \RT6 N19 o-----o------------o----o N16 /|\ 6/ |\ 7 8/8|8\ / 6| \7 / | \ o | \ o | o N3 | \ N12 o N14 | \ N13 2 | \ N4 o-----o RT3 \ / \ 1/ RT10 o / |\ RT4 o-----o N3 3| \1 /| | \ N6 RT7 / | N8 o o---------o / | | | /| RT2 o o RT1 | | 2/ |9 / | | |RT8 / | /3 |3 RT11 o o o o / | | | N12 N15 N2 o o N1 1| |4 | | N9 o o N7 /| / | N11 RT9 / |RT12 o--------o-------o o 3 | |2 | o N10 Figure 6: Full SPF tree for Router RT6 Thomas et al [Page 27] Internet Draft August 2007 Destination Next Hop Distance __________________________________ N1 RT3 10 N2 RT3 10 N3 RT3 7 N4 RT3 8 N5 self 6 (A connected route is preferred over OSPF-lite) N6 RT10 8 N7 RT10 12 N8 RT10 10 N9 RT10 11 N10 RT10 13 N11 RT10 14 N12 RT5 14 N13 RT5 14 N14 RT5 14 N15 RT10 17 N16 self 7 N17 RT5 12 (A connected route is preferred over OSPF-lite) N18 self 6 (A connected route is preferred over OSPF-lite) N19 RT5 14 __________________________________ RT5 RT5 6 RT7 RT10 8 Table 2: The portion of Router RT6's routing table listing local destinations. The routers are shown in the ospf-lite routing table. The routing table is merely showing the OSPF-lite routes that will be offered to the main routing table of the router. Other protocols may have routes with a prefereable administrative distance. The routes to the routers RT5 and RT7 are not offerred to the main routing table and are only stored in the OSPF-lite routing table as an aid to calculting the SPF tree. Where this document simply refers to a 'routing table' the OSPF-lite table is meant, not the main routing function of the device. The externally derived routing information is considered in the next section. Thomas et al [Page 28] Internet Draft August 2007 2.2.1. NBMA network example with LSA and graph Figure 7.1 shows a Frame Relay network with three attached routers The routers are not fully meshed. There is no PVC between RT102 and RT103. All of the routers are on the same IP subnetwork. For data to be passed between RT102 and RT103, there must be a 32-bit host route in RT101 to both RT102 and RT103. OSPF-lite adds an extra link to the Router LSA 1's, of type OSPF-lite-stub. This link contains the 32-bit IP adddress of the connected interface. Figure 7.2 shows the router LSA generated by RT101, and the additional link. +-----+ +-----+ |RT101| |RT102| +-----+ +-----+ 3 *|* * /3 Interface 1.1.1.1 /24 *|* * /Interface 1.1.1.2 /24 link N21 1.1.1.1 /32 *|* * / link N22 1.1.1.2 /32 *|* * / PVC1 *|* PVC2 * / *|* * / *|* * / *|* * / * | * * / * | * * * / * __|______ /___ * | |N20 * | (NBMA) |(Implied vertex) * | 1.1.1.0 /24 | * |______________| * | * | * | * | * | link N23 1.1.1.3 /32 * 3| Interface 1.1.1.3 /24 +-----+ |RT103| +-----+ Figure 7.1 Router 101's LSA Router101: 2 links linkID: OSPF-lite-transit 1.1.1.1 255.255.255.0 linkID: OSPF-lite-stub 1.1.1.1 255.255.255.255 Figure 7.2 Thomas et al [Page 29] Internet Draft August 2007 |RT101 |RT102 |RT103 | N20 | (Implied vertex) RT101 | | | | 0 | RT102 | | | | 0 | RT103 | | | | 0 | Implied Vertex N20 | 3 | 3 | 3 | - | ------------------------------------------------ o-lite-stub N21 | 3 | | | | o-lite-stub N22 | | 3 | | | o-lite-stub N23 | | | 3 | | Finally Figure 7.3 shows the resulting SPF tree for this small network. N21, N22 and N23 are shown as stub vertices hanging off the router transit vetices. RT101 (origin) RT101 o 3/ \3 / oN21 RT102 / o--------o N20 3/ \ / \ o \RT103 N22 o-------oN23 3 Figure 7.3 SPF tree from router 101 This is implemented on all NBMA interfaces, but not on interfaces manually overridden to be point-to-point (Section 2.1.1.1). For a full analysis of the LSA gerenated by RT101, and the extra host routes added to the table, refer to Sections 12.4.4.2, and 16.0.7.1. 2.2.1.1 Neighbors Adjacencies are fully meshed on NBMA networks RT101, RT102 and RT103 have adjacencies that are fully meshed. The packets are routed via RT101, from RT102 to RT103. This is acceptable as both the source of the packets and the destination are located on the same network (N20). Note: Section 16 recommends the preloading of the 32 bit host routes to the Main routing table on discovery, to facilitate the forwarding during adjacency establishment. See Section 16.0.7.1. 2.3. Use of external routing information The external routing information may originate from another routing protocol such as BGP, or be statically configured (static routes). Default routes can also be included as part of the Autonomous System's external routing information. Thomas et al [Page 30] Internet Draft August 2007 External routing information is flooded unaltered throughout the AS. In our example, all the routers in the Autonomous System know that Router RT7 has two external routes, with metrics 2 and 9. This information is carried by means of an LSA type 5 (external LSA). Note: OSPF-lite fully supports the two types of OSPF Version 2 external metrics. Type 1 external metrics are expressed in the same units as the OSPF-lite interface cost (i.e., in terms of the link state metric). Type 2 external metrics are an order of magnitude larger; any Type 2 metric is considered greater than the cost of any path internal to the AS. Use of Type 2 external metrics assumes that routing between AS's is the major cost of routing a packet, and eliminates the need for conversion of external costs to internal link state metrics. As an example of Type 1 external metric processing, assume that the Routers RT7 and RT5 in Figure 2 are advertising Type 1 external metrics. For each advertised external route, the total cost from Router RT6 is calculated as the sum of the external route's advertised cost and the distance from Router RT6 to the advertising router. When two routers are advertising the same external destination, RT6 picks the advertising router providing the minimum total cost. RT6 then sets the next hop to the external destination equal to the next hop that would be used when routing packets to the chosen advertising router. In Figure 2, both Router RT5 and RT7 are advertising an external route to destination Network N12. Router RT7 is preferred since it is advertising N12 at a distance of 10 (8+2) to Router RT6, which is better than Router RT5's 14 (6+8). Table 3 shows the entries that are added to the routing table when external routes are examined: Destination Next hop Distance ___________________________________ N12 RT10 10 N13 RT5 14 N14 RT5 14 N15 RT10 17 Table 3: The portion of Router RT6's routing table listing external destinations. Thomas et al [Page 31] Internet Draft August 2007 Processing of Type 2 external metrics is simpler. The AS boundary router advertising the smallest external metric is chosen, regardless of the internal distance to the AS boundary router. Assume in our example both Router RT5 and Router RT7 were advertising Type 2 external routes. Then all traffic destined for Network N12 would be forwarded to Router RT7, since 2 < 8. When several equal-cost Type 2 routes exist, the internal distance to the advertising routers is used to break the tie. Both Type 1 and Type 2 external metrics can be present in the AS at the same time. In that event, Type 1 external metrics always take precedence. This section has assumed that packets destined for external destinations are always routed through the advertising AS boundary router. This is not always desirable. For example, suppose in Figure 2 there is an additional router attached to Network N6, called Router RTX. Suppose further that RTX does not participate in OSPF-lite routing, but does exchange BGP information with the AS boundary router RT7. Then, Router RT7 would end up advertising OSPF-lite external routes for all destinations that should be routed to RTX. An extra hop will sometimes be introduced if packets for these destinations need always be routed first to Router RT7 (the advertising router). To deal with this situation, the OSPF-lite protocol allows an AS boundary router to specify a "forwarding address" in its AS- external-LSAs. In the above example, Router RT7 would specify RTX's IP address as the "forwarding address" for all those destinations whose packets should be routed directly to RTX. The "forwarding address" has one other application. It enables routers in the Autonomous System's interior to function as "route servers". For example, in Figure 2 the router RT6 could become a route server, gaining external routing information through a combination of static configuration and external routing protocols. RT6 would then start advertising itself as an AS boundary router, and would originate a collection of OSPF- lite AS-external-LSAs. In each AS-external-LSA, Router RT6 would specify the correct Autonomous System exit point to use for the destination through appropriate setting of the LSAs "forwarding address" field. 2.4. Equal-cost multipath The above discussion has been simplified by considering only a single route to any destination. In reality, if multiple equal-cost routes to a destination exist, they are all Thomas et al [Page 32] Internet Draft August 2007 discovered and used. This requires no conceptual changes to the algorithm, and its discussion is postponed until we consider the tree-building process in more detail. With equal cost multipath, a router potentially has several available next hops towards any given destination. 3. Splitting the AS into Areas Ospf-lite does not support areas. Ospf-lite is a simplified protocol that allows the router to 'roam' fully throughout the AS without needing reconfiguring. OSPF-lite fully supports external routes. Shielding an AS from Interet routes can be accomplished by running multiple smaller AS's of the protocol and resdistributing selected route destination. OSPF-lite fully supports the use of external LSAs (type 5), and the use of both Supernet and VLSM routes. 3.1. The backbone of the Autonomous System For consistencey with OSPF V2, the single OSPF-lite area is numbered 0.0.0.0 This looks similar to the backbone area of OSPF Version 2. This allows OSPF-lite, to use all of the packet structures (Appendix A) that are used in OSPF Version 2 3.2. Not applicable 3.3. Classification of routers AS boundary routers A router that exchanges routing information with routers belonging to other Autonomous Systems. Such a router advertises AS external routing information throughout the Autonomous System. The paths to each AS boundary router are known by every router in the AS. 3.4. Not applicable 3.5. IP subnetting support Ospf-lite fully supports the use of supernet and subnet routes including VLSM. (ref RFC2328 3.5) 3.6. Not applicable 3.7. Not applicable Thomas et al [Page 33] Internet Draft August 2007 4. Functional Summary A brief summary of the routing algorithm follows. When a router starts, it first initializes the routing protocol data structures. The router then waits for indications from the lower-level protocols that its interfaces are functional. A router then uses the OSPF-LITE's Hello Protocol to acquire neighbors. The router sends Hello packets to its neighbors, and in turn receives their Hello packets. On all networks, the router dynamically detects its neighboring routers by sending its Hello packets to the multicast address AllSPFRouters. OSPF-lite switches the hellos to unicast packets as soon as a neighbor is seen in ANY arriving hello. this is different to OSPF Version 2. the Hello protocol continues to use the Unicast addresses. see Section 7.1.1. Flooding still uses the multicast address AllSPFRouters. OSPF-lite does NOT use Designated Routers or Backup Designated routers. The router will attempt to form adjacencies with ALL of its newly acquired neighbors. Link-state databases are synchronized between all pairs of adjacent routers. Adjacencies control the distribution of routing information. Routing updates are sent and received to all neighbors, using the Flooding protocol AllSPFRouter multicast. A router periodically advertises its state, which is also called link state. Link state is also advertised when a router's state changes. A router's adjacencies are reflected in the contents of its LSAs. This relationship between adjacencies and link state allows the protocol to detect non-functioning routers in a timely fashion. LSAs are flooded throughout the AS. The flooding algorithm is reliable, ensuring that all routers in an area have exactly the same link-state database. This database consists of the collection of LSAs originated by each router belonging to the AS. From this database each router calculates a shortest-path tree, with itself as root. This shortest-path tree in turn yields a routing table for the protocol. Thomas et al [Page 34] Internet Draft August 2007 4.1. Not applicable 4.2. AS external routes Routers that have information regarding other Autonomous Systems can flood this information throughout the AS. This external routing information is distributed verbatim to every participating router in an external LSA (type 5). 4.3. Routing protocol packets The OSPF-lite protocol runs directly over IP, using IP protocol 89. OSPF-lite does not provide any explicit fragmentation/ reassembly support. When fragmentation is necessary, IP Fragmentation /reassembly is used. OSPF-LITE protocol packets have been designed so that large protocol packets can generally be split into several smaller protocol packets. This practice is recommended; IP fragmentation should be avoided whenever possible. Routing protocol packets should always be sent with the IP TOS field set to 0. If at all possible, routing protocol packets should be given preference over regular IP data traffic, both when being sent and received. As an aid to accomplishing this, OSPF-lite protocol packets should have their IP precedence field set to the value Internetwork Control (see [Ref5]). All OSPF-lite protocol packets share a common protocol header that is described in Appendix A. The OSPF-lite packet types are listed below in Table 4. Their formats are also described in Appendix A. Type Packet name Protocol function __________________________________________________________ 1 Hello Discover/maintain neighbors 2 Database Description Summarize database contents 3 Link State Request Database download 4 Link State Update Database update 5 Link State Ack Flooding acknowledgment Table 4: OSPF-lite packet types. These packet types and protocol header are the same as OSPF Version 2. OSPF-lite differs only in the version number of the Packet header. OSPF-lite is currently waiting for a Version number indicator to be assigned. Thomas et al [Page 35] Internet Draft August 2007 OSPF-lite's Hello protocol uses Hello packets to discover and maintain neighbor relationships. The Database Description and Link State Request packets are used in the forming of adjacencies. OSPF-lites's reliable update mechanism is implemented by the Link State Update and Link State Acknowledgment packets. Each Link State Update packet carries a set of new link state advertisements (LSAs) one hop further away from their point of origination. A single Link State Update packet may contain the LSAs of several routers. Each LSA is tagged with the ID of the originating router and a checksum of its link state contents. Each LSA also has a type field; the different types of OSPF-lite LSAs are listed in Table 5. Please note, that while OSPF-lite is a slimmed down protocol, there is full support for Opaque LSA's type 9, 10, and 11. [ref7]This enables OSPF-lite to be compliant with TE Extensions for OSPF.[ref9] Multiple areas are not supported. LSA type 10s are therefore flooded throughout the single 0.0.0.0 AS. OSPF-LITE routing packets are sent over all neighbors. Unlike OSPF Version 2, OSPF-lite creates adjacencies with all directly connected neighbors. This means that all OSPF-lite protocol packets travel a single IP hop. OSPF-lite does also not support Virtual links. This means that OSPF-lite packets normally always travel over 1 hop. (unless there is tunnelling involved or some other mechanism). The IP source address of an OSPF-lite protocol packet is one end of a router adjacency, and the IP destination address is either the other end of the adjacency or an IP multicast address. The The address of 224.0.0.5 ALLSPFRouters is used by the router initially on attachment to a network. Once ANY neighbor is either; directly heard from or referenced in a hello packet from another neighbor, the destination address of the Hello packets being sent by the router is changed to a unicast for that particular neighbor, and the router will attempt to contact the neighbor directly. This means a router may generate more than one Hello packet per interface. The Hello packets continue from this point to be unicast. The resulting Database Description and Exchange packets are also unicast, but for flooding the LSUpdates are again sent to the multicast address AllSPFRouters. 4.4. Basic implementation requirements An implementation of OSPF-lite requires the following pieces of system support: Thomas et al [Page 36] Internet Draft August 2007 Timers Two different kind of timers are required. The first kind, called "single shot timers", fire once and cause a protocol event to be processed. The second kind, called "interval timers", fire at continuous intervals. These are used for the sending of packets at regular intervals. A good example of this is the regular broadcast of Hello packets. The granularity of both kinds of timers is one second. MAXage in ospf-lite is set to 1 hour. See Appendix C for details on MAXage timer. This value should allow maximum spread of LSUpdates while resending the Databse when refreshing. LS LSA LSA description type name __________________________________________________________________ 1 Router-LSAs Originated by all routers. This LSA describes the collected states of the router's interfaces to the single area. Flooded throughout the single AS. __________________________________________________________________ 5 AS-external-LSAs Originated by AS boundary routers, and flooded through-out the AS. Each AS-external-LSA describes a route to a destination in another Autonomous System. Default routes for the AS can also be described by AS External LSAs __________________________________________________________________ 9 Opaque LSA Link Local __________________________________________________________________ 10 Opaque LSA Area wide (ospf-lite AS has single area) __________________________________________________________________ 11 Opaque LSA AS Wide __________________________________________________________________ Table 5: OSPF-lite link state advertisements (LSAs). IP multicast Certain OSPF-lite packets take the form of IP multicast datagrams. Support for receiving and sending IP multicast datagrams, along with the appropriate lower-level protocol support, is required. The IP multicast datagrams used by OSPF- lite never travel more than one hop. For this reason, the ability to forward IP multicast datagrams is not required. For information on IP multicast, see [ref8]. Thomas et al [Page 37] Internet Draft August 2007 Variable-length subnet support. The router's IP protocol support must include VLSM and Supernetting. For more information on IP supernetting, see [ref4]. Lower-level protocol support including NBMA. Indications must be passed from these protocols to OSPF-lite as the network interface goes up and down. For example, on an ethernet it would be valuable to know when the Ethernet transceiver cable becomes unplugged. On an X.25 PDN a dead neighboring router may be indicated by the reception of a X.25 clear with an appropriate cause and diagnostic, and this information would be passed to OSPF-lite. 4.5. Optional OSPF-lite capabilities The options field from OSPF V2 has been retained in ospf-lite. This is to provide future support for added features. This will enable routers supporting a mix of optional capabilities to coexist in a single Autonomous System. Some capabilities must be supported by all routers attached to an AS. In this case, a router will not accept a neighbor's Hello Packet unless there is a match in reported capabilities (i.e., a capability mismatch prevents a neighbor relationship from forming). An example of this is the ExternalRoutingCapability (see below). Other capabilities can be negotiated during the Database Exchange process. This is accomplished by specifying the optional capabilities in Database Description packets. The OSPF-lite optional capabilities defined in this memo are listed in Section A.2, but include the ExternalRoutingCapability and the Opaque LSA option. ExternalRoutingCapability OSPF-lite does not support Stub Areas so All LSA's are flooded into the single default area. It is mandatory for OSPF-lite to have the E bit set in the corresponding Router1 LSA options field. Thomas et al [Page 38] Internet Draft August 2007 5. Protocol Data Structures The OSPF-LITE protocol is described herein in terms of its operation on various protocol data structures. The following list comprises the top-level OSPF-LITE data structures. Any initialization that needs to be done is noted. Interfaces and neighbors also have associated data structures that are described later in this specification. Router ID If the router's OSPF-LITE Router ID is changed, the router's OSPF-lite software should be restarted before the new Router ID takes effect. In this case the router should flush its self- originated LSAs from the routing domain (see Section 14.1), before restarting, or they may persist in some circumstances for up to MaxAge minutes. Area structures There is not support for Areas in Ospf-lite. List of external routes These are routes to destinations external to the Autonomous System, that have been gained either through direct experience with another routing protocol (such as BGP), or through configuration information, or through a combination of the two (e.g., dynamic external information to be advertised by OSPF- lite with configured metric). Any router having these external routes is called an AS boundary router. These routes are advertised by the router into the OSPF-lite routing domain via AS-external-LSAs. (LSA Type 5). These LSA's are fully supported by OSPF-lite. List of AS-external-LSAs Part of the link-state database. These have originated from the AS boundary routers. They comprise routes to destinations external to the Autonomous System. Note that, if the router is itself an AS boundary router, some of these AS-external-LSAs have been self-originated. The routing table This refers to the ospf-lite routing table and not the main routing table for the device. Often multiple IGPs are running, and a system of administrative distance in the main routing table is used to select the most appropriate route. The ospf-lite routing table is Derived from the link-state database. Each entry in the routing table is indexed by a destination, and contains the Thomas et al [Page 39] Internet Draft August 2007 destination's cost and a set of paths to use in forwarding packets to the destination. A path is described by its type and next hop. [ref1] 6. The AS Data Structure Multiple areas are not supported in OSPF-lite. Area ID An 'Area' ID of 0.0.0.0 is used in this field for OSPF-lite. List of router-LSAs A router-LSA is generated by each router. It describes the state of the router's participating interfaces. Shortest-path tree The shortest-path tree for the AS, with this router itself as root. Derived from the collected router-LSAs and External-LSAs by the Dijkstra algorithm (see Section 16.1). ExternalRoutingCapability This is mandatory in OSPF-lite. 7. Bringing Up Adjacencies OSPF-lite always creates adjacencies between neighboring routers for the purpose of exchanging routing information. Every two neighboring, and communicating routers will become adjacent. This section covers the generalities involved in creating adjacencies. For further details consult Section 10. 7.1. The Hello Protocol The Hello Protocol is responsible for establishing and maintaining neighbor relationships. It also ensures that communication between neighbors remains bidirectional. Hello packets are sent periodically out all router interfaces. Bidirectional communication is indicated when the router sees itself listed in the neighbor's Hello Packet. 7.1.1 ospf-lite Hello protocol differences ospf-lite has some differences to OSPF Version 2 in the way that it operates the Hello protocol; Thomas et al [Page 40] Internet Draft August 2007 The Hello protocol initiates on an interface by using the ip multicast address ALLSPFRouters, but moves to a unicast directed packet: A router starts by send a multicast to AllSPFRouters indicating any neighbors that it may know about. With Ospf-lite, if a Hello packet arrives that lists any neighbor, EVEN a neighbor that it has NOT seen a Hello packet from (perhpas due to a non fully meshed NBMA network for example), it will attempt to contact that neighbor directly on the neighbors listed unicast address. (This is different from OSPF version 2 which requires the Hello packet to arrive from the neighbor directly). The Hello packets are unicast from this point onwards. The hello packets all still retain a full list of ALL neighbors found on that interface, but the packets are unicast individually to each neighbor as they become aware of them. This is done before bidirectional communication is reached. After a router has seen itsef listed directly in a neighbor's Hello packet, bidirectional communication is ensured. Any new neighbor attached to the network will send out a multicast Hello packet, which will be seen by one of the existing routers on the network. This existing router will then; both advertise the new router in the unicast Hello packets to the other attached routers, and also will attempt to connect to the new router in a unicast fashion as described. The next step is to synchronize the neighbors' link-state databases. 7.2. The Synchronization of Databases In a link-state routing algorithm, it is very important for all routers' link-state databases to stay synchronized. OSPF-lite requires full synchronisation between all neighbors regardless of media. The synchronization process begins as soon as the routers attempt to bring up the adjacency. Each router describes its database by sending a sequence of Database Description packets to its neighbor. Each Database Description Packet describes a set of LSAs belonging to the router's database. When the neighbor sees an LSA that is more recent than its own database copy, it makes a note that this newer LSA should be requested. This sending and receiving of Database Description packets is called the "Database Exchange Process". During this process, the two routers form a master/slave relationship. Each Database Description Packet has a sequence number. Database Description Packets sent by the master (polls) are acknowledged by the slave through echoing of the sequence number. Both polls and their Thomas et al [Page 41] Internet Draft August 2007 responses contain summaries of link state data. The master is the only one allowed to retransmit Database Description Packets. It does so only at fixed intervals, the length of which is the configured per-interface constant RxmtInterval. Each Database Description contains an indication that there are more packets to follow --- the M-bit. The Database Exchange Process is over when a router has received and sent Database Description Packets with the M-bit off. During and after the Database Exchange Process, each router has a list of those LSAs for which the neighbor has more up-to-date instances. These LSAs are requested in Link State Request Packets. Link State Request packets that are not satisfied are retransmitted at fixed intervals of time RxmtInterval. When the Database Description Process has completed and all Link State Requests have been satisfied, the databases are deemed synchronized and the routers are marked fully adjacent. At this time the adjacency is fully functional and is advertised in the two routers' router-LSAs (by the inclusion of the network on the router links). Ospf-lite also implements the ospf-lite-stub and ospf-lite-transit mechanism. Both the Adjacency and the Router LSAs listing the attached network are required in order to move the network type to ospf-lite transit. For ospf-lite-stub ospf-lite-transit mechanism see Section 2.1.0.5. First the Adjacency is built, and then the Router LSA type 1's are sent. When the router sees the type 1 referencing the same network that it is attached to, from a directly sent type 1, then it alters the network type in its LSA from ospf-lite-stub, to ospf-lite-transit, and resends the LSA with an incremented LS-sequence number. Both the Hellos and the recieved LSA type 1 referencing the connected network are required for the type to change in the router LSA. 7.3. Removal of the Designated Router OSPF-lite does not use the principle of Designated Router, and does not generate or support network LSA's. 7.4. Not applicable 7.5. The graph of adjacencies ALL directly connected neighbors in OSPF-lite are Adjacent. An adjacency is bound to the network that the two routers have in common. If two routers have multiple networks in common, they may have multiple adjacencies between them. See Section 2.1.0.9, and 2.1.2.4 for graph examples. Thomas et al [Page 42] Internet Draft August 2007 8. Protocol Packet Processing This section discusses the general processing of OSPF-lite routing protocol packets. It is important that the router link-state databases remain synchronized, hence routing protocol packets should receive preferential treatment over other data packets, both when they are being sent and being received. All OSPF-lite routing protocol packets travel a single IP hop. All routing protocol packets begin with a standard header. The sections below describe its division into fields and show how it is verified. Then, for each packet type, the section which provides further details is specified. 8.1. Sending protocol packets When a router sends a routing protocol packet, it fills in the fields of the standard OSPF-lite packet header as follows. For more details about the header format consult Section A.3.1: Version # The version number of OSPF-lite has not yet been designated. Packet type The type of OSPF-lite packet, such as Link state Update or Hello Packet. Packet length The length of the entire OSPF-lite packet in bytes, including the standard OSPF-lite packet header. Router ID The identity of the router itself which is originating the packet. [2] Area ID This field of the OSPF-lite packet must be set to 0.0.0.0 because multiple areas are not supported with OSPF-lite. Checksum The standard IP 16-bit one's complement checksum of the entire OSPF-lite packet, excluding the 64-bit authentication field. This checksum is calculated as part of the appropriate authentication procedure; for some OSPF-lite authentication types, the checksum calculation is omitted. See Section D.4 for details. Thomas et al [Page 43] Internet Draft August 2007 AuType and Authentication Each OSPF-lite packet exchange is authenticated. Authentication types are assigned by the protocol and are documented in Appendix D. A different authentication procedure can be used for each IP network/subnet. Autype indicates the type of authentication procedure in use. The 64-bit authentication field is then available for use by the chosen authentication procedure. This procedure should be the last called when forming the packet to be sent. See Section D.4 for details. The IP destination address for the packet is selected as follows. Initial Hellos use the multicast address AllSPFRouters. OSPF Hellos always follow this rule, unless neighbors are statically configured. this is NOT recommended. The address for the Hellos changes to a directed unicast upon hearing about a neighbor as explained in Section 7.1 and 7.1.1. The majority of OSPF-lite packets though are sent as unicasts, i.e., sent directly to the other end of the adjacency. This is true for DD packets, LSRequests, LS Updates, and LS Acks. In this case, the IP destination is the Neighbor IP address associated with the other end of the adjacency. Retransmissions of Link State Update packets are ALWAYS sent directly to the neighbor. The IP source address should be set to the IP address of the sending interface. Un-numbered point-to-point interfaces are supported, but not encouraged. In this case the IP source address of the packet is the 'borrowed' Interface address. 8.2. Receiving protocol packets Whenever a protocol packet is received by the router it is marked with the interface on which it was received. In order for the packet to be accepted at the IP level, it must pass a number of tests, even before the packet is passed to OSPF-lite for processing: o The IP checksum must be correct. o The packet's IP destination address must be the IP address of the receiving interface, or the IP multicast address AllSPFRouters. Thomas et al [Page 44] Internet Draft August 2007 o The IP protocol specified must be OSPF-lite (89). o Locally originated packets should not be passed on to OSPF- lite. That is, the source IP address should be examined to make sure this is not a multicast packet that the router itself generated. Next, the OSPF-lite packet header is verified. The fields specified in the header must match those configured for the receiving interface. If they do not, the packet should be discarded: o The version number field must specify the correct protocol version (still to be designated). o The Area ID found in the OSPF-lite header must be 0.0.0.0. o The packet has been sent over a single hop, therefore it is a requirement that the packet's IP source address is on the same network as the receiving interface. o The AuType specified in the packet must match the AuType specified for the AS. o The packet must be authenticated. The authentication procedure employed is indicated by the setting of AuType (see Appendix D). It may use one or more Authentication keys, which can be configured on a per-interface basis. It may also verify the checksum field in the OSPF-lite packet header (which, when used, is set to the standard IP 16-bit one's complement checksum of the OSPF-lite packet's contents after excluding the 64-bit authentication field). If the authentication procedure fails, the packet should be discarded. If the packet type is Hello, it should then be further processed by the Hello Protocol. At this point all received protocol packets are associated with an active neighbor. Fro further specific packets types consult the sections listed in Table 6. Thomas et al [Page 45] Internet Draft August 2007 Type Packet name detailed section (receive) ________________________________________________________ 1 Hello Section 10.5 2 Database description Section 10.6 3 Link state request Section 10.7 4 Link state update Section 13 5 Link state ack Section 13.7 Table 6: Sections describing OSPF-lite protocol packet reception. 9. The Interface Data Structure The following data items are associated with an interface. Note that a number of these items are actually configuration information for the attached network; such items must be identical for all routers connected to the network. Type The OSPF-lite interface type is either OSPF-lite-stub, or OSPF-lite-transit. This is not the same as in OSPF Version 2, and also is independent of the underlying media type or technology. NBMA Y/N It is also important for OSPF-lite to indicate whether the interface is NBMA. This is not sent in any of the LSAs, but taken from the MIB and stored for reference by the protocol. This can also be manually configured or overridden. State The functional level of an interface. State determines whether or not full adjacencies may be formed over the interface. IP interface address The IP address associated with the interface. This appears as the IP source address in all routing protocol packets originated by this interface. Interfaces to unnumbered point-to-point networks do not have an associated IP address. Unnumbered point-to- point interfaces are supported but not recommended with OSPF-lite. Their OSPF-lite type is stub or transit as previously stated. IP interface mask Also referred to as the subnet mask, this indicates the portion of the IP interface address that identifies the attached network. Masking the IP interface address with the IP interface mask yields the IP network number of the attached network. Thomas et al [Page 46] Internet Draft August 2007 HelloInterval The length of time, in seconds, between the Hello packets that the router sends on the interface. This is advertised in Hello packets sent out by this interface. RouterDeadInterval The number of seconds after a router's neigbors stop hearing its Hello packets, before they will declare it down. Advertised within Hello packets sent out this interface. InfTransDelay The estimated number of seconds it takes to transmit a Link State Update Packet over this interface. LSAs contained in the Link State Update packet will have their age incremented by this amount before transmission. This value should take into account transmission and propagation delays; With ospf-lite this can be set to zero. Router Priority This 8-bit unsigned integer must be set to zero, as DR election is not implemented in OSPF-lite. Hello Timer An interval timer that causes the interface to send a Hello packet. This timer fires every HelloInterval seconds. Wait Timer This is not currently used in OSPF-lite. List of neighboring routers The other routers attached to this network. This list is formed by the Hello Protocol. Interface output cost(s) The cost of sending a data packet on the interface, expressed in the link state metric. This is advertised as the link cost for this interface in the router-LSA. The cost of an interface must be greater than zero. RxmtInterval The number of seconds between LSA retransmissions, for adjacencies belonging to this interface. Also used when retransmitting Database Description and Link State Request Packets. AuType The type of authentication used on the attached network/subnet. Authentication types are defined in Appendix D. All OSPF-lite packet exchanges are authenticated. Different authentication schemes may be used on different networks/subnets. Thomas et al [Page 47] Internet Draft August 2007 Authentication key This configured data allows the authentication procedure to generate and/or verify OSPF-lite protocol packets. The Authentication key can be configured on a per-interface basis (see Section D.3). 9.1. Interface states The various states that router interfaces may attain are documented in this section. The states are listed in order of progressing functionality. For example, the inoperative state is listed first, followed by a list of intermediate states before the final, fully functional state is achieved. The specification makes use of this ordering by sometimes making references such as "those interfaces in state greater than X". Figure 8 shows the graph of interface state changes. The arcs of the graph are labelled with the event causing the state change. These events are documented in Section 9.2. The interface state machine is described in more detail in Section 9.3. Down This is the initial interface state. In this state, the lower-level protocols have indicated that the interface is unusable. No protocol traffic at all will be sent or received on such a interface. In this state, interface parameters should be set to their initial values. All interface timers should be disabled, and there should be no adjacencies associated with the interface. +-------+ UnloopInd +--------+ | Down |<--------------|Loopback| +-------+ +--------+ | |InterfaceUp | Neighbour sends RouterLSA V AND adjacency in place +-------+ +-------+ |stub |<---------->|Transit| +-------+ +-------+ Figure 8: OSPF-lite simplified Interface State changes [In addition to the state transitions pictured, Event InterfaceDown always forces Down State, and Event LoopInd always forces Loopback State.] Thomas et al [Page 48] Internet Draft August 2007 Loopback In this state, the router's interface to the network is looped back. It may be looped back via hardware or software, and will be unavailable for regular data traffic. However, it may still be desirable to gain information on the quality of this interface, either through sending ICMP pings to the interface, through a bit error test, or similar. For this reason, IP packets may still be addressed to an interface in Loopback state. To facilitate this, such interfaces are advertised in router-LSAs as single host routes, the destination of which is the IP interface address. OSPF-lite-stub (with or without NBMA set) In this state, the interface is operational, and connects to any physical medium, such as point-to-point or broadcast. Upon entering this state, the router attempts to form adjacencies with any neighboring routers that it learns of through any Hello packets received. The packets do not need to be sourced by the neighbor, but can be Hello Packets from a seperate router on the network. Hellos are sent to all potential neighbors unicast every HelloInterval seconds. This overcomes difficulties with non fully meshed networks when carrying out neighbor discovery. See Section 7.1.1. OSPF-lite-transit (with or without NBMA set) To be in this state two things must have occurred: firstly there is an adjacency on the interface, and secondly there is an associated Router LSA 1 from the neighbor listing the directly connected network. See Section 2.1.0.5 for the operation of ospf-lite-stub and ospf-lite-transit. 9.2. Events causing interface state changes State changes can be invoked by a number of events, which are shown as the labelled arcs in Figure 8. The label definitions are listed below. For a detailed explanation of the effect of these events on OSPF-lite protocol operation, consult Section 9.3. InterfaceUp Lower-level protocols have indicated that the network interface is operational. This enables the interface to move out of Down state. NeighborChange There has been a change in the set of Adjacencies / neighbors associated with the interface; there are two possibilities: Thomas et al [Page 49] Internet Draft August 2007 o Bidirectional communication with the first discovered neighbour has taken place. In other words, the state of the neighbor (not interface) has moved to 2-Way or higher. o Bidirectional communication with the last neighbour has been lost, and its state has been lost. LoopInd An indication has been received that the interface is now looped back to itself. This indication can be received either from network management or from lower-level protocols. UnloopInd An indication has been received that the interface is no longer looped back. As with the LoopInd event, this indication can be received either from network management or from lower- level protocols. InterfaceDown Lower-level protocols indicate that this interface is no longer functional. No matter what the current interface state is, the new interface state will be Down. 9.3. The Interface state machine A detailed description of the interface state changes follows. Each state change is invoked by an event (Section 9.2). This event may produce different effects, depending on the current state of the interface. For this reason, the state machine below is organized by current interface state and received event. Each entry in the state machine describes the resulting new interface state and the required set of additional actions. When an interface's state changes, it may be necessary to originate a new router-LSA. See Section 12.4 for more details. Some of the required actions below involve generating events for the neighbor state machine. For example, when an interface becomes inoperative, all neighbor connections associated with the interface must be destroyed. This whole process is greatly simplified in OSPF-lite by the removal of several Interface States. State(s): Down Event: InterfaceUp Thomas et al [Page 50] Internet Draft August 2007 New state: Depends upon action routine Action: Start the interval Hello Timer, enabling the periodic sending of Hello packets from the interface. Event: InterfaceDown New state: Down Action: All interface variables are reset, and interface timers disabled. Also, all neighbor connections associated with the interface are destroyed. This is done by generating the event KillNbr on all associated neighbors (see Section 10.2). State(s): ospf-lite-stub Event: Adjacency in place and RouterLSA referencing network arrives on interface concerned New state: ospf-lite-transit Action: change Link type in RouterLSA increment sequence number and pass to flooding protocol. State(s): ospf-lite-transit Event: Adjacency lost to last neighbor on network New state: ospf-lite-stub Action: change Link type in RouterLSA increment sequence number and pass to flooding protocol. State(s): Any State Event: LoopInd New state: Loopback Action: Since this interface is no longer connected to the attached network, the actions associated with the above InterfaceDown event are executed. Thomas et al [Page 51] Internet Draft August 2007 State(s): Loopback Event: UnloopInd New state: Down Action: No actions are necessary. For example, the interface variables have already been reset upon entering the Loopback state. Note that reception of an InterfaceUp event is necessary before the interface again becomes fully functional. 9.4. Not applicable 9.5. Sending Hello packets Hello packets are sent out on each functioning router interface, and are used to discover and maintain neighbor relationships. The format of an Hello packet is detailed in Section A.3.2. Hello packets in OSPF-lite differ from those of OSPF V2. The router begins using the multicast address ALLSPFRouters but changes to unicast packets. See Section 7.1.1. 9.5.1. Sending Hello packets on NBMA physical networks This function is implemented in exactly the same way as for all network types. See Section 7.1.1, for Hello protocol operation, Section 2.1.1.0 for general NBMA operation, and Section 2.2.1 for a specific NBMA example. 10. The Neighbor Data Structure An OSPF-lite router can converse with many different neighboring routers on the same and or different interfaces. In OSPF-lite all neighbors become adjacent. Each separate conversation is described by a "neighbor data structure" and is identified either by the neighboring router's OSPF-lite Router ID or by its Neighbor IP address (see below). If two OSPF-lite routers have multiple attached networks in common, multiple conversations ensue, one for each network, with each described by a unique neighbor data structure. Each separate conversation is loosely referred to in the text as being a separate "neighbor". In this case when graphed, the two routers should appear as transit vertices only once each i.e., two Routers implies exactly two corresponding transit Vertices. Definitions for the neighbor Data structure follow: State The functional level of the neighbor conversation. This is described in more detail in Section 10.1. Thomas et al [Page 52] Internet Draft August 2007 Inactivity Timer A single shot timer whose firing indicates that no Hello Packet has been seen from this neighbor recently. The length of the timer is RouterDeadInterval seconds. Master/Slave When the two neighbors are exchanging databases, they form a master/slave relationship. The master sends the first Database Description Packet, and is the only part that it is allowed to retransmit. The slave can only respond to the master's Database Description Packets. The master/slave relationship is negotiated in state ExStart; this state is described below. DD Sequence Number The DD Sequence number of the Database Description packet that is currently being sent to the neighbor. Last received Database Description packet The initialize (I), more (M) and master (MS) bits, Options field, and DD sequence number contained in the last Database Description packet received from the neighbor. Used to determine whether the next Database Description packet received from the neighbor is a duplicate. Neighbor ID The OSPF-lite Router ID of the neighboring router. The Neighbor ID is learned when Hello packets are received from the neighbour. Neighbor Priority Set to zero in OSPF-lite and not supported. Neighbor IP address The IP address of the neighboring router's interface to the attached network. Used as the Destination IP address when protocol packets are sent as unicasts along this adjacency. Neighbor Options The optional OSPF-lite capabilities supported by the neighbor. Learned during the Database Exchange process (see Section 10.6). The neighbor's optional OSPF-lite capabilities are also listed in its Hello packets. This enables received Hello Packets to be rejected (i.e., neighbor relationships will not even start to form) if there is a mismatch in certain OSPF-lite capabilities. See Section 10.5. The optional OSPF-lite capabilities are documented in Section A.2, and briefly in Section 4.5. Thomas et al [Page 53] Internet Draft August 2007 The next set of variables are lists of LSAs. These lists describe subsets of the link-state database. This memo describes five distinct types of LSAs, all of which may be present in an AS link-state database: router-LSAs (Type 1), AS-external-LSAs (Type 5), Opaque LSA-9 (Link local), Opaque LSA-10 (Area), and Opaque LSA-11 (AS). OSPF-lite does not support LSA Types 2, 3, 4 or 7, because it supports neither network LSAs nor areas. Link state retransmission list The list of LSAs that have been flooded but not acknowledged on this adjacency. These will be retransmitted at intervals until they are acknowledged, or until the adjacency is destroyed. Database summary list The complete list of LSAs that make up the link-state database, at the moment the neighbor goes into Database Exchange state. This list is sent to the neighbor in Database Description packets. Link state request list The list of LSAs that need to be received from this neighbor in order to synchronize the two neighbors' link-state databases. This list is created as Database Description packets are received, and is then sent to the neighbor in Link State Request packets. The list is depleted as appropriate Link State Update packets are received. 10.1. Neighbor states The state of a neighbor (really, the state of a conversation being held with a neighboring router) is documented in the following sections. The states are listed in order of progressing functionality. For example, the inoperative state is listed first, followed by a list of intermediate states before the final, fully functional state is achieved. The specification makes use of this ordering by sometimes making references such as "those neighbors/adjacencies in state greater than X". Figures 9 and 10 show the graph of neighbor state changes. The arcs of the graphs are labelled with the event causing the state change. The neighbor events are documented in Section 10.2. The graph in Figure 9 shows the state changes invoked by the Hello Protocol. The Hello Protocol is responsible for neighbor acquisition and maintenance, and for ensuring two-way communication between neighbors. A copy of the state machine in Figures 9 and 10 exists on every router for each neighbor. Thomas et al [Page 54] Internet Draft August 2007 The adjacency starts to form when the neighbor is in state ExStart. After the two routers discover their master/slave status, the state transitions to Exchange, and the two neighboring routers begin synchronizing their databases. When this synchronization is finished, the neighbor is in state Full and we say that the two routers are fully adjacent. At this point the adjacency is listed in LSAs. For a more detailed description of neighbor state changes, together with the additional actions involved in each change, see Section 10.3. Down This is the initial state of a neighbor conversation. It indicates that there has been no recent information received from the neighbor. Hello packets will still be sent to "Down" neighbors, if they are still referenced in any Hello arriving from another neighbor on the interface. This overcomes problems with non fully meshed multiaccess networks. See Section 7.1.1 and 9.5. +----+ |Down| +----+ | | HelloRecieved | OR | HelloReferenced: | (neighbor referenced | in a received Hello) | +----+<-+ |Init| +----+<--------+ | | |2-Way |1-Way |Received |Received v | +-------+ | |ExStart|-------+ +-------+ Figure 9: Neighbor state changes (Hello Protocol) In addition to the state transitions pictured, Event KillNbr always forces Down State, Event InactivityTimer always forces Down State, Event LLDown always forces Down State Thomas et al [Page 55] Internet Draft August 2007 +-------+ |ExStart| +-------+ | NegotiationDone| +->+--------+ |Exchange| +--+--------+ | Exchange| Done | +----+ | +-------+ |Full|<---------+----->|Loading| +----+<-+ +-------+ | LoadingDone | +------------------+ Figure 10: Neighbor state changes (Database Exchange) In addition to the state transitions pictured, Event SeqNumberMismatch forces ExStart state, Event BadLSReq forces ExStart state, Event 1-Way forces Init state, Event KillNbr always forces Down State, Event InactivityTimer always forces Down State, Event LLDown always forces Down State, Init In this state, a Hello packet has recently been seen from either; 1.) The neighbor itself, (HelloReceived) OR 2.) A potential neighbor (HelloReferenced), that is listed in a Hello packet received from a different neighbor that is on the same interface. However, bidirectional communication has not yet been established with the neighbor (i.e., the router itself did not appear in the neighbor's Hello packet - this allows OSPF-lite to treat non fully meshed networks appropriately.) At this point (Init) on all interface types, OSPF-lite changes the destination address of the Hello protocol to the unicast address of each neighbor. All neighbors in this state (or higher) are listed in each of the Unicast Hello packets sent from the associated interface. Thomas et al [Page 56] Internet Draft August 2007 2-Way N/A This state does has been removed with ospf-lite. In ospf-lite neighbors are always formed after the required bi-directional communication (2Wayreceived) is ensured. ExStart In this state, communication between the two routers is bidirectional. This has been assured by the operation of the Hello Protocol. This is the first step in creating an adjacency between the two neighboring routers. In this state, the decision is made as to which router is the master, and the initial DD sequence number is determined. Neighbor conversations in this state or greater are called adjacencies. Exchange In this state the router describes its entire link state database by sending Database Description packets to the neighbor. Each Database Description Packet has a DD sequence number, and is explicitly acknowledged. Only one Database Description Packet is allowed outstanding at any one time. In this state, Link State Request Packets may also be sent asking for the neighbor's more recent LSAs. All adjacencies in Exchange state or greater are used by the flooding procedure. In fact, these adjacencies are fully capable of transmitting and receiving all types of OSPF-lite routing protocol packets. Loading In this state, Link State Request packets are sent to the neighbor asking for the more recent LSAs that have been discovered (but not yet received) in the Exchange state. Full In this state, the neighboring routers are fully adjacent. 10.2. Events causing neighbor state changes State changes can be invoked by a number of events. These events are shown in the labels on the arcs in Figures 9 and 10. Helloreferenced is a new event for OSPF-lite, which does not exist in OSPF V2. The label definitions are as follows: HelloReceived An Hello packet has been received from the neighbor. Thomas et al [Page 57] Internet Draft August 2007 HelloReferenced A potential neighbor has been referenced in a Hello packet received from a different neighbor on the same interface. This event allows OSPF-lite to behave appropriately with non fully meshed networks. 2-WayReceived Bidirectional communication has been realized between the two neighboring routers. This is indicated by the router seeing itself being referenced in the neighbor's Hello packet. NegotiationDone The Master/Slave relationship has been negotiated, and DD sequence numbers have been exchanged. This signals the start of the sending/receiving of Database Description packets. For more information on the generation of this event, consult Section 10.8. ExchangeDone Both routers have successfully transmitted a full sequence of Database Description packets. Each router now knows what parts of its link state database are out of date. For more information on the generation of this event, see Section 10.8. BadLSReq A Link State Request has been received for an LSA not contained in the database. This indicates an error in the Database Exchange process. Loading Done Link State Updates have been received for all out-of-date portions of the database. This is indicated by the Link state request list becoming empty after the Database Exchange process has completed. AdjOK? has been removed in ospf-lite. The following events cause well developed neighbors to revert to lesser states. Unlike the above events, these events may occur when the neighbor conversation is in any of a number of states. SeqNumberMismatch A Database Description packet has been received that either a) has an unexpected DD sequence number, b) unexpectedly has the Init bit set or c) has an Options field differing from the last Options field received in a Database Description packet. Any of these conditions indicate that some error has occurred during adjacency establishment. Thomas et al [Page 58] Internet Draft August 2007 1-Way A Hello packet has been received from the neighbor,in which the router is not mentioned, indicating that communication with the neighbor is not bidirectional. KillNbr This is an indication that all communication with the neighbor is now impossible, forcing the neighbor to revert to Down state. InactivityTimer The inactivity Timer has fired. This means that no Hello packets have been seen recently from the neighbor. The neighbor reverts to Down state. LLDown This is an indication from the lower level protocols that the neighbor is now unreachable. For example, on an X.25 network this could be indicated by an X.25 clear indication with appropriate cause and diagnostic fields. This event forces the neighbor into Down state. 10.3. The Neighbor state machine A detailed description of the neighbor state changes shown in Figures 9 and 10 follows. Each state change is invoked by an event (Section 10.2). This event may produce different effects, depending on the current state of the neighbor. For this reason, the state machine below is organized by current neighbor state and received event. Each entry in the state machine describes the resulting new neighbor state and the required set of additional actions. When the neighbor state machine invokes the interface state machine, it can be done as a scheduled task. This simplifies the operation, by ensuring that neither state machine will be executed more than once. State(s): Down Event: HelloReferenced New state: Init Action: Send Hellos to the unicast IP address of the potential neighbor referenced. Thomas et al [Page 59] Internet Draft August 2007 State(s): Init or higher Event: HelloReferenced New state: no change Action: none required. State(s): Down Event: HelloReceived New state: Init Action: 1.) Make the future destination address of all Hellos the unicast address of each of the neighbors. List ALL neighbors in each Hello packet. 2.) Start the Inactivity Timer for the neighbor from which the Hello was received. If it fires later, it will indicate that the neighbor is dead. These actions are new in OSPF-lite. State(s): Init or greater Event: HelloReceived New state: No state change. Action: Restart the Inactivity Timer for the neighbor, since it has been heard from again. State(s): Init Event: 2-WayReceived New state: Exstart Action: Upon entering this state, the router increments the DD sequence number in the neighbor data structure. If this is the first time that an adjacency has been attempted, the DD sequence number should be assigned some unique value (like the time of day clock). It then declares itself master (sets the master/slave bit to master), and starts sending Database Description Packets, with the initialize (I), more (M) and master (MS) bits set. This Database Description Packet should be otherwise empty and should be retransmitted at intervals of RxmtInterval until the next state is entered (see Section 10.8). Thomas et al [Page 60] Internet Draft August 2007 State(s): ExStart Event: NegotiationDone New state: Exchange Action: The router must list the contents of its entire link state database in the neighbor Database summary list. The link-state database consists of the Router LSAs, AS External LSAs and types 9, 10, and 11 Opaque LSAs. [ref7]. Type-9 Opaque LSAs are omitted from the Database summary list if the interface associated with the neighbor is not the interface associated with the Opaque LSA (as noted upon reception). [ref7] LSAs whose age is equal to MaxAge are instead added to the neighbor's Link state retransmission list. A summary of the Database summary list will be sent to the neighbor in Database Description packets. Each Database Description Packet has a DD sequence number, and is explicitly acknowledged. Only one Database Description Packet is allowed to be outstanding at any one time. For more detail on the sending and receiving of Database Description packets, see Sections 10.6 and 10.8. State(s): Exchange Event: ExchangeDone New state: Depends upon action routine. Action: If the neighbor Link state request list is empty, the new neighbor state is Full. No other action is required. This is an adjacency's final state. Otherwise, the new neighbor state is Loading. Start (or continue) sending Link State Request packets to the neighbor (see Section 10.9). These are requests for the neighbor's more recent LSAs (which were discovered but not yet received in the Exchange state). These LSAs are listed in the Link state request list associated with the neighbor. State(s): Loading Event: Loading Done New state: Full Action: No action required. This is an adjacency's final state. Thomas et al [Page 61] Internet Draft August 2007 State(s): Exchange or greater Event: SeqNumberMismatch New state: ExStart Action: The (possibly partially formed) adjacency is torn down, and then an attempt is made at reestablishment. The neighbor state first transitions to ExStart. The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. Then the router increments the DD sequence number in the neighbor data structure, declares itself master (sets the master/slave bit to master), and starts sending Database Description Packets, with the initialize (I), more (M) and master (MS) bits set. This Database Description Packet should be otherwise empty (see Section 10.8). State(s): Exchange or greater Event: BadLSReq New state: ExStart Action: The action for event BadLSReq is exactly the same as for the neighbor event SeqNumberMismatch. The (possibly partially formed) adjacency is torn down, and then an attempt is made at re-establishment. For more information, see the neighbor state machine entry that is invoked when event SeqNumberMismatch is generated in state Exchange or greater. State(s): Any state Event: KillNbr New state: Down Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. Also, the Inactivity Timer is disabled. State(s): Any state Event: LLDown New state: Down Thomas et al [Page 62] Internet Draft August 2007 Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. Also, the Inactivity Timer is disabled. State(s): Any state Event: InactivityTimer New state: Down Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. State(s): Exstart or greater Event: 1-WayReceived New state: Init Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. State(s): Exstart or greater Event: 2-WayReceived New state: No state change. Action: No action required. State(s): Init Event: 1-WayReceived New state: No state change. Action: No action required. 10.4. In OSPF-lite, all neigbors become adjacencies. 10.5. Receiving Hello Packets This section explains the detailed processing of a received Hello Packet. (See Section A.3.2 for the format of Hello packets.) Thomas et al [Page 63] Internet Draft August 2007 The generic input processing of OSPF-lite packets will have checked the validity of the IP header and the OSPF-lite packet header. Next, the values of the Network Mask, HelloInterval, and RouterDeadInterval fields in the received Hello packet must be checked against the values configured for the receiving interface. Any mismatch causes processing to stop and the packet to be dropped. In other words, the above fields are really describing the attached network's configuration. There is one exception to the above rule: if the Network Mask in the received Hello Packet is set to 0.0.0.1 this non-contiguous mask identifies the link as IP unnumbered and simply indicates that the mask should be ignored. The setting of the E-bit found in the Hello Packet's Options field must match. In OSPF-lite hello packets, the E bit must be set to 1. At this point, an attempt is made to match the source of the Hello Packet to one of the receiving interface's neighbors. The source is identified by the IP source address found in the Hello's IP header. If the receiving interface connects to an unnumbered point-to-point link the source is identified by the Router ID found in the Hello's OSPF-lite packet header. The interface's current list of neighbors is contained in the interface's data structure. If a matching neighbor structure cannot be found, (i.e.,this is the first time the neighbor has been detected), one is created. The initial state of a newly created neighbor is set to Down. Now the rest of the Hello Packet is examined, generating events to be given to the neighbor and interface state machines. These state machines are specified either to be executed or scheduled. o Each Hello Packet received causes the neighbor state machine to be executed with the event HelloReceived. o Then the list of neighbors contained in the Hello Packet is examined. If the router itself appears in this list, the neighbor state machine should be executed with the event 2-WayReceived. Otherwise, the neighbor state machine should be executed with the event 1-WayReceived. Thomas et al [Page 64] Internet Draft August 2007 A fundamental change with OSPF-lite then follows; all of the Router IDs listed in the Hello packet are examined and checked against the interface's current list of neighbors contained in the interface's data structure. If a matching neighbor structure cannot be found, for any router listed in the Hello, (i.e., this is the first time the Router has been detected), then the event HelloReferenced is executed, and one is created. The initial state of a newly created neighbor is this scenario is Init. Hello packets are now sent to this neighbor in an effort to achieve two-way communication. On ALL networks, receipt of an Hello Packet causes a Hello Packet to be sent back to the neighbor in response. 10.6. Receiving Database Description Packets This section explains the detailed processing of a received Database Description Packet. The incoming Database Description Packet has already been associated with a neighbor and receiving interface by the generic input packet processing (Section 8.2). Whether the Database Description packet should be accepted, and if so, how it should be further processed depends upon the neighbor state. If a Database Description packet is accepted, the following packet fields should be saved in the corresponding neighbor data structure under "last received Database Description packet": the packet's initialize (I), more (M) and master (MS) bits, Options field, and DD sequence number. If these fields are set identically in two consecutive Database Description packets received from the neighbor, the second Database Description packet is considered to be a "duplicate" in the processing described below. If the Interface MTU field in the Database Description packet indicates an IP datagram size that is larger than the router can accept on the receiving interface without fragmentation, the Database Description packet is rejected. Otherwise, if the neighbor state is: Down The packet should be rejected. Init The neighbor state machine should be executed with the event 2-WayReceived. This causes an immediate state change to state ExStart. The processing of the current packet should then continue in this new state. Thomas et al [Page 65] Internet Draft August 2007 ExStart If the received packet matches one of the following cases, then the neighbor state machine should be executed with the event NegotiationDone (causing the state to transition to Exchange), the packet's Options field should be recorded in the neighbor structure's Neighbor Options field and the packet should be accepted as next in sequence and processed further (see below). Otherwise, the packet should be ignored. o The initialize (I), more (M) and master (MS) bits are set, the contents of the packet are empty, and the neighbor's Router ID is larger than the router's own. In this case the router is now Slave. Set the master/slave bit to slave, and set the neighbor data structure's DD sequence number to that specified by the master. o The initialize (I) and master (MS) bits are off, the packet's DD sequence number equals the neighbor data structure's DD sequence number (indicating acknowledgment) and the neighbor's Router ID is smaller than the router's own. In this case the router is Master. Exchange Duplicate Database Description packets are discarded by the master, and cause the slave to retransmit the last Database Description packet that it had sent. Otherwise (i.e., the packet is not a duplicate): o If the state of the MS-bit is inconsistent with the master/slave state of the connection, generate the neighbor event SeqNumberMismatch and stop processing the packet. o If the initialize (I) bit is set, generate the neighbour event SeqNumberMismatch and stop processing the packet. o If the packet's Options field indicates a different set of optional OSPF-lite capabilities than were previously received from the neighbor (recorded in the Neighbor Options field of the neighbor structure), generate the neighbor event SeqNumberMismatch and stop processing the packet. o Database Description packets must be processed in sequence, as indicated by the packets' DD sequence numbers. If the router is master, the next packet received should have DD sequence number equal to the DD sequence number in the neighbor data structure. If the router is slave, the next packet received should have DD sequence number equal to one more than the DD sequence number stored in the neighbor data structure. In either case, if the Thomas et al [Page 66] Internet Draft August 2007 packet is the next in sequence it should be accepted and its contents processed as specified in the sections below. o Otherwise, generate the neighbor event SeqNumberMismatch and stop processing the packet. Loading or Full In this state, the router has sent and received an entire sequence of Database Description Packets. The only packets received should be duplicates (see above). In particular, the packet's Options field should match the set of optional OSPF-lite capabilities previously indicated by the neighbour (stored in the neighbor structure's Neighbor Options field). Any other packets received, including the reception of a packet with the Initialize (I) bit set, should generate the neighbor event SeqNumberMismatch [1]. Duplicates should be discarded by the master. The slave must respond to duplicates by repeating the last Database Description packet that it had sent. When the router accepts a received Database Description Packet as the next in sequence the packet contents are processed as follows. For each LSA listed, the LSA's LS type is checked for validity. If the LS type is unknown, e.g., not one of the LS types [1, 5, 9, 10 or 11] defined by this specification, then generate the neighbor event SeqNumberMismatch and stops processing the packet. Otherwise, the router looks up the LSA in its database to see whether it also has an instance of the LSA. If it does not, or if the database copy is less recent (see Section 13.1), the LSA is put on the Link state request list so that it can be requested (immediately or at some later time) in Link State Request Packets. When the router accepts a received Database Description Packet as the next in sequence, it also performs the following actions, depending on whether it is master or slave: Master Increments the DD sequence number in the neighbor data structure. If the router has already sent its entire sequence of Database Description Packets, and the just accepted packet has the more bit (M) set to 0, the neighbour event ExchangeDone is generated. Otherwise, it should send a new Database Description to the slave. Slave Sets the DD sequence number in the neighbor data structure to the DD sequence number appearing in the received packet. The slave must send a Database Description Packet in reply. If the received packet Thomas et al [Page 67] Internet Draft August 2007 has the more bit (M) set to 0, and the packet to be sent by the slave will also have the M-bit set to 0, the neighbor event ExchangeDone is generated. Note that the slave always generates this event before the master. 10.7. Receiving Link State Request Packets This section explains the detailed processing of received Link State Request packets. Received Link State Request Packets specify a list of LSAs that the neighbor wishes to receive. Link State Request Packets should be accepted when the neighbor is in states Exchange, Loading, or Full. In all other states Link State Request Packets should be ignored. Each LSA specified in the Link State Request packet should be identified in the router's database, and copied into Link State Update packets for transmission to the neighbor. These LSAs should NOT be placed on the Link state retransmission list for the neighbor. If an LSA cannot be identified in the database, there has been an error in the Database Exchange process, and neighbor event BadLSReq should be generated. 10.8. Sending Database Description Packets This section describes how Database Description Packets are sent to a neighbor. The Database Description packet's Interface MTU field is set to the size of the largest IP datagram that can be sent out the sending interface, without fragmentation. Common MTUs in use in the Internet can be found in Table 7-1 of [ref10]. The router's optional OSPF-lite capabilities (see Section A.2) are transmitted to the neighbor in the Options field of the Database Description packet. The router should maintain the same set of optional capabilities throughout the Database Exchange and flooding procedures. If for some reason the router's optional capabilities change, the Database Exchange procedure should be restarted by reverting to neighbor state ExStart. One optional capability is defined in this specification. The E bit in OSPF-lite must be set to display the mandatory support of External LSA type 5's. Unrecognized bits in the Options field should be set to zero. The sending of Database Description packets depends on the neighbor's state. In state ExStart the router sends empty Database Description packets, with the initialize (I), more (M) and master (MS) bits set. These packets are retransmitted every RxmtInterval seconds. Thomas et al [Page 68] Internet Draft August 2007 In state Exchange the Database Description Packets actually contain summaries of the link state information contained in the router's database. Each LSA in the AS's link-state database (at the time the neighbor transitions into Exchange state) is listed in the neighbor Database summary list. Each new Database Description Packet copies its DD sequence number from the neighbor data structure and then describes the current top of the Database summary list. Items are removed from the Database summary list when the previous packet is acknowledged. In state Exchange, the determination of when to send a Database Description packet depends on whether the router is master or slave: Master Database Description packets are sent when either a) the slave acknowledges the previous Database Description packet by echoing the DD sequence number or b) RxmtInterval seconds elapse without an acknowledgment, in which case the previous Database Description packet is retransmitted. Slave Database Description packets are sent only in response to Database Description packets received from the master. If the Database Description packet received from the master is new, a new Database Description packet is sent, otherwise the previous Database Description packet is re-sent. In states Loading and Full the slave must resend its last Database Description packet in response to duplicate Database Description packets received from the master. For this reason the slave must wait RouterDeadInterval seconds before freeing the last Database Description packet. Reception of a Database Description packet from the master after this interval will generate a SeqNumberMismatch neighbor event. 10.9. Sending Link State Request Packets In neighbor states Exchange or Loading, the Link state request list contains a list of those LSAs that need to be obtained from the neighbor. To request these LSAs, a router sends the neighbor the beginning of the Link state request list, packaged in a Link State Request packet. Thomas et al [Page 69] Internet Draft August 2007 When the neighbor responds to these requests with the proper Link State Update packet(s), the Link state request list is truncated and a new Link State Request packet is sent. This process continues until the Link state request list becomes empty. LSAs on the Link state request list that have been requested, but not yet received, are packaged into Link State Request packets for retransmission at intervals of RxmtInterval. There should be at most one Link State Request packet outstanding at any one time. When the Link state request list becomes empty, and the neighbor state is Loading (i.e., a complete sequence of Database Description packets has been sent to and received from the neighbor), the Loading Done neighbor event is generated. 10.10. An Example Figure 11 shows an example of an adjacency forming. Routers RT1 and RT2 are both connected to a broadcast network. The neighbor state changes realized by each router are listed on the sides of the figure. Thomas et al [Page 70] Internet Draft August 2007 +---+ +---+ |RT1| |RT2| +---+ +---+ Down Down Hello (seen=0) ------------------------------> Hello (seen=RT1,...) Init <------------------------------ EXstart Hello (seen=RT2,...) Exstart ------------------------------> D-D (Seq=x,I,M,Master) ------------------------------> D-D (Seq=y,I,M,Master) <------------------------------ Exchange D-D (Seq=y,M,Slave) ------------------------------> D-D (Seq=y+1,M,Master) Exchange <------------------------------ D-D (Seq=y+1,M,Slave) ------------------------------> ... ... ... D-D (Seq=y+n, Master) <------------------------------ D-D (Seq=y+n, Slave) Loading ------------------------------> LS Request Full ------------------------------> LS Update <------------------------------ LS Request ------------------------------> LS Update <------------------------------ Full Figure 11: An adjacency bring-up example At the beginning of Figure 11, Router RT1's interface to the network becomes operational. It begins sending Hello Packets, although it doesn't know the identity of any other neighboring routers. Router RT2 hears this Hello (moving the neighbor to Init state), and in its next Hello Packet indicates that it has heard Hello Packets from RT1. This in turn causes RT1 to go to state ExStart, as it starts to bring up the adjacency. If a Hello is received on an interface that references a Router currently Thomas et al [Page 71] Internet Draft August 2007 unknown then the receiving router sends Hellos unicast to the referenced router and changes the state to Init also. RT1 begins by asserting itself as the master by sending an empty DD packet. When it sees that RT2 is indeed the master (when RT2 sends an empty DD packet, because of RT2's higher Router ID), RT1 transitions to slave state and adopts its neighbor's DD sequence number. Database Description packets are then exchanged, with polls coming from the master (RT2) and responses from the slave (RT1). This sequence of Database Description Packets ends when both the poll and associated response has the M-bit off. In this example, it is assumed that RT2 has a completely up-to- date database. In that case, RT2 goes immediately into Full state. RT1 will go into Full state after updating the necessary parts of its database. This is done by sending Link State Request Packets, and receiving Link State Update Packets in response. Note that, while RT1 has waited until a complete set of Database Description Packets has been received (from RT2) before sending any Link State Request Packets, this need not be the case. RT1 could have interleaved the sending of Link State Request Packets with the reception of Database Description Packets. 11. The Routing Table Structure A distinction exists between the Main routing table in a device and the OSPF-lite routing table to be offered to the device. When referring to 'The routing table' we are not referring to the Main table of routing in the device, but only the OSPF-lite calculated table. The role of the Main routing table is outside the scope of this document but can be referred to in RFC 2328.[ref1] 11.1 Routing tables See RFC 2328 [ref1] for a general overview of routing tables. 11.2 For a sample OSPF-lite routing table see Section 2.2.0 11.3 Not applicable 12. Link State Advertisements (LSAs) Each router in the Autonomous System originates one Router LSA type 1 (to describe its links), and possibly other Opaque or External LSAs. OSPF-lite does not support Network Type LSAs (Type 2). Thomas et al [Page 72] Internet Draft August 2007 The collection of LSAs forms the link-state database. Each separate type of LSA has a separate function. Router-LSAs describe how an AS's Routers and networks are interconnected. AS-external-LSAs provide a way of transparently advertising externally-derived routing information throughout the Autonomous System. Opaque LSAs [ref7]allow routing information from other Protocols to pass through OSPF-lite without being lost, and form the basis for the support of GMPLS.[ref11] Each LSA begins with a standard 20-byte header, which is discussed below. 12.1. The LSA Header The LSA header contains the LS type, Link State ID and Advertising Router fields; together, these three fields uniquely identify the LSA. There may be several instances of an LSA present in the Autonomous System, all at the same time. It must then be ascertained which instance is most recent by examining the LS sequence, LS checksum and LS age fields, which are also contained in the 20-byte LSA header. Several of the OSPF-lite packet types list LSAs. When it is not necessary to identify the particular instance of an LSA, it is referred to only by its LS type, Link State ID and Advertising Router (see Link State Request Packets). Otherwise, the LS sequenc number, LS age and LS checksum fields must also be referenced. A detailed explanation of the fields contained in the LSA header follows. 12.1.1. LS age This field represents the age of the LSA in seconds. It should be processed as an unsigned 16-bit integer, and is set to zero when the LSA is originated. It must be incremented by InfTransDelay on every hop of the flooding procedure. InfTransDelay can be set to zero with ospf-lite. LSAs are also aged as they are held in each router's database. The age of an LSA is never incremented past MaxAge. LSAs having age MaxAge are not used in the routing table calculation. When an LSAs age first reaches MaxAge, it is reflooded. An LSA of age MaxAge is finally flushed from the database when it is no longer needed to ensure database synchronization. For more information on the aging of LSAs, consult Section 14. Thomas et al [Page 73] Internet Draft August 2007 The LS age field is examined when a router receives two instances of an LSA, both having identical LS sequence numbers and LS checksums. An instance of age MaxAge is then always accepted as most recent; this allows old LSAs to be flushed quickly from the routing domain. Otherwise, if the ages differ by more than MaxAgeDiff, the instance having the smaller age is accepted as most recent [3]. See Section 13.1 for more details. 12.1.2. Options The Options field in the LSA header indicates which optional capabilities are associated with the LSA. Because areas are not supported in OSPF-lite, the E-bit (indicating the router's ability to create external LSAs if necessary) has lost its meaning. However OSPF-lite specifies that this bit must be set in the Router1 LSAs, for consistency with OSPF Version 2. (OSPF-lite fully supports Type 5 LSAs.) The other Optional capabilities are described in Section A.2. The unused bits in the Options field should be set to zero. 12.1.3. LS type The LS type field dictates the format and function of the LSA. LSAs of different types have different names (e.g., router-LSAs or AS-external-LSAs). All LSA types in OSPF-lite are flooded throughout the entire area except for Type 9 Opaque LSAs which are link-local in scope. This is in contrast to OSPF Version 2, which implements areas, and therefore must permit restricted flooding. Each separate LSA type is briefly described below in Table 7. LSA Type OSPF-lite LSA Description ________________________________________________ 1 These are the router-LSAs. They describe the collected states of the router's interfaces. For more information, consult Section 12.4.1. ________________________________________________ 5 These are the AS-external-LSAs. Originated by AS boundary routers, they describe routes to destinations external to the Autonomous System. A default route for the Autonomous System can also be described by an AS-external-LSA. ----------------------------------------------- 9, 10, 11 Opaque LSAs which are fully supported. Table 7: Valid OSPF-lite LSA Types. Thomas et al [Page 74] Internet Draft August 2007 12.1.3.1 Opaque LSAs supported Opaque LSAs [ref7] are supported as in RFC 2370. Type 10 LSAs have area scope. Although areas are not supported in OSPF-lite, the area field is set to 0.0.0.0. In this sense Opaque LSAs of type 10 are supported and treated like Type 11, as they flood throughout the 'area' which in the case of OSPF-lite is the entire AS. The modifications to the neighbor state machine described in RFC 2370 are also implemented in OSPF-lite. 12.1.4. Link State ID This field identifies the piece of the routing domain that is being described by the LSA. Depending on the LSA's LS type, the Link State ID takes on the values listed in Table 8. LS Type Link State ID _______________________________________________ 1 The originating router's Router ID. 5 The destination network's IP address. network / subnetwork / supernet Table 8: The LSAs Link State ID. There can be conflicts in assigning the Link State ID in the case of two networks with different (overlapping) address spaces, for example with aggregate routes and supernets. To avoid this conflict for AS-external-LSAs (LS type = 5), the Link State ID may additionally have one or more of the destination network's 'host' bits set. For example, when originating an AS-external-LSA for the network 10.0.0.0 with mask of 255.0.0.0, the Link State ID can be set to anything in the range 10.0.0.0 through to 10.255.255.255 inclusive (although 10.0.0.0 should be used whenever possible). The freedom to set certain host bits allows a router to originate separate LSAs for two networks having the same address but different masks. See Appendix E for details. When the LSA is describing a network (LS type = 5), the network's IP address is easily derived by masking the Link State ID with the network/subnet mask contained in the body of the LSA. When the LSA is describing a router (LS type = 1), the Link State ID is always the described router's OSPF-lite Router ID.[2] When an AS-external-LSA (LS Type = 5) is describing a default route, its Link State ID is set to DefaultDestination (0.0.0.0). Thomas et al [Page 75] Internet Draft August 2007 12.1.5. Advertising Router This field specifies the OSPF-lite Router ID of the LSA's originator. For router-LSAs, this field is identical to the Link State ID field, but AS-external-LSAs are originated by AS boundary routers. 12.1.6. LS sequence number The sequence number field is a signed 32-bit integer. It is used to detect old and duplicate LSAs. The space of sequence numbers is linearly ordered. The larger the sequence number (when compared as signed 32-bit integers) the more recent the LSA. To describe the sequence number space more precisely, let N refer in the discussion below to the constant 2**31. The sequence number -N (0x80000000) is reserved (and unused). This leaves -N + 1 (0x80000001) as the smallest (and therefore oldest) sequence number; this sequence number is referred to as the constant InitialSequenceNumber. A router uses InitialSequenceNumber the first time it originates any LSA. Afterwards, the LSA's sequence number is incremented each time the router originates a new instance of the LSA. When an attempt is made to increment the sequence number past the maximum value of N - 1 (0x7fffffff; also referred to as MaxSequenceNumber), the current instance of the LSA must first be flushed from the routing domain. This is done by prematurely aging the LSA (see Section 14.1) and reflooding it. As soon as this flood has been acknowledged by all neighbors, a new instance can be originated with sequence number of InitialSequenceNumber. The router may be forced to promote the sequence number of one of its LSAs when a more recent instance of the LSA is unexpectedly received during the flooding process. This should be a rare event. This may indicate that an out-of-date LSA, originated by the router itself before its last restart/reload, still exists in the Autonomous System. For more information see Section 13.4. 12.1.7. LS checksum This field is the checksum of the complete contents of the LSA, excepting the LS age field. The LS age field is excepted so that an LSA's age can be incremented without updating the checksum. The checksum used is the same that is used for ISO connectionless datagrams; it is commonly referred to as the Fletcher checksum. It is documented in Annex B of [ref12]. The LSA header also contains the length of the LSA in bytes; subtracting the size of the LS age field (two bytes) yields the amount of data to be used in the checksum calculation. Thomas et al [Page 76] Internet Draft August 2007 The checksum is used to detect data corruption of an LSA, which can occur while an LSA is being flooded, or while it is being held in a router's memory. The LS checksum field cannot take on the value of zero; the occurrence of such a value should be considered a checksum failure. In other words, calculation of the checksum is not optional. The checksum of an LSA is verified in two cases: a) when it is received in a Link State Update Packet and b) at times during the aging of the link state database. The detection of a checksum failure leads to separate actions in each case. See Sections 13 and 14 for more details. Whenever the LS sequence number field indicates that two instances of an LSA are the same, the LS checksum field is examined. If there is a difference, the instance with the larger LS checksum is considered to be most recent [4]. See Section 13.1 for more details. 12.2. The link state database A router has a single OSPF-lite link State Database for each instance of OSPF-lite it is running. (A router may belong to two or more different Autonomous Systems, each running OSPF-lite.) All routers belonging to an AS have identical link state databases, which are synchronized through the Hello protocol and through flooding. When an adjacency is being brought up, only the LSA database is synchronized between the two routers. The OSPF-lite database is composed of all of the LSAs. An implementation of OSPF-lite must be able to access individual pieces of the database. This lookup function is based on the LSAs LS type, Link State ID and Advertising Router [5]. There will be a single instance (the most up-to-date) of each LSA in the database. The database lookup function is invoked during the LSA flooding procedure (Section 13) and the routing table calculation (Section 16). In addition, by using this lookup function the router can determine whether it has itself ever originated a particular LSA, and if so, with what LS sequence number. An LSA is added to a router's database when either a) it is received during the flooding process (Section 13) or b) it is originated by the router itself and has not yet been flooded (Section 12.4). An LSA is deleted from a router's database when either a) it has been overwritten by a newer instance during the flooding process (Section 13) or b) the router originates a newer instance of one of its self- originated LSAs (Section 12.4) or c) the LSA ages out and is flushed from the routing domain via premature aging (Section 14). Whenever an LSA is deleted from the database it must also be removed from all neighbors' Link state retransmission lists. Thomas et al [Page 77] Internet Draft August 2007 12.3. Representation of TOS For backward consistancy with previous versions of the OSPF specification [ref1], and only for that reason, TOS-specific information can be included in router-LSAs, and AS-external-LSAs. The encoding of TOS in OSPF-lite LSAs is specified in Table 9, which relates the OSPF-lite encoding to the IP packet header's TOS field (defined in [ref13]). The OSPF-lite encoding is expressed as a decimal integer, and the IP packet header's TOS field is expressed in the binary TOS values used in [ref13]. OSPF-lite encoding RFC 1349 TOS values ___________________________________________ 0 0000 normal service 2 0001 minimize monetary cost 4 0010 maximize reliability 6 0011 8 0100 maximize throughput 10 0101 12 0110 14 0111 16 1000 minimize delay 18 1001 20 1010 22 1011 24 1100 26 1101 28 1110 30 1111 Table 9: Representing TOS in OSPF-lite. 12.4. Originating LSAs in OSPF-lite Unlike OSPF Version 2, an OSPF-lite router will only generate a single Router-LSA Type 1 and not an LSA type 2. OSPF-lite routers that are also AS Boundary routers, or are redistributing routes from other protocol will also generate Type 5 LSAs. Each router originates a router-LSA. AS boundary routers originate a single AS-external-LSA for each known AS external destination. Destinations are advertised with separate LSAs so that a change in any single route can be flooded without reflooding the entire collection of routes. During the flooding procedure, many LSAs can be carried by a single Link State Update packet. Thomas et al [Page 78] Internet Draft August 2007 As an example, consider Router RT4 in Figure 2. + | 3+---+ external; N12 N13 N14 N1|--|RT1|\ 1 \ | / | +---+ \ 8\ |8/8 + \ ____ \|/ / \ 1+---+8 8+---+6 * N3 *---|RT4|------|RT5|--------+ \____/ +---+ N19 +---+ | + / | |7 | | 3+---+ / | N18| | N2|--|RT2|/1 |1 |6 N17| | +---+ +---+8 6+---+ | + |RT3|--------------|RT6| | +---+ N5 +---+ | |2 |7 | | | | +---------+ | | N4 | | | | N16 | | N11 | |external; +---------+ | | | | | N12 |3 | |6 2/ +---+ | +---+/ |RT9| | |RT7|---N15 +---+ | +---+ 9 |1 + | |1 _|__ | |5 __|_ / \ 1+----+2 | 3+----+1 / \ * N9 *------|RT11|----|---|RT10|---* N6 * \____/ +----+ | +----+ \____/ | | | |1 + |1 +----+ N8 +---+ |RT12| |RT8| +----+ +---+ |2 |4 | | +---------+ +--------+ N10 N7 Figure 2: A sample Autonomous System Thomas et al [Page 79] Internet Draft August 2007 Router RT4 originates one router-LSA into the Topological Database. In this same figure, Router RT5 will originate one Router-LSA (type 1), and three AS-external-LSAs (type 5), one for each of the networks N12-N14. These will be flooded throughout the entire AS. Whenever a new instance of an LSA is originated, its LS sequence number is incremented, its LS age is set to zero, its LS checksum is calculated, and the LSA is added to the link state database and flooded out the appropriate interfaces. See Section 13.2 for details concerning the installation of the LSA into the link state database. See Section 13.3 for details concerning the flooding of newly originated LSAs. The five events in OSPF-lite excluding any extra introduced by the Opaque LSA types), that can cause a new instance of an LSA to be originated are: (1) The LS age field of one of the router's self-originated LSAs reaches the value LSRefreshTime. In this case, a new instance of the LSA is originated, even though the contents of the LSA (apart from the LSA header) will be the same. This guarantees periodic originations of all LSAs. This periodic updating of LSAs adds robustness to the link state algorithm. LSAs that solely describe unreachable destinations should not be refreshed, but should instead be flushed from the routing domain (see Section 14.1). When the information described by an LSA changes, a new LSA is originated. However, two instances of the same LSA may not be originated within the time period MinLSInterval. This may require that the generation of the next instance be delayed by up to MinLSInterval, therefore implementing a type of damping. The following events may cause the contents of an LSA to change. These events should cause new originations if and only if the contents of the new LSA would be different: (2) An interface's state changes (see Section 9.1). This may mean that it is necessary to produce a new instance of the router-LSA. (2.1) A change from OSPF-lite-stub to OSPF-lite-transit is considered a change in state. A new Router-LSA is created and the LS sequence number is incremented. (3) One of the neighboring routers changes to/from the FULL state. This may mean that it is necessary to produce a new instance of the router-LSA. The last two events concern AS boundary routers (and former AS boundary routers - see (5) below) only: Thomas et al [Page 80] Internet Draft August 2007 (4) An external route gained through direct experience with an external routing protocol (such as BGP) changes, causing an AS boundary router to originate a new instance of an AS-external-LSA. (5) A router ceases to be an AS boundary router, perhaps after restarting or reconfiguration. In this situation the router should flush all AS-external-LSAs that it had previously originated. These LSAs can be flushed via the premature aging procedure specified in Section 14.1. The construction of each type of LSA is explained in detail below. In general, these sections describe the contents of the LSA body (i.e., the part coming after the 20-byte LSA header). For information concerning the construction of the LSA header, see Section 12.1. 12.4.1. Router-LSAs A router originates a router-LSA to describe itself to the Database. Such an LSA describes the collected states of the router's directly connected links. The LSA is fully flooded throughout the entire AS in OSPF-lite. The format of a router-LSA is shown in Appendix A (Section A.4.2). The first 20 bytes of the LSA consist of the generic LSA header that was discussed in Section 12.1. Router-LSAs have an LS type of 1. In OSPF Version 2, a router also indicates whether it is able to processing external routes, by setting the E-bit appropriately in its router-LSAs. This enables paths to those routers to be saved in the database routing table, for later processing of AS-external-LSAs. In OSPF-lite this setting of the E-bit in the options field has lost its meaning as there are no stub areas, however for consistancey with previous OSPF versions the E-bit is always set in OSPF-lite Router-LSAs, and signifies the protocol's support of LSA Type 5 (AS-external-LSA). Virtual links are not supported in OSPF-lite. The router-LSA then describes the router's working connections (i.e., interfaces or links) to the connected networks. Each network is added as a Link type in the Router-LSA. NBMA networks also add an additional link type. OSPF-lite differs here from OSPF Version 2 in the way that the links are typed. OSPF Version 2 used the characteristics of the link. OSPF- lite categorises each link as OSPF-lite-stub, regardless of the physical or datalink characteristics of the link. Thomas et al [Page 81] Internet Draft August 2007 In OPSF-lite, an OSPF-lite-stub link type can transistion to OSPF- lite-transit if there is an adjacency on the interface and an Router LSA is received referencing the same directly connected network. This is reflected in the Router LSA. Hence with OSPF-lite, there are only two link types: Type 8 (OSPF-lite-stub), and type 9 (OSPF-lite-transit). Neighbors are discovered either via OSPF-lite Hellos, or via manual configuration. Manual configuration is NOT recommended. Each link type is labelled with its Link ID. This Link ID gives a name to the entity that is connected. In OSPF-lite this should always be the Interface IP address for the associated network. For unnumbered interfaces, this value should be left as the interface's MIB-II ifIndex value. With ospf-lite the Link Data field must be set to 0.0.0.1 this reflects the unnumbered status and tells the router to ignore the Link ID and Data fields. OSPF Version 2 handles these fields quite differently. OSPF Version 2 introduces extra links for point-to-point networks. With ospf-lite, a point-to-point network is represented by a single link in the Router-LSA. (see Sections 2.1.0.7 and 2.1.0.9 for an example). This Link ID represents what the router itself is locally attached to. Table 10 summarizes the values used for the Type and Link ID fields for the OSPF-lite Router-LSA. Physical Type Link type Description Link ID / Link Data _______________________________________________________________________ Point-to-point 8 or 9 OSPF-lite-stub/transit Intf IP / net mask unnumbered 8 or 9 OSPF-lite-stub/transit MIB-if / 0.0.0.1 Broadcast 8 or 9 OSPF-lite-stub/transit Intf IP / net mask NBMA 8 or 9 OSPF-lite-stub/transit Intf IP / net mask 8 extra OSPF-lite-stub Intf IP / HOST mask Loopback Intfce 8 OSPF-lite-stub Intf IP / net mask Table 10: Link ID and descriptions in the OSPF-lite router-LSA. In addition, the link Data field is specified for each link. This field gives 32 bits of extra information about the link. Thomas et al [Page 82] Internet Draft August 2007 In OSPF-lite this Link Data field normally specifies the IP address Mask of the Interface. As with OSPF Version 2 this information is required by the routing table calculation, see Section 16.1.1). The only exception to this is with a Network type of NBMA, where OSPF-lite sees the network as a Link type of OSPF-lite-stub or OSPF-lite-transit as expected. OSPF-lite then places an additional link type in the Router-LSA. This link type has a link ID of the Interface IP address but includes a mask of 32 bits in the Link Data field of the Link. This link Type is set to OSPF-lite-stub. This ensures that a host route to the network itself gets added to the routing table, ensuring the forwarding of routes across a non fully meshed network. See Section 2.2.1, and Section 16.0.7.1 for an example. Finally, the cost of using the link for output is specified; this is configurable. With the exception of loopback OSPF-lite-stub networks, it must always be non-zero. To describe further the process of building the list of link descriptions, suppose a router wishes to build a router-LSA for the AS. The router examines its collection of interface data structures. For each interface, the following steps are taken: o If the attached network does not belong to the AS, (ie: not configured to paricipate) no links are added to the LSA, and the next interface should be examined. o If the state of the interface is Down, no links are added. o If the state of the interface is Loopback, add a Type 8 link (OSPF-lite-stub network). The Link ID should be set to the Interface IP address, and the Link Data set to the interface mask, and the cost set to zero. This will not necessarily be a host route, depending on how the mask on loopback Interface is configured. o Otherwise, the link descriptions added to the router-LSA depend on the OSPF-lite link type. This is independent of physical network type in OSPF-lite. (The only data taken from the physical setup is whether an interface is NBMA.) Interfaces are added with type OSPF-lite-stub. If there is a corresponding Router-LSA received over the same network locally advertising the same link then change the link Type to OSPF-lite-transit. o If a network is NBMA then an additional link type is added. This is set to OSPF-lite-stub with the mask of the interface in the Link Data field being set to 32 bits. Thomas et al [Page 83] Internet Draft August 2007 12.4.1.1. Point-to-point interfaces: simply OSPF-lite-stub/transit For point-to-point interfaces, one or more link descriptions are added to the router-LSA as follows: If the neighboring router is not yet seen in Hellos, then add a Type 8 link (OSPF-lite-stub). The Link ID is always the Interface IP address, and not set to the Router ID of the neighboring router. If there is an adjacency on the link and there is a RouterLSA received that references the same network, then change the type to ospf-lite-transit. (see Sections 2.1.0.7 and 2.1.0.9.) No other stub information is required concerning the point- to-point network in OSPF-lite, except ensuring that the cost is set to the interface's configured output cost. 12.4.1.1.1 IP unnumbered issues with Router LSA generation An unnumbered point-to-point link in OSPF lite is simply a special case of OSPF-lite-transit. Here the IP address is not available and so the field is set to the interface's MIB-II [ref14] ifIndex value. Although the graph does not need to know that the underlying link type is unnumbered the Link Data field is set to 0.0.0.1, informing the receiving router to ignore the link-ID field. OSPF-lite still sees this connection as an OSPF-lite-transit link type. The cost should be set to the output cost of the point-to- point interface. 12.4.1.1.2 Note: Hello protocol assistance with IP unnumbered The OSPF-lite Hello protocol will see an advertisement arriving on the Interface. It will use this information to build an adjacency with the new neighbor, and connect the received LSA's router ID via the interface information to form the SPF Tree. Note: The graph does need not need to be aware that the underlying link type is unnumbered. The field is set to 0.0.0.1 to instruct the receiving router's Hello protocol to ignore the mask. This is the same value as in the Router LSA link Data field, again indicating to the Hello protocol to ignore this field upon receiving it. 12.4.1.2. Describing broadcast and NBMA interfaces (simply OSPF- lite-stub/transit) Thomas et al [Page 84] Internet Draft August 2007 As described in the previous section; For operational broadcast and NBMA interfaces, two link types are added to the router LSA. The first had the Link ID set to the interface address as expected, with the Link Data set to the network mask. This is type OSPF-lite-stub or transit as with all networks. To allow for routing over a non fully meshed network a further link type is added. This Link type always remains OSPF-lite-stub, and has the Link ID field set to the Interface IP address. The Link Data field is set to the 32-bit host mask. This generates a host route to the interface, and ensures OSPF-lite communication over a non fully meshed connection. This operates in a similar way to an OSPF Version 2 'point-to-multipoint' interface but is the default behavior. See Sections 16.0.7.1, and Section 2.2.1, for an example. 12.4.1.3. Not applicable 12.4.1.4. Describing Point-to-MultiPoint interfaces Point-to-multipoint interfaces are not required in OSPF-lite, as all NBMA interfaces are treated in a similar way. These types of interfaces are implicit in OSPF-lite. Thomas et al [Page 85] Internet Draft August 2007 OSPF-lite also allows manual over-riding of link type via configuration commands. If an interface or subinterface is over-ridden to type NBMA then it is treated simply as an NBMA interface. Also an NBMA interface manualy over-ridden to be a point-to-point interface is treated as a true point-to-point interface. As a separate 'link type', point-to-multipoint is NOT supported. 192.1.2.0/24 Single AS + | | 3+---+1 N1 |--|RT1|-----+ | +---+ \ 192.1.1.0 /24 | \ _______ + \/ \ 1+---+ * N3 *-----|RT4| + /\_______/ +---+ | / | | 3+---+1 / | N2 |--|RT2|-----+ 1| | +---+ 3 +---+8 unnumbered 6+---+ | /|RT3|---------------|RT6| + 19.10.1.0/24/ +---+ (N5) +---+ 192.1.3.0/24 / |2 | +------+ / | | RT14 | / +-----------+ | |/ 192.1.4.0/24 (N4) +------+ Figure 12: Example LSA Generation (N5 set to unnumbered). 12.4.1.5. Examples of router-LSAs Consider the router-LSAs generated by Router RT3, as shown in Figure 12. Assume that the last byte of all of RT3's interface addresses is 3, giving it the interface addresses 192.1.1.3 and 192.1.4.3, and that the other routers have similar addressing schemes. In addition, assume that all links are functional, and that Router IDs are assigned as the smallest IP interface address. [2] RT3's router-LSA for the network pictured above is shown below. Thomas et al [Page 86] Internet Draft August 2007 RT3's router-LSA for AS LS age = 0 ;always true on origination Options = (E-bit) ;Mandatory with OSPF-lite LS type = 1 ;indicates router-LSA Link State ID = 192.1.1.3 ;RT3's Router ID Advertising Router = 192.1.1.3 ;RT3's Router ID bit E = 1 ;mandatory with OSPF-lite bit B = 0 ;Unsupported options set to zero #links = 4 Link ID = 192.1.1.3 ;Interface IP address. Link Data = 0xffffff00 ;Network Mask Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 1 Link ID = 192.1.4.3 ;Interface IP address Link Data = 0xffffff00 ;Network mask Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 2 Link ID = 0.0.0.3 ;MIB-II ifIndex of P-P link Link Data = 0.0.0.1 ;signifies unnumbered IP Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 8 Link ID = 19.10.1.3 ;Interface IP address Link Data = 0xffffff00 ;Network Mask Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 After Adjacenceis are built with neighbors, with corresponding Router-LSAs arriving from neighboring routers, R3's Router-LSA changes as follows: RT3's router-LSA for AS LS age = 0 ;always true on origination Options = (E-bit) ;Mandatory with OSPF-lite LS type = 1 ;indicates router-LSA Link State ID = 192.1.1.3 ;RT3's Router ID Advertising Router = 192.1.1.3 ;RT3's Router ID bit E = 1 ;mandatory with OSPF-lite Thomas et al [Page 87] Internet Draft August 2007 #links = 4 Link ID = 192.1.1.3 ;Interface IP address. Link Data = 0xffffff00 ;Network Mask Type = 9 ;OSPF-lite-transit # TOS metrics = 0 metric = 1 Link ID = 192.1.4.3 ;Interface IP address Link Data = 0xffffff00 ;Network mask Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 2 Link ID = 0.0.0.3 ;MIB-II ifIndex of P-P link Link Data = 0.0.0.1 ;signifies unnumbered IP Type = 9 ;OSPF-lite-transit # TOS metrics = 0 metric = 8 Link ID = 19.10.1.3 ;Interface IP address Link Data = 0xffffff00 ;Network Mask Type = 9 ;OSPF-lite-transit # TOS metrics = 0 metric = 3 12.4.2. Network-LSAs are not supported in OSPF-lite 12.4.1.1. Not applicable 12.4.3. Summary-LSAs are not supported in OSPF-lite 12.4.3.1. Not applicable 12.4.3.2. Not applicable 12.4.4. AS-external-LSAs OSPF-lite does not change the operation or structure of Type 5 LSAs, when compared to OSPF Version 2, except of course that they are flooded throughout the entire AS with OSPF-lite, because OSPF-lite has no area support. Fields in the LSA type remain as in previous OSPF Versions. AS-external-LSAs describe routes to destinations external to the Autonomous System. Most AS-external-LSAs describe routes to specific external destinations; in these cases the LSAs Link State ID is set to the destination network's IP address (if necessary, the Link State ID can also have one or more of the network's 'host' bits set; see Appendix E for details). However, a default route for the Autonomous System can be described in an AS-external-LSA by setting the LSAs Link State ID to DefaultDestination (0.0.0.0). AS-external-LSAs are originated by AS boundary routers. An AS boundary router originates a single AS-external-LSA for each external route that it has learned, either through another routing protocol (such as BGP), or through configuration information. Thomas et al [Page 88] Internet Draft August 2007 AS-external-LSAs like ALL OSPF-lite LSAs are flooded throughout the entire Autonomous System. The metric that is advertised for an external route can be one of two types. Type 1 metrics are comparable to the link state metric. Type 2 metrics are assumed to be larger than the cost of any intra-AS path. If a router advertises an AS-external-LSA for a destination which then becomes unreachable, the router must then flush the LSA from the routing domain by setting its age to MaxAge and reflooding (see Section 14.1). 12.4.4.1. Examples of AS-external-LSAs Consider once again the AS pictured in Figure 2. There are two AS boundary routers: RT5 and RT7. Router RT5 originates three AS-external-LSAs, for networks N12-N14. Router RT7 originates two AS-external-LSAs, for networks N12 and N15. Assume that RT7 has learned its route to N12 via BGP, and that it wishes to advertise a Type 2 metric to the AS. RT7 would then originate the following LSA for N12: ; AS-external-LSA for Network N12, ; originated by Router RT7 LS age = 0 ;always true on origination Options = (E-bit not set) ; LS type = 5 ;AS-external-LSA Link State ID = N12's IP network number Advertising Router = Router RT7's ID bit E = 1 ;Type 2 metric metric = 2 ; This is the cost of 2 Forwarding address = 0.0.0.0 In the above example, the forwarding address field has been set to 0.0.0.0, indicating that packets for the external destination should be forwarded to the advertising OSPF-lite router (RT7). This is not always desirable. Consider the example pictured in Figure 13. There are three OSPF- lite routers (RTA, RTB and RTC) connected to a common network. Only one of these routers, RTA, is exchanging BGP information with the non-OSPF-lite router RTX. RTA must then originate AS-external-LSAs for those destinations it has learned from RTX. By using the AS- external-LSAs forwarding address field, RTA can specify that packets for these destinations be forwarded directly to RTX. Without this feature, Routers RTB and RTC would take an extra hop to get to these destinations. Thomas et al [Page 89] Internet Draft August 2007 A forwarding address can also be specified for the default route. For example, in figure 13 RTA may want to specify that all externally-destined packets should by default be forwarded to its BGP peer RTX. The resulting AS-external-LSA is shown below. Note that the Link State ID is set to DefaultDestination. ; Default route, originated by Router RTA ; Packets forwarded through RTX LS age = 0 ;always true on origination Options = (E-bit not set) ; LS type = 5 ;AS-external-LSA Link State ID = DefaultDestination ; default route Advertising Router = Router RTA's ID bit E = 1 ;Type 2 metric metric = 1 ;This is the cost of 1 Forwarding address = RTX's IP address In figure 13, suppose instead that both RTA and RTB exchange BGP information with RTX. In this case, RTA and RTB would originate the same set of AS-external-LSAs. These LSAs, if they specify the same metric, would be functionally equivalent since they would specify the same destination and forwarding address (RTX). This leads to a clear duplication of effort. If only one of RTA or RTB originated the set of AS-external-LSAs, the routing would remain the same, and the size of the link state database would decrease. However, it must be unambiguously defined as to which router originates the LSAs (otherwise neither may do so, or the identity of the originator may oscillate). The following rule is thereby established: if two routers, both reachable from one another, originate functionally equivalent AS-external-LSAs (i.e., same destination, cost and non-zero forwarding address), then the LSA originated by the router having the highest OSPF-lite Router ID is used. The router having the lower OSPF-lite Router ID can then flush its LSA. Flushing an LSA is discussed in Section 14.1. + +---+.....|.BGP |RTA|-----|.....+---+ +---+ |-----|RTX| | +---+ +---+ | |RTB|-----| +---+ +---+ |-----|RTC| | +---+ + Figure 13: Forwarding address example Thomas et al [Page 90] Internet Draft August 2007 12.4.4.2. Example of Router LSA with NBMA interface. Consider the example from Section 2.1.1 reproduced below as Figure 14. +-----+ +-----+ |RT101| |RT102| +-----+ +-----+ 3 *|* * /3 Interface 1.1.1.1/24 *|* * /Interface 1.1.1.2/24 link N21 1.1.1.1/32 *|* * / link N22 1.1.1.2/32 *|* * / PVC1 *|* PVC2 * / *|* * / *|* * / *|* * / * | * * / * | * * * / * __|______ /___ * | |N20 * | (NBMA) |(Implied vertex) * | 1.1.1.0/24 | * |______________| * | * | * | * | * | link N23 1.1.1.3/32 * 3| Interface 1.1.1.3/24 +-----+ |RT103| +-----+ Figure 14 RT101 will show two links in its Router-LSAs. The first link for the NBMA network will show as OSPF-lite-transit once a Router-LSA from RT102 or RT103 arrives advertising the same network. The second link shown in RT101s Router-LSa will be a link advertising the interface address with the 32-bit Host mask in the Link Data field. This will eventually result in a host router to the interface, and allow communication over a non fully meshed NBMA network. This action is required and is default. RT101's router-LSA for the network pictured above is shown below. Thomas et al [Page 91] Internet Draft August 2007 ; RT101's router-LSA for AS LS age = 0 ;always true on origination Options = (E-bit set) ;Mandatory with OSPF-lite LS type = 1 ;indicates router-LSA Link State ID = 1.1.1.0 ;RT101's Router ID Advertising Router = 1.1.1.1 ;RT101's Router ID bit B = 0 ;Unsupported options set to zero #links = 2 Link ID = 1.1.1.1 ;Interface IP address. Link Data = 0xffffff00 ;Network Mask Type = 9 ;OSPF-lite-transit # TOS metrics = 0 metric = 3 ;cost = 3 Link ID = 1.1.1.1 ;Interface IP address Link Data = 0xffffffff ;32 bit HOST mask Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 RT101 will become fully adjacent with RT102 and RT103, and RT102 will also become fully adjacent with RT103. The adjacency graph is fully meshed. This differs from OSPF Version 2's point-to-multipoint implementation slightly. Also, due to the link Data field in the Router LSA, the network is being advertised. This network will also is also a cadidate for an implied transit vertex. For a full analysis of the extra host route introduced, see Section 16.0.7.1 13. The Flooding Procedure Link State Update packets provide the mechanism for flooding LSAs. A Link State Update packet may contain several distinct LSAs, and floods each LSA one hop further from its point of origination. To make the flooding procedure reliable, each LSA must be acknowledged separately. Acknowledgments are transmitted in Link State Acknowledgment packets. Many separate acknowledgments can also be grouped together into a single packet. The flooding procedure starts when a Link State Update packet has been received. Many consistency checks have been made on the received packet before being handed to the flooding procedure (see Section 8.2). In particular, the Link State Update packet has been associated with a particular neighbor. If the neighbor is in a lesser state than Exchange, the packet should be dropped without further processing. Thomas et al [Page 92] Internet Draft August 2007 In OSPF Version 2 LSAs, (other than AS-external-LSAs), were associated with a specific area. LSAs do not contain an area field, so the LSA's area had to be deduced from the Link State Update packet header. OSPF-lite does not support multiple areas and the area field must be zero (0.0.0.0). For each LSA contained in a Link State Update packet, the following steps are taken: (1) Validate the LSA's LS checksum. If the checksum turns out to be invalid, discard the LSA and get the next one from the Link State Update packet. (2) Examine the LSA's LS type. If the LS type is unknown, discard the LSA and get the next one from the Link State Update Packet. OSPF-lite supports Router LSAs (Type 1), AS-external LSAs (Type 5), Opaque-LSAs Link-Local (Type 9), Opaque-LSAs Area-Local (type 10), and Opaque-LSAs AS-Wide (Type 11). Because the OSPF-lite protocol has a single 'area' for the AS, Type 10 Opaque LSAs are flooded thoughout the AS (area 0.0.0.0). (3) Not applicable. (4) Otherwise, if the LSA's LS age is equal to MaxAge, and there is currently no instance of the LSA in the router's link state database, and none of router's neighbors are in states Exchange or Loading, then take the following actions: a) Acknowledge the receipt of the LSA by sending a Link State Acknowledgment packet back to the sending neighbor (see Section 13.5), and b) Discard the LSA and examine the next LSA (if any) listed in the Link State Update packet. (5) Otherwise, find the instance of this LSA that is currently contained in the router's link state database. If there is no database copy, or the received LSA is more recent than the database copy (see Section 13.1 below for the determination of which LSA is more recent) the following steps must be performed: (a) If there is already a database copy, and if the database copy was received via flooding and installed less than MinLSArrival seconds ago, discard the new LSA (without acknowledging it) and examine the next LSA (if any) listed in the Link State Update packet. (b) Otherwise, immediately flood the new LSA out some subset of the router's interfaces (see Section 13.3). In many cases with OSPF- lite, the LSA will be flooded back out the receiving interface. This occurrence should be noted for later use by the acknowledgment process (Section 13.5). Thomas et al [Page 93] Internet Draft August 2007 (c) Remove the current database copy from all neighbors' Link state retransmission lists. (d) Install the new LSA in the link state database (replacing the current database copy). This may cause the routing table calculation to be scheduled. In addition, timestamp the new LSA with the current time (i.e., the time it was received). The flooding procedure cannot overwrite the newly installed LSA until MinLSArrival seconds have elapsed. The LSA installation process is discussed further in Section 13.2. (e) Possibly acknowledge the receipt of the LSA by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5. (f) If this new LSA indicates that it was originated by the receiving router itself (i.e., is considered a self-originated LSA that has been flooded back to the router via a circuitous route), the router must take special action, either updating the LSA or in some cases flushing it from the routing domain. For a description of how such self-originated LSAs are detected and subsequently handled, see Section 13.4. (6) Otherwise, if there is an instance of the LSA on the sending neighbor's Link state request list, an error has occurred in the Database Exchange process. In this case, restart the Database Exchange process by generating the neighbor event BadLSReq for the sending neighbor and stop processing the Link State Update packet. (7) Otherwise, if the received LSA is the same instance as the database copy (i.e., neither one is more recent) the following two steps should be performed: (a) If the LSA is listed in the Link state retransmission list for the receiving adjacency, the router itself is expecting an acknowledgment for this LSA. The router should treat the received LSA as an acknowledgment by removing the LSA from the Link state retransmission list. This is termed an 'implied acknowledgment'. Its occurrence should be noted for later use by the acknowledgment process (Section 13.5). (b) Possibly acknowledge the receipt of the LSA by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5. Thomas et al [Page 94] Internet Draft August 2007 (8) Otherwise, the database copy is more recent. If the database copy has LS age equal to MaxAge and LS sequence number equal to MaxSequenceNumber, simply discard the received LSA without acknowledging it. (In this case, the LSA's LS sequence number is wrapping, and the MaxSequenceNumber LSA must be completely flushed before any new LSA instance can be introduced). Otherwise, as long as the database copy has not been sent in a Link State Update within the last MinLSArrival seconds, send the database copy back to the sending neighbor, encapsulated within a Link State Update Packet. The Link State Update Packet should be sent directly to the neighbor. In so doing, do not put the database copy of the LSA on the neighbor's link state retransmission list, and do not acknowledge the received (less recent) LSA instance. 13.1. Determining which LSA is more recent When a router encounters two instances of an LSA, it must determine which is more recent. This occurred above when comparing a received LSA to its database copy. This comparison must also be done during the Database Exchange procedure which occurs during adjacency bring- up. An LSA is identified by its LS type, Link State ID and Advertising Router. For two instances of the same LSA, the LS sequence number, LS age, and LS checksum fields are used to determine which instance is more recent: o The LSA having the newer LS sequence number is more recent. See Section 12.1.6 for an explanation of the LS sequence number space. If both instances have the same LS sequence number, then: o If the two instances have different LS checksums, then the instance having the larger LS checksum (when considered as a 16-bit unsigned integer) is considered more recent. o Otherwise, if only one of the instances has its LS age field set to MaxAge, the instance of age MaxAge is considered to be more recent. o Otherwise, if the LS age fields of the two instances differ by more than MaxAgeDiff, the instance having the smaller (younger) LS age is considered to be more recent. o Otherwise, the two instances are considered to be identical. Thomas et al [Page 95] Internet Draft August 2007 13.2. Installing LSAs in the database Installing a new LSA in the database, either as the result of flooding or a newly self-originated LSA, may cause the OSPF-lite routing table structure to be recalculated. The contents of the new LSA should be compared to the old instance, if present. If there is no difference, there is no need to recalculate the routing table. When comparing an LSA to its previous instance, the following are all considered to be differences in contents: o The LSA's Options field has changed. o One of the LSA instances has its LS age set to MaxAge, and the other does not. o The length field in the LSA header has changed. o The body of the LSA (i.e., anything outside the 20-byte LSA header) has changed. Note that this excludes changes in LS Sequence Number and LS Checksum. If the contents are different, the following pieces of the routing table must be recalculated, depending on the new LSA's LS type field: Router-LSAs The entire routing table must be recalculated, starting with the shortest path calculations for the AS. [Various versions of SPF calculations exist for which some of the processing need not be repeated.] AS-external-LSAs The best route to the destination described by the AS-external-LSA must be recalculated (see Section 16.5). Also, any old instance of the LSA must be removed from the database when the new LSA is installed. This old instance must also be removed from all neighbors' Link state retransmission lists (see Section 10). 13.3. Next step in the flooding procedure When a new (and more recent) LSA has been received, it must be flooded out some set of the router's interfaces. This section describes the second part of flooding procedure (the first part being the processing that occurred in Section 13), namely, selecting the outgoing interfaces and adding the LSA to the appropriate neighbors' Link state retransmission lists. Also included in this part of the flooding procedure is the maintenance of the neighbors' Link state request lists. Thomas et al [Page 96] Internet Draft August 2007 This section is equally applicable to the flooding of an LSA that the router itself has just originated (see Section 12.4). For these LSAs, this section provides the entirety of the flooding procedure (i.e., the processing of Section 13 is not performed, since, for example, the LSA has not been received from a neighbor and therefore does not need to be acknowledged). Depending upon the LSA's LS type, the LSA can be flooded out only on certain interfaces. These interfaces, defined by the following, are called the eligible interfaces: Router LSA's and AS-external-LSAs (LS Type = 5) are flooded throughout the entire AS. The eligible interfaces are all the router's interfaces participating in the OSPF-lite AS. Link state databases must remain synchronized over all adjacencies associated with the above eligible interfaces. This is accomplished by executing the following steps on each eligible interface. For each eligible interface: (1) Each of the neighbors attached to this interface are examined, to determine whether they must receive the new LSA. The following steps are executed for each neighbor: (a) If the neighbor is in a lesser state than Exchange, it does not participate in flooding, and the next neighbour should be examined. (b) Otherwise, if the adjacency is not yet full (neighbor state is Exchange or Loading), examine the Link state request list associated with this adjacency. If there is an instance of the new LSA on the list, it indicates that the neighboring router has an instance of the LSA already. Compare the new LSA to the neighbor's copy: o If the new LSA is less recent, then examine the next neighbor. o If the two copies are the same instance, then delete the LSA from the Link state request list, and examine the next neighbor [6]. o Otherwise, the new LSA is more recent. Delete the LSA from the Link state request list. (c) If the new LSA was received from this neighbor, examine the next neighbor. (d) Add the new LSA to the Link state retransmission list for the adjacency. This ensures that the flooding procedure is reliable; the LSA will be retransmitted at intervals until an acknowledgment is seen from the neighbor. Thomas et al [Page 97] Internet Draft August 2007 (2) The router must now decide whether to flood the new LSA out this interface. If in the previous step, the LSA was NOT added to any of the Link state retransmission lists, there is no need to flood the LSA out the interface and the next interface should be examined. (3) Not applicable. (4) Not applicable. (5) If this step is reached, the LSA must be flooded out the interface. Send a Link State Update packet (including the new LSA as contents) out the interface. The LSA's LS age must be incremented by InfTransDelay (which must be greater than zero) when it is copied into the outgoing Link State Update packet (until the LS age field reaches the maximum value of MaxAge). On all networks, the Link State Update packets are multicast unless retransmitting or replying to specific LSrequests. The destination IP address specified for the Link State Update Packet depends on the state of the interface. The address AllSPFRouters should be used. Note, with OSPF-lite, neighbor adjacencies on NBMA networks are fully meshed. 13.4. Receiving self-originated LSAs It is a common occurrence for a router to receive self-originated LSAs via the flooding procedure. A self-originated LSA is detected when the LSA's Advertising Router is equal to the router's own Router ID. However, if the received self-originated LSA appears to be newer than the last instance that the router actually originated, the router must take special action. The reception of such an LSA indicates that there are LSAs in the routing domain that were originated by the router before the last time it was restarted. In most cases, the router must then advance the LSA's LS sequence number one past the received LS sequence number, and originate a new instance of the LSA. Thomas et al [Page 98] Internet Draft August 2007 Also, the router may no longer wish to originate the received LSA. A possible reason might be that the LSA is an AS-external-LSA and the router no longer has an (advertisable) route to the destination. In this case, instead of updating the LSA, it should be flushed from the routing domain by incrementing the received LSA's LS age to MaxAge and reflooding (see Section 14.1). 13.5. Sending Link State Acknowledgment packets Each newly received LSA must be acknowledged. This is usually done by sending Link State Acknowledgment packets. However, acknowledgments can also be accomplished implicitly by sending Link State Update packets (see step 7a of Section 13). Many acknowledgments may be grouped together into a single Link State Acknowledgment packet. Such a packet is sent back out the interface which received the LSAs. The packet can be sent in one of two ways: delayed and sent on an interval timer, or sent directly to a particular neighbor. The particular acknowledgment strategy used depends on the circumstances surrounding the receipt of the LSA. Sending delayed acknowledgments accomplishes several things: 1) it facilitates the packaging of multiple acknowledgments in a single Link State Acknowledgment packet, 2) it enables a single Link State Acknowledgment packet to indicate acknowledgments to several neighbors at once (through multicasting) and 3) it randomizes the Link State Acknowledgment packets sent by the various routers attached to a common network. The fixed interval between a router's delayed transmissions must be short (less than RxmtInterval) or needless retransmissions will ensue. Direct acknowledgments are sent directly to a particular neighbor in response to the receipt of duplicate LSAs. They are sent directly to the neighbor's IP address, immediately when the duplicate is received. The precise procedure for sending Link State Acknowledgment packets is described in Table 11. The circumstances surrounding the receipt of the LSA are listed in the left column. The acknowledgment action then taken is listed in one of the two right columns. Delayed acknowledgments must be delivered to all adjacent routers associated with the interface. On broadcast networks, this is accomplished by sending the delayed Link State Acknowledgment packets as multicasts. Thomas et al [Page 99] Internet Draft August 2007 Action taken in state Circumstances All Routers _________________________________________________________________ LSA has No acknowledgment been flooded back sent. out receiving in- terface (see Sec- tion 13, step 5b). _________________________________________________________________ LSA is more recent Delayed acknowledg- than database copy, ment sent but was not flooded back out receiving interface. _________________________________________________________________ LSA is a duplicate, Delayed acknowledg- and was treated as ment sent. an implied acknowledgment (see Section 13, step 7a). _________________________________________________________________ LSA is a duplicate, Direct acknowledg- and was not treated ment sent. as an implied acknowledgment. _________________________________________________________________ LSA's LS age is Direct acknowledg- equal to MaxAge, and ment sent. there is no current instance of the LSA in the link state database, and none of router's neighbors are in states Exchange or Loading (see Section 13, step 4). Table 11: Sending link state acknowledgements. In all states, the destination AllSPFRouters is used. Multicasting is used irrespective of the underlying network type. Layer 3 to Layer 2 mapping (as with Frame Relay inverse-arp) is required to transmit Layer 3 multicasts over NBMA networks. No protocol specific configuration is required. Thomas et al [Page 100] Internet Draft August 2007 13.6. Retransmitting LSAs LSAs flooded out an adjacency are placed on the adjacency's Link state retransmission list. In order to ensure that flooding is reliable, these LSAs are retransmitted repeatedly until they are acknowledged. The length of time between retransmissions is a configurable per-interface value, RxmtInterval. If this time is set too short for an interface, needless retransmissions will ensue. If the value is set too long, the speed of the flooding, in the face of lost packets, may be affected. Retransmissions are sent to the neighbors unicast address on all networks. Several retransmitted LSAs may fit into a single Link State Update packet. When LSAs are to be retransmitted, only the number fitting in a single Link State Update packet should be sent. Another packet of retransmissions can be sent whenever some of the LSAs are acknowledged, or upon the next firing of the retransmission timer. Link State Update Packets carrying retransmissions are always sent directly to the neighbor,on all networks. This means that retransmissions are sent directly to the neighbor's IP address. Each LSA's LS age must be incremented by InfTransDelay when it is copied into the outgoing Link State Update packet (until the LS age field reaches the maximum value of MaxAge). InfTransDelay can be set to zero With ospf-lite. If an adjacent router goes down, retransmissions may occur until the adjacency is destroyed by OSPF-lite's Hello Protocol. When the adjacency is destroyed, the Link state retransmission list is cleared. 13.7. Receiving link state acknowledgments Many consistency checks have been made on a received Link State Acknowledgment packet before it is handed to the flooding procedure. In particular, it has been associated with a particular neighbor. If this neighbor is in a lesser state than Exchange, the Link State Acknowledgment packet is discarded. Otherwise, for each acknowledgment in the Link State Acknowledgment packet, the following steps are performed: o Does the LSA acknowledged have an instance on the Link state retransmission list for the neighbor? If not, examine the next acknowledgment. Otherwise: Thomas et al [Page 101] Internet Draft August 2007 o If the acknowledgment is for the same instance that is contained on the list, remove the item from the list and examine the next acknowledgment. Otherwise: o Log the questionable acknowledgment, and examine the next one. 14. Aging The Link State Database Each LSA has an LS age field, which is incremented while it is contained in a router's database. The LS age is expressed in seconds. Also, when copied into a Link State Update Packet for flooding out a particular interface, the LSA's LS age is incremented by InfTransDelay. An LSA's LS age is never incremented past the value MaxAge. LSAs having age MaxAge are not used in the ospf-lite routing table calculation. As a router ages its link state database, an LSA's LS age may reach MaxAge. [With the LSRefresh timer this should not occur]. At this time, the router must attempt to flush the LSA from the routing domain. This is done simply by reflooding the MaxAge LSA just as if it were a newly originated LSA (see Section 13.3). When creating a Database summary list for a newly forming adjacency, any MaxAge LSAs present in the link state database are added to the neighbor's Link state retransmission list instead of the neighbor's Database summary list. See Section 10.3 for more details. A MaxAge LSA must be removed immediately from the router's link state database as soon as both a) it is no longer contained in any neighbor Link state retransmission lists and b) none of the router's neighbors are in states Exchange or Loading. Checking checksums of LSAs at set intervals in the LS database is not required with ospf-lite, and the timer CheckAge has been removed. 14.1. Premature aging of LSAs An LSA can be flushed from the routing domain by setting its LS age to MaxAge, while leaving its LS sequence number alone, and then reflooding the LSA. This procedure follows the same course as flushing an LSA whose LS age has naturally reached the value MaxAge (see Section 14). In particular, the MaxAge LSA is removed from the router's link state database as soon as a) it is no longer contained on any neighbor Link state retransmission lists and b) none of the router's neighbors are in states Exchange or Loading. We call the setting of an LSA's LS age to MaxAge "premature aging". Thomas et al [Page 102] Internet Draft August 2007 Premature aging is used when it is time for a self-originated LSA's sequence number field to wrap. At this point, the current LSA instance (having LS sequence number MaxSequenceNumber) must be prematurely aged and flushed from the routing domain before a new instance with sequence number equal to InitialSequenceNumber can be originated. See Section 12.1.6 for more information. Premature aging can also be used when, for example, one of the router's previously advertised external routes is no longer reachable. In this circumstance, the router can flush its AS- external-LSA from the routing domain via premature aging. This procedure is preferable to the alternative, which is to originate a new LSA for the destination specifying a metric of LSInfinity. Premature aging is also be used when unexpectedly receiving self-originated LSAs during the flooding procedure (see Section 13.4). A router may only prematurely age its own self-originated LSAs. The router may not prematurely age LSAs that have been originated by other routers. An LSA is considered self- originated when the LSA's Advertising Router is equal to the router's own Router ID. 15. Virtual Links are not supported in OSPF-lite 16. Calculation of the ospf-lite routing table 16.0.1. Introduction to Calculations (see also 2.1.2.4) Unless explicity specified all reouting table references refer to the internal protocol ospf-lite routing table, and not the Main routing table of the device. Router LSAs arrive at a router through the process of flooding or are generated locally. The LSAs should be stored in such a way as to facilitate easy access to the data they contain. Matrix 1 and matrix 2 shown in figures 15.1 and 15.2 represent one suggestion as to how to do this; depending on the actual data structures used to represent them (for example using pointers), having two tables may expedite information retrieval. The networks are shown as arcs to connect the router transit vertices. Thomas et al [Page 103] Internet Draft August 2007 Initial processing matrix 1 **FROM** |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT| |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12| ----- ---------------------------------- | | | | | | | | | | | | | **TO** | | | | | | | | | | | | | | | | | | | | | | | | | | o-lite-stub N1|3 | | | | | | | | | | | | o-lite-stub N2| |3 | | | | | | | | | | | o-lite-transit N3|1 |1 |1 |1 | | | | | | | | |<-multiple o-lite-stub N4| | |2 | | | | | | | | | | o-lite-transit N5| | |8 | | |6 | | | | | | | o-lite-transit N6| | | | | | |1 |1 | |1 | | |<-multiple o-lite-stub N7| | | | | | | |4 | | | | | o-lite-transit N8| | | | | | | | | |3 |2 | | o-lite-transit N9| | | | | | | | |1 | |1 |1 |<-multiple o-lite-stub N10| | | | | | | | | | | |2 | o-lite-stub N11| | | | | | | | |3 | | | | o-lite-transit N16| | | | | |7 | | | |5 | | | o-lite-transit N17| | | | |6 | |6 | | | | | | o-lite-transit N18| | | | |7 |6 | | | | | | | o-lite-transit N19| | | |8 |8 | | | | | | | | external lsa5 N12| | | | |8 | |2 | | | | | | external lsa5 N13| | | | |8 | | | | | | | | external lsa5 N14| | | | |8 | | | | | | | | external lsa5 N15| | | | | | |9 | | | | | | Figure 15.1 Each Column is built from a Router LSA 16.0.2. Connect router transit vertices with implied arcs If a network has two routers connected and is advertised as OSPF-lite-transit then create an implied arc to connect the two router transit vertices in the graph representation. Although figure 15.1 and 15.2 appear to be rotations of the same table, the difference lies in the way the data is accessed. In figure 15.1 (read 'from' the top, 'to' the side) the Router LSAs are listed. Figure 15.2 shows how the networks are used to connect the routers (again read 'from' the top 'to' the side). Thomas et al [Page 104] Internet Draft August 2007 **FROM** |N|N|N|N|N|N|N|N|N|N |N | |N |N |N |N |N | |1|2|3|4|5|6|7|8|9|10|11| |15|16|17|18|19| -------------------------------------------------- **TO** RT1 |3| |1| | | | | | | | | | | | | | | RT2 | |3|1| | | | | | | | | | | | | | | RT3 | | |1|2|8| | | | | | | | | | | | | RT4 | | |1| | | | | | | | | | | | | |8 | RT5 | | | | | | | | | | | | | | |6 |7 |8 | RT6 | | | | |6| | | | | | | | |7 | |6 | | RT7 | | | | | |1| | | | | | |9 | | | | | RT8 | | | | | |1|4| | | | | | | | | | | RT9 | | | | | | | | |1| |3 | | | | | | | RT10| | | | | |1| |3| | | | | |5 | | | | RT11| | | | | | | |2|1| | | | | | | | | RT12| | | | | | | | |1|2 | | | | | | | | ^ ^ ^ IV IV IV N3, N6, and N9 can be represented as implied vertices Figure 15.2 Initial processing matrix 2 Figures 15.1, 15.2 and 15.3 are all generated prior to any Dijkstra calculation and show part of the data structure initialization. 16.0.3. Create implied transit vertices if desired If a network has more than two routers connected that are advertising the network as transit then implied transit vertices can be created in the graph. Networks 3, 6 and 9 have more than two connected routers. Figure 15.3 lists the networks that could be represented as implied transit vertices from figure 15.2 Thomas et al [Page 105] Internet Draft August 2007 Implied Vertices N |3|6|9| ----------- RT1 |1| | | RT2 |1| | | RT3 |1| | | RT4 |1| | | RT5 | | | | RT6 | | | | RT7 | |1| | RT8 | |1| | RT9 | | |1| RT10| |1| | RT11| | |1| RT12| | |1| Figure 15.3 Implied Transit Vertices 16.0.4. Adding Stub Vertices For stage two, create implied stub vertices for the remaining networks. The rest of the networks; OSPF-lite-stub, OSPF-lite-transit (with fewer than three routers) and external networks can be added as implied Stub vertices during stage two. 16.0.5. External networks and implied arcs External routes can be added during the second stage but Implied Arcs must not be created between router vertices that advertise the same external network. The external LSAs are processed, so that this information can be added to the table. 16.0.6. Full graph (see Section 2.1.2.4) The information contained in figures 15.1, 15.2 and 15.3 could be represented in the format of figure 16. Thomas et al [Page 106] Internet Draft August 2007 Full graph for two stage system TRANSIT VERTICES (pass 1) ------------------------- **FROM** Implied |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|T Vertex |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N9| ----- ------------------------------------------- **TO** RT1| | | | | | | | | | | | |0 | | | RT2| | | | | | | | | | | | |0 | | | RT3| | | | | |6 | | | | | | |0 | | | RT4| | | | |8 | | | | | | | |0 | | | RT5| | | |8 | |6 |6 | | | | | | | | | RT6| | |8 | |7 | | | | |5 | | | | | | RT7| | | | |6 | | | | | | | | |0 | | RT8| | | | | | | | | | | | | |0 | | RT9| | | | | | | | | | | | | | |0 | RT10| | | | | |7 | | | | |2 | | |0 | | RT11| | | | | | | | | |3 | | | | |0 | RT12| | | | | | | | | | | | | | |0 | Implied T Vertex N3|1 |1 |1 |1 | | | | | | | | | | | | Implied T Vertex N6| | | | | | |1 |1 | |1 | | | | | | Implied T Vertex N9| | | | | | | | |1 | |1 |1 | | | | ---------------------------------------------------------------- STUB VERTICES (stage 2) ---------------------------------------------------------------- o-lite-stub N1|3 | | | | | | | | | | | | | | | o-lite-stub N2| |3 | | | | | | | | | | | | | | o-lite-stub N4| | |2 | | | | | | | | | | | | | o-lite-stub N7| | | | | | | |4 | | | | | | | | o-lite-stub N10| | | | | | | | | | | |2 | | | | o-lite-stub N11| | | | | | | | |3 | | | | | | | ---------------------------------------------------------------- STUB VERTICES (stage 2) cont... ---------------------------------------------------------------- o-lite-transit N5| | |8 | | |6 | | | | | | | | | | o-lite-transit N8| | | | | | | | | |3 |2 | | | | | o-lite-transit N16| | | | | |7 | | | |5 | | | | | | o-lite-transit N17| | | | |6 | |6 | | | | | | | | | o-lite-transit N18| | | | |7 |6 | | | | | | | | | | o-lite-transit N19| | | |8 |8 | | | | | | | | | | | ---------------------------------------------------------------- STUB VERTICES (stage 2) cont... ---------------------------------------------------------------- external lsa5 N12| | | | |8 | |2 | | | | | | | | | external lsa5 N13| | | | |8 | | | | | | | | | | | external lsa5 N14| | | | |8 | | | | | | | | | | | external lsa5 N15| | | | | | |9 | | | | | | | | | Figure 16. Data stored from the Router LSAs Thomas et al [Page 107] Internet Draft August 2007 16.0.7. Calculating the SPF tree and resulting table. This section details the OSPF-lite routing table calculation. Using the link state databases as input, each router runs the following algorithm, building its ospf-lite routing table step by step. At each step, the router must access individual pieces of the link state database (e.g., a router-LSA originated by a certain router). This access is performed by the lookup function discussed in Section 12.2. The lookup process may return an LSA whose LS age is equal to MaxAge. Such an LSA should not be used in the ospf-lite routing table calculation, and is treated just as if the lookup process had failed. The OSPF-lite routing table is briefly overviewd in Section 11. The build process for the table can be seperated into the following steps: 16.0.7.1 Preloading Main device routing table If there are any ospf-lite-stub host links on directly connected networks (ie: ip addresses with 32 bit masks), then offer these routes to the main routing process as finished routes: An example follows from Section 12.4.4.2, and Section 2.2.1. RT101s LSA is reproduced here as figure 17.1: ; RT101's router-LSA for AS LS age = 0 ;always true on origination Options = (E-bit set) ;Mandatory with OSPF-lite LS type = 1 ;indicates router-LSA Link State ID = 1.1.1.0 ;RT101's Router ID Advertising Router = 1.1.1.1 ;RT101's Router ID bit B = 0 ;Unsupported options set to zero #links = 2 Link ID = 1.1.1.1 ;Interface IP address. Link Data = 0xffffff00 ;Network Mask Type = 9 ;OSPF-lite-transit # TOS metrics = 0 metric = 3 ;cost = 3 >> Link ID = 1.1.1.1 ;Interface IP address << >> Link Data = 0xffffffff ;32 bit HOST mask << Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 Figure 17.1 RT101s router LSA Thomas et al [Page 108] Internet Draft August 2007 Link extracted from RT101s Router LSA (on same 1.1.1.0 network): >> Link ID = 1.1.1.1 ;Interface IP address << >> Link Data = 0xffffffff ;32 bit HOST mask << Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 Link extracted from RT102s Router LSA (on same 1.1.1.0 network): >> Link ID = 1.1.1.2 ;Interface IP address << >> Link Data = 0xffffffff ;32 bit HOST mask << Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 Link extracted from RT103s Router LSA (on same 1.1.1.0 network): >> Link ID = 1.1.1.3 ;Interface IP address << >> Link Data = 0xffffffff ;32 bit HOST mask << Type = 8 ;OSPF-lite-stub # TOS metrics = 0 metric = 3 Figure 17.2 Extracted 32 bit host routes In order to promote connectivity on non fully meshed networks, we are recommending the addition of directly connected 32-bit host links as seen in figure 17.2, to the router's Main routing table. These routes need not be analysed further as they are OSPF-lite-stub. As 32-bit host routes they cannot constitute implied transit vertices. In graphical terms they would constitute implied stub vertices, and as they are directly connected no more processing is required. They can be added to the Router's main routing table before further processing. RT101s Main routing table would appear as follows after the addition: Dest network 1.1.1.0 255.255.255.0 Directly connected Dest network 1.1.1.2 255.255.255.255 next hop 1.1.1.2 Dest network 1.1.1.3 255.255.255.255 next hop 1.1.1.3 Thomas et al [Page 109] Internet Draft August 2007 And the internal ospf-lite Routing table: Dest network 1.1.1.0 255.255.255.0 next hop 1.1.1.1 Dest network 1.1.1.1 255.255.255.255 next hop 1.1.1.1 Dest network 1.1.1.2 255.255.255.255 next hop 1.1.1.2 Dest network 1.1.1.3 255.255.255.255 next hop 1.1.1.3 Although not essential for these routes to be preloaded, this will increase response time for neighbor discovery on non fully meshed networks. See section 12.4.4.2 for a non fully meshed NBMA example (figure 14). (1) The present Main routing table with the added directly connected host routes should be used by the router during the calculation and refreshed after the new table is calculated. The OSPF-lite routing table is calculated from scratch. (2) The AS routes are calculated by building the shortest- path tree for the AS. This step is described in two parts: At first the tree is constructed by only considering those links between routers and transit network vertices. Then the stub networks are incorporated into the tree as implied stub vertices. (3) N/A (4) N/A (5) Routes to external destinations are calculated during this second stage, through examination of AS-external-LSAs. The Above Steps 1-2 are explained in further detail below. Changes made to the ospf-lite routing table entries as a result of these calculations can cause the ospf-lite protocol to take further actions. 16.1. Calculation of the AS SFP tree (with OSPF-lite Implied transit Vertices.) This calculation yields the set of AS routes associated with the AS. A router calculates the shortest-path tree using itself as the root. [Strictly speaking, because of equal-cost multipath, the algorithm does not create a pure tree. However we will continue to use the "tree" terminology to comply with existing literature]. Thomas et al [Page 110] Internet Draft August 2007 The formation of the shortest path tree is done here in two stages. In the first stage, only links between router vertices and transit network vertices are considered. Using the Dijkstra algorithm, a tree is formed from this subset of the link state database. In the second stage, leaves are added to the tree by considering the links to stub network vertices, and external networks which are also represented by stub network vertices. The procedure will be explained using the graph terminology that was introduced in Section 2. The AS's link state database is represented as a directed graph. The graph's vertices are routers, transit networks with more than two routers and, in stage 2, the stub network vertices. The first stage of the procedure concerns only the transit vertices (routers and implied transit vertices) and their connecting links. Throughout the shortest path calculation, the following data is also associated with each transit vertex: Vertex (node) ID A 32-bit number which together with the vertex type (router or network) uniquely identifies the vertex. For router vertices the Vertex ID is the router's OSPF-lite Router ID. For network vertices, it is the network number. An LSA Only Router transit vertices have an associated LSA, which is the router-LSA. Implied transit vertices are produced from the information contained in the Router LSAs. List of next hops The list of next hops for the current set of shortest paths from the root to this vertex. There can be multiple shortest paths due to the equal-cost multipath capability. Each next hop indicates the outgoing router interface to use when forwarding traffic to the destination. On ALL media except un-numbered, the next hop also includes the IP address of the next router (if any) in the path towards the destination. Distance from root The link state cost of the current set of shortest paths from the root to the vertex. The link state cost of a path is calculated as the sum of the costs of the path's constituent links (as advertised in the router-LSAs). One path is said to be "shorter" than another if it has a smaller link state cost. The first stage of the procedure (i.e., the Dijkstra algorithm) can now be summarized as follows. At each iteration of the algorithm, there is a list of candidate vertices. Paths from Thomas et al [Page 111] Internet Draft August 2007 the root to these vertices have been found, but not necessarily the shortest ones. However, the paths to the candidate vertex that is closest to the root are guaranteed to be shortest; this vertex is added to the shortest-path tree, removed from the candidate list, and its adjacent vertices are examined for possible addition to/modification of the candidate list. The algorithm then iterates again. It terminates when the candidate list becomes empty. The following steps describe the algorithm in detail. Remember that we are computing the shortest path tree for the AS. All references to link state database lookup below are from the entire AS database. (1) Initialize the algorithm's data structures. (For OSPF-lite, this includes storing the implied information from Matrix 1 and 2 (figures 14 and 15) for the Network OSPF-lite-transit vertices.) Clear the list of candidate vertices. Initialize the shortest-path tree to only the root (which is the router carrying out the calculation). (Areas are not supported in OSPF-lite). (2) Call the vertex just added to the tree vertex V. Examine the LSA associated with vertex V. This is a lookup in the link state database based on the Vertex ID. Each link described by the LSA gives the cost to an adjacent vertex. For each described link, (say it joins vertex V to vertex W): (a) If this is a link to an OSPF-lite-stub network, examine the next link in V's LSA. Links to OSPF-lite-stub networks will be considered in the second stage of the shortest path calculation. (b) Otherwise, W is a transit vertex (router or inplied transit vertex). Look up the vertex W's LSA (if a router-LSA) in the link state database, or the implied information from Matrix 2. IF the LSA does not exist for a router LSA type 1, or its LS age is equal to MaxAge, or it does not have a link back to vertex V, examine the next link in V's LSA.[7] (c) If vertex W is already on the shortest-path tree, examine the next link in the LSA. (d) Calculate the link state cost D of the resulting path from the root to vertex W. D is equal to the sum of the link state cost of the (already calculated) shortest path to vertex V and the advertised cost of the link between vertices V and W. If D is: Thomas et al [Page 112] Internet Draft August 2007 o Greater than the value that already appears for vertex W on the candidate list, then examine the next link. o Equal to the value that appears for vertex W on the candidate list, calculate the set of next hops that result from using the advertised link. Input to this calculation is the destination (W), and its parent (V). This calculation is shown in Section 16.1.1. This set of hops should be added to the next hop values that appear for W on the candidate list. o Less than the value that appears for vertex W on the candidate list, or if W does not yet appear on the candidate list, then set the entry for W on the candidate list to indicate a distance of D from the root. Also calculate the list of next hops that result from using the advertised link, setting the next hop values for W accordingly. The next hop calculation is described in Section 16.1.1; it takes as input the destination (W) and its parent (V). (3) If at this step the candidate list is empty, the shortest- path tree (of transit vertices) has been completely built and this stage of the procedure terminates. Otherwise, choose the vertex belonging to the candidate list that is closest to the root, and add it to the shortest-path tree (removing it from the candidate list in the process). Note that when there is a choice of vertices closest to the root, network vertices should be chosen before router vertices in order to necessarily find all equal-cost paths. This is consistent with the tie-breakers that were introduced in the modified Dijkstra algorithm used by OSPF Multicast routing extensions (MOSPF-lite). (4) Possibly modify the ospf-lite routing table. For those ospf-lite routing table entries modified, the cost will be set to the newly discovered shortest path's calculated distance. If the newly added vertex is an AS boundary router, an ospf-lite routing table entry is added whose destination type is "router". The Options field found in the associated router-LSA is copied into the routing table entry's Optional capabilities field. Call the newly added vertex Router X. (5) Iterate the algorithm by returning to Step 2. The OSPF-lite-stub networks, and OSPF-lite-transit networks with no more than two routers are added to the graph at this stage. They are added as implied stub vertices. In this stage, all router vertices are again examined. Those that have been determined to be unreachable (this should not occur) in the above first phase are Thomas et al [Page 113] Internet Draft August 2007 discarded. For each reachable router vertex (call it V), the associated router-LSA is found in the link state database. Each OSPF-lite-stub network link or OSPF-lite-transit link (with no more than two routers) appearing in the LSA is then examined, and the following steps are executed: (1) Calculate the distance D of the new stub vertex from the root. D is equal to the distance from the root to the router transit vertex (calculated in stage 1), plus the stub vertex's link's advertised cost. Compare this distance to the current best cost to the stub vertex. This is done by looking up the stub vertex's current ospf-lite routing table entry. If the calculated distance D is larger, go on to examine the next stub vertex link in the LSA. (2) If this step is reached, the stub vertex's ospf-lite routing table entry must be updated. Calculate the set of next hops that would result from using the stub vertex network link. This calculation is shown in Section 16.1.1; input to this calculation is the destination (the stub network) and the parent vertex (the router vertex). If the distance D is the same as the current ospf-lite routing table cost, simply add this set of next hops to the ospf-lite routing table entry's list of next hops. In this case, the ospf-lite routing table already has a Link State Origin. If this Link State Origin is a router-LSA whose Link State ID is smaller than V's Router ID, reset the Link State Origin to V's router-LSA. Otherwise D is smaller than the ospf-lite routing table cost. Overwrite the current ospf-lite routing table entry by setting the ospf-lite routing table entry's cost to D, and by setting the entry's list of next hops to the newly calculated set. Set the ospf-lite routing table entry's Link State Origin to V's router-LSA. Then go on to examine the next stub vertex link. When the list of reachable router-LSAs is exhausted, the second stage is completed. At this time, all intra-AS routes associated with the AS have been determined. The specification does not require that the above two stage method be used to calculate the shortest path tree. However, if another algorithm is used, an identical tree must be produced. For this reason, it is important to note that links between transit vertices must be bidirectional in order to be included in the above tree. It should also be mentioned that more efficient algorithms exist for calculating the tree; for example, the incremental SPF algorithm described in [ref15]. Thomas et al [Page 114] Internet Draft August 2007 16.1.1. The next hop calculation This section explains how to calculate the current set of next hops to use for a destination. Each next hop consists of the outgoing interface to use in forwarding packets to the destination together with the IP address of the next hop router (if any). The next hop calculation is invoked each time a shorter path to the destination is discovered. This can happen in either stage of the shortest-path tree calculation (see Section 16.1). In stage 1 of the shortest-path tree calculation a shorter path is found as the destination is added to the candidate list, or when the destination's entry on the candidate list is modified (Step 2d of Stage 1). In stage 2 a shorter path is discovered each time the destination's ospf-lite routing table entry is modified (Step 2 of Stage 2). The set of next hops to use for the destination may be recalculated several times during the shortest-path tree calculation, as shorter and shorter paths are discovered. In the end, the destination's ospf-lite routing table entry will always reflect the next hops resulting from the absolute shortest path(s). Input to the next hop calculation is a) the destination and b) its parent in the current shortest path between the root (the calculating router) and the destination. The parent is always a transit vertex router. If there is at least one intervening router in the current shortest path between the destination and the root, the destination simply inherits the set of next hops from the parent. Otherwise, there are two cases. In the first case, the parent vertex is the root (the calculating router itself). This means that the destination is either a directly connected network (or external network) or a directly connected router. The outgoing interface in this case is simply the OSPF-lite interface connecting to the destination network/router. If the destination is a router which connects to the calculating router via an OSPF-lite-transit network, the destination's next hop IP address(es) can be determined by examining the destination's router-LSA: each link pointing back to the calculating router and having a Link Data field belonging to the OSPF-lite-transit link type, provides an IP address of the next hop router. The outgoing interface to use can then be derived from the next hop IP address (or it can be inherited from the parent network). Thomas et al [Page 115] Internet Draft August 2007 16.2. Not applicabe 16.3. Not applicable 16.4. Calculating AS external routes AS external routes are calculated by examining AS-external-LSAs. Each of the AS-external-LSAs is considered in turn. Most AS- external-LSAs describe routes to specific IP destinations. An AS-external-LSA can also describe a default route for the Autonomous System (Destination ID = DefaultDestination, network/subnet mask = 0x00000000). For each AS-external-LSA: (1) If the cost specified by the LSA is LSInfinity, or if the LSA's LS age is equal to MaxAge, then examine the next LSA. (2) If the LSA was originated by the calculating router itself, examine the next LSA. (3) Call the destination described by the LSA N. N's address is obtained by masking the LSA's Link State ID with the network/subnet mask contained in the body of the LSA. Look up the ospf-lite routing table entries for the AS boundary router (ASBR) that originated the LSA. If no entries exist for router ASBR (i.e., ASBR is unreachable), do nothing with this LSA and consider the next in the list. Otherwise, this LSA describes an AS external path to destination N. Examine the forwarding address specified in the AS-external-LSA. This indicates the IP address to which packets for the destination should be forwarded. If the forwarding address is set to 0.0.0.0, packets should be sent to the ASBR itself. Among the multiple ospf-lite routing table entries for the ASBR, select the preferred entry as follows: Prune the set of ospf-lite routing table entries for the ASBR. In any case, among the remaining ospf-lite routing table entries, select the ospf-lite routing table entry with the least cost; If there are multiple least cost routing Paths then load share all being equal. If the forwarding address is non-zero, look up the forwarding address in the ospf-lite routing table. The matching ospf-lite routing table entry must specify an intra-AS path; if no such path exists, do nothing with the LSA and consider the next in the list. (4) Let X be the cost specified by the preferred ospf-lite routing table entry for the ASBR/forwarding address, and Y the cost specified in the LSA. X is in terms of the link state metric, and Y is a type 1 or 2 external metric. Thomas et al [Page 116] Internet Draft August 2007 (5) Look up the ospf-lite routing table entry for the destination N. If no entry exists for N, install the AS external path to N, with next hop equal to the list of next hops to the forwarding address, and advertising router equal to ASBR. If the external metric type is 1, then the path-type is set to type 1 external, and the cost is equal to X+Y. If the external metric type is 2, the path-type is set to type 2 external, the link state component of the route's cost is X, and the type 2 cost is Y. (6) Compare the AS external path described by the LSA with the existing paths in N's ospf-lite routing table entry, as follows: If the new path is preferred, it replaces the present paths in N's ospf-lite routing table entry. If the new path is of equal preference, it is added to N's ospf-lite routing table entry's list of paths. (a) Intra-AS paths are always preferred over AS external paths. (b) Type 1 external paths are always preferred over type 2 external paths. When all paths are type 2 external paths, the paths with the smallest advertised type 2 metric are always preferred. (c) N/A all paths within ospf-lite are single area. (d) If the new AS external path is still indistinguishable from the current paths in the N's ospf-lite routing table entry, select the preferred path based on a least cost comparison. Type 1 external paths are compared by looking at the sum of the distance to the forwarding address and the advertised type 1 metric (X+Y). Type 2 external paths advertising equal type 2 metrics are compared by looking at the distance to the forwarding addresses. 16.4.1. Not applicable 16.5. Not applicable 16.6. Incremental updates - AS-external-LSAs When a new AS-external-LSA is received, it is not necessary to recalculate the entire ospf-lite routing table. The procedure outlined in Section 16.4 can be followed. 16.7. Not applicable Thomas et al [Page 117] Internet Draft August 2007 16.8. Equal-cost multipath The OSPF-lite protocol maintains multiple equal-cost routes to all destinations. This can be seen in the steps used above to calculate the ospf-lite routing table, and in the definition of the ospf-lite routing table structure. Each one of the multiple routes will be of the same type (intra-AS, type 1 external or type 2 external), and cost, However, each route may specify a separate next hop and advertising router. There is no requirement that a router running OSPF-lite maintain records of all possible equal-cost routes to a destination. Thomas et al [Page 118] Internet Draft August 2007 Footnotes [1]Note that it is possible for a router to resynchronize any of its fully established adjacencies by setting the adjacency's state back to ExStart. This will cause the other end of the adjacency to process a SeqNumberMismatch event, and therefore to also go back to ExStart state. [2]The address space of IP networks and the address space of OSPF Version 2 Router IDs may overlap. That is, a network must not have an IP address which is identical (when considered as a 32-bit number) to some router's Router ID. This SHOULD not happen with OSPF-lite. [3]MaxAgeDiff is an architectural constant. It indicates the maximum dispersion of ages, in seconds, that can occur for a single LSA instance as it is flooded throughout the AS. If two LSAs differ by more than this, they are assumed to be different instances of the same LSA. This can occur when a router restarts and loses track of the LSA's previous LS sequence number. See Section 13.4 for more details. [4]When two LSAs have different LS checksums, they are assumed to be separate instances. This can occur when a router restarts, and loses track of the LSA's previous LS sequence number. In the case where the two LSAs have the same LS sequence number, it is not possible to determine which LSA is actually newer. However, if the wrong LSA is accepted as newer, the originating router will simply originate another instance. See Section 13.4 for further details. [5] An Implied transit Network Vertex is constructed before or during the SPF process for OSPF-lite. This is documented in sections 16.0.1 to 16.0.4. As such there is no LSA to reference for such an implied transit vertex. [6]This is how the Link state request list is emptied, which eventually causes the neighbor state to transition to Full. See Section 10.9 for more details. [7]Note that the presence of any link back to V is sufficient; it need not be the matching half of the link under consideration from V to W. This is enough to ensure that, before data traffic flows between a pair of neighboring routers, their link state databases will be synchronized. Thomas et al [Page 119] Internet Draft August 2007 Normative References [ref1] Moy, J., "OSPF Version 2", RFC 2328, STD 54, April 1998. [ref2] Leiner, B., et.al., "The DARPA Internet Protocol Suite", DDN Protocol Handbook, April 1985 [ref3] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC 1700, October 1994. [ref4] Fuller, V., T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC1519, September 1993. [Ref5] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. [ref6] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [ref7] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, July 1998. [ref8] Deering, S., "Host extensions for IP multicasting", STD 5, RFC 1112, May 1988. Informative Refereces [ref9] Katz, D., Kompella, K., and Yeung, D., "Traffic Engineering (TE) Extensions to OSPF Version 2", RFC 3630, September 2003. [ref10] Mogul, J., and S. Deering, "Path MTU Discovery", RFC 1191, November 1990. [ref11] K. Kompella, Y. Rekhter, "OSPF Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS)" RFC 4203, October 2005. [ref12] McKenzie, A., "ISO Transport Protocol specification ISO DP 8073", RFC 905, April 1984. [ref13] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, July 1992. [ref14] McCloghrie, K., and M. Rose, "Management Information Base for network management of TCP/IP-based internets: MIB-II", STD 17, RFC 1213, March 1991. [ref15] McQuillan, J., I. Richer and E. Rosen, "ARPANET Routing Algorithm Improvements", BBN Technical Report 3803, April 1978. Thomas et al [Page 120] Internet Draft August 2007 [ref16] McQuillan, J., et.al., "The New Routing Algorithm for the ARPANET", IEEE Transactions on Communications, May 1980. [ref17] Moy, J., "Extending OSPF to Support Demand Circuits", RFC 1793, April 1995. [ref18] www.cisco.com [ref19] Moy, J., "Multicast Extensions to OSPF Version 2 ", RFC 1584, March 1994. [ref20] Bellovin, S., "Security Problems in the TCP/IP Protocol Suite", ACM Computer Communications Review, Volume 19, Number 2, pp. 32-38, April 1989. [ref21] Perlman, R., "Fault-Tolerant Broadcast of Routing Information", Computer Networks, December 1983. [ref22] Hinden, R., "Internet Routing Protocol Standardization Criteria", BBN, October 1991. A. OSPF-lite Data formats This Appendix describes the format of OSPF-lite protocol packets and OSPF-lite LSAs. The OSPF-lite protocol runs directly over the IP network layer protocol. Before any data formats are described, the details of OSPF-lite encapsulation are explained. Next the OSPF-lite Options field is described, which describes various capabilities that may or may not be supported by pieces of the OSPF-lite routing domain. It is contained in OSPF-lite Hello packets, Database Description packets and in OSPF-lite LSAs. Some of the options are not applicable to OSPF-lite and must be set to zero. OSPF-lite packet formats are detailed in Section A.3. A description of OSPF-lite LSAs appears in Section A.4. A.1 Encapsulation of OSPF-lite packets OSPF-lite runs directly over the IP network layer protocol, hence OSPF-lite packets are encapsulated solely by IP and local data-link headers. OSPF-lite does not define a way to fragment its protocol packets, and depends on IP fragmentation when transmitting packets larger than the network MTU. If necessary, the length of OSPF-lite packets Thomas et al [Page 121] Internet Draft August 2007 can be up to 65,535 bytes (including the IP header). The OSPF-lite packet types that are likely to be large (Database Description Packets, Link State Request, Link State Update, and Link State Acknowledgment packets) can usually be split into several separate protocol packets, without loss of functionality. This is recommended; IP fragmentation should be avoided whenever possible. The other important features of OSPF-lite's IP encapsulation are: o Use of IP multicast. Some OSPF-lite messages are multicast. Packets sent to this multicast address should never be forwarded; they are meant to travel a single hop only. To ensure that these packets will not travel multiple hops, their IP TTL must be set to 1. AllSPFRouters This multicast address has been assigned the value 224.0.0.5. All routers running OSPF-lite should be prepared to receive packets sent to this address. Hello packets are always initially sent to this destination. Also, certain OSPF-lite protocol packets are sent to this address during the flooding procedure. o OSPF uses IP protocol number 89. This number has been registered for use with OSPF with the Network Information Center. IP protocol number assignments are documented in [ref3]. o All OSPF-lite routing protocol packets are sent using the normal service TOS value of binary 0000 defined in [ref13]. o Routing protocol packets are sent with IP precedence set to Internetwork Control. OSPF-lite protocol packets should be given precedence over regular IP data traffic, both whtn sending and when receiving. Setting the IP precedence field in the IP header to Internetwork Control [Ref5] may help implement this objective. A.2 The Options field The OSPF-lite Options field is present in OSPF-lite Hello packets, Database Description packets and all LSAs. The Options field enables OSPF-lite routers to support (or, as appropriate, not support) optional capabilities, and to communicate their capability level to other OSPF-lite routers. Through this mechanism different capabilities can be enabled. When used in Hello packets, the Options field allows a router to reject a neighbor because of a capability mismatch. Alternatively, when capabilities are exchanged in Database Description packets a router could in theory choose not to forward certain LSAs to a neighbor because of its reduced functionality. Thomas et al [Page 122] Internet Draft August 2007 Six bits of the OSPF-lite Options field are currently used in Version 2, although in OSPF-lite there is currently support for two. One (the E-bit) has a mandatory setting to 1, for OSPF-lite routers. Each bit is described briefly below. Routers should reset (i.e. clear) unrecognized bits in the Options field when sending Hello packets or Database Description packets and when originating LSAs. Conversely, routers encountering unrecognized Option bits in received Hello Packets, Database Description packets or LSAs should ignore the capability and process the packet/LSA normally. +------------------------------------+ | * | O | DC | L | N/P | MC | E | * | +------------------------------------+ 0 0/1 0 0 0 0 1 0 The Options field O-bit Support for Opaque LSAs. DC-bit REserved for future work. Demand circuit support [ref17]. L-bit Reserved for future work; LLS Data block support. LLS allows for the extension of the ospf packet. With ospf Version 2 this is used by the Non Stop Forwarding NSF feature. [ref18] N/P-bit Must be set to zero; NSSA (Not So Stubby Areas) are not supported in OSPF-lite. MC-bit This bit describes whether IP multicast datagrams are forwarded according to the specifications in [ref19]. E-bit This bit describes the way AS-external-LSAs are flooded, as described in Section 9.5, 10.8 and Section 12.1.2 of this memo. It signifies support for Type 5 LSAs. This is mandatory in OSPF-lite. A.3 OSPF-lite Packet Formats There are five distinct OSPF-lite packet types. All OSPF-lite packet types begin with a standard 24-byte header. This header is described first. Each packet type is then described in a succeeding section. Thomas et al [Page 123] Internet Draft August 2007 In these sections each packet's division into fields is displayed, and then the field definitions are enumerated. All OSPF-lite packet types (other than the OSPF-lite Hello packets) deal with lists of LSAs. For example, Link State Update packets implement the flooding of LSAs throughout the OSPF-lite routing domain. Because of this, OSPF-lite protocol packets cannot be parsed unless the format of LSAs is also understood. The format of LSAs is described in Section A.4. The receive processing of OSPF-lite packets is detailed in Section 8.2. The sending of OSPF-lite packets is explained in Section 8.1. A.3.1 The OSPF-lite packet header Every OSPF-lite packet starts with a standard 24-byte header, which contains all the information necessary to determine whether the packet should be accepted for further processing. Section 8.2 of this specification describes how this decision is made. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | Type | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID (must be 0.0.0.0 for OSPF-lite) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version # The OSPF-lite version number. A version number has not yet been assigned to OSPF-lite. Type The OSPF-lite packet types are as follows. See Sections A.3.2 through A.3.6 for details. Thomas et al [Page 124] Internet Draft August 2007 Type OSPF-lite Description ________________________________ 1 OSPF-lite Hello 2 Database Description 3 Link State Request 4 Link State Update 5 Link State Acknowledgment Packet length The length of the OSPF-lite protocol packet in bytes. This length includes the standard OSPF-lite header. Router ID The Router ID of the packet's source. Area ID OSPF-lite does not support multiple areas. This field is set to 0.0.0.0 for OSPF-lite. This is the same as for the Backbone Area 0 with OSPF Version 2. Checksum The standard IP checksum of the entire contents of the packet, starting with the OSPF-lite packet header but excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. The checksum is considered to be part of the packet authentication procedure; for some authentication types the checksum calculation is omitted. AuType Identifies the authentication procedure to be used for the packet. Authentication is discussed in Appendix D of the specification. Consult Appendix D for a list of the currently defined authentication types. Authentication A 64-bit field for use by the authentication scheme. See Appendix D for details. A.3.2 The Hello packet Hello packets are OSPF-lite packet type 1. These packets are sent periodically on all interfaces in order to establish and maintain neighbor relationships. Hello Packets are initially multicast on Thomas et al [Page 125] Internet Draft August 2007 all networks, enabling dynamic discovery of neighboring routers. Layer 2 to Layer 3 multicast mapping may be required on some mediums. All routers connected to a common network must agree on certain parameters (Network mask, HelloInterval and RouterDeadInterval). These parameters are included in Hello packets, so that differences can inhibit the forming of neighbor relationships. A detailed explanation of the receive processing for Hello packets is presented in Section 10.5. The sending of Hello packets is covered in Section 9.5. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 1 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area (set to 0.0.0.0 for OSPF-lite) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HelloInterval | Options | RtrPri = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RouterDeadInterval | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DR = 0.0.0.0 for OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | BDR = 0.0.0.0 for OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | Network mask The network mask associated with this interface. For example, if the interface is to a class B network whose third byte is used for subnetting, the network mask is 0xffffff00. Thomas et al [Page 126] Internet Draft August 2007 Options The optional capabilities supported by the router, as documented in Section A.2. HelloInterval The number of seconds between this router's Hello packets. Rtr Pri = 0 This router's Router Priority, which is legacy from OSPF Version 2. This field MUST be set to zero in OSPF-lite. RouterDeadInterval The number of seconds before declaring a silent router down. Designated Router = 0.0.0.0 Not supported. This Field is legacy from OSPF Version 2, and must be set to zero. Backup Designated Router = 0.0.0.0 Not supported. This Field is legacy from OSPF Version 2, and must be set to zero. Neighbor The Router IDs of each router from which valid Hello packets have been seen recently on the network i.e., within the last RouterDeadInterval seconds. A.3.3 The Database Description packet Database Description packets are OSPF-lite packet type 2. These packets are exchanged when an adjacency is being initialized. They describe the contents of the link-state database. Multiple packets may be used to describe the database. For this purpose a poll-response procedure is used. One of the routers is designated to be the master, while the other the slave. The master sends Database Description packets (polls) which are acknowledged by Database Description packets sent by the slave (responses). The responses are linked to the polls via the packets' DD sequence numbers. Thomas et al [Page 127] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OSPF-lite | 2 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID = 0.0.0.0 for OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Interface MTU | Options |0|0|0|0|0|I|M|MS +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DD sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- -+ | | +- An LSA Header -+ | | +- -+ | | +- -+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | The format of the Database Description packet is very similar to both the Link State Request and Link State Acknowledgment packets. The main part of all three is a list of items, each item describing a piece of the link-state database. The sending of Database Description Packets is documented in Section 10.8. The receiving of Database Description packets is documented in Section 10.6. Interface MTU The size in bytes of the largest IP datagram that can be sent out of the associated interface, without fragmentation. The MTUs of common Internet link types can be found in Table 7-1 of [ref10]. Options The optional capabilities supported by the router, as documented in Section A.2. Thomas et al [Page 128] Internet Draft August 2007 I-bit The Init bit. When set to 1, this packet is the first in the sequence of Database Description Packets. M-bit The More-bit. When set to 1, it indicates that more Database Description Packets are to follow. MS-bit The Master/Slave-bit. When set to 1, it indicates that the router is the master during the Database Exchange process. Otherwise, the router is the slave. DD sequence number Used to sequence the collection of Database Description Packets. The initial value (indicated by the Init bit being set) should be unique. The DD sequence number then increments until the complete database description has been sent. The rest of the packet consists of a (possibly partial) list of the link-state database's pieces. Each LSA in the database is described by its LSA header. The LSA header is documented in Section A.4.1. It contains all the information required to identify uniquely both the LSA and the LSA's current instance. A.3.4 The Link State Request packet Link State Request packets are OSPF-lite packet type 3. After exchanging Database Description packets with a neighboring router, a router may find that parts of its link-state database are out-of- date. The Link State Request packet is used to request the pieces of the neighbor's database that are more up-to-date. Multiple Link State Request packets may have to be used. A router that sends a Link State Request packet has in mind the precise instance of the database pieces it is requesting. Each instance is defined by its LS sequence number, LS checksum, and LS age, although these fields are not specified in the Link State Request Packet itself. The router may receive even more recent instances in response. The sending of Link State Request packets is documented in Section 10.9. The reception of Link State Request packets is documented in Section 10.7. Thomas et al [Page 129] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OSPF-lite | 3 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID 0.0.0.0 in OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | Each LSA requested is specified by its LS type, Link State ID, and Advertising Router. This uniquely identifies the LSA, but not its instance. Link State Request packets are understood to be requests for the most recent instance (whatever that might be). A.3.5 The Link State Update packet Link State Update packets are OSPF-lite packet type 4. These packets implement the flooding of LSAs. Each Link State Update packet carries a collection of LSAs one hop further from their origin. Several LSAs may be included in a single packet. Link State Update packets are multicast on all networks including NBMA networks. In order to make the flooding procedure reliable, flooded LSAs are acknowledged by Link State Acknowledgment packets. If retransmission of certain LSAs is necessary, the retransmitted LSAs are always sent directly to the neighbor. For more information on the reliable flooding of LSAs, consult Section 13. Thomas et al [Page 130] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OSPF-lite | 4 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID 0.0.0.0 in OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # LSAs | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- +-+ | LSAs | +- +-+ | ... | # LSAs The number of LSAs included in this update. The body of the Link State Update packet consists of a list of LSAs. Each LSA begins with a common 20-byte header, described in Section A.4.1. Detailed formats of the different types of LSAs are described in Section A.4. A.3.6 The Link State Acknowledgment packet Link State Acknowledgment Packets are OSPF-lite packet type 5. To make the flooding of LSAs reliable, flooded LSAs are explicitly acknowledged. This acknowledgment is accomplished through the sending and receiving of Link State Acknowledgment packets. Multiple LSAs can be acknowledged in a single Link State Acknowledgment packet. Depending on the state of the sending interface and the sender of the corresponding Link State Update packet, a Link State Acknowledgment packet is sent either to the multicast address AllSPFRouters, or as a unicast. The sending of Link State Acknowledgement packets is documented in Section 13.5. The receiving of Link State Acknowledgement packets is documented in Section 13.7. Thomas et al [Page 131] Internet Draft August 2007 The format of this packet is similar to that of the Data Description packet. The body of both packets is simply a list of LSA headers. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OSPF-lite | 5 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID 0.0.0.0 in OSPF-lite | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- -+ | | +- An LSA Header -+ | | +- -+ | | +- -+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | Each acknowledged LSA is described by its LSA header. The LSA header is documented in Section A.4.1. It contains all the information required to identify uniquely both the LSA and the LSA's current instance. A.4 LSA formats This memo defines in detail two distinct types of LSAs. Each LSA begins with a standard 20-byte LSA header. This header is explained in Section A.4.1. Succeeding sections then describe and illustrate the separate LSA types. Thomas et al [Page 132] Internet Draft August 2007 Each LSA describes a piece of the OSPF-lite routing domain. Every router originates a router-LSA. Other types of LSAs may also be originated (see Section 12.4). All LSAs are then flooded throughout the OSPF-lite routing domain. The flooding algorithm is reliable, ensuring that all routers have the same collection of LSAs. (See Section 13 for more information concerning the flooding algorithm.) This collection of LSAs is called the link-state database. From the link state database, each router constructs a shortest path tree with itself as root. This yields a routing table (see Section 2). For the details of the graph processing, see Section 16. A.4.1 The LSA header All LSAs begin with a common 20-byte header, which contains enough information to identify the LSA uniquely (LS type, Link State ID, and Advertising Router). Multiple instances of the LSA may exist in the routing domain at the same time. It is then necessary to determine which instance is more recent. This is accomplished by examining the LS age, LS sequence number and LS checksum fields that are also contained in the LSA header. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | LS type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ LS age The time in seconds since the LSA was originated. Options The optional capabilities supported by the described portion of the routing domain. OSPF-lite's optional capabilities are documented in Section A.2. Thomas et al [Page 133] Internet Draft August 2007 LS type The type of the LSA. Each LSA type has a separate advertisement format. The LSA types allowed in ospf-lite are as follows (see Section 12.1.3 for further explanation): LS Type Description ___________________________________ 1 Router-LSAs 5 AS-external-LSAs 9 Opaque LSA Link Local 10 Opaque LSA Area (AS) wide 11 Opaque LSA AS Wide Note that LSA typeS 2, 3, 4 and 7 are not supported in OSPF-lite, but Opaque LSAs (types 9, 10 and 11) are supported. Link State ID This field identifies the portion of the Internet environment that is being described by the LSA. The contents of this field depend on the LSA's LS type. In a type 1 LSA, the Link State ID is set to the Router ID. In a type 5 LSA, it is set to the Network being advertised. Advertising Router The Router ID of the router that originated the LSA. For example, in Router-LSAs this field is equal to the Router ID of the LSA. LS sequence number Detects old or duplicate LSAs. Successive instances of an LSA are given successive LS sequence numbers. See Section 12.1.6 for more details. LS checksum The Fletcher checksum of the complete contents of the LSA, including the LSA header but excluding the LS age field. See Section 12.1.7 for more details. length The length in bytes of the LSA. This includes the 20-byte LSA header. A.4.2 Router-LSAs Router-LSAs are Type 1 LSAs. Each router in an AS originates a router-LSA. The LSA describes the state and cost of the router's links (i.e., interfaces) to the AS. All of the router's links to the AS must be described in a single router-LSA. For details concerning the construction of router-LSAs, see Section 12.4.1. Thomas et al [Page 134] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 Nt|W|V|E|B| 0 | # links | ¦ 0 ¦0¦ ¦0¦ | ¦ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Data | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | # TOS | metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TOS | 0 | TOS metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Data | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | In router-LSAs, the Link State ID field is set to the router's OSPF- lite Router ID. Router-LSAs are flooded throughout the whole AS with OSPF-lite. bit-V Not supported. MUST be set to zero. bit-E When set, the router is an AS boundary router (E is for external). bit-B Not supported. MUST be set to zero. bit-W Not currently supported. When set, the router is a wild-card multicast receiver (W is for wild). Thomas et al [Page 135] Internet Draft August 2007 bit-Nt Not supported. MUST be set to zero. # links The number of router links described in this LSA. This must be the total collection of router links (i.e., interfaces) into the AS. The following fields are used to describe each router link (i.e., interface). Each router link is typed (see the Type field below). The Type field indicates the kind of link being described. It may Either be a link to a stub network; OSPF-lite-stub (type 8), or OSPF-lite-transit (link type 9). This is regardless of the physical network type. The values of the fields describing a router link do not depend on the link's Type in OSPF-lite. The only exception arises if the underlying type is NBMA. In this case another link is also added into the Router LSA, namely an OSPF-lite-stub link to the 32-bit IP address of the NBMA interface (see Section 2.1.1 and Section 2.2.1) Type A quick description of the router link. In OSPF-lite this can be OSPF-lite-stub (type 8), or OSPF-lite-transit (type 9). Type Description _____________________________ 8 OSPF-lite-stub 9 OSPF-lite-transit Link ID Identifies the object to which this router link connects, and is set in OSPF-lite to the IP address of the Interface connected. The only exception to this is if the interface has no IP address, in which case the interface's MIB-II [ref14] ifIndex value is used. Type Link ID _________________________ 8 Interface IP address 9 Interface IP address Link Data This value with OSPF-lite no longer depends on the link's Type field. For both OSPF-lite-stub, and OSPF-lite-transit, the value of this field is the Mask of the Interface IP address. Thomas et al [Page 136] Internet Draft August 2007 There are two exceptions to this rule. The first is for the additional link added to the Router LSA for NBMA networks. This link has the interface IP address in the Link ID and a full 32-bit mask in the Link Data field. This information is needed to create host routes to the interface, for correct operation over non fully meshed networks. The second exception arises if the Interface has no IP address. In this case the Link Data field is set to 0.0.0.1, indicating to the receiving Router that the field can be ignored as the link must be IP unnumbered. This differs from the operation of OSPF Version 2. # TOS The number of different TOS metrics given for this link, not counting the required link metric (referred to as the TOS 0 metric in [ref1]). For example, if no additional TOS metrics are given, this field is set to zero. metric The cost of using this router link. Additional TOS-specific information may also be included, for backward consistency with previous versions of the OSPF specification ([ref1]). A.4.3 Not applicable A.4.4 Not applicable A.4.5 AS-external-LSAs are fully supported by OSPF-lite AS-external-LSAs are Type 5 LSAs. These LSAs are originated by AS boundary routers, and describe destinations external to the AS. For details concerning the construction of AS-external-LSAs, see Section 12.4.3. AS-external-LSAs usually describe a particular external destination. For these LSAs the Link State ID field specifies an IP network number (if necessary, the Link State ID can also have one or more of the network's 'host' bits set; see Appendix E for details). AS- external-LSAs are also used to describe a default route. Default routes are used when no specific route exists to the destination. When describing a default route, the Link State ID is always set to DefaultDestination (0.0.0.0) and the Network Mask is set to 0.0.0.0. Thomas et al [Page 137] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 5 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |E| 0 | metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forwarding address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | External Route Tag | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |E| TOS | TOS metric | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forwarding address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | External Route Tag | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | Network Mask The IP address mask for the advertised destination. bit-E The type of external metric. If bit-E is set, the metric specified is a Type 2 external metric. This means the metric is considered larger than any link state path. If bit-E is zero, the specified metric is a Type 1 external metric. This means that it is expressed in the same units as the link state metric (i.e., the same units as interface cost). metric The cost of this route. Interpretation depends on the external type indication (bit-E above). Forwarding address Data traffic for the advertised destination will be forwarded to this address. If the Forwarding address is set to 0.0.0.0, data traffic will be forwarded instead to the LSA's originator (i.e., the responsible AS boundary router). Thomas et al [Page 138] Internet Draft August 2007 External Route Tag A 32-bit field attached to each external route, which is not used by the OSPF-lite protocol itself, but may be used to communicate information between AS boundary routers; the precise nature of such information is outside the scope of this specification. This can be used to prevent routing loops when redistributing between attached AS's. Additional TOS-specific information may also be included, for backward consistency with previous versions of the OSPF specification ([ref1]). For each desired TOS, TOS-specific information is encoded as follows: TOS The Type of Service that the following fields concern. The encoding of TOS in OSPF-lite LSAs is described in Section 12.3. B. Architectural Constants Several OSPF-lite protocol parameters have fixed architectural values; they have been referred to in the text by names such as LSRefreshTime. The same naming convention is used for the configurable protocol parameters which are defined in Appendix C. The name of each architectural constant follows, together with its value and a short description of its function. LSRefreshTime The maximum time between distinct originations of any particular LSA. If the LS age field of one of the router's self-originated LSAs reaches the value LSRefreshTime, a new instance of the LSA is originated, even though the contents of the LSA (apart from its header) will be the same. The value of LSRefreshTime is set to 30 minutes. MinLSInterval The minimum time between distinct originations of any particular LSA. The value of MinLSInterval is set to 5 seconds. MinLSArrival For any particular LSA, the minimum time that must elapse between reception of new LSA instances during flooding. LSA instances received at higher frequencies are discarded. The value of MinLSArrival is set to 1 second. Thomas et al [Page 139] Internet Draft August 2007 MaxAge The maximum age that an LSA can attain. When an LSA's LS age field reaches MaxAge, it is reflooded in an attempt to flush the LSA from the routing domain (see Section 14). LSAs of age MaxAge are not used in the routing table calculation. The value of MaxAge is set to 1 hour. CheckAge Not required in ospf-lite. MaxAgeDiff The maximum time dispersion that can occur, as an LSA is flooded throughout the AS. Most of this time is accounted for by the LSAs waiting in router output queues (and therefore not aging) during the flooding process. The value of MaxAgeDiff is set to 15 minutes. LSInfinity The metric value indicating that the destination described by an LSA is unreachable. Used in AS-external-LSAs as an alternative to premature aging (see Section 14.1). It is defined to be the 24-bit binary value of all ones: 0xffffff. DefaultDestination The Destination ID that indicates the default route. This route is used when no other matching routing table entry can be found. The default destination can only be advertised in AS-external- LSAs. Its value is the IP address 0.0.0.0 and its associated Network Mask is also always 0.0.0.0. InitialSequenceNumber The value used for LS Sequence Number when originating the first instance of any LSA. Its value is the signed 32-bit integer 0x80000001. MaxSequenceNumber The maximum value that LS Sequence Number can attain. Its value is the signed 32-bit integer 0x7fffffff. C. Configurable constants The OSPF-lite protocol has several configurable parameters, which are listed below. They are grouped into general functional categories (AS parameters, interface parameters, etc.). Sample values are given for some of them. Some parameter settings need to be consistent among groups of routers. For example, all routers attached to a network must agree on that network's IP network number and mask. Thomas et al [Page 140] Internet Draft August 2007 Some parameters may be determined by router algorithms outside of this specification (e.g., dynamically assigned IP addresses). From OSPF-lite's point of view, these items are still configurable. C.1 Global parameters The few global configuration parameters are listed below. Router ID This is a 32-bit number that uniquely identifies the router in the Autonomous System. One algorithm for Router ID assignment is to choose the largest or smallest IP address assigned to the router. If a router's OSPF-lite Router ID is changed, the router's OSPF-lite software should be restarted before the new Router ID takes effect. Before restarting in order to change its Router ID, the router should flush its self-originated LSAs from the routing domain (see Section 14.1), or they may persist for up to MaxAge minutes. RFC1583Compatibility removed Must be zero, since OSPF-lite does not support multiple areas. In previous versions of OSPF, in order to minimize the chance of routing loops, all OSPF Version 2 routers in a routing domain had to have RFC1583Compatibility set. C.2 AS parameters All routers belonging to an AS must agree on that AS's configuration. Disagreements between two routers will prevent adjacencies forming between them, hindering the flow of routing protocol traffic and data traffic. The following items must be configured for an AS: Area ID must be set to 0.0.0.0 for OSPF-lite, because multiple areas are not supported. ExternalRoutingCapability Set to 1 for all OSPF-lite packets except External Type 5 LSAs. For more information, see Section A.2, and Section 10.8 C.3 Router interface parameters Some of the configurable router interface parameters (such as IP interface address and subnet mask) actually imply properties of the attached networks, and therefore must be consistent across all the routers attached to that network. The parameters that must be configured for a router interface are: Thomas et al [Page 141] Internet Draft August 2007 IP interface address The IP protocol address for this interface. This uniquely identifies the router over the entire Internet. An IP address is not required on point-to-point networks, but one should be used if possible. A point-to-point network without IP addresses is called 'unnumbered'. IP interface mask Also referred to as the subnet/network mask, this indicates the portion of the IP interface address that identifies the attached network. Masking the IP interface address with the IP interface mask yields the IP network number of the attached network. Interface output cost The cost of sending a packet on the interface, expressed in the link state metric. This is advertised as the link cost for this interface in the router's router-LSA. The interface output cost must always be greater than zero. RxmtInterval The number of seconds between LSA retransmissions, for adjacencies belonging to this interface. Also used when retransmitting Database Description and Link State Request Packets. This should be well over the expected round-trip delay between any two routers on the attached network. The setting of this value should be conservative, otherwise needless retransmissions will result. InfTransDelay The estimated number of seconds it takes to transmit a Link State Update Packet over this interface. LSAs contained in the update packet must have their age incremented by this amount before transmission. In OSPF-lite this may be set to zero. Router Priority Must be set to zero. This is NOT supported in OSPF-lite. HelloInterval The length of time, in seconds, between the Hello Packets that the router sends on the interface. This value is advertised in the router's Hello Packets. It must be the same for all routers attached to a common network. The smaller the HelloInterval, the faster topological changes will be detected. RouterDeadInterval After ceasing to hear a router's Hello Packets, the number of seconds before its neighbors declare the router down. This is also advertised in the router's Hello Packets in their RouterDeadInterval field. This should be some multiple of the HelloInterval. This value must be the same for all routers attached to a common network. Thomas et al [Page 142] Internet Draft August 2007 AuType Identifies the authentication procedure to be used on the attached network. This value must be the same for all routers attached to the network. See Appendix D for a discussion of the defined authentication types. Authentication key This configured data allows the authentication procedure to verify OSPF-lite protocol packets received over the interface. For example, if the AuType indicates simple password, the Authentication key would be a clear 64-bit password. Authentication keys associated with the other OSPF-lite authentication types are discussed in Appendix D. C.4 Not applicable C.5 NBMA network parameters OSPF-lite treats an NBMA in the same way as any other network (assigning it a link type os OSPF-lite-stub, and then OSPF-lite- transit should a suitable neighbor be found). The router LSA also contains an extra host link as described in Section 2.1.1 Section 2.2.1, Section 12.4.4.2 and Section 16.0.7.1. However, due to the lack of broadcast capabilities, it may be necessary to use configuration parameters to ensure the correct packetisation of the OSPF-lite packets. For example over NBMA media, Layer 2 to Layer 3 mapping may need to be configured. OSPF-lite does not consider these commands to be related to the protocol. In some cases Layer 2 protocols, such as Inverse-ARP Over Frame Relay for example, may help with Layer 3 to Layer 2 mappings. Overriding network type It is possible to use configuration commands to 'override' the way that a router perceives the underlying network type. If the network that has an underlying NBMA type is overridden to say a point-to-point network, then OSPF-lite will treat this interface in the same way as a true point-to-point interface. The converse is also true. Manual neighbor configuration As with all interfaces, neighbors can be configured manually. This is STRONGLY discouraged. OSPF-lite can discover neighbors in most network scenarios and even operate with non fully meshed networks automatically. An error in configuring neighbors may result in adjacencies not being formed correctly. Thomas et al [Page 143] Internet Draft August 2007 C.6 Point-to-MultiPoint is not supported. Similar support is provided on all networks. C.7 Host route parameters Host routes are advertised in router-LSAs as OSPF-lite-stub networks with mask 0xffffffff. D. Authentication OSPF-lite Authenticates in the same way as OSPF Version 2, as detailed below. All OSPF-lite protocol exchanges are authenticated. The OSPF-lite packet header (see Section A.3.1) includes an authentication type field, and 64-bits of data for use by the appropriate authentication scheme (determined by the type field). The authentication type is configurable on a per-interface (or equivalently, on a per-network/subnet) basis. Additional authentication data is also configurable on a per-interface basis. Authentication types 0, 1 and 2 are defined by this specification. All other authentication types are reserved for definition by the IANA (iana@ISI.EDU). The current list of authentication types is described below in Table 12. AuType Description ___________________________________________ 0 Null authentication 1 Simple password 2 Cryptographic authentication All others Reserved for assignment by the IANA (iana@ISI.EDU) Table 12: OSPF-lite authentication types. D.1 Null authentication Use of this authentication type means that routing exchanges over the network/subnet are not authenticated. The 64-bit authentication field in the OSPF-lite header can contain anything; it is not examined on packet reception. When employing Null authentication, the entire contents of each OSPF-lite packet (other than the 64-bit authentication field) are checksummed in order to detect data corruption. Thomas et al [Page 144] Internet Draft August 2007 D.2 Simple password authentication Using this authentication type, a 64-bit field is configured on a per-network basis. All packets sent on a particular network must have this configured value in their OSPF-lite header 64-bit authentication field. This essentially serves as a "clear" 64- bit password. In addition, the entire contents of each OSPF-lite packet (other than the 64-bit authentication field) are checksummed in order to detect data corruption. Simple password authentication guards against routers inadvertently joining the routing domain; each router must first be configured with its attached networks' passwords before it can participate in routing. However, simple password authentication is vulnerable to passive attacks currently widespread in the Internet (see [ref20]). Anyone with physical access to the network can learn the password and compromise the security of the OSPF-lite routing domain. D.3 Cryptographic authentication Using this authentication type, a shared secret key is configured in all routers attached to a common network/subnet. For each OSPF-lite protocol packet, the key is used to generate/verify a "message digest" that is appended to the end of the OSPF-lite packet. The message digest is a one-way function of the OSPF-lite protocol packet and the secret key. Since the secret key is never sent over the network in the clear, protection is provided against passive attacks. The algorithms used to generate and verify the message digest are specified implicitly by the secret key. This specification completely defines the use of OSPF-lite Cryptographic authentication when the MD5 algorithm is used. In addition, a non-decreasing sequence number is included in each OSPF-lite protocol packet to protect against replay attacks. This provides long term protection; however, it is still possible to replay an OSPF-lite packet until the sequence number changes. To implement this feature, each neighbor data structure contains a new field called the "cryptographic sequence number". This field is initialized to zero, and is also set to zero Thomas et al [Page 145] Internet Draft August 2007 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | Key ID | Auth Data Len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cryptographic sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 18: Usage of the Authentication field in the OSPF-lite packet header when Cryptographic Authentication is employed whenever the neighbor's state transitions to "Down". Whenever an OSPF-lite packet is accepted as authentic, the cryptographic sequence number is set to the received packet's sequence number. This specification does not provide a rollover procedure for the cryptographic sequence number. When the cryptographic sequence number that the router is sending hits the maximum value, the router should reset the cryptographic sequence number that it is sending back to 0. After this is done, the router's neighbors will reject the router's OSPF-lite packets for a period of RouterDeadInterval, and then the router will be forced to reestablish all adjacencies over the interface. However, it is expected that many implementations will use "seconds since reboot" (or "seconds since 1960", etc.) as the cryptographic sequence number. Such a choice will essentially prevent rollover, since the cryptographic sequence number field is 32 bits in length. The OSPF-lite Cryptographic authentication option does not provide confidentiality. When cryptographic authentication is used, the 64-bit Authentication field in the standard OSPF-lite packet header is redefined as shown in Figure 18. The new field definitions are as follows: Key ID This field identifies the algorithm and secret key used to create the message digest appended to the OSPF-lite packet. Key Identifiers are unique per-interface (or equivalently, per-subnet). Auth Data Len The length in bytes of the message digest appended to the OSPF-lite packet. Thomas et al [Page 146] Internet Draft August 2007 Cryptographic sequence number An unsigned 32-bit non-decreasing sequence number. Used to guard against replay attacks. The message digest appended to the OSPF-lite packet is not actually considered part of the OSPF-lite protocol packet: the message digest is not included in the OSPF-lite header's packet length, although it is included in the packet's IP header length field. Each key is identified by the combination of interface and Key ID. An interface may have multiple keys active at any one time. This enables smooth transition from one key to another. Each key has four time constants associated with it. These time constants can be expressed in terms of a time-of-day clock, or in terms of a router's local clock (e.g., number of seconds since last reboot): KeyStartAccept The time that the router will start accepting packets that have been created with the given key. KeyStartGenerate The time that the router will start using the key for packet generation. KeyStopGenerate The time that the router will stop using the key for packet generation. KeyStopAccept The time that the router will stop accepting packets that have been created with the given key. In order to achieve smooth key transition, KeyStartAccept should be less than KeyStartGenerate and KeyStopGenerate should be less than KeyStopAccept. If KeyStopGenerate and KeyStopAccept are left unspecified, the key's lifetime is infinite. When a new key replaces an old, the KeyStartGenerate time for the new key must be less than or equal to the KeyStopGenerate time of the old key. Key storage should persist across a system restart, warm or cold, to avoid operational issues. In the event that the last key associated with an interface expires, it is unacceptable to revert to an unauthenticated condition, and not advisable to disrupt routing. Therefore, the router should send a "last authentication key expiration" notification to the network manager and treat the key as having an infinite lifetime until the lifetime is extended, the key is deleted by network management, or a new key is configured. Thomas et al [Page 147] Internet Draft August 2007 D.4 Message generation After building the contents of an OSPF-lite packet, the authentication procedure indicated by the sending interface's Autype value is called before the packet is sent. The authentication procedure modifies the OSPF-lite packet as follows. D.4.1 Generating Null authentication When using Null authentication, the packet is modified as follows: (1) The Autype field in the standard OSPF-lite header is set to 0. (2) The checksum field in the standard OSPF-lite header is set to the standard IP checksum of the entire contents of the packet, starting with the OSPF-lite packet header but excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. D.4.2 Generating Simple password authentication When using Simple password authentication, the packet is modified as follows: (1) The Autype field in the standard OSPF-lite header is set to 1. (2) The checksum field in the standard OSPF-lite header is set to the standard IP checksum of the entire contents of the packet, starting with the OSPF-lite packet header but excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. (3) The 64-bit authentication field in the OSPF-lite packet header is set to the 64-bit password (i.e., authentication key) that has been configured for the interface. Thomas et al [Page 148] Internet Draft August 2007 D.4.3 Generating Cryptographic authentication When using Cryptographic authentication, there may be multiple keys configured for the interface. In this case, among the keys that are valid for message generation (i.e, that have KeyStartGenerate <= current time < KeyStopGenerate) choose the one with the most recent KeyStartGenerate time. Using this key, modify the packet as follows: (1) The Autype field in the standard OSPF-lite header is set to 2. (2) The checksum field in the standard OSPF-lite header is not calculated, but is instead set to 0. (3) The Key ID (see Figure 18) is set to the chosen key's Key ID. (4) The Auth Data Len field is set to the length in bytes of the message digest that will be appended to the OSPF-lite packet. When using MD5 as the authentication algorithm, Auth Data Len will be 16. (5) The 32-bit Cryptographic sequence number (see Figure 18) is set to a non-decreasing value (i.e., a value at least as large as the last value sent out the interface). The precise values to use in the cryptographic sequence number field are implementation-specific. For example, it may be based on a simple counter, or be based on the system's clock. (6) The message digest is then calculated and appended to the OSPF- lite packet. The authentication algorithm to be used in calculating the digest is indicated by the key itself. Input to the authentication algorithm consists of the OSPF-lite packet and the secret key. When using MD5 as the authentication algorithm, the message digest calculation proceeds as follows: (a) The 16 byte MD5 key is appended to the OSPF-lite packet. (b) Trailing pad and length fields are added, as specified in [ref6]. (c) The MD5 authentication algorithm is run over the concatenation of the OSPF-lite packet, secret key, pad and length fields, producing a 16 byte message digest (see [ref6]). (d) The MD5 digest is written over the OSPF-lite key (i.e., appended to the original OSPF-lite packet). The digest is not counted in the OSPF-lite packet's length field, but is included in the packet's IP length field. Any trailing pad or length fields beyond the digest are not counted or transmitted. Thomas et al [Page 149] Internet Draft August 2007 D.5 Message verification When an OSPF-lite packet has been received on an interface, it must be authenticated. The authentication procedure is indicated by the setting of Autype in the standard OSPF-lite packet header, which matches the setting of Autype for the receiving OSPF-lite interface. If an OSPF-lite protocol packet is accepted as authentic, processing of the packet continues as specified in Section 8.2. Packets which fail authentication are discarded. D.5.1 Verifying Null authentication When using Null authentication, the checksum field in the OSPF-lite header must be verified. It must be set to the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. (If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming.) D.5.2 Verifying Simple password authentication When using Simple password authentication, the received OSPF-lite packet is authenticated as follows: (1) The checksum field in the OSPF-lite header must be verified. It must be set to the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. (If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming.) (2) The 64-bit authentication field in the OSPF-lite packet header must be equal to the 64-bit password (i.e., authentication key) that has been configured for the interface. D.5.3 Verifying Cryptographic authentication When using Cryptographic authentication, the received OSPF-lite packet is authenticated as follows: (1) Locate the receiving interface's configured key having Key ID equal to that specified in the received OSPF-lite packet (see Figure 18). If the key is not found, or if the key is not valid for reception (i.e., current time < KeyStartAccept or current time >= KeyStopAccept), the OSPF-lite packet is discarded. Thomas et al [Page 150] Internet Draft August 2007 (2) If the cryptographic sequence number found in the OSPF-lite header (see Figure 18) is less than the cryptographic sequence number recorded in the sending neighbor's data structure, the OSPF-lite packet is discarded. (3) Verify the appended message digest in the following steps: (a) The received digest is set aside. (b) A new digest is calculated, as specified in Step 6 of Section D.4.3. (c) The calculated and received digests are compared. If they do not match, the OSPF-lite packet is discarded. If they do match, the OSPF- lite protocol packet is accepted as authentic, and the "cryptographic sequence number" in the neighbor's data structure is set to the sequence number found in the packet's OSPF-lite header. E. An algorithm for assigning Link State IDs The Link State ID in AS-external-LSAs is usually set to the described network's IP address. However, if necessary one or more of the network's host bits may be set in the Link State ID, allowing the router to originate separate LSAs for networks having the same address, yet different masks. Such networks can occur in the presence of supernetting and subnet zeros (see [ref4]). This Appendix gives one possible algorithm for setting the host bits in Link State IDs. The choice of such an algorithm is a local decision. Separate routers are free to use different algorithms, since the only LSAs affected are the ones that the router itself originates. The only requirement on the algorithms used is that the network's IP address should be used as the Link State ID whenever possible. The algorithm below is stated for AS-external-LSAs. Suppose that the router wishes to originate an AS-external-LSA for a network having address NA and mask NM1. The following steps are then used to determine the LSA's Link State ID: (1) Determine whether the router is already originating an AS- external-LSA with Link State ID equal to NA (in such an LSA the router itself will be listed as the LSA's Advertising Router). If not, the Link State ID is set equal to NA and the algorithm terminates. Otherwise, Thomas et al [Page 151] Internet Draft August 2007 (2) Obtain the network mask from the body of the already existing AS-external-LSA. Call this mask NM2. There are then two cases: o NM1 is longer (i.e., more specific) than NM2. In this case, set the Link State ID in the new LSA to be the network [NA,NM1] with all the host bits set (i.e., equal to NA or'ed together with all the bits that are not set in NM1, which is network [NA,NM1]'s broadcast address). o NM2 is longer than NM1. In this case, change the existing LSA (having Link State ID of NA) to reference the new network [NA,NM1] by incrementing the sequence number, changing the mask in the body to NM1 and inserting the cost of the new network. Then originate a new LSA for the old network [NA,NM2], with Link State ID equal to NA or'ed together with the bits that are not set in NM2 (i.e., network [NA,NM2]'s broadcast address). The above algorithm assumes that all masks are contiguous; this ensures that when two networks have the same address, one mask is more specific than the other. The algorithm also assumes that no network exists having an address equal to another network's broadcast address. Given these two assumptions, the above algorithm always produces unique Link State IDs. The above algorithm can also be reworded as follows: When originating an AS-external-LSA, try to use the network number as the Link State ID. If that produces a conflict, examine the two networks in conflict. One will be a subset of the other. For the less specific network, use the network number as the Link State ID and for the more specific use the network's broadcast address instead (i.e., flip all the "host" bits to 1). If the most specific network was originated first, this will cause two LSAs to be originated at once. As an example of the algorithm, consider its operation when the following sequence of events occurs in a single router (Router A). (1) Router A wants to originate an AS-external-LSA for [10.0.0.0,255.255.255.0]: (a) A Link State ID of 10.0.0.0 is used. (2) Router A then wants to originate an AS-external-LSA for [10.0.0.0,255.255.0.0]: (a) The LSA for [10.0.0,0,255.255.255.0] is reoriginated using a new Link State ID of 10.0.0.255. Thomas et al [Page 152] Internet Draft August 2007 (b) A Link State ID of 10.0.0.0 is used for [10.0.0.0,255.255.0.0]. (3) Router A then wants to originate an AS-external-LSA for [10.0.0.0,255.0.0.0]: (a) The LSA for [10.0.0.0,255.255.0.0] is reoriginated using a new Link State ID of 10.0.255.255. (b) A Link State ID of 10.0.0.0 is used for [10.0.0.0,255.0.0.0]. (c) The network [10.0.0.0,255.255.255.0] keeps its Link State ID of 10.0.0.255. F. Multiple interfaces to the same network/subnet This is discouraged with OSPF-lite, althought OSPF-lite fully supports it in the same way as OSPF Version 2. It is worth noting that in many circumstances there are proprietary Datalink protocols developed by Vendors to produce a better resultant redundancy. Security Considerations All OSPF-lite protocol exchanges are authenticated. OSPF-lite supports multiple types of authentication; the type of authentication in use can be configured on a per network segment basis. One of OSPF- lite's authentication types, namely the Cryptographic authentication option, is believed to be secure against passive attacks and provide significant protection against active attacks. When using the Cryptographic authentication option, each router appends a "message digest" to its transmitted OSPF-lite packets. Receivers then use the shared secret key and received digest to verify that each received OSPF-lite packet is authentic. The quality of the security provided by the Cryptographic authentication option depends completely on the strength of the message digest algorithm (MD5 is currently the only message digest algorithm specified), the strength of the key being used, and the correct implementation of the security mechanism in all communicating OSPF-lite implementations. It also requires that all parties maintain the secrecy of the shared secret key. None of the OSPF-lite authentication types provide confidentiality. Nor do they protect against traffic analysis. Key management is also not addressed by this memo. Thomas et al [Page 153] Internet Draft August 2007 For more information, see Sections 8.1, 8.2, and Appendix D. Authors' Addresses Matthew R Thomas University of Essex, Department of Computing and Electronic Systems, Wivenhoe Park, Colchester CO4 3SQ, UK Telephone (+44) 7940 585456 E-Mail mrthom@essex.ac.uk Dr. David K. Hunter, Room 1NW.3.22 Department of Computing and Electronic Systems, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, UK Telephone: +44 1206 872416 E-mail: dkhunter@essex.ac.uk Dr. M.J. Reed Room 4 SB 6.15 Department of Computing and Electronic Systems University of Essex Wivenhoe Park Colchester Essex CO4 3SQ Telephone (+44) 1206 872479 E-mail mjreed@essex.ac.uk Thomas et al [Page 154] Internet Draft August 2007 Expires: 3 March 2008 Full Copyright Statement Copyright (C) The IETF Trust (2007). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org. Thomas et al [Page 155]