UNICAST ROUTING PROTOCOLS

unicast routing protocols
a routing table can be either static or dynamic. a static table is one with manual entries. a dynamic table, on the other hand, is one that is updatingd automatically when there is a change somewhere in the internet. today, an internet needs dynamic routing tables. the tables need to be updatingd as soon as there is a change in the internet. for instance, they need to be updatingd when a router is down, and they need to be updatingd whenever a better route has been found.
routing protocols have been created in response to the demand for dynamic routing tables. a routing protocol is a combination of rules and procedures that lets routers in the internet inform each other of changes. it allows routers to share whatever they know about the internet or their neighborhood. the sharing of information allows a router in san francisco to know about the failure of a network in texas. the routing protocols also include procedures for combining information received from other routers.

optimization
a router receives a packet from a network and passes it to another network. a router is usually attached to several networks. when it receives a packet, to which network should it pass the packet? the decision is based on optimization: which of the available pathways is the optimum pathway? what is the definition of the term optimum? one approach is to assign a cost for passing through a network. we call this cost a metric. however, the metric assigned to each network depends on the type of protocol. some simple protocols, such as the routing information protocol (rip), treat all networks as equals. the cost of passing through a network is the same it is one hop count. so if a packet passes through 10 networks to reach the destination, the total cost is 10 hop counts. other protocols, such as open shortest path first (ospf), allow the administrator to assign a cost for passing through a network based on the type of service required. a route through a network can have different costs (metrics). for example, if maximum throughput is the desired type of service, a satellite link has a lower metric than a fiber-optic line. on the other hand, if minimum delay is the desired type of service, a fiber-optic line has a lower metric than a satellite link. routers use routing tables to help decide the best route. ospf protocol allows each router to have several routing tables based on the required type of service. other protocols define the metric in a totally different way. in the border gateway protocol (bgp), the criterion is the policy, which can be set by the administrator. the policy defines what paths should be chosen.


intra- and interdomain routing
today, an internet can be so large that one routing protocol cannot handle the task of updating the routing tables of all routers. for this reason, an internet is divided into autonomous systems. an autonomous system (as) is a group of networks and routers under the authority of a single administration. routing inside an autonomous system is referred to as intradomain routing. routing between autonomous systems is referred to as interdomain routing. each autonomous system can choose one or more intradomain routing protocols to handle routing inside the autonomous system. however, only one interdomain routing protocol handles routing between autonomous systems (see figure below).

several intradomain and interdomain routing protocols are in use. in this section, we cover only the most popular ones. two intradomain routing protocols: distance vector and link state. one interdomain routing protocol: path vector (see figure below).


routing information protocol (rip) is an implementation of the distance vector protocol. open shortest path first (ospf) is an implementation of the link state protocol. border gateway protocol (bgp) is an implementation of the path vector protocol.

shortest path algorithm
a simple technique for computing optimal paths given a complete picture of the network. these paths are the ones that we want a distributed routing algorithm to find, even though not all routers may know all of the details of the network.
the idea is to build a graph of the network, with each node of the graph representing a router and each edge of the graph representing a communication line, or link. to choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph.
the concept of a shortest path deserves some explanation. one way of measuring path length is the number of hops. using this metric, the paths abc and abe in figure below are equally long. another metric is the geographic distance in kilometers, in which case abc is clearly much longer than abe.

the first five steps used in computing the shortest path from a to d. the arrows indicate the working node.
however, many other metrics besides hops and physical distance are also possible. for example, each edge could be labeled with the mean delay of a standard test packet, as measured by hourly runs. with this graph labeling, the shortest path is the fastest path rather than the path with the fewest edges or kilometers.
in the general case, the labels on the edges could be computed as a function of the distance, bandwidth, average traffic, communication cost, measured delay, and other factors. by changing the weighting function, the algorithm would then compute the ‘‘shortest’’ path measured according to any one of a number of criteria or to a combination of criteria.
to find the shortest paths between a source and all destinations in the network. each node is labeled (in parentheses) with its distance from the source node along the best known path. the distances must be non-negative, as they will be if they are based on real quantities like bandwidth and delay. initially, no paths are known, so all nodes are labeled with infinity. as the algorithm proceeds and paths are found, the labels may change, reflecting better paths. a label may be either tentative or permanent. initially, all labels are tentative. when it is discovered that a label represents the shortest possible path from the source to that node, it is made permanent and never changed thereafter.
to illustrate how the labeling algorithm works, look at the weighted, undirected graph of figure above (a), where the weights represent, for example, distance. we want to find the shortest path from a to d. we start out by marking node a as permanent, indicated by a filled-in circle. then we examine, in turn, each of the nodes adjacent to a (the working node), relabeling each one with the distance to a. whenever a node is relabeled, we also label it with the node from which the probe was made so that we can reconstruct the final path later. if the network had more than one shortest path from a to d and we wanted to find all of them, we would need to remember all of the probe nodes that could reach a node with the same distance.
having examined each of the nodes adjacent to a, we examine all the tentatively labeled nodes in the whole graph and make the one with the smallest label permanent, as shown in figure above (b). this one becomes the new working node. we now start at b and examine all nodes adjacent to it. if the sum of the label on b and the distance from b to the node being considered is less than the label on that node, we have a shorter path, so the node is relabeled.
after all the nodes adjacent to the working node have been inspected and the tentative labels changed if possible, the entire graph is searched for the tentatively labeled node with the smallest value. this node is made permanent and becomes the working node for the next round. figure above shows the first six steps of the algorithm.
to see why the algorithm works, look at figure above (c). at this point we have just made e permanent. suppose that there were a shorter path than abe, say axyze (for some x and y). there are two possibilities: either node z has already been made permanent, or it has not been. if it has, then e has already been probed (on the round following the one when z was made permanent), so the axyze path has not escaped our attention and thus cannot be a shorter path.
now consider the case where z is still tentatively labeled. if the label at z is greater than or equal to that at e, then axyze cannot be a shorter path than abe. if the label is less than that of e, then z and not e will become permanent first, allowing e to be probed from z.
this algorithm is given in figure above. the global variables n and dist describe the graph and are initialized before shortest path is called. the only difference between the program and the algorithm described above is that in figure above, we compute the shortest path starting at the terminal node, t, rather than at the source node, s.
since the shortest paths from t to s in an undirected graph are the same as the shortest paths from s to t, it does not matter at which end we begin. the reason for searching backward is that each node is labeled with its predecessor rather than its successor. when the final path is copied into the output variable, path, the path is thus reversed. the two reversal effects cancel, and the answer is produced in the correct order.