| :: [Networking] Brief explanation of Routing algorithms. :: | ||||
| HOME |
|
Here are brief explanations
of some important routing algorithms. All the routing algorithms can also be
categorised in to
(1) Distance Vector
Routing Protocol: In this each router maintains a Distance Vector to
every other router in its network. This vector contains, among other things, the
cost of reaching the destination router and the next hop to forward to.
Each router starts by exchanging a distance vector to its neighbors and
eventually ends of exchanging a distance vector to all routers in its domain.
Obviously, this routing protocol is preferred for small network
sizes.
(2) Link State routing
protocols: In this each router creates a link state packets containing
cost to eact of its neighbours and floods this packet to all routers in the
network. Such flooding allows each router to construct a topology, and determine
using Shortest path Graph algorithms to determine the shortest path.
Static
routing:
Routing tables are manually configured
possible through a management system.
RIP (Routing
Information Protocol) [RFC2453]
This is an example of Distance Vector
Routing protocol. RIP is an interior gateway protocol and is used within an
autonomous system. It sends out routing updates at regular intervals and
whenever the network topology changes. Routing information is then
propagated by the adjacent routers to their neighbors and thus to the entire
network. A route from a source to a destination is the path with the least
number of routers. This number is called the "hop count" and its maximum
value is 15. This implies that RIP is suitable for a small- or
medium-sized networks.
OSPF (Open Shortest
Path First) [RFC2328]
This is an example of Link State Routing protocol. OSPF is an interior gateway protocol and is applied to a single autonomous system. Each router distributes the state of its interfaces and neighboring routers as a link state advertisement, and maintains a database describing the autonomous system's topology. A link state is advertised every 30 minutes or when the topology is reconfigured. Each router maintains an identical topological database, from which it constructs a tree of shortest paths with itself as the root. The algorithm is known as the Shortest Path First or SPF. The router generates a routing table from the tree of shortest paths. OSPF supports a variable length subnet mask, which enables effective use of the IP address space. OSPF allows sets of networks to be grouped together into an area. Each area has its own topological database. The topology of the area is invisible from outside its area. The areas are interconnected via a "backbone" network. The backbone network distributes routing information between the areas. The area routing scheme can reduce the routing traffic and compute the shortest path trees and is indispensable for larger scale networks. Each multi-access network with multiple routers attached has a designated router. The designated router generates a link state advertisement for the multi-access network and synchronizes the topological database with other adjacent routers in the area. The concept of designated router can thus reduce the routing traffic and compute shortest path trees. To achieve high availability, a backup designated router is used. IS-IS (intermediate system to intermediate system) [RFC1195] This is an example of Link State Routing protocol. IS-IS is a routing protocol designed for the OSI (Open Systems Interconnection) protocol suites. Integrated IS-IS is derived from IS-IS in order to support the IP protocol. In the Internet community, IS-IS means integrated IS-IS. In this, a link state is advertised over a connectionless network service. IS-IS has the same basic features as OSPF. They include: link state advertisement and maintenance of a topological database within an area, calculation of a tree of shortest paths, generation of a routing table from a tree of shortest paths, the area routing scheme, a designated router, and a variable length subnet mask. BGP-4 (Border Gateway
Protocol version 4) [RFC1771]
This is an example of Distance Vector Routing protocol. BGP-4 is an exterior gateway protocol and is applied to the routing of inter-autonomous systems. A BGP speaker establishes a session with other BGP speakers and advertises routing information to them. A session may be an External BGP (EBGP) that connects two BGP speakers within different autonomous systems, or an internal BGP (IBGP) that connects two BGP speakers within a single autonomous system. Routing information is qualified with path attributes, which differentiate routes for the purpose of selecting an appropriate one from possible routes. Also, routes are grouped by the community attribute. The IBGP mesh size tends to increase dramatically with the number of BGP speakers in an autonomous system. BGP can reduce the number of IBGP sessions by dividing the autonomous system into smaller autonomous systems and grouping them into a single confederation [RFC1965]. Route reflection is another way to reduce the number of IBGP sessions [RFC1966]. BGP divides the autonomous system into clusters. Each cluster establishes the IBGP full mesh within itself, and designates one or more BGP speakers as "route reflectors," which communicate with other clusters via their route reflectors. Route reflectors in each cluster maintain path and attribute information across the autonomous system. The autonomous system still functions like a fully meshed autonomous system. On the other hand, confederations provide finer control of routing within the autonomous system by allowing for policy changes across confederation boundaries, while route reflection requires the use of identical policies. BGP-4 has been extended to support IPv6, IPX, and others as well as IPv4 [RFC2858]. Multiprotocol BGP-4 carries routes from multiple "address families." |