One document matched: draft-thomas-hunter-reed-ospf-lite-00.txt
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]
| PAFTECH AB 2003-2026 | 2026-04-23 20:13:08 |