This chapter is from the book
This chapter is from the book
This chapter is from the book
General Link State Operation
Link State Routing protocols reduce broadcast traffic because they do not send out periodic broadcasts or send out their entire tables with each broadcast. Link state routing protocols exchange a complete copy of their route tables upon initialization. Thereafter route updates are multicast only when a change has occurred (triggered by a change in the topology), including only the change in the update not the entire table. Changes are flooded immediately and computed in parallel. If no changes occur, they do not generate an update.
Triggered updates improve convergence time by requiring routers to send an update message immediately upon learning of a route change. These updates are triggered by some event, such as a new link becoming available or an existing link failing.
When these changes do occur, they only propagate to and affect routers within the same logical area. In addition link state protocols support VLSM (Variable Length Subnet Masks), which allows routers to recognize and forward traffic to subnets within a network. Unlike most distance vector routing protocols, link state updates include the subnet mask, which allows a router to clearly identify the exact subnet to forward traffic to. This is also referred to as classless routing, which means that the routing protocol does not assume a specific default class type address and mask are being used.
All Link State protocols must build and maintain three separate tables (also referred to as databases): The neighbor table (also known as Adjacency database), Topology Map (also known as Link State database) and Route Table (also known as Forwarding database). Before traffic can be forwarded certain things must happen.
-
All routers attached to the same network must identify themselves and their neighbors, establishing a relationship with one another (referred to as adjacency). Adjacent routers form this relationship through the exchange of hello messages. From these hellos each local router builds its first table (the neighbor). Figure 3.26 shows the neighbor hello exchange and 3.27 shows a routers neighbor table. If this first stage fails, routing will never occur.
Note
Within hello messages routers announce themselves, identify the links they are directly attached to and the state of these links (up or down), among other things.
-
Once the adjacency relationship is intact, route information may be exchanged by flooding updates throughout the routing domain. Unlike Distance Vector routing protocols, which must receive, process, and wait for their periodic timer to expire before sending route updates on. Any change in the network triggers Link State protocols to immediately flood route updates to all segments except the one from which it was received, with all routers processing these updates in parallel. This speeds up convergence as routers can virtually receive and process updates simultaneousxly.
-
From received route updates routers build and maintain local Topology Maps (also known as Link State database) of the entire routing domain. Unlike distance vector protocols, which do maintain a complete picture of the network, Link State protocols have first-hand knowledge of all networks and subnets within their area and the paths to reach these networks.
-
Each router then builds a logical tree structure placing itself in the root position, with all networks and subnets emanating from this root.
-
All Link State routing protocols derive their route table by running Dijikstra's SPF (Shortest Path First) algorithm against the tree (topology map or Link State database) placing lowest cost paths to destinations in the route table (also known as Forwarding Database).
Figure 3.26 Link state routers exchange hello messages.
Figure 3.27 Router D has discovered two neighbors on network 3.
){kind=link}
){kind=link}
The main drawbacks to Link State protocols are the amount of CPU overhead involved in calculating route changes and memory resources that are required to store neighbor tables, route tables, and a complete topology map.