Saturday, November 6, 2010


There are only two Link-State routing protocols in this world: IS-IS and OSPF.
Link-State routing protocols maintain three tables:
-Neighbor Table
-Topology Table
-Routing Table

Like EIGRP, Link-State routing protocols maintain a Neighbor Table. They are similar in operation in that they keep track of their neighbors. But the biggest difference comes when we look at the Topology Table.

The Topology Table in a Link-State protocol has information about every single route in the area that the running router belongs to. The EIGRP Topology Table is just a list of routes that the neighbors passed on.

The best routes then appear in the Routing table.

Link-State routing protocol uses the SPF (Shortest Path First) protocols. The SPF protocol is also known as Dijkstra's Protocol. Compared to the DUAL algorithm which processes only information their neighbor tells them about, the SPF algorithm has to calculate through the entire area which uses a lot of resources. This is why in design we should keep areas small.

Triggered updates are also used. However, once every 30 minutes, a router will do a mass exchange known as a "Link State Refresh" to make sure that nothing gets missed by their neighbors.

OSPF Divides the area into multiple areas. Every single area contains a group of routers. All areas must connect to area 0. All routers in the same area have the same topology table. Areas localizes updates within an area which makes calculation more efficient. Areas forces network designers to create a hierarchical IP design.

Below is a diagram to depict the terminologies used to describe OSPF routers:

ABR stands for Area Border Router. A router that has multiple interfaces in different areas is an ABR. The ABR localizes a change in an area. It can do route summarization.

ASBR stands for Autonomous System Boundary Router. It refers to a router that has one or more interfaces in an OSPF domain, and one or more interfaces in another autonomous system such as the Internet or another routing protocol. It can also do route summarization.

An Internal Router is simply a router that only has interfaces in the same area

Finally, a Backbone Router is a router with one or more interfaces connected to Area 0.

Notice that I specified Stubby and Not So Stubby Areas in the diagram, but I'll not go into much detail now. It will be explained later.

Now let's take a look at how neighbors form. Each router has a Router ID. The Router ID is simply a name that a router is known by in the OSPF process. It can be anything and it does not affect the routing, although you would need to know your Router ID when doing Virtual Links which I'll describe later.

These are the major steps taken by routers to create neighbor relationships:
1) Determine neighbor's Router ID

The Router ID is simply the highest active interface IP address when OSPF starts. If you have a Loopback, it will take the Loopback's address. If you have multiple Loopbacks, it will take the highest loopback IP address ( beats, regardless of lo0 or lo1).

It is dangerous to have an auto Router ID. Changes would not take effect immediately. It would only change when the router is rebooted or the OSPF process is cleared through "clear ip ospf proc". It is recommended that the Router ID be hard-coded using the Router-ID command in the OSPF context.

2) Add interfaces to the Link-State database
3) Send a Hello message on chosen interface(s)

At this point, the neighbor would be in **DOWN STATE**.

Hello messages are sent once every 10 seconds on broadcast/point-to-point networks. It is sent once every 30 seconds on NBMA networks. The Dead Timer is always 4 times the Hello interval.

Hello messages contain a lot of information including Router ID, Hello and Dead Timers*, Network Mask*, Area ID*, Neighbors, Router Priority, DR/BDR IP Address, Authentication Password*.

Anything marked with an asterisk (*) needs to be the same between neighbors for them to form.

Neighbors help tell if a relationship is old or new. If a router sees itself in the neighbors list, then it knows that that is an old relationship and no mass exchange is required.

4) Receive Hello

At this point, the neighbor would be in **INIT STATE**.

Check Hello/Dead Interval
Check Netmasks
Check Area ID
Check Authentication Passwords

If any of these fail, you will go back to **DOWN STATE**.

5) Send Reply Hello

At this point, they are in the **2-WAY STATE**.

This is the point, the routers will consider themselves neighbors. For every packet they receive, they will ask:

"Am I listed as a neighbor in your Hello packet?"
1) Yes - Reset dead timer
2) No - Add new neighbor, go to step 6

6) Master-Slave Relationship is Determined

The routers both go into **EXSTART STATE**.

This is when the routers begin exchanging. EXSTART simply stands for Exchange Start. The Master sends the DBD before the Slave. The relationship is determined by the Priority, and Router ID breaks the tie (the higher Router ID wins).

The summarized information sent is in the form of DBD (Database Description Packet). It is simply a cliff note of the Link-State database. The receiving router then replies with a list of whatever they need in the next step.

7) DBDs are acknowledged and reviewed

At this point, routers are in the **LOADING STATE**.

Slave requests Details (LSR - Link State Requests)
Master sends Updates (LSU - Link State Updates)
Master requests Details (LSR)
Slave sends Updates (LSU)

8) Neighbors are Synchronized

Routers are finally in **FULL STATE**.

No comments :

Post a Comment