Details of routing algorithms Essay Example for Free

Details of routing algorithms Essay In a link state algorithm, every router in the network is notified of a topology change at the same time. This avoids some of the problems associated with the nearest neighbour update propagation that occurs in the distance vector algorithms. The ‘Open Shortest Path First’ (OSPF) protocol uses a graph topology algorithm like Dijkstra’s Algorithm to determine the best path for data transmission between a given data source and a data destination. The metric used for route optimisation is specific to the manual configuration of the router. However, the default metric is the speed of the interface. The OSPF uses a two level, hierarchical network classification. The lower level of hierarchy is groups of routers called areas. All the routers in an area have full knowledge of all the other routers in the area, but reduced knowledge of routers in a different area. The different areas organized within the OSPF algorithm are connected by border routers, which have full knowledge of multiple areas. The upper level of the hierarchy is the backbone network, to which all areas must be connected. That is, all data traffic going from one area to another must pass through the backbone routers. Distance Vector Algorithms In order for data to be transmitted from a source to a destination on the Internet, the destination must be identified using some mechanism. That is, each possible destination for data transmission must be described with an address. The scheme currently used to address the internet space is the Internet Protocol (IP) version 4. The IP version 4 uses an address length limited by 32 bits. An example of an Internet address is 227. 130. 107. 5 with the corresponding bit vector 11100011 10000010 01101011 00000101. An initial difficulty in managing the available address space was the implementation of a class structure, where large blocks of internet address space was reserved for organisations such as universities, leaving commercial applications with limited address space. Routing of data transmission in this address environment was referred to as class-full routing. To alleviate this problem of limited address space, the internet community has slowly evolved to a classless structure, with classless routing. In distance vector protocols, each router sends adjacent routers information about known paths to specific addresses. The neighbouring routers are sent information giving a distance metric of each one from a destination address. The distance metric could be the number of routers which must be used to reach the destination address, known as the ‘hop count’, or it could be the actual transmission distance in the network. Although this information is advertised only to the adjacent routers, these routers will then communicate the information with their neighbouring routers, and so on, until the entire network has the same information. This information is then used to build the routing table which associates the distance metric with a destination address. The distance vector protocol is implemented when a router receives a packet, notes the destination, determines the path with the shortest distance to the destination and then forwards the packet to the next router along the shortest distance path. One of the first distance vector protocols implemented on the Internet was the Routing Information Protocol (RIP). RIP uses the distance metric of hop count to determine the shortest distance to the destination address. It also implements several protocols to avoid having data packets pass through the same router more than once (router loops). The path vector protocol is a distance vector protocol that includes information on the routes over which the routing updates have been transmitted. It is this information on path structure which is used to avoid routing loops. Path Vector Protocols are also somewhat more sophisticated than RIP because an attempt is made to ‘weight’ each path based on a locally defined criteria that may not simply reflect the highest quality of service, but rather the highest profit for an ISP. The implementation of these types of router algorithms may be different in different parts of the Internet. When the algorithms are implemented inside an autonomous system, they are called Interior Gateway Protocols (IGP). Because the different autonomous systems that make up the Internet are independent from one another, the type of routing algorithm used within the autonomous systems can also be independent of one another. That is, the managers of each autonomous system are free to choose the type of algorithm which best suits their particular network, whether it is static or dynamic link-state or dynamic distance-vector. When the algorithms are implemented to control data transmission between autonomous systems, they are referred to as Exterior Gateway Protocols (EGP). The EGP connect all autonomous systems together to form the Internet and thus all EGP should use the same algorithm. The specific algorithm currently used as the EGP on the Internet is the Border Gateway Protocol (BGP), which is a type of distance vector algorithm called a path vector algorithm [9]. A path vector algorithm uses information about the final destination of the data transmission in addition to the attributes of the neighbouring links. It should be noted that the BGP algorithm can also be used as a router protocol within an autonomous system and is called an interior BGP (IBGP) in that instance. This necessitates calling the BGP an EBGP when it is implemented as an EGP.