The LSA format should include a field for the age of the advertisement. When an LSA is created, the
router sets this field to zero. As the packet is flooded, each router increments the age of the
advertisement.
Maximum age difference
This process of aging adds another layer of reliability to the flooding process. The protocol defines a
maximum age difference (MaxAgeDiff) value for the internetwork. A router may receive multiple copies
of the same LSA with identical sequence numbers but different ages. If the difference in the ages is lower
than the MaxAgeDiff, it is assumed that the age difference was the result of normal network latencies; the
original LSA in the database is retained, and the newer LSA (with the greater age) is not flooded. If the
difference is greater than the MaxAgeDiff value, it is assumed that an anomaly has occurred in the
internetwork in which a new LSA was sent without incrementing the sequence number. In this case, the
newer LSA will be recorded, and the packet will be flooded. A typical MaxAgeDiff value is 15 minutes
(used by OSPF).
NOTE
Maximum age
The age of an LSA continues to be incremented as it resides in a link state database. If the age for a link
state record is incremented up to some maximum age (MaxAge)—again defined by the specific routing
protocol—the LSA, with age field set to the MaxAge value, is flooded to all neighbors and the record is
deleted from the databases.
NOTE
Link state refresh time
If the LSA is to be flushed from all databases when MaxAge is reached, there must be a mechanism to
periodically validate the LSA and reset its timer before MaxAge is reached. A link state refresh time
(LSRefeshTime)[11] is established; when this time expires, a router floods a new LSA to all its neighbors,
who will reset the age of the sending router's records to the new received age. OSPF defines a MaxAge of
1 hour and an LSRefreshTime of 30 minutes. 100
IT Certification CCIE,CCNP,CCIP,CCNA,CCSP,Cisco Network Optimization and Security Tips
Lollipop-Shaped Sequence Number Spaces
This whimsically-named construct was proposed by Dr. Radia Perlman[9] . Lollipop-shaped sequence
number spaces are a hybrid of linear and circular sequence number spaces; if you think about it, a lollipop
has a linear component and a circular component. The problem with circular spaces is that there is no
number less than all other numbers. The problem with linear spaces is that they are—well—not circular.
That is, their set of sequence numbers is finite.
[9] R. Perlman."Fault-Tolerant Broadcasting of Routing Information." Computer Networks, Vol. 7, December 1983, pp. 395–405.
When router A restarts, it would be nice to begin with a number a that is less than all other numbers.
Neighbors will recognize this number for what it is, and if they have a pre-restart number b in their
databases from router A, they can send that number to router A and router A will jump to that sequence
number. Router A might be able to send more than one LSA before hearing about the sequence number it
had been using before restarting. Therefore, it is important to have enough restart numbers so that A
cannot use them all before neighbors either inform it of a previously used number or the previously used
number ages out of all databases.
These linear restart numbers form the stick of the lollipop. When they have been used up, or after a
neighbor has provided a sequence number to which A can jump, A enters a circular number space, the
candy part of the lollipop.
One way of designing a lollipop address space is to use signed sequence numbers, where –k <> 0, a <> 0, b > 0, a > b, and (a – b) > n/2.
Figure 4.10 shows an implementation of the lollipop-shaped sequence number space. A 32-bit signed
number space N is used, yielding 231 positive numbers and 231 negative numbers. –N (–231, or
0x80000000) and N – 1 (231 – 1, or 0x7FFFFFFF) are not used. A router coming online will begin its
sequence numbers at –N + 1 (0x80000001) and increment up to zero, at which time it has entered the
circular number space. When the sequence reaches N – 2 (0x7FFFFFFE), the sequence wraps back to
zero (again, N–1 is unused).
Next, suppose the router restarts. The sequence number of the last LSA sent before the restart is
0x00005de3 (part of the circular sequence space). As it synchronizes its database with its neighbor after
the restart, the router sends an LSA with a sequence number of 0x80000001 (–N + 1). The neighbor looks
into its own database and finds the pre-restart LSA with a sequence number of 0x00005de3. The neighbor
sends this LSA to the restarted router, essentially saying, "This is where you left off." The restarted router
then records the LSA with the positive sequence number. If it needs to send a new copy of the LSA at
some future time, the new sequence number will be 0x00005de6.
Lollipop sequence spaces were used with the original version of OSPF, OSPFv1 (RFC 1131). Although
the use of signed numbers was an improvement over the linear number space, the circular part was found
to be vulnerable to the same ambiguities as a purely circular space. The deployment of OSPFv1 never
progressed beyond the experimental stage. The current version of OSPF, OSPFv2 (originally specified in
RFC 1247) adopts the best features of linear and lollipop sequence number spaces. It uses a signed
number space like lollipop sequence numbers, beginning with 0x80000001. However, when the sequence
number goes positive, the sequence space continues to be linear until it reaches the maximum of
0x7fffffff. At that point the OSPF process must flush the LSA from all link state databases before
restarting.
number spaces are a hybrid of linear and circular sequence number spaces; if you think about it, a lollipop
has a linear component and a circular component. The problem with circular spaces is that there is no
number less than all other numbers. The problem with linear spaces is that they are—well—not circular.
That is, their set of sequence numbers is finite.
[9] R. Perlman."Fault-Tolerant Broadcasting of Routing Information." Computer Networks, Vol. 7, December 1983, pp. 395–405.
When router A restarts, it would be nice to begin with a number a that is less than all other numbers.
Neighbors will recognize this number for what it is, and if they have a pre-restart number b in their
databases from router A, they can send that number to router A and router A will jump to that sequence
number. Router A might be able to send more than one LSA before hearing about the sequence number it
had been using before restarting. Therefore, it is important to have enough restart numbers so that A
cannot use them all before neighbors either inform it of a previously used number or the previously used
number ages out of all databases.
These linear restart numbers form the stick of the lollipop. When they have been used up, or after a
neighbor has provided a sequence number to which A can jump, A enters a circular number space, the
candy part of the lollipop.
One way of designing a lollipop address space is to use signed sequence numbers, where –k <> 0, a <> 0, b > 0, a > b, and (a – b) > n/2.
Figure 4.10 shows an implementation of the lollipop-shaped sequence number space. A 32-bit signed
number space N is used, yielding 231 positive numbers and 231 negative numbers. –N (–231, or
0x80000000) and N – 1 (231 – 1, or 0x7FFFFFFF) are not used. A router coming online will begin its
sequence numbers at –N + 1 (0x80000001) and increment up to zero, at which time it has entered the
circular number space. When the sequence reaches N – 2 (0x7FFFFFFE), the sequence wraps back to
zero (again, N–1 is unused).
Next, suppose the router restarts. The sequence number of the last LSA sent before the restart is
0x00005de3 (part of the circular sequence space). As it synchronizes its database with its neighbor after
the restart, the router sends an LSA with a sequence number of 0x80000001 (–N + 1). The neighbor looks
into its own database and finds the pre-restart LSA with a sequence number of 0x00005de3. The neighbor
sends this LSA to the restarted router, essentially saying, "This is where you left off." The restarted router
then records the LSA with the positive sequence number. If it needs to send a new copy of the LSA at
some future time, the new sequence number will be 0x00005de6.
Lollipop sequence spaces were used with the original version of OSPF, OSPFv1 (RFC 1131). Although
the use of signed numbers was an improvement over the linear number space, the circular part was found
to be vulnerable to the same ambiguities as a purely circular space. The deployment of OSPFv1 never
progressed beyond the experimental stage. The current version of OSPF, OSPFv2 (originally specified in
RFC 1247) adopts the best features of linear and lollipop sequence number spaces. It uses a signed
number space like lollipop sequence numbers, beginning with 0x80000001. However, when the sequence
number goes positive, the sequence space continues to be linear until it reaches the maximum of
0x7fffffff. At that point the OSPF process must flush the LSA from all link state databases before
restarting.
Circular Sequence Number Spaces
Another approach is to use circular sequence number space, where the numbers "wrap"—that is, in a 32-
bit space the number following 4,294,967,295 is 0. Malfunctions can cause interesting dilemmas here,
too. A restarting router may encounter the same believability problem as discussed for linear sequence
numbers.
Circular sequence numbering creates a curious bit of illogic. If x is any number between 1 and
4,294,967,295 inclusive, then 0 < x < 0. This situation can be managed in well-behaved internetworks by
asserting two rules for determining when a sequence number is greater than or less than another sequence
number. Given a sequence number space n and two sequence numbers a and b, a is considered more
recent (of larger magnitude) in either of the following situations:
a b, and (a – b) \? n/2
a <> n/2
For the sake of simplicity, take a sequence number space of six bits, shown in Figure 4.9:
n = 26 = 64, so n/2 = 32.
Given two sequence numbers 48 and 18, 48 is more recent because by rule (1):
48 > 18and(48 – 18) = 30,and30 < 32.
Given two sequence numbers 3 and 48, 3 is more recent because by rule (2):
3 <> 32.
Given two sequence numbers 3 and 18, 18 is more recent because by rule (1):
18 > 3and(18 – 3) = 15,and15 <>.
So the rules seem to enforce circularity.
But what about a not-so-well-behaved internetwork? Imagine an internetwork running a six-bit sequence
number space. Now imagine that one of the routers on the internetwork decides to go belly-up, but as it
does so, it blurts out three identical LSAs with a sequence number of 44 (101100). Unfortunately, a
neighboring router is also malfunctioning—it is dropping bits. The neighbor drops a bit in the sequence
number field of the second LSA, drops yet another bit in the third LSA, and floods all three. The result is
three identical LSAs with three different sequence numbers:
44 (101100)
40 (101000)
8 (001000)
Applying the circularity rules reveals that 44 is more recent than 40, which is more recent than 8, which is
more recent than 44! The result is that every LSA will be continuously flooded, and databases will be
continually overwritten with the "latest" LSA, until finally buffers become clogged with LSAs, CPUs
become overloaded, and the whole internetwork comes crashing down.
This chain of events sounds pretty far-fetched. It is, however, factual. The ARPANET, the precursor of
the modern Internet, ran an early link state protocol with a six-bit circular sequence number space; on
October 27, 1980, two routers experiencing the malfunctions just described brought the entire ARPANET
to a standstill.
bit space the number following 4,294,967,295 is 0. Malfunctions can cause interesting dilemmas here,
too. A restarting router may encounter the same believability problem as discussed for linear sequence
numbers.
Circular sequence numbering creates a curious bit of illogic. If x is any number between 1 and
4,294,967,295 inclusive, then 0 < x < 0. This situation can be managed in well-behaved internetworks by
asserting two rules for determining when a sequence number is greater than or less than another sequence
number. Given a sequence number space n and two sequence numbers a and b, a is considered more
recent (of larger magnitude) in either of the following situations:
a b, and (a – b) \? n/2
a <> n/2
For the sake of simplicity, take a sequence number space of six bits, shown in Figure 4.9:
n = 26 = 64, so n/2 = 32.
Given two sequence numbers 48 and 18, 48 is more recent because by rule (1):
48 > 18and(48 – 18) = 30,and30 < 32.
Given two sequence numbers 3 and 48, 3 is more recent because by rule (2):
3 <> 32.
Given two sequence numbers 3 and 18, 18 is more recent because by rule (1):
18 > 3and(18 – 3) = 15,and15 <>.
So the rules seem to enforce circularity.
But what about a not-so-well-behaved internetwork? Imagine an internetwork running a six-bit sequence
number space. Now imagine that one of the routers on the internetwork decides to go belly-up, but as it
does so, it blurts out three identical LSAs with a sequence number of 44 (101100). Unfortunately, a
neighboring router is also malfunctioning—it is dropping bits. The neighbor drops a bit in the sequence
number field of the second LSA, drops yet another bit in the third LSA, and floods all three. The result is
three identical LSAs with three different sequence numbers:
44 (101100)
40 (101000)
8 (001000)
Applying the circularity rules reveals that 44 is more recent than 40, which is more recent than 8, which is
more recent than 44! The result is that every LSA will be continuously flooded, and databases will be
continually overwritten with the "latest" LSA, until finally buffers become clogged with LSAs, CPUs
become overloaded, and the whole internetwork comes crashing down.
This chain of events sounds pretty far-fetched. It is, however, factual. The ARPANET, the precursor of
the modern Internet, ran an early link state protocol with a six-bit circular sequence number space; on
October 27, 1980, two routers experiencing the malfunctions just described brought the entire ARPANET
to a standstill.
Linear Sequence Number Spaces
One approach is to use a linear sequence number space so large that it is unlikely the upper limit will ever
be reached. If, for instance, a 32-bit field is used, there are 232 = 4,294,967,296 available sequence
numbers starting with zero. Even if a router was creating a new link state packet every 10 seconds, it
would take some 1361 years to exhaust the sequence number supply; few routers are expected to last so
long.
In this imperfect world, unfortunately, malfunctions occur. If a link state routing process somehow runs
out of sequence numbers, it must shut itself down and stay down long enough for its LSAs to age out of
all databases before starting over at the lowest sequence number (see the section "Aging," later in this
chapter).
A more common difficulty presents itself during router restarts. If router A restarts, it probably will have
no way of remembering the sequence number it last used and must begin again at, say, one. But if its
neighbors still have router A's previous sequence numbers in their databases, the lower sequence numbers
will be interpreted as older sequence numbers and will be ignored. Again, the routing process must stay
down until all old LSAs are aged out of the internetwork. Given that a maximum age might be an hour or
more, this solution is not very attractive.
A better solution is to add a new rule to the flooding behavior described thus far: If a restarted router
issues to a neighbor an LSA with a sequence number that appears to be older than the neighbor's stored
sequence number, the neighbor will send its own stored LSA and sequence number back to the router.
The router will thus learn the sequence number it was using before it restarted and may adjust
accordingly.
Care must be taken, however, that the last-used sequence number was not close to the maximum;
otherwise, the restarting router will simply have to restart again. A rule must be set limiting the "jump"
the router may make in sequence numbers—for instance, a rule might say that the sequence numbers
cannot make a single increase more than one-half the total sequence number space. (The actual formulas
are more complex than this example, taking into account age constraints.)
IS-IS uses a 32-bit linear sequence number space.
be reached. If, for instance, a 32-bit field is used, there are 232 = 4,294,967,296 available sequence
numbers starting with zero. Even if a router was creating a new link state packet every 10 seconds, it
would take some 1361 years to exhaust the sequence number supply; few routers are expected to last so
long.
In this imperfect world, unfortunately, malfunctions occur. If a link state routing process somehow runs
out of sequence numbers, it must shut itself down and stay down long enough for its LSAs to age out of
all databases before starting over at the lowest sequence number (see the section "Aging," later in this
chapter).
A more common difficulty presents itself during router restarts. If router A restarts, it probably will have
no way of remembering the sequence number it last used and must begin again at, say, one. But if its
neighbors still have router A's previous sequence numbers in their databases, the lower sequence numbers
will be interpreted as older sequence numbers and will be ignored. Again, the routing process must stay
down until all old LSAs are aged out of the internetwork. Given that a maximum age might be an hour or
more, this solution is not very attractive.
A better solution is to add a new rule to the flooding behavior described thus far: If a restarted router
issues to a neighbor an LSA with a sequence number that appears to be older than the neighbor's stored
sequence number, the neighbor will send its own stored LSA and sequence number back to the router.
The router will thus learn the sequence number it was using before it restarted and may adjust
accordingly.
Care must be taken, however, that the last-used sequence number was not close to the maximum;
otherwise, the restarting router will simply have to restart again. A rule must be set limiting the "jump"
the router may make in sequence numbers—for instance, a rule might say that the sequence numbers
cannot make a single increase more than one-half the total sequence number space. (The actual formulas
are more complex than this example, taking into account age constraints.)
IS-IS uses a 32-bit linear sequence number space.
Sequence Numbers
A difficulty with flooding, as described so far, is that when all routers have received all LSAs, the
flooding must stop. A time-to-live value in the packets could simply be relied on to expire, but it is hardly
efficient to permit LSAs to wander the internetwork until they expire. Take the internetwork in Figure
4.8. Subnet 172.22.4.0 at router A has failed, and A has flooded an LSA to its neighbors B and D,
advertising the new state of the link. B and D dutifully flood to their neighbors, and so on.
Figure 4.8. When a topology change occurs, LSAs advertising the change will be flooded throughout the
internetwork.
Look next at what happens at router C. An LSA arrives from router B at time t1, is entered into C's
topological database, and is forwarded to router F. At some later time t3, another copy of the same LSA
arrives from the longer A-D-E-F-C route. Router C sees that it already has the LSA in its database; the
question is, should C forward this LSA to router B? The answer is no because B has already received the
advertisement. Router C knows this because the sequence number of the LSA it received from router F is
the same as the sequence number of the LSA it received earlier from router B.
When router A sent out the LSA, it included an identical sequence number in each copy. This sequence
number is recorded in the routers' topological databases along with the rest of the LSA; when a router
receives an LSA that is already in the database and its sequence number is the same, the received
information is discarded. If the information is the same but the sequence number is greater, the received
information and new sequence number are entered into the database and the LSA is flooded. In this way,
flooding is abated when all routers have seen a copy of the most recent LSA.
As described so far, it seems that routers could merely verify that their link state databases contain the
same LSA as the newly received LSA and make a flood/discard decision based on that information,
without needing a sequence number. But imagine that immediately after Figure 4.8's network 172.22.4.0
failed, it came back up. Router A might send out an LSA advertising the network as down, with a
sequence number of 166; then it sends out a new LSA announcing the same network as up, with a
sequence number of 167. Router C receives the down LSA and then the up LSA from the A-B-C path, but
then it receives a delayed down LSA from the A-D-E-F-C path. Without the sequence numbers, C would
not know whether or not to believe the delayed down LSA. With sequence numbers, C's database will
indicate that the information from router A has a sequence number of 167; the late LSA has a sequence
number of 166 and is therefore recognized as old information and discarded.
Because the sequence numbers are carried in a set field within the LSAs, the numbers must have some
upper bound. What happens when this maximum sequence number is reached?
flooding must stop. A time-to-live value in the packets could simply be relied on to expire, but it is hardly
efficient to permit LSAs to wander the internetwork until they expire. Take the internetwork in Figure
4.8. Subnet 172.22.4.0 at router A has failed, and A has flooded an LSA to its neighbors B and D,
advertising the new state of the link. B and D dutifully flood to their neighbors, and so on.
Figure 4.8. When a topology change occurs, LSAs advertising the change will be flooded throughout the
internetwork.
Look next at what happens at router C. An LSA arrives from router B at time t1, is entered into C's
topological database, and is forwarded to router F. At some later time t3, another copy of the same LSA
arrives from the longer A-D-E-F-C route. Router C sees that it already has the LSA in its database; the
question is, should C forward this LSA to router B? The answer is no because B has already received the
advertisement. Router C knows this because the sequence number of the LSA it received from router F is
the same as the sequence number of the LSA it received earlier from router B.
When router A sent out the LSA, it included an identical sequence number in each copy. This sequence
number is recorded in the routers' topological databases along with the rest of the LSA; when a router
receives an LSA that is already in the database and its sequence number is the same, the received
information is discarded. If the information is the same but the sequence number is greater, the received
information and new sequence number are entered into the database and the LSA is flooded. In this way,
flooding is abated when all routers have seen a copy of the most recent LSA.
As described so far, it seems that routers could merely verify that their link state databases contain the
same LSA as the newly received LSA and make a flood/discard decision based on that information,
without needing a sequence number. But imagine that immediately after Figure 4.8's network 172.22.4.0
failed, it came back up. Router A might send out an LSA advertising the network as down, with a
sequence number of 166; then it sends out a new LSA announcing the same network as up, with a
sequence number of 167. Router C receives the down LSA and then the up LSA from the A-B-C path, but
then it receives a delayed down LSA from the A-D-E-F-C path. Without the sequence numbers, C would
not know whether or not to believe the delayed down LSA. With sequence numbers, C's database will
indicate that the information from router A has a sequence number of 167; the late LSA has a sequence
number of 166 and is therefore recognized as old information and discarded.
Because the sequence numbers are carried in a set field within the LSAs, the numbers must have some
upper bound. What happens when this maximum sequence number is reached?
Link State Flooding
After the adjacencies are established, the routers may begin sending out LSAs. As the term flooding
implies, the advertisements are sent to every neighbor. In turn, each received LSA is copied and
forwarded to every neighbor except the one that sent the LSA. This process is the source of one of link
state's advantages over distance vector. LSAs are forwarded almost immediately, whereas distance vector
must run its algorithm and update its route table before routing updates, even the triggered ones, can be
forwarded. As a result, link state protocols converge much faster than distance vector protocols converge
when the topology changes.
The flooding process is the most complex piece of a link state protocol. There are several ways to make
flooding more efficient and more reliable, such as using unicast and multicast addresses, checksums, and
positive acknowledgments. These topics are examined in the protocol-specific chapters, but two
procedures are vitally important to the flooding process: sequencing and aging.
implies, the advertisements are sent to every neighbor. In turn, each received LSA is copied and
forwarded to every neighbor except the one that sent the LSA. This process is the source of one of link
state's advantages over distance vector. LSAs are forwarded almost immediately, whereas distance vector
must run its algorithm and update its route table before routing updates, even the triggered ones, can be
forwarded. As a result, link state protocols converge much faster than distance vector protocols converge
when the topology changes.
The flooding process is the most complex piece of a link state protocol. There are several ways to make
flooding more efficient and more reliable, such as using unicast and multicast addresses, checksums, and
positive acknowledgments. These topics are examined in the protocol-specific chapters, but two
procedures are vitally important to the flooding process: sequencing and aging.
Neighbors
Neighbor discovery is the first step in getting a link state environment up and running. In keeping with the
friendly neighbor terminology, a Hello protocol is used for this step. The protocol will define a Hello
packet format and a procedure for exchanging the packets and processing the information the packets
contain.
NOTE
Router ID
At a minimum, the Hello packet will contain a router ID and the address of the network on which the
packet is being sent. The router ID is be something by which the router originating the packet can be
uniquely distinguished from all other routers; for instance, an IP address from one of the router's
interfaces. Other fields of the packet may carry a subnet mask, Hello intervals, a specified maximum
period the router will wait to hear a Hello before declaring the neighbor "dead," a descriptor of the circuit
type, and flags to help in bringing up adjacencies.
NOTE
Adjacent neighbors
When two routers have discovered each other as neighbors, they go through a process of synchronizing
their databases in which they exchange and verify database information until their databases are identical.
The details of database synchronization are described in Chapters 9, "Open Shortest Path First," and 10,
"Integrated IS-IS." To perform this database synchronization, the neighbors must be adja cent—that is,
they must agree on certain protocol-specific parameters such as timers and support of optional
capabilities. By using Hello packets to build adjacencies, link state protocols can exchange information in
a controlled fashion. Contrast this approach with distance vector, which simply broadcasts updates out
any interface configured for that routing protocol.
Beyond building adjacencies, Hello packets serve as keepalives to monitor the adjacency. If Hellos are
not heard from an adjacent neighbor within a certain established time, the neighbor is considered
unreachable and the adjacency is broken. A typical interval for the exchange of hello packets is 10
seconds, and a typical dead period is four times that.
friendly neighbor terminology, a Hello protocol is used for this step. The protocol will define a Hello
packet format and a procedure for exchanging the packets and processing the information the packets
contain.
NOTE
Router ID
At a minimum, the Hello packet will contain a router ID and the address of the network on which the
packet is being sent. The router ID is be something by which the router originating the packet can be
uniquely distinguished from all other routers; for instance, an IP address from one of the router's
interfaces. Other fields of the packet may carry a subnet mask, Hello intervals, a specified maximum
period the router will wait to hear a Hello before declaring the neighbor "dead," a descriptor of the circuit
type, and flags to help in bringing up adjacencies.
NOTE
Adjacent neighbors
When two routers have discovered each other as neighbors, they go through a process of synchronizing
their databases in which they exchange and verify database information until their databases are identical.
The details of database synchronization are described in Chapters 9, "Open Shortest Path First," and 10,
"Integrated IS-IS." To perform this database synchronization, the neighbors must be adja cent—that is,
they must agree on certain protocol-specific parameters such as timers and support of optional
capabilities. By using Hello packets to build adjacencies, link state protocols can exchange information in
a controlled fashion. Contrast this approach with distance vector, which simply broadcasts updates out
any interface configured for that routing protocol.
Beyond building adjacencies, Hello packets serve as keepalives to monitor the adjacency. If Hellos are
not heard from an adjacent neighbor within a certain established time, the neighbor is considered
unreachable and the adjacency is broken. A typical interval for the exchange of hello packets is 10
seconds, and a typical dead period is four times that.
Link State Routing Protocols
The information available to a distance vector router has been compared to the information available from
a road sign. Link state routing protocols are like a road map. A link state router cannot be fooled as easily
into making bad routing decisions, because it has a complete picture of the network. The reason is that
unlike the routing-by-rumor approach of distance vector, link state routers have firsthand information
from all their peer[7] routers. Each router originates information about itself, its directly connected links,
and the state of those links (hence the name). This information is passed around from router to router,
each router making a copy of it, but never changing it. The ultimate objective is that every router has
identical information about the internetwork, and each router will independently calculate its own best
paths.
[7] That is, all routers speaking the same routing protocol.
Link state protocols, sometimes called shortest path first or distributed database protocols, are built
around a well-known algorithm from graph theory, E. W. Dijkstra'a shortest path algorithm. Examples of
link state routing protocols are:
Open Shortest Path First (OSPF) for IP
The ISO's Intermediate System to Intermediate System (IS-IS) for CLNS and IP
DEC's DNA Phase V
Novell's NetWare Link Services Protocol (NLSP)
Although link state protocols are rightly considered more complex than distance vector protocols, the
basic functionality is not complex at all:
NOTE
Link state advertisement
1. Each router establishes a relationship—an adjacency—with each of its neighbors.
2. Each router sends link state advertisements (LSAs), sometimes called link state packets (LSPs), to
each neighbor. One LSA is generated for each of the router's links, identifying the link, the state of
the link, the metric cost of the router's interface to the link, and any neighbors that may be
connected to the link. Each neighbor receiving an advertisement in turn forwards (floods) the
advertisement to its own neighbors.
3. Each router stores a copy of all the LSAs it has seen in a database. If all works well, the databases
in all routers should be identical.
4. The completed topological database, also called the link state database, describes a graph of the
internetwork. Using the Dijkstra algorithm, each router calculates the shortest path to each
network and enters this information into the route table.
a road sign. Link state routing protocols are like a road map. A link state router cannot be fooled as easily
into making bad routing decisions, because it has a complete picture of the network. The reason is that
unlike the routing-by-rumor approach of distance vector, link state routers have firsthand information
from all their peer[7] routers. Each router originates information about itself, its directly connected links,
and the state of those links (hence the name). This information is passed around from router to router,
each router making a copy of it, but never changing it. The ultimate objective is that every router has
identical information about the internetwork, and each router will independently calculate its own best
paths.
[7] That is, all routers speaking the same routing protocol.
Link state protocols, sometimes called shortest path first or distributed database protocols, are built
around a well-known algorithm from graph theory, E. W. Dijkstra'a shortest path algorithm. Examples of
link state routing protocols are:
Open Shortest Path First (OSPF) for IP
The ISO's Intermediate System to Intermediate System (IS-IS) for CLNS and IP
DEC's DNA Phase V
Novell's NetWare Link Services Protocol (NLSP)
Although link state protocols are rightly considered more complex than distance vector protocols, the
basic functionality is not complex at all:
NOTE
Link state advertisement
1. Each router establishes a relationship—an adjacency—with each of its neighbors.
2. Each router sends link state advertisements (LSAs), sometimes called link state packets (LSPs), to
each neighbor. One LSA is generated for each of the router's links, identifying the link, the state of
the link, the metric cost of the router's interface to the link, and any neighbors that may be
connected to the link. Each neighbor receiving an advertisement in turn forwards (floods) the
advertisement to its own neighbors.
3. Each router stores a copy of all the LSAs it has seen in a database. If all works well, the databases
in all routers should be identical.
4. The completed topological database, also called the link state database, describes a graph of the
internetwork. Using the Dijkstra algorithm, each router calculates the shortest path to each
network and enters this information into the route table.
Asynchronous Updates
Figure 4.7 shows a group of routers connected to an Ethernet backbone. The routers should not broadcast
their updates at the same time; if they do, the update packets will collide. Yet this situation is exactly what
can happen when a several routers share a broadcast network. System delays related to the processing of
updates in the routers tend to cause the update timers to become synchronized. As a few routers become
synchronized, collisions will begin to occur, further contributing to system delays, and eventually all
routers sharing the broadcast network may become synchronized.
Asynchronous updates may be maintained by one of two methods:
Each router's update timer is independent of the routing process and is, therefore, not affected by
processing loads on the router.
A small random time, or timing jitter, is added to each update period as an offset.
If routers implement the method of rigid, system-independent timers, then all routers sharing a broadcast
network must be brought online in a random fashion. Rebooting the entire group of routers
simultaneously could result in all the timers attempting to update at the same time.
Adding randomness to the update period is effective if the variable is large enough in proportion to the
number of routers sharing the broadcast network. Sally Floyd and Van Jacobson[6] , have calculated that a
too-small randomization will be overcome by a large enough network of routers and that to be effective
the update timer should range as much as 50% of the median update period.
their updates at the same time; if they do, the update packets will collide. Yet this situation is exactly what
can happen when a several routers share a broadcast network. System delays related to the processing of
updates in the routers tend to cause the update timers to become synchronized. As a few routers become
synchronized, collisions will begin to occur, further contributing to system delays, and eventually all
routers sharing the broadcast network may become synchronized.
Asynchronous updates may be maintained by one of two methods:
Each router's update timer is independent of the routing process and is, therefore, not affected by
processing loads on the router.
A small random time, or timing jitter, is added to each update period as an offset.
If routers implement the method of rigid, system-independent timers, then all routers sharing a broadcast
network must be brought online in a random fashion. Rebooting the entire group of routers
simultaneously could result in all the timers attempting to update at the same time.
Adding randomness to the update period is effective if the variable is large enough in proportion to the
number of routers sharing the broadcast network. Sally Floyd and Van Jacobson[6] , have calculated that a
too-small randomization will be overcome by a large enough network of routers and that to be effective
the update timer should range as much as 50% of the median update period.
Holddown Timers
Triggered updates add responsiveness to a reconverging internetwork. Holddown timers introduce a
certain amount of skepticism to reduce the acceptance of bad routing information.
If the distance to a destination increases (for example, the hop count increases from 2 to 4), the router sets
a holddown timer for that route. Until the timer expires, the router will not accept any new updates for the
route.
Obviously, a trade-off is involved here. The likelihood of bad routing information getting into a table is
reduced but at the expense of the reconvergence time. Like other timers, holddown timers must be set
with care. If the holddown period is too short, it will be ineffective, and if it is too long, normal routing
will be adversely affected.
certain amount of skepticism to reduce the acceptance of bad routing information.
If the distance to a destination increases (for example, the hop count increases from 2 to 4), the router sets
a holddown timer for that route. Until the timer expires, the router will not accept any new updates for the
route.
Obviously, a trade-off is involved here. The likelihood of bad routing information getting into a table is
reduced but at the expense of the reconvergence time. Like other timers, holddown timers must be set
with care. If the holddown period is too short, it will be ineffective, and if it is too long, normal routing
will be adversely affected.
Triggered Updates
Triggered updates, also known as flash updates, are very simple: If a metric changes for better or for
worse, a router will immediately send out an update without waiting for its update timer to expire.
Reconvergence will occur far more quickly than if every router had to wait for regularly scheduled
updates, and the problem of counting to infinity is greatly reduced, although not completely eliminated.
Regular updates may still occur along with triggered updates. Thus a router might receive bad
information about a route from a not-yet-reconverged router after having received correct information
from a triggered update. Such a situation shows that confusion and routing errors may still occur while an
internetwork is reconverging, but triggered updates will help to iron things out more quickly.
A further refinement is to include in the update only the networks that actually triggered it, rather than the
entire route table. This technique reduces the processing time and the impact on network bandwidth.
worse, a router will immediately send out an update without waiting for its update timer to expire.
Reconvergence will occur far more quickly than if every router had to wait for regularly scheduled
updates, and the problem of counting to infinity is greatly reduced, although not completely eliminated.
Regular updates may still occur along with triggered updates. Thus a router might receive bad
information about a route from a not-yet-reconverged router after having received correct information
from a triggered update. Such a situation shows that confusion and routing errors may still occur while an
internetwork is reconverging, but triggered updates will help to iron things out more quickly.
A further refinement is to include in the update only the networks that actually triggered it, rather than the
entire route table. This technique reduces the processing time and the impact on network bandwidth.
Counting to Infinity
Split horizon will break loops between neighbors, but it will not stop loops in a network such as the one
in Figure 4.6. Again, 10.1.5.0 has failed. Router D sends the appropriate updates to its neighbors router C
(the dashed arrows) and router B (the solid arrows). Router B marks the route via D as unreachable, but
router A is advertising a next-best path to 10.1.5.0, which is 3 hops away. B posts that route in its route
table.
B now informs D that it has an alternative route to 10.1.5.0. D posts this information and updates C,
saying that it has a 4-hop route to the network. C tells A that 10.1.5.0 is 5 hops away. A tells B that the
network is now 6 hops away.
"Ah," router B thinks, "router A's path to 10.1.5.0 has increased in length. Nonetheless, it's the only route
I've got, so I'll use it!"
B changes the hop count to 7, updates D, and around it goes again. This situation is the counting-toinfinity
problem because the hop count to 10.1.5.0 will continue to increase to infinity. All routers are
implementing split horizon, but it doesn't help.
NOTE
Defining infinity
The way to alleviate the effects of counting to infinity is to define infinity. Most distance vector protocols
define infinity to be 16 hops. As the updates continue to loop among the routers in Figure 4.6, the hop
count to 10.1.5.0 in all routers will eventually increment to 16. At that time, the network will be
considered unreachable.
This method is also how routers advertise a network as unreachable. Whether it is a poisoned reverse
route, a network that has failed, or a network beyond the maximum network diameter of 15 hops, a router
will recognize any 16-hop route as unreachable.
Setting a maximum hop count of 15 helps solve the counting-to-infinity problem, but convergence will
still be very slow. Given an update period of 30 seconds, a network could take up to 7.5 minutes to
reconverge and is susceptible to routing errors during this time. The two methods for speeding up
reconvergence are triggered updates and holddown timers.
in Figure 4.6. Again, 10.1.5.0 has failed. Router D sends the appropriate updates to its neighbors router C
(the dashed arrows) and router B (the solid arrows). Router B marks the route via D as unreachable, but
router A is advertising a next-best path to 10.1.5.0, which is 3 hops away. B posts that route in its route
table.
B now informs D that it has an alternative route to 10.1.5.0. D posts this information and updates C,
saying that it has a 4-hop route to the network. C tells A that 10.1.5.0 is 5 hops away. A tells B that the
network is now 6 hops away.
"Ah," router B thinks, "router A's path to 10.1.5.0 has increased in length. Nonetheless, it's the only route
I've got, so I'll use it!"
B changes the hop count to 7, updates D, and around it goes again. This situation is the counting-toinfinity
problem because the hop count to 10.1.5.0 will continue to increase to infinity. All routers are
implementing split horizon, but it doesn't help.
NOTE
Defining infinity
The way to alleviate the effects of counting to infinity is to define infinity. Most distance vector protocols
define infinity to be 16 hops. As the updates continue to loop among the routers in Figure 4.6, the hop
count to 10.1.5.0 in all routers will eventually increment to 16. At that time, the network will be
considered unreachable.
This method is also how routers advertise a network as unreachable. Whether it is a poisoned reverse
route, a network that has failed, or a network beyond the maximum network diameter of 15 hops, a router
will recognize any 16-hop route as unreachable.
Setting a maximum hop count of 15 helps solve the counting-to-infinity problem, but convergence will
still be very slow. Given an update period of 30 seconds, a network could take up to 7.5 minutes to
reconverge and is susceptible to routing errors during this time. The two methods for speeding up
reconvergence are triggered updates and holddown timers.
Split Horizon
According to the distance vector algorithm as it has been described so far, at every update period each
router broadcasts its entire route table to every neighbor. But is this really necessary? Every network
known by router A in Figure 4.3, with a hop count higher than 0, has been learned from router B.
Common sense suggests that for router A to broadcast the networks it has learned from router B back to
router B is a waste of resources. Obviously, B already knows about those networks.
A route pointing back to the router from which packets were received is called a reverse route. Split
horizon is a technique for preventing reverse routes between two routers.
Besides not wasting resources, there is a more important reason for not sending reachability information
back to the router from which the information was learned. The most important function of a dynamic
routing protocol is to detect and compensate for topology changes—if the best path to a network becomes
unreachable, the protocol must look for a next-best path.
Look yet again at the converged internetwork of Figure 4.3 and suppose that network 10.1.5.0 goes down.
Router D will detect the failure, flag the network as unreachable, and pass the information along to router
C at the next update interval. However, before D's update timer triggers an update, something unexpected
happens. C's update arrives, claiming that it can reach 10.1.5.0, one hop away! Remember the road sign
analogy? Router D has no way of knowing that C is not advertising a legitimate next-best path. It will
increment the hop count and make an entry into its route table indicating that 10.1.5.0 is reachable via
router C's interface 10.1.4.1, just 2 hops away.
Now a packet with a destination address of 10.1.5.3 arrives at router C. C consults its route table and
forwards the packet to D. D consults its route table and forwards the packet to C, C forwards it back to D,
ad infinitum. A routing loop has occurred.
Implementing split horizon prevents the possibility of such a routing loop. There are two categories of
split horizon: simple split horizon and split horizon with poisoned reverse.
The rule for simple split horizon is, When sending updates out a particular interface, do not include
networks that were learned from updates received on that interface.
The routers in Figure 4.4 implement simple split horizon. Router C sends an update to router D for
networks 10.1.1.0, 10.1.2.0, and 10.1.3.0. Networks 10.1.4.0 and 10.1.5.0 are not included because they
were learned from router D. Likewise, updates to router B include 10.1.4.0 and 10.1.5.0 with no mention
of 10.1.1.0, 10.1.2.0, and 10.1.3.0.Simple split horizon works by suppressing information. Split horizon with poisoned reverse is a
modification that provides more positive information.
The rule for split horizon with poisoned reverse is, When sending updates out a particular interface,
designate any networks that were learned from updates received on that interface as unreachable.
NOTE
Split horizon with poisoned reverse
In the scenario of Figure 4.4, router C would in fact advertise 10.1.4.0 and 10.1.5.0 to router D, but the
network would be marked as unreachable. Figure 4.5 shows what the route tables from C to B and D
would look like. Notice that a route is marked as unreachable by setting the metric to infinity; in other
words, the network is an infinite distance away. Coverage of a routing protocol's concept of infinity
continues in the next section.
Split horizon with poisoned reverse is considered safer and stronger than simple split horizon—a sort of
"bad news is better than no news at all" approach. For example, suppose that router B in Figure 4.5
receives corrupted information causing it to believe that subnet 10.1.1.0 is reachable via router C. Simple
split horizon would do nothing to correct this misperception, whereas a poisoned reverse update from
router C would immediately stop the potential loop. For this reason, most modern distance vector
implementations use split horizon with poisoned reverse. The trade-off is that routing update packets are
larger, which may exacerbate any congestion problems on a link.
router broadcasts its entire route table to every neighbor. But is this really necessary? Every network
known by router A in Figure 4.3, with a hop count higher than 0, has been learned from router B.
Common sense suggests that for router A to broadcast the networks it has learned from router B back to
router B is a waste of resources. Obviously, B already knows about those networks.
A route pointing back to the router from which packets were received is called a reverse route. Split
horizon is a technique for preventing reverse routes between two routers.
Besides not wasting resources, there is a more important reason for not sending reachability information
back to the router from which the information was learned. The most important function of a dynamic
routing protocol is to detect and compensate for topology changes—if the best path to a network becomes
unreachable, the protocol must look for a next-best path.
Look yet again at the converged internetwork of Figure 4.3 and suppose that network 10.1.5.0 goes down.
Router D will detect the failure, flag the network as unreachable, and pass the information along to router
C at the next update interval. However, before D's update timer triggers an update, something unexpected
happens. C's update arrives, claiming that it can reach 10.1.5.0, one hop away! Remember the road sign
analogy? Router D has no way of knowing that C is not advertising a legitimate next-best path. It will
increment the hop count and make an entry into its route table indicating that 10.1.5.0 is reachable via
router C's interface 10.1.4.1, just 2 hops away.
Now a packet with a destination address of 10.1.5.3 arrives at router C. C consults its route table and
forwards the packet to D. D consults its route table and forwards the packet to C, C forwards it back to D,
ad infinitum. A routing loop has occurred.
Implementing split horizon prevents the possibility of such a routing loop. There are two categories of
split horizon: simple split horizon and split horizon with poisoned reverse.
The rule for simple split horizon is, When sending updates out a particular interface, do not include
networks that were learned from updates received on that interface.
The routers in Figure 4.4 implement simple split horizon. Router C sends an update to router D for
networks 10.1.1.0, 10.1.2.0, and 10.1.3.0. Networks 10.1.4.0 and 10.1.5.0 are not included because they
were learned from router D. Likewise, updates to router B include 10.1.4.0 and 10.1.5.0 with no mention
of 10.1.1.0, 10.1.2.0, and 10.1.3.0.Simple split horizon works by suppressing information. Split horizon with poisoned reverse is a
modification that provides more positive information.
The rule for split horizon with poisoned reverse is, When sending updates out a particular interface,
designate any networks that were learned from updates received on that interface as unreachable.
NOTE
Split horizon with poisoned reverse
In the scenario of Figure 4.4, router C would in fact advertise 10.1.4.0 and 10.1.5.0 to router D, but the
network would be marked as unreachable. Figure 4.5 shows what the route tables from C to B and D
would look like. Notice that a route is marked as unreachable by setting the metric to infinity; in other
words, the network is an infinite distance away. Coverage of a routing protocol's concept of infinity
continues in the next section.
Split horizon with poisoned reverse is considered safer and stronger than simple split horizon—a sort of
"bad news is better than no news at all" approach. For example, suppose that router B in Figure 4.5
receives corrupted information causing it to believe that subnet 10.1.1.0 is reachable via router C. Simple
split horizon would do nothing to correct this misperception, whereas a poisoned reverse update from
router C would immediately stop the potential loop. For this reason, most modern distance vector
implementations use split horizon with poisoned reverse. The trade-off is that routing update packets are
larger, which may exacerbate any congestion problems on a link.
Route Invalidation Timers
Now that the internetwork in Figure 4.3 is fully converged, how will it handle reconvergence when some
part of the topology changes? If network 10.1.5.0 goes down, the answer is simple enough—router D, in
its next scheduled update, flags the network as unreachable and passes the information along.
But what if, instead of 10.1.5.0 going down, router D fails? Routers A, B, and C still have entries in their
route tables about 10.1.5.0; the information is no longer valid, but there's no router to inform them of this
fact. They will unknowingly forward packets to an unreachable destination—a black hole has opened in
the internetwork.
This problem is handled by setting a route invalidation timer for each entry in the route table. For
example, when router C first hears about 10.1.5.0 and enters the information into its route table, C sets a
timer for that route. At every regularly scheduled update from router D, C discards the update's alreadyknown
information about 10.1.5.0 as described in "Routing by Rumor." But as C does so, it resets the
timer on that route.
If router D goes down, C will no longer hear updates about 10.1.5.0. The timer will expire, C will flag the
route as unreachable and will pass the information along in the next update.
Typical periods for route timeouts range from three to six update periods. A router would not want to
invalidate a route after a single update has been missed, because this event may be the result of a corrupted or lost packet or some sort of network delay. At the same time, if the period is too long,
reconvergence will be excessively slow.
part of the topology changes? If network 10.1.5.0 goes down, the answer is simple enough—router D, in
its next scheduled update, flags the network as unreachable and passes the information along.
But what if, instead of 10.1.5.0 going down, router D fails? Routers A, B, and C still have entries in their
route tables about 10.1.5.0; the information is no longer valid, but there's no router to inform them of this
fact. They will unknowingly forward packets to an unreachable destination—a black hole has opened in
the internetwork.
This problem is handled by setting a route invalidation timer for each entry in the route table. For
example, when router C first hears about 10.1.5.0 and enters the information into its route table, C sets a
timer for that route. At every regularly scheduled update from router D, C discards the update's alreadyknown
information about 10.1.5.0 as described in "Routing by Rumor." But as C does so, it resets the
timer on that route.
If router D goes down, C will no longer hear updates about 10.1.5.0. The timer will expire, C will flag the
route as unreachable and will pass the information along in the next update.
Typical periods for route timeouts range from three to six update periods. A router would not want to
invalidate a route after a single update has been missed, because this event may be the result of a corrupted or lost packet or some sort of network delay. At the same time, if the period is too long,
reconvergence will be excessively slow.
Routing by Rumor
Figure 4.3 shows a distance vector algorithm in action. In this example, the metric is hop count. At time
t0, routers A through D have just become active. Looking at the route tables across the top row, at t0 the
only information any of the four routers has is its own directly connected networks. The tables identify
these networks and indicate that they are directly connected by having no next-hop router and by having a
hop count of 0. Each of the four routers will broadcast this information on all links.
Figure 4.3. Distance vector protocols converge hop-by-hop.
At time t1, the first updates have been received and processed by the routers. Look at router A's table at t1.
Router B's update to router A said that router B can reach networks 10.1.2.0 and 10.1.3.0, both 0 hops
away. If the networks are 0 hops from B, they must be 1 hop from A. Router A incremented the hop count by 1 and then examined its route table. It already knew about 10.1.2.0, and the hop count (0) was less than
the hop count B advertised, (1), so A disregarded that information.
Network 10.1.3.0 was new information, however, so A entered this in the route table. The source address
of the update packet was router B's interface (10.1.2.2) so that information is entered along with the
calculated hop count.
Notice that the other routers performed similar operations at the same time t1. Router C, for instance,
disregarded the information about 10.1.3.0 from B and 10.1.4.0 from C but entered information about
10.1.2.0, reachable via B's interface address 10.1.3.1, and 10.1.5.0, reachable via C's interface 10.1.4.2.
Both networks were calculated as 1 hop away.
At time t2, the update period has again expired and another set of updates has been broadcast. Router B
sent its latest table; router A again incremented B's advertised hop counts by 1 and compared. The
information about 10.1.2.0 is again discarded for the same reason as before. 10.1.3.0 is already known,
and the hop count hasn't changed, so that information is also discarded. 10.1.4.0 is new information and is
entered into the route table.
The network is converged at time t3. Every router knows about every network, the address of the next-hop
router for every network, and the distance in hops to every network.
Time for an analogy. You are wandering in the Sangre de Cristo mountains of northern New Mexico—a
wonderful place to wander if you aren't lost. But you are lost. You come upon a fork in the trail and a sign
pointing west, reading "Taos, 15 miles." You have no choice but to trust the sign. You have no clue what
the terrain is like over that 15 miles; you don't know whether there is a better route or even whether the
sign is correct. Someone could have turned it around, in which case you will travel deeper into the forest
instead of to safety!
Distance vector algorithms provide road signs to networks.[5] They provide the direction and the distance,
but no details about what lies along the route. And like the sign at the fork in the trail, they are vulnerable
to accidental or intentional misdirection. Following are some of the difficulties and refinements
associated with distance vector algorithms.
t0, routers A through D have just become active. Looking at the route tables across the top row, at t0 the
only information any of the four routers has is its own directly connected networks. The tables identify
these networks and indicate that they are directly connected by having no next-hop router and by having a
hop count of 0. Each of the four routers will broadcast this information on all links.
Figure 4.3. Distance vector protocols converge hop-by-hop.
At time t1, the first updates have been received and processed by the routers. Look at router A's table at t1.
Router B's update to router A said that router B can reach networks 10.1.2.0 and 10.1.3.0, both 0 hops
away. If the networks are 0 hops from B, they must be 1 hop from A. Router A incremented the hop count by 1 and then examined its route table. It already knew about 10.1.2.0, and the hop count (0) was less than
the hop count B advertised, (1), so A disregarded that information.
Network 10.1.3.0 was new information, however, so A entered this in the route table. The source address
of the update packet was router B's interface (10.1.2.2) so that information is entered along with the
calculated hop count.
Notice that the other routers performed similar operations at the same time t1. Router C, for instance,
disregarded the information about 10.1.3.0 from B and 10.1.4.0 from C but entered information about
10.1.2.0, reachable via B's interface address 10.1.3.1, and 10.1.5.0, reachable via C's interface 10.1.4.2.
Both networks were calculated as 1 hop away.
At time t2, the update period has again expired and another set of updates has been broadcast. Router B
sent its latest table; router A again incremented B's advertised hop counts by 1 and compared. The
information about 10.1.2.0 is again discarded for the same reason as before. 10.1.3.0 is already known,
and the hop count hasn't changed, so that information is also discarded. 10.1.4.0 is new information and is
entered into the route table.
The network is converged at time t3. Every router knows about every network, the address of the next-hop
router for every network, and the distance in hops to every network.
Time for an analogy. You are wandering in the Sangre de Cristo mountains of northern New Mexico—a
wonderful place to wander if you aren't lost. But you are lost. You come upon a fork in the trail and a sign
pointing west, reading "Taos, 15 miles." You have no choice but to trust the sign. You have no clue what
the terrain is like over that 15 miles; you don't know whether there is a better route or even whether the
sign is correct. Someone could have turned it around, in which case you will travel deeper into the forest
instead of to safety!
Distance vector algorithms provide road signs to networks.[5] They provide the direction and the distance,
but no details about what lies along the route. And like the sign at the fork in the trail, they are vulnerable
to accidental or intentional misdirection. Following are some of the difficulties and refinements
associated with distance vector algorithms.
Full Routing Table Updates
Most distance vector routing protocols take the very simple approach of telling their neighbors everything
they know by broadcasting their entire route table, with some exceptions that are covered in following
sections. Neighbors receiving these updates glean the information they need and discard everything else.
they know by broadcasting their entire route table, with some exceptions that are covered in following
sections. Neighbors receiving these updates glean the information they need and discard everything else.
Broadcast Updates
When a router first becomes active on a network, how does it find other routers and how does it announce
its own presence? Several methods are available. The simplest is to send the updates to the broadcast
address (in the case of IP, 255.255.255.255). Neighboring routers speaking the same routing protocol will
hear the broadcasts and take appropriate action. Hosts and other devices uninterested in the routing
updates will simply drop the packets.
its own presence? Several methods are available. The simplest is to send the updates to the broadcast
address (in the case of IP, 255.255.255.255). Neighboring routers speaking the same routing protocol will
hear the broadcasts and take appropriate action. Hosts and other devices uninterested in the routing
updates will simply drop the packets.
Neighbors
In the context of routers, neighbors always means routers sharing a common data link. A distance vector
routing protocol sends its updates to neighboring routers[4] and depends on them to pass the update
information along to their neighbors. For this reason, distance vector routing is said to use hop-by-hop
updates.
routing protocol sends its updates to neighboring routers[4] and depends on them to pass the update
information along to their neighbors. For this reason, distance vector routing is said to use hop-by-hop
updates.
Subscribe to:
Posts (Atom)