Chapter 12 Routing Architecture: Cores, Peers and Algorithms
Routing protocols serve two important functions. First, they compute a set of shortest paths. Second, they respond to network failures or topology changes by continually updating the routing information.
Although a routing protocol computes shortest paths, the routing protocol software does not store information directly in the router’s forwarding table. Instead, routing software creates aForwarding Information Base(FIB).
When the FIB changes, routing software recomputes a forwarding table for the
router and installs the new forwarding table.
12.3 Distance-Vector (Bellman-Ford) Routing
Each router keeps a list of all known destinations in its FIB. When it boots, a router initializes its FIB to contain an entry for each directly connected network. Each entry in the FIB identifies a destination network, a next-hop router used to reach the destination, and the “distance” to the network (according to some measure of distance).
A directly-connected network is zero hops away; if a datagram must travel through N
routers to reach a destination, the destination is N hops away.
When routes change rapidly, however, the computations may not stabilize. When a route changes (i.e, a new connection appears or an old one fails), the information propagates slowly
from one router to another. Meanwhile, some routers may have incorrect routing information.
12.4 Reliability and Routing Protocols
Most routing protocols use connectionless transport — early protocols encapsulated messages directly in IP; modern routing protocols usually encapsulate in UDP.
Routing protocols use several techniques to handle reliability. First, checksums are used to handle corruption. Loss is either handled bysoft state‡ or through acknowledgements and retransmission. Sequence numbersare used to handle two problems.
First, sequence numbers allow a receiver to handle out-of-order delivery by placing incoming messages back in the correct order. Second, sequence numbers can be used to handle replay, a condition that can occur if a duplicate of a message is delayed and arrives long after newer updates have been processed.
12.1 Original Internet architecture and Cores
The advantage of a core routing architecture lies in autonomy: the manager of a noncore router can make changes locally. The chief disadvantage is inconsistency: an outlying site can introduce errors that make some destinations unreachable.
12.2 Automatic Route Propagation and a FIBThe advantage of a core routing architecture lies in autonomy: the manager of a noncore router can make changes locally. The chief disadvantage is inconsistency: an outlying site can introduce errors that make some destinations unreachable.
Routing protocols serve two important functions. First, they compute a set of shortest paths. Second, they respond to network failures or topology changes by continually updating the routing information.
Although a routing protocol computes shortest paths, the routing protocol software does not store information directly in the router’s forwarding table. Instead, routing software creates aForwarding Information Base(FIB).
When the FIB changes, routing software recomputes a forwarding table for the
router and installs the new forwarding table.
12.3 Distance-Vector (Bellman-Ford) Routing
Each router keeps a list of all known destinations in its FIB. When it boots, a router initializes its FIB to contain an entry for each directly connected network. Each entry in the FIB identifies a destination network, a next-hop router used to reach the destination, and the “distance” to the network (according to some measure of distance).
A directly-connected network is zero hops away; if a datagram must travel through N
routers to reach a destination, the destination is N hops away.
When routes change rapidly, however, the computations may not stabilize. When a route changes (i.e, a new connection appears or an old one fails), the information propagates slowly
from one router to another. Meanwhile, some routers may have incorrect routing information.
12.4 Reliability and Routing Protocols
Most routing protocols use connectionless transport — early protocols encapsulated messages directly in IP; modern routing protocols usually encapsulate in UDP.
Routing protocols use several techniques to handle reliability. First, checksums are used to handle corruption. Loss is either handled bysoft state‡ or through acknowledgements and retransmission. Sequence numbersare used to handle two problems.
First, sequence numbers allow a receiver to handle out-of-order delivery by placing incoming messages back in the correct order. Second, sequence numbers can be used to handle replay, a condition that can occur if a duplicate of a message is delayed and arrives long after newer updates have been processed.
12.5 Link-State (SPF) Routing
The primary alternative to distance-vector algorithms is a class of algorithms known aslink state, link status,orShortest Path First†(SPF). The SPF algorithm requires each participating router to compute topology information.
Each router participating in an SPF algorithm performs two tasks:
* Actively test the status of each neighboring router.
Two routers are considered neighbors if they attach to a common network.
* Periodically broadcast link-state messages of the form, “The link between me and router X is up” or “The link between me and router X is down.”
To inform all other routers, each router periodically broadcasts a message that lists the status (state) of each of its links. A status message does not specify routes — it simply
reports whether communication is possible between pairs of routers.
Whenever a link-state message arrives, software running on the router uses the information to update its map of the internet. First, it extracts the pair of routers mentioned in the message and makes sure that the local graph contains an edge between the two. Second, it uses the status reported in the message to mark the link as up or down.
The primary alternative to distance-vector algorithms is a class of algorithms known aslink state, link status,orShortest Path First†(SPF). The SPF algorithm requires each participating router to compute topology information.
Each router participating in an SPF algorithm performs two tasks:
* Actively test the status of each neighboring router.
Two routers are considered neighbors if they attach to a common network.
* Periodically broadcast link-state messages of the form, “The link between me and router X is up” or “The link between me and router X is down.”
To inform all other routers, each router periodically broadcasts a message that lists the status (state) of each of its links. A status message does not specify routes — it simply
reports whether communication is possible between pairs of routers.
Whenever a link-state message arrives, software running on the router uses the information to update its map of the internet. First, it extracts the pair of routers mentioned in the message and makes sure that the local graph contains an edge between the two. Second, it uses the status reported in the message to mark the link as up or down.
No comments:
Post a Comment