'Distance Vector'에 해당되는 글 1건
- 2006/07/15 Distance Vector vs. Link-State
- Distance Vector vs. Link-State
- CS&E/Network
- 2006/07/15 14:26
- Distance Vector, Link State, Routing Protocol
Examples of distance-vector routing protocols include RIPv1 or 2 and IGRP.
Working
The distance-vector routing protocol assumes a network connected through several routers, each of which is connected to two or more computer networks. Each network may be connected to one or more routers.
The description below describes a very simple distance-vector routing protocol:
- In the first stages, the router makes a list of which networks it can reach, and the cost to reach them (cost is protocol dependent, in RIP case, the cost is measured by number hops). In the outset this will be the two or more networks to which this router is connected. The number of hops for these networks will be 1. This table is called a routing table.
- Periodically (typically every 30 seconds) the routing table is shared with other routers on each of the connected networks via some specified inter-router protocol. These routers will add 1 to every hop-count in the table, as it associates a hop cost of 1 for reaching the router that sent the table. This information is just shared inbetween physically connected routers ("neighbors"), so routers on other networks are not reached by the new routing tables yet.
- A new routing table is constructed based on the directly configured network interfaces, as before, with the addition of the new information received from other routers. The hop-count is used as a cost measure for each path. The table also contains a column stating which router offered this hop count, so that the router knows who is next in line for reaching a certain network.
- Bad routing paths are then purged from the new routing table. If two identical paths to the same network exist, only the one with the smallest hop-count is kept. When the new table has been cleaned up, it may be used to replace the existing routing table used for packet forwarding.
- The new routing table is then communicated to all neighbors of this router. This way the routing information will spread and eventually all routers know the routing path to each network, which router it shall use to reach this network, and to which router it shall route next.
Advantage and Disadvantage
Distance-vector routing protocols are simple and efficient in small networks, and require little, if any management. However, they do not scale well, and have poor convergence properties, which has led to the development of more complex but more scalable link-state routing protocols for use in large networks. They suffer from the "Count to Infinity problem".
Link State Routing Protocol
The link-state protocol is performed by every switching node in the network (i.e. nodes which are prepared to forward packets; in the Internet, these are called routers). The basic concept of link-state routing is that every node receives a map of the connectivity of the network, in the form of a graph showing which nodes are connected to which other nodes.
Each node then independently calculates the best next hop from it for every possible destination in the network. (It does this using only its local copy of the map, and without communicating in any other way with any other node.) The collection of best next hops forms the routing table for the node.
This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors. In a link-state protocol, the only information passed between the nodes is information used to construct the connectivity maps.
Detailed Description : Distributing maps
This description covers only the simplest configuration; i.e. one with no areas, so that all nodes do have a map of the entire network. The hierarchical case is somewhat more complex; see the various protocol specifications.
As previously mentioned, the first main stage in the link-state algorithm is to give a map of the network to every node. This is done with several simple subsidiary steps.
Determining the neighbours of each node
First, each node needs to determine what other nodes it is connected to, over fully-working links; it does this using a simple reachability protocol which it runs separately with each of its directly-connected neighbours.
Distributing the information for the map
Next, each node periodically makes up a short message, the link-state advertisement, which:
Identifies the node which is producing it.
Identifies all the other nodes to which it is directly connected.
Includes a sequence number, which increases every time the source node makes up a new version of the message.
This message is then flooded throughout the network. As a necessary precursor, each node in the network remembers, for every other node in the network, the sequence number of the last link-state message which it received from that node. With that in hand, the method used is simple.
Starting with the node which originally produced the message, it sends a copy to all of its neighbours. When a link-state advertisement is received at a node, the node looks up the sequence number it has stored for the source of that link-state message. If this message is newer (i.e. has a higher sequence number), it is saved, and a copy is sent in turn to each of that node's neighbours.
This procedure rapidly gets a copy of the latest version of each node's link-state advertisement to every node in the network.
Creating the map
Finally, with the complete set of link-state advertisements (one from each node in the network) in hand, it is obviously easy to produce the graph for the map of the network.
The algorithm simply iterates over the collection of link-state advertisements; for each one, it makes links on the map of the network, from the node which sent that message, to all the nodes which that message indicates are neighbours of the sending node.
No link is considered to have been correctly reported unless the two ends agree; i.e. if one node reports that it is connected to another, but the other node does not report that it is connected to the first, there is a problem, and the link is not included on the map.
Notes about this stage
The link-state message giving information about the neighbours is recomputed, and then flooded throughout the network, whenever there is a change in the connectivity between the node and its neighbours, e.g. when a link fails. Any such change will be detected by the reachability protocol which each node runs with its neighbours.
Detailed description: Calculating the routing table
As initially mentioned, the second main stage in the link-state algorithm is to produce routing tables, by inspecting the maps. This is again done with several steps.
Calculating the shortest paths
Each node independently runs an algorithm over the map to determine the shortest path from themselves to every other node in the network; generally some variant of Dijkstra's algorithm is used.
Basically, a node maintains two data structures: a tree containing nodes which are "done", and a list of candidates. The algorithm starts with both structures empty; it then adds to the first one the node itself. The algorithm then repetitively:
Adds to the second (candidate) list all nodes which are connected to the node just added to the tree (excepting of course any nodes which are already in either the tree or the candidate list).
Of the nodes in the candidate list, moves to the tree (attaching it to the appropriate neighbour node already there) the one which is the closest to any of the nodes already in the tree.
Repeat as long as there are any nodes left in the candidate list. (When there are none, all the nodes in the network will have been added to the tree.)
This procedure ends with the tree containing all the nodes in the network, with the node on which the algorithm is running as the root of the tree. The shortest path from that node to any other node is indicated by the list of nodes one traverses to get from the root of the tree, to the desired node in the tree.
Filling the routing table
With the shortest paths in hand, filling in the routing table is again obviously easy.
For any given destination node, the best next hop for that destination is the node which is the first step from the root node, down the branch in the shortest-path tree which leads toward the desired destination node.
To create the routing table, it is only necessary to walk the tree, remembering the identity of the node at the head of each branch, and filling in the routing table entry for each node one comes across with that identity.
Optimizations to the algorithm
The algorithm described above was made as simple as possible, to aid in ease of understanding. In practise, there are a number of optimizations which are used.
Most importantly, whenever a change in the connectivity map happens, it is necessary to recompute the shortest-path tree, and then recreate the routing table. The BBN work discovered how to recompute only that part of the tree which could have been affected by a given change in the map.
Also, the routing table would normally be filled in as the shortest-path tree is computed, instead of making it a separate operation.
Recent comment