IP addressing is based on the concept of hosts and networks. A host is essentially anything on the network that is capable of receiving and transmitting IP packets on the network, such as a workstation or a router. Routing is a process of moving data from one host computer to another. The difference between routing and bridging is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (the network layer). Routing determines the optimal routing paths through a network.
Routing Algorithms
The routing algorithm is stored in the router's memory. The routing algorithm is a major factor in the performance of your routing environment. The purpose of the routing algorithm is to make decisions for the router concerning the best paths for data. The router uses the routing algorithm to compute the path that would best serve to transport the data from the source to the destination. Note that you do not directly choose the algorithm that your router uses. Rather, the routing protocol you choose for your network determines which algorithm you will use. For example, whereas the routing protocol Routing Information Protocol (RIP) may use one type of routing algorithm to help the router move data, the routing protocol Open Shortest Path First (OSPF) uses another. The routing algorithm cannot be changed. The only way to change it is to change routing protocols. The overall performance of your network depends mainly on the routing algorithm, so you should research the algorithms each protocol uses before deciding which to implement on your network. There are two major categories of routing algorithms - distance vector or link-state. Every routing protocol named "distance vector" uses the distance vector algorithm, and every link-state protocol uses the link-state algorithm.
Routing Algorithms within Routing Protocols
One of the jobs of the routing protocol is to provide the information needed by the routing algorithm to compute its decisions. This is the point where many protocols differ. The information provided to the algorithm can be different from protocol to protocol. The routing protocol gathers information about networks and routers from the surrounding environment and stores the information within a routing table in the router's memory. The routing algorithm is run using the information within this table to calculate the best path from one network to another. Calculating the new values within the formula then generates a sum. The result of this calculation is used then to determine where to send information. For example, the table below illustrates a sample routing table for a fictitious routing environment. The information that is passed to the routing algorithm within the routing table is gathered by the routing protocol through a process known as a routing update. Through a series of updates, each router will tell the other what information it has. Eventually, an entire routing table will be built.
| Router Link | Metric |
|---|---|
| Router A to Router B | 2 |
| Router B to Router C | 3 |
| Router A to Router C | 6 |
| Router C to Router D | 5 |
The sample routing algorithm states that the best path to any destination is the one that has the lowest metric value. A metric is a number that is used as a standard of measurement for the links of a network. Each link is assigned a metric to represent anything from monetary cost to use the line, to the amount of available bandwidth. When Router A is presented with a packet bound from Router C, the routing table shows two possible paths to choose from. The first choice is to send the packet from Router A directly over the link to Router C. The second option is to send the packet from Router A to Router B and then on to Router C. The routing algorithm is used to determine which option is best. Some routing protocols might only provide one metric to the routing algorithm, whereas others might provide up to ten. On the other hand, whereas two protocols might both send only one metric to the algorithm, the origin of that metric might differ from protocol to protocol. One routing protocol might give an algorithm the single metric of cost, but that cost could represent something different than another protocol using the same metric. The algorithm in our example states that the best path is the one with the lowest metric value. Therefore, by adding the metric numbers associated with each possible link, we see that the route from Router A to Router B to Router C has a metric value of 5, while the direct link to Router C has a value of 6. The algorithm selects the A-B-C path and sends the information along.
Distance Vector Algorithms
A distance vector algorithm uses metrics known as costs in order to help determine the best path to a destination. The path with the lowest total cost is chosen as the best path. When a router utilizes a distance vector algorithm, different costs are gathered by each router. These costs can be completely arbitrary numbers. Costs can also be dynamically gathered values, such as the amount of delay experienced by routers when sending packets over one link as opposed to another. All the costs are compiled and placed within the router's routing table and then they are used by the algorithm to calculate a best path for any given network scenario. Although there are many resources that will offer complex mathematical representations of what distance vector algorithms are and how they compute their decisions,the core concept remains the same - by adding the metrics for every optional path on a network, you will come up with at least one best path. The formula for this is as follows:
M(i,k) = min [M(i,t) + M(t,k)]
This formula states that the best path between two networks (M(i,k)) can be found by finding the lowest (min) value of paths between all network points. Let's look again at the routing information in the table above. Plugging this information into the formula, we see that the route from A to B to C is still the best path:
5(A,C) = min[2(A,B) + 3(B,C)]
Whereas the formula for the direct route A to C looks like this:
6(A,C) = min[6(A,C)]
This example shows how distance vector algorithms use the information passed to them to make informed routing decisions. The algorithms used by routers and routing protocols are not configurable,nor can they be modified. Another major difference between distance vector algorithms and link state protocols is that when distance vector routing protocols update each other, all or part of the routing table (depending on the type of update) is sent from one router to another. By this process, each router is exposed to the information contained within the other router's tables, thus giving each router a more complete view of the networking environment and enabling them to make better routing decisions. Examples of distance vector algorithms include RIP and BGP, two of the more popular protocols in use today. Other popular protocols such as OSPF are examples of protocols which use the link state routing algorithm. Distance vector algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. In these algorithms, each router has a routing table which shows it the best route for any destination. A typical graph and routing table for router J is shown below.
| Destination | Weight | Line |
|---|---|---|
| A | 8 | A |
| B | 20 | A |
| C | 20 | I |
| D | 20 | H |
| E | 17 | I |
| F | 30 | I |
| G | 18 | H |
| H | 12 | H |
| I | 10 | I |
| J | 0 | N/A |
| K | 6 | K |
| L | 15 | K |
The table shows that if router J wants to get packets to router D, it should send them to router H first. When the packets arrive at router H, the current router checks its own table and makes a decision how to send the packets to D. In distance vector algorithms, each router has to follow the following steps:
1. It counts the weight of the links directly connected to it and saves the information to its table.
2. In a particular period of time, the router sends its table to its neighbor routers (not to all routers) and receives the routing table of each of its neighbors.
3. Based on the information the router receives from its neighbors' routing tables, it updates its own.
Let's consider one more example (the figure represented below).
The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops. The table below represents each node knowledge about the distance to all other nodes:
| Information stored at node | Distance to reach node | ||||||
|---|---|---|---|---|---|---|---|
| A | B | C | D | E | F | G | |
| A | 0 | 1 | 1 |  | 1 | 1 | |
| B | 1 | 0 | 1 | | | | |
| C | 1 | 1 | 0 | 1 | | | |
| D | | | 1 | 0 | | | 1 |
| E | 1 | | | | 0 | | |
| F | 1 | | | | | 0 | 1 |
| G | | | | 1 | | 1 | 0 |
Initially, each node sets a cost of 1 to its directly connected neighbors and infinity to all the other nodes. Below is shown the initial routing table at node A:
| Destination | Cost | Next Hop |
|---|---|---|
| B | 1 | B |
| C | 1 | C |
| D | | - |
| E | 1 | E |
| F | 1 | F |
| G | | - |
During the next step, every node sends a message to its directly connected neighbors. That message contains the node's personal list of distances. Node F, for example, tells node A that it can reach node G at cost of 1; node A also knows that it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. Because 2 is less than the current cost of infinity, node A records that it can reach G at a cost of 2 by going trough F. Node A learns from C that node B can be reached from C at a cost of 1, so it concludes that the cost of reaching B via C is 2. Because this is worse than the current cost of reaching B, which is 1, the new information is ignored. The final routing table at node A is shown below:
| Destination | Cost | Next Hop |
|---|---|---|
| B | 1 | B |
| C | 1 | C |
| D | 2 | C |
| E | 1 | E |
| F | 1 | F |
| G | 2 | F |
The process of getting consistent routing information to all the nodes is called convergence. The final set of costs from each node to all other nodes is shown in the table below:
| Information stored at node | Distance to reach node | ||||||
|---|---|---|---|---|---|---|---|
| A | B | C | D | E | F | G | |
| A | 0 | 1 | 1 | 2 | 1 | 1 | 2 |
| B | 1 | 0 | 1 | 2 | 2 | 2 | 3 |
| C | 1 | 1 | 0 | 1 | 2 | 2 | 2 |
| D | 2 | 2 | 1 | 0 | 3 | 2 | 1 |
| E | 1 | 2 | 2 | 3 | 0 | 2 | 3 |
| F | 1 | 2 | 2 | 2 | 2 | 0 | 1 |
| G | 2 | 3 | 2 | 1 | 3 | 1 | 0 |
The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops.
One of the problems with distance vector algorithms is called "count to infinity." Let's examine the following problem with an example:
Consider a network with a graph as shown below. There is only one link between D and the other parts of the network.
with vectors
d [A][A] = 0 d [A][B] = 1 d [A][C] = 2 d [A][D] = 3
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 2 | 3 |
| B | 1 | 0 | 1 | 2 |
| C | 2 | 1 | 0 | 1 |
| D | 3 | 2 | 1 | 0 |
Now the C to D link crashes So cost [C][D] = ∞ C used to forward any packets with address D directly on the CD link, but now link is down, so C has to recompute its distance vector (and make a new choice of how to forward packets to D) - similarly D has to update its vector. After updating their vectors at C and D, we have
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 2 | 3 |
| B | 1 | 0 | 1 | 2 |
| C | 2 | 1 | 0 | 3 |
| D | | | | 0 |
C views B as the best route to D, with cost 1 + 2, so C sends new vector to B. B learns that its former choice for sending to D via C now has higher cost, so B should recompute its vector.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 2 | 3 |
| B | 1 | 0 | 1 | 4 |
| C | 2 | 1 | 0 | 3 |
| D | | | | 0 |
View of B is that routing to D can either go via A or C with equal cost - B sends updated vector. Both A and C get updated vector from B and learn that their preferred route to D now has higher cost, so they recompute their own vectors.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 2 | 5 |
| B | 1 | 0 | 1 | 4 |
| C | 2 | 1 | 0 | 5 |
| D | | | | 0 |
Then A and C send their vectors, B has to update its vector again, sending another round to A and C, obtaining.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 2 | 7 |
| B | 1 | 0 | 1 | 6 |
| C | 2 | 1 | 0 | 7 |
| D | | | | 0 |
Notice that the routing table is very slowly converging to the fact that
d [x][D] = ∞ for x = A or x = B or x = C
This process loops until all nodes find out that the weight of link to D is infinity. In this way, experts say that distance vector algorithms have a slow convergence rate. In conclusion, distance vector algorithm is not robust. One way to solve this problem is for routers to send information only to the neighbors that are not exclusive links to the destination. For example, in this case, B should not send any information to C about D, because C is the only way to D.
No comments:
Post a Comment