7. Bringing Up Adjacencies
-
Bringing Up Adjacencies
OSPF creates adjacencies between neighboring routers for the purpose of exchanging routing information. Not every two neighboring 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 is 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. On broadcast and NBMA networks,
the Hello Protocol elects a Designated Router for the network.
The Hello Protocol works differently on broadcast networks, NBMA
networks and Point-to-MultiPoint networks. On broadcast
networks, each router advertises itself by periodically
multicasting Hello Packets. This allows neighbors to be
discovered dynamically. These Hello Packets contain the
router's view of the Designated Router's identity, and the list
of routers whose Hello Packets have been seen recently.
On NBMA networks some configuration information may be necessary
for the operation of the Hello Protocol. Each router that may
potentially become Designated Router has a list of all other
routers attached to the network. A router, having Designated
Router potential, sends Hello Packets to all other potential
Designated Routers when its interface to the NBMA network first
becomes operational. This is an attempt to find the Designated
Router for the network. If the router itself is elected
Designated Router, it begins sending Hello Packets to all other
routers attached to the network.
On Point-to-MultiPoint networks, a router sends Hello Packets to
all neighbors with which it can communicate directly. These
neighbors may be discovered dynamically through a protocol such
as Inverse ARP (see [Ref14]), or they may be configured.
After a neighbor has been discovered, bidirectional
communication ensured, and (if on a broadcast or NBMA network) a
Designated Router elected, a decision is made regarding whether
or not an adjacency should be formed with the neighbor (see
Section 10.4). If an adjacency is to be formed, the first step
is to synchronize the neighbors' link-state databases. This is
covered in the next section.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
simplifies this by requiring only adjacent routers to remain
synchronized. 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
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.
The adjacency is used by the flooding procedure as soon as the
Database Exchange Process begins. This simplifies database
synchronization, and guarantees that it finishes in a
predictable period of time.7.3. The Designated Router
Every broadcast and NBMA network has a Designated Router. The
Designated Router performs two main functions for the routing
protocol:
o The Designated Router originates a network-LSA on behalf of
the network. This LSA lists the set of routers (including
the Designated Router itself) currently attached to the
network. The Link State ID for this LSA (see Section
12.1.4) is the IP interface address of the Designated
Router. The IP network number can then be obtained by using
the network's subnet/network mask.
o The Designated Router becomes adjacent to all other routers
on the network. Since the link state databases are
synchronized across adjacencies (through adjacency bring-up
and then the flooding procedure), the Designated Router
plays a central part in the synchronization process.
The Designated Router is elected by the Hello Protocol. A
router's Hello Packet contains its Router Priority, which is
configurable on a per-interface basis. In general, when a
router's interface to a network first becomes functional, it
checks to see whether there is currently a Designated Router for
the network. If there is, it accepts that Designated Router,
regardless of its Router Priority. (This makes it harder to
predict the identity of the Designated Router, but ensures that
the Designated Router changes less often. See below.)
Otherwise, the router itself becomes Designated Router if it has
the highest Router Priority on the network. A more detailed
(and more accurate) description of Designated Router election is
presented in Section 9.4.
The Designated Router is the endpoint of many adjacencies. In
order to optimize the flooding procedure on broadcast networks,
the Designated Router multicasts its Link State Update Packets
to the address AllSPFRouters, rather than sending separate
packets over each adjacency.
Section 2 of this document discusses the directed graph
representation of an area. Router nodes are labelled with their
Router ID. Transit network nodes are actually labelled with the
IP address of their Designated Router. It follows that when the
Designated Router changes, it appears as if the network node on
the graph is replaced by an entirely new node. This will cause
the network and all its attached routers to originate new LSAs.
Until the link-state databases again converge, some temporary
loss of connectivity may result. This may result in ICMP
unreachable messages being sent in response to data traffic.
For that reason, the Designated Router should change only
infrequently. Router Priorities should be configured so that
the most dependable router on a network eventually becomes
Designated Router.7.4. The Backup Designated Router
In order to make the transition to a new Designated Router
smoother, there is a Backup Designated Router for each broadcast
and NBMA network. The Backup Designated Router is also adjacent
to all routers on the network, and becomes Designated Router
when the previous Designated Router fails. If there were no
Backup Designated Router, when a new Designated Router became
necessary, new adjacencies would have to be formed between the
new Designated Router and all other routers attached to the
network. Part of the adjacency forming process is the
synchronizing of link-state databases, which can potentially
take quite a long time. During this time, the network would not
be available for transit data traffic. The Backup Designated
obviates the need to form these adjacencies, since they already
exist. This means the period of disruption in transit traffic
lasts only as long as it takes to flood the new LSAs (which
announce the new Designated Router).
The Backup Designated Router does not generate a network-LSA for
the network. (If it did, the transition to a new Designated
Router would be even faster. However, this is a tradeoff
between database size and speed of convergence when the
Designated Router disappears.)
The Backup Designated Router is also elected by the Hello
Protocol. Each Hello Packet has a field that specifies the
Backup Designated Router for the network.
In some steps of the flooding procedure, the Backup Designated
Router plays a passive role, letting the Designated Router do
more of the work. This cuts down on the amount of local routing
traffic. See Section 13.3 for more information.7.5. The graph of adjacencies
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.
One can picture the collection of adjacencies on a network as
forming an undirected graph. The vertices consist of routers,
with an edge joining two routers if they are adjacent. The
graph of adjacencies describes the flow of routing protocol
packets, and in particular Link State Update Packets, through
the Autonomous System.
Two graphs are possible, depending on whether a Designated
Router is elected for the network. On physical point-to-point
networks, Point-to-MultiPoint networks and virtual links,
neighboring routers become adjacent whenever they can
communicate directly. In contrast, on broadcast and NBMA
networks only the Designated Router and the Backup Designated
Router become adjacent to all other routers attached to the
network.
+---+ +---+
|RT1|------------|RT2| o---------------o
+---+ N1 +---+ RT1 RT2
RT7
o---------+
+---+ +---+ +---+ /|\ |
|RT7| |RT3| |RT4| / | \ |
+---+ +---+ +---+ / | \ |
| | | / | \ |
+-----------------------+ RT5o RT6o oRT4 |
| | N2 * * * |
+---+ +---+ * * * |
|RT5| |RT6| * * * |
+---+ +---+ *** |
o---------+
RT3
Figure 10: The graph of adjacencies
These graphs are shown in Figure 10. It is assumed that Router
RT7 has become the Designated Router, and Router RT3 the Backup
Designated Router, for the Network N2. The Backup Designated
Router performs a lesser function during the flooding procedure
than the Designated Router (see Section 13.3). This is the
reason for the dashed lines connecting the Backup Designated
Router RT3.