. 41
( 132 .)


not provide any authentication.
Figure 5.18 shows an RIP message advertising the three links available on a router,
with the metric for each.

5.3.3 Link state protocols
Link state protocols are more complicated than distance vector algorithms but have many
signi¬cant advantages. Many organizations on the Internet are now using an implemen-
tation of a link state protocol known as OSPF, in preference to RIP.
5.3 IP ROUTING 187

Figure 5.18 RIP router advertisement

Assume a new router is attached to the network. It will send out a broadcast hello packet
to the other routers. An existing router will discover its new neighbour and will learn its
network address. This router will send an echo packet back to the new router and the
new router will reply immediately to this packet. It is now possible to calculate the delay
in reaching the new router. Knowing the delay is important because on a complicated
internetwork there may be different paths through numerous routers to a destination, and
the quickest route is usually sought (there are other factors which may result in a preferred
route such as bandwidth and cost).
Once information about this new router has been established a link state packet is
constructed and ¬‚ooded to all other routers on the network (not just immediate neighbours
as in RIP). This is shown in Figure 5.19. All routers on the network will now have a
full picture of the internetwork in their link state protocol table rather than just a table of
directly connected routers as is the case with RIP.
The above can be broken down into ¬ve simple steps:

1. Discover neighbours and learn their network addresses.
2. Measure the delay or cost to reach each neighbour.
3. Build a packet with the information it has received.
4. Send this packet to all routers (not just neighbours as in RIP).
5. Compute the shortest path to every other router.

Router 2 Router 4

Router 1 Router 3

Router 6 Router 5

Router 7

Router 8

Figure 5.19 Example of link state protocol ¬‚ooding Open shortest path ¬rst (OSPF)
OSPF is a commonly used link state routing protocol on larger IP networks. It is a
complicated routing system and only a simpli¬ed view is presented here. For further
information on OSPF the reader is referred to RFCs 1245, 1246 and 1247. The OSPF
hello packet is responsible for establishing and maintaining a relationship between neigh-
bours. Figure 5.20 shows how different paths through an internetwork have different costs
associated with them. Unlike the RIP routing protocol, where each path has a metric of 1,


Router Router
4 3


8 7

Router Router Router
4 5




LAN Router Router

Figure 5.20 OSPF routing metrics
5.3 IP ROUTING 189

OSPF has many factors which can in¬‚uence the cost of a route, e.g. bandwidth, reliability
and latency. As such, the ˜cost™ for each route is worked out individually by combining
the above factors.
The name, OSPF, comes from the fact that it uses an implementation of Djikstra™s
˜shortest path™ algorithm for quickly calculating the best route based on cost factors. This
calculation is not done each time a packet is routed, but rather a table of best routes is
generated as routes are added or removed. One problem that has been experienced with
OSPF is that it will always choose the best route, so ˜popular™ routes become heavily
loaded, with no option to choose non-ideal routes for load balancing. One could consider
this analogous to a highway to the seaside becoming congested on a public holiday,
whereas a back road, although longer and normally slower, would work out quicker in
these circumstances.
The hello packet:

• announces the router™s availability, including its address and subnet mask, to the other
routers on the network;
• is used to determine the router™s neighbours;
• establishes the interval at which each router will send hello packets. This is used to
determine when a neighbouring router is down;
• identi¬es the designated router (DR, see below) and backup DR (BDR).

Each router will periodically multicast hello packets to its neighbouring routers to
inform them that it is still functioning. These are small packets which do not cause too
much congestion on the network. Figure 5.21 shows the structure of the OSPF header.
To indicate a hello packet, the packet type ¬eld will contain 1.
Unlike RIP, where there is one type of packet, OSPF has ¬ve different types (Table 5.8).
The other ¬elds in the OSPF header are listed in Table 5.9
Each router constructs its own database representing a map of the whole internetwork
from information it receives from other routers via these packets. When a router detects
that one of its interfaces has changed, it will propagate this update information to all other

0 32
Ver No. Packet Type Packet Length

Router ID

Area ID

Checksum AU type


Header related to specific packet type

Figure 5.21 OSPF header structure

Table 5.8 OSPF packet types
Packet type Description
1 Hello See text
2 Database description Sends sequence number of data, to show if it is up to
3 Link state request Requests information from another router
4 Link state update Sends a router™s costs to its neighbour
5 Link state acknowledge Acknowledges link state update

Table 5.9 OSPF header ¬elds
Field Description

Version number The version number of the OSPF protocol used by this
router, currently version 1
Packet length The length of the protocol packet in bytes, including the
Router ID The address of the source router
Area ID All OSPF packets are associated with an area that the
packet belongs to
Checksum The standard IP checksum of the entire contents of the
packet including the header but excluding the 64-bit
authentication ¬eld
AU type Identi¬es the authentication scheme used in this packet
Authentication A 64-bit ¬eld to ensure that the packet is genuine

routers through a process known as ¬‚ooding. Flooding is achieved through a designated
router (DR) and allows other routers to update their databases.

Designated router (DR)
It is inef¬cient to have every router on the network send large link state packets to every
other router on the network as this causes congestion. To avoid this situation, one router is
elected as the designated router. One of the tasks of the hello packets is to inform routers
which one is the DR. The DR is the router that has the highest priority number in its
priority ¬eld in the hello header. This is a parameter set by the network administrator to
elect the DR. In addition to the DR, a backup DR (BDR) is also elected in case of failure
of the DR, which is the router with the next highest priority. Both of these routers (DR
and BDR) are said to be adjacent to the other routers, and exchange link state information
with them.
Neighbouring routers that are not adjacent only exchange the small hello packets with
each other, so that they know the router is not faulty. When a route changes, the router
affected will inform the DR and the DR will broadcast this information to the other routers.
This is illustrated in Figure 5.22, where R22 sends the initial packet (1) to the DR. The
DR checks the authentication, checksum and sequence number before multicasting it (2)
to the other routers in the area.
During normal operation, each router periodically ¬‚oods link state update packets to
its adjacent routers. The default period for this is 30 minutes or when a route comes up
5.3 IP ROUTING 191

Here is the latest
routing table from
Router R22
Hi! My routing
table has changed.
Here is the latest Designated Router

link down

Router R22 Router


Router Router

Figure 5.22 DR updating routers

or goes down, or its cost changes. These packets contain its state and the costs used in
its database. The ¬‚ooded messages are acknowledged, to make them reliable (link state
acknowledge packet). Each packet has a sequence number, so that a router can check
whether an incoming link state update is older or newer than the one that it currently has.
Database description packets provide the sequence numbers of all the link state entries
currently held by the sending router. By comparing its own values with those of the
sender, a receiving router can determine who has the most recent values. As well as
a sequence number, entries also have a time associated with them. The database has an
ageing timer, which keeps track of all entries. When the ageing timer reaches a value four
times the hello interval (usually 4 — 10 seconds), entries are discarded. This is known as
the router dead interval.
Routers can request link state information from one another using link state request
packets. Using this method, adjacent routers can check to see who has the most recent
data. The latest information can be spread throughout the network in this way.
By using the information received through ¬‚ooding, each router can construct a graph
for its network and compute the shortest paths. In this way they can maintain synchro-
nization with the DR.

OSPF terminology
The following are some of the common terms relating to OSPF:


. 41
( 132 .)