Intra-domain Routing II

On last entry we have talked about Intra-domain routing, and some protocols involved. Today the entry is going to talk about Link State Protocols, and particuarly the Open Shortest Path First protocol:

Link State Routing Protocols are those protocols that react to changes in the link (up/down) sending connectivity information in contrast to vector-distance that sends the current distance to that node (i.e., routing table information). In general, these protocols are characterized by:

• Discovering neighbors.
• Every node learns the topology of the network flooding Link State Packets. Those packets travel with a sequence number and an aging field, to know the distance to the source.
• A minimum cost algorithm that calculates the best next hop using the data base, the most used is Dijkstra algorithm.

An example of this kind of protocols is the Open Shortest Path First (OSPF). The main idea is that each router draws a map with the whole network, and when a link state change is detected, each router sends information to all network routers. From this information each router recalculates the routing table using Dijkstra algorithm.
OSPF may be used in broadcast multi-access topologies, i.e. LANs, non-broadcast multi-access, i.e. ATM or Frame Relay, or point-to-point topologies.

OPSF algorithm is based on:

• Discovering neighbors using a protocol called HELLO.
• Send Link State Advertisements (LSA) to the rest of the routers, using flooding protocols, with all the changes detected.
• Maintain a data base with the network topology at each router (Link State Database).
• A minimum cost algorithm, in this case Dijkstra, which calculates the best next hop using the data base.

OSPF packets’ format uses IP encapsulation (with transport protocol 89) and an OSPF Header which define the different kind of packets on it: Hello, Database Description, Link-State Update, Link-State Request and Link-State ACK. Other appearing fields in the header are: Router ID, Area ID, Checksum and Authentication information.

Hello packets are special: they cannot bring LSA information, they are used to test that the line with a neighbor is operative and thus may interchange packets. They also choose a designated router (DR) and a designated backup router (DBR).

A DR is a special router; choose in order to minimize the amount of flooding and the database synchronization mechanism, centralizing the exchange of information. Routers just exchange link state with DR, and if it fails with BDR, although the amount of packets would be very high.

The election of the DR is set at interface level; a router connected to multiple networks could act as DR in a BMA network and as a normal router in another one. The highest priority level’s router is going to be the DR, while the second one is chosen as BDR.

Once the DR and BDR are elected, routers have to learn network routes through an exchange protocol:

• DR and DBR form an adjacency with each router of the BMA network, generally DR acting as “master” and the others as “slaves”.
• Master router sends a database summary to the slave and this one acknowledges this packet and viceversa.
• The slave looks at its database and request for those lacking information routes.
• Finally it builds the routing table.