background image
Chapter 7
BGP's Basic Components
Link-State Routing Protocols
One of the best features of a link-state routing protocol is its ability to count
to infinity. This means that there is no hop count limit. A link-state routing
protocol works on the theory that routers send out a link state, which carries
information about each interface and the nodes attached.
A link-state-type of routing protocol--as well as the Spanning Tree Pro-
tocol--uses an algorithm called "graph theory" or the shortest path algo-
rithm, which was developed by Edgar Dijkstra. This theory is used to
construct a loop-free subset of the network topology using bits of informa-
tion contained in each link-state message to create a directed graph where
each link is represented by vertices and weighted edges, as shown in Figure
7.6. Each link represents a cost.
The weighted edges usually have more hops in the link than the straight-
through points, so these are assigned higher values. When the paths are cal-
culated, each link in the path has a given value, and the total of the values to
a given point or destination is the total weighted value of the path. The low-
est total weighted value represents the most efficient path from one point to
another point.
F I G U R E 7 . 6
An example of a directed graph
The graph takes into account that each link's bandwidth has better con-
vergence times, supports VLSM, and supports CIDR. Link-state routing pro-
tocols also differ from distance-vector protocols because of their procedure
for route calculation and advertisement. This procedure enables link-state
routing protocols to scale well with the growth of a network.
Link-state routing protocols also maintain a formal neighbor relationship
with directly connected routers, which allows for faster route convergence.
Copyright ©2001 SYBEX , Inc., Alameda, CA