Many routing strategies rely on mechanisms for sharing and announcing their routes among routing nodes. Traditional routing algorithms may be classified as Distance Vector and Link State under this angle.
Distance Vector algorithms are characterized by the fact that each network node announces the content of its routing table, known as a vector in this context, to "only" its neighbors. Although such limited scope announcement saves networking resources, it is also the root for some known route convergence latency related problems suffered by large networks. Each vector entry contains local information on some node k and how this may be reached in terms of number of hops and delay for example. Each neighbor for node k receives its advertisement (routing vector or information from node k) to build a routing database with size m.metric′, where m is the number of routers known by node k and metricis a number of metrics announced about each node. So, the traffic size generated by each node is given by formula (6) in order for a network node to get to know the network's topology. Once, a node acquires this knowledge through these advertisements, each node locally calculates the importance of each other node in the network according to its own vector and those received vector from the neighbors. Hence there is a combination of both local and external information to perform shortest paths selection. The result of such regular calculus updates the routing table based on algorithms such as Bellman-Ford and Ford-Fulkerson.
Given that the advertisement is relayed from neighbor to neighbor until all network nodes acquire network topology and path information, the protocols classified as Distance Vector suffer from slow convergence. The following protocols are example of Distance Vector: the Routing Internet Protocol (RIP) executed in intra-domain, Border Gateway Protocol (BGP) executed in inter-domain, DVMRP (Distance Vector Multicast Routing Protocol) for multicast applications, AODV (Ad-hoc On-demand Distance Vector) for mobile ad hoc networks (MANETs) and DSDV (Destination-Sequence Distance-Vector) also for MANETs.
link-state algorithms are different from distance vector ones in terms of the scope of their announcements. Unlike the former one where each node notifies the neighbors only about its vector, link-state routing floods such announcement to all the network nodes. Further, link-state updates are conveyed over small messages to all nodes. Each message contains the link-state of its neighbor's node such as occupied bandwidth, throughput, delay and so forth. A network node then builds a routing database with size m.n.metric where m is the number of neighbor nodes, n is the number of routers in the network and m etric the number of metrics announced for each node. As a result, the traffic size generated by each node is given by formula (7) in order for network node to build its database and get to know the current topology. With this knowledge at hand, each node locally then calculates the importance of each neighbor to forward messages over the shortest paths determined for each destination. This may be achieved usually using Dijkstra's algorithm, although there are others as described in. The most common and widespread link state protocols used are the OSPF (Open Shortest Path Frist) and IS-IS. Similarly, Multicast OSPF (MOSPF) has been developed to lead with multicast transmission. Other link state protocols include SPF
No comments:
Post a Comment