WIXLIB

Literature Review:Y. Rekhter, T. Li, S. Hares, “A Border Gateway Protocol 4 (BGP – 4)”, January 2006https://tools.ietf.org/html/rfc4271This document gives a clear idea about Border Gateway Protocol (BGP). It discusses about theAutonomous Systems (ASes) and how the communication is happening between them usingBGP. The route advertisement mechanism and the message format is clearly explained here. Thelocal Routing Information Base (RIB) consists of all the possible routes but only one route isadvertised among all the peers in the network. This best route is selected by the BGP by usingpath Attributes.It discussed about the Error handling capability of the protocol and also about the collisiondetection. It also tells us about the route origination and the route replacement in the case ofroute failure. This document is the base for my topic as my paper discusses about the BGPenhancements.As per my view this paper gives a clear introduction about the BGP protocol and how the bestpath is selected to propagate the information in the network.D. Walton, A. Retana, E. Chen and J. Scudder, “Advertisement of Multiple Paths in BGP”,Network Working Group, Internet Draft, May 23, 2016 (Work in progress).This draft mainly focuses on the extension to the existing BGP protocol. In traditional BGP onlysingle best path is advertised but this extension allows multiple paths to be advertised for thesame destination prefix without replacing the previous ones. Each path in the list is identified bya new attribute called ‘Path Identifier’ which is added to the address prefix. Previously when anew advertisement for the same destination prefix is made then it is replaced with the previousone. There were no provisions to allow multiple path advertisement for the same address prefix.Each path is uniquely identified by the address prefix and the path identifier. This draft isrelevant to my topic as it discusses about the enhancements to the existing BGP protocol.In my view this draft clearly explains about the advertisement of multiple paths to the sameaddress prefix, which was not possible before. This might open up new doors in the advancementof Internet world.11

P. Brighten Godfrey, Mathew Caesar, Ian Haken, Yaron Singer, Scott Shenker and Ian Stoica,“Stabilizing Route Selection in BGP”, IEEE/ACM Transactions on Networking, VOL. 23, NO.1, February 2015This paper mainly discussed about the problems in route stability and the trade-offs that occur bymodifying the route selection. It also explains about the existing route stability mechanism, RFD(Route Flap Damping) which filters the short-term update routes above some threshold. But thismechanism arises two main problems, slow convergence and degradation of availability. Hencethere has been proposed a new approach called SRS (Stable Route Selection). This approachimproves the stability by using the flexibility in route selection without sacrificing theavailability and also controls the amount of deviation.The main goal of this paper is to work on improving the BGP’s decision process in routeselection. It mainly discusses about Stabilizing and route availability of the BGP. This paper alsodiscusses about the points which are feasible for the tradeoff spaces which are novel routeselection categories and provable lower bounds. There are a lot of simulations that have beenconducted on the BGP route selection by using SRS. The results show that this new selectionprocess improves a significant control-place overhead and reliability in the data-plane with onlyconsiderable amount of deviation from the preferred routes. This paper is relevant to my topic asit mainly focuses on the route selection methods and the approach to improve the availability ofthe routes.As per my view, this paper heavily focused on the tradeoffs that appear during route switchingand the mechanism to overcome the instability.Aleksandra Cvjetic and Aleksandra Smiljanic, “Improving BGP Protocol to Advertise MultipleRoutes for the Same Destination Prefix”, IEEE Communications Letters, VOL. 18, NO. 1,January 2014.This paper mainly discusses about the enhancement in the route selection of the BGP. It clearlyexplains about the present problems with the routing system and path selection in BGP. A newroute selection algorithm called BGP-FRP (BGP with Flexible Routing Policies) was putforward. The BGP-FRP advertises the multiple routes present for a destination prefix, so that theimplementation of BGP policies can be done simultaneously.The BGP-FRP algorithm was implemented in XORP open-source router, in which previouslyonly one route was advertised. In case of change in network topology, it is better to havemultiple alternate routes stored in the routers as the routing gets adjusted much faster. A LinuxOperating System is used to deploy a virtual network with XORP routers and there are somesimulations. After implementing the algorithm, the reliability of the routing is improved as therouter stores multiple routes for the given destination.12

In my view, this paper explains about how multiple routes are advertised in the network androute selection changes immediately if there is any failure in the present route.L L Ragha, K V Ghag, “Multiple Route Selector BGP (MSR-BGP)”, ICWET’10, February 26–27, 2010, Mumbai, Maharashtra, India.This paper mainly discusses about the protocol which is an extension to BGP, which is MRSBGP (Multi Route Selector Border Gateway Protocol). This paper clearly explains about therouting system in the BGP. Even though there are many routes present between origin anddestination prefix, the BGP selects only one best route and advertises it to the other ASes(Autonomous Systems). Hence if there is any failure in the route, the BGP looks to construct anew route. Due to this there are two disadvantages, Network bandwidth underutilization and lowresistance to link failure.This paper clearly explains how to overcome these disadvantages by using the MSR-BGPprotocol. It also explains how this protocol is less susceptible to looping over other multi routeselection algorithms. It also explains about the existing multiple route selection algorithms, theiradvantages and disadvantages and how the proposed protocol is better than them. It clearlyexplains how the proposed algorithm perfectly uses the residual bandwidth and avoids thetransient loops formed in the network.According to my view, this paper was able to give a solution to the existing routing problems inBGP by proposing a new protocol.13

Classification of Routing Protocols:A Routing protocol is a set of guidelines that a router has to follow when it communicates orexchanges the routing information. Routing protocols are used to calculate the optimal routes byusing the reachability information in the network and update the routing tables. Routers use theserouting protocols to know the different possible routes and store them in their tables. Eachprotocol has its own metrics to calculate the feasible paths. They use metrics to calculate the bestpaths. As discussed earlier, Routing protocols are mainly divided into two types, InteriorGateway Protocols and Exterior Gateway Protocols. The following classification in figure 2clearly explains their division,Figure 2: Classification of Routing Protocols 14

Interior Gateway Routing Protocols:The routing protocols used within the Autonomous System to distribute the routing informationare called as Interior Gateway Protocols (IGPs). These are responsible for routing updates within the Autonomous System. Each IGP protocol have their own metrics to choose the best path inthe network. These are further classified into two types, distance vector routing protocols andlink-state routing protocols. Most of the IGP protocols fall under these two categories.Routing Information Protocol popularly known as RIP is one of the oldest protocols which is anexample for distance vector routing protocol. Open Shortest Path First protocol which ispopularly known as OSPF is an IGP protocol which is an example for link state routing protocol.The Enhanced Interior Gateway Routing Protocol (EIGRP) is known as the hybrid routingprotocol which has the features of both distance vector and link state routing protocols. We willlook into each protocol in detail in the next sections.Distance Vector Routing Protocols:Distance vector routing protocols are the first generation protocols. These are fairly simple andnot designed for the complex networks. They have limited scope of technology. They can see asfar as they are connected to their neighbors or next routers. They have no idea how the topologylooks like behind these routers. They have the hop count as their metric. Metrics are used tomake the routing decisions by the routers in the network.The distance vector routing protocol follows the distance vector algorithm, which states thatroutes are advertised with the vector of distance and direction. The distance implies to thenumber of hops required to reach the destination i.e. number of routers that it has to pass to get tothe destination and the direction refers to the direction of next hop router.Each router implementing this protocol advertises the network reachability information to theneighboring routers. Neighbors always mean the routers sharing a common data link in thenetwork. These advertisements happen periodically with 10 to 90 seconds interval depending onwhich type of protocol we are using. The common examples for the distance vector routingprotocols are Routing Information Protocol (RIP) and Cisco’s Interior Gateway Routing Protocol(IGRP). RIP usually advertises periodically for every 30 seconds.The distance vector routing protocols usually select the best path which has the lowest cost.Lowest cost here refers to the lowest number of hops. It automatically selects the best path as thepath which has the least number of hops. The working of the protocol is further explained in RIPprotocol in the next section.15

Routing Information Protocol:Routing Information Protocol (RIP) is one of the oldest distance vector routing protocols. Themain function of the routing protocol is to choose the best path to reach the destination prefix.This is done by updating the routing tables in the router by information received from theneighboring routers in the network. Every protocol has a metric to choose the best path amongthe available paths. RIP uses hop count as the metric to calculate the best path. The maximumnumber of hops that would allow RIP to reach the destination is 15 hops. If the destination prefixis more than 15 hops then the prefix is marked as unreachable. Hence the RIP is not suitable forthe larger networks.Let us looking at the functioning of the RIP by looking at a small network which has 3 routers A,B and C. E0 and E1 represent the Interfaces through which the routers are configured to thenetwork.In figure 3, we can see each router has its own routing table with the network information that itis connected to. Router A has directly connected to 1.0.0.0 network and 2.0.0.0 network with theInterface E0 and E1. The third column in the routing table represents the number of hopsrequired to reach that particular network. As the router A is directly connected to 1.0.0.0 and2.0.0.0 networks, the hop count is going to be 0. Same with Router B and Router C. This is howit looks before running the protocol.Figure 3: RIP Initial Network al16

Now let’s assume every router implements RIP protocol in the network. Now router A shares itnetwork information to its neighbor router B. And router B adds the 1.0.0.0 network to itsrouting table and ignores the 2.0.0.0 network as it is also directly connected to the same network.As we can see the routing table of the router B added the new network prefix with hop count as‘1’ in the third column. This means it has to cross one router to reach that particular network.Figure 4: RIP: Router A sharing reachability information alIn the same way, router B shares its routing table with router A. And router A adds the 3.0.0.0network into its routing table with hop count as 1. We can see this in figure 5,17

Figure 5: Router A table updated from Router B alIn figure 6, we can see router B shares its Routing table with router C. And router C updates itsrouting table with router B’s information and adds the two new networks, 1.0.0.0 and 2.0.0.0 toits routing table. As we can see the hop count to reach the 1.0.0.0 network is 2 as it has to crosstwo routers, router A and router B in order to reach that network. In order to reach 2.0.0.0network, it just needs to cross router B, hence its hop count is 1.18

Figure 6: Router C updated with neighbor Router B alThe figure 7 shows the full updated routing tables of the routers in the network. We can seerouter B got to know about the 4.0.0.0 network from router C and added that network in itsrouting table. In the same way in next periodic update, the router A gets updated with the newnetwork 4.0.0.0 from router B. It keeps the hop count as 2 as it has to cross router B and router Cto reach that network.19

Figure 7: Complete Network setup in Routing tables alHence in this way all the routing tables in the network gets updated. The RIP sends the periodicupdates for every 30 seconds. Suddenly if a link gets failed in the network, it will wait till thenext periodic update to update the other routers in the network. Hence the convergence timetaken will be more in the network.20

Link State Routing Protocols:Link state routing protocols are like road map and whereas the distance vector routing protocolsare like road signs. They have full scope of the topology. Each router in the networkimplementing Link state routing protocol initiates its reachability information and passes on tothe neighboring routers. In this way it has the whole topology information of the network. Theultimate goal is to have the identical information in every router about the network.Link state routing protocols are also called as the distributed database protocol or the short pathfirst which runs on the Dijkstra’s shortest path algorithm. Open Short Path First (OSPF) is thesuitable example for the Link state routing protocol. The routers in the network does not sendrouting updates periodically like distance vector protocol, instead it only sends updates if there isany link failure or if there is any change in the topology. This update from the router is sent toeach and every router that is connected in the network not only to the directly connected router.It reduces the CPU overhead by great amount as there won’t be any periodic updates.First of all, all the routers in the network implementing same protocol should get to know abouteach other. This is done by sending the ‘Hello’ message by a router to the neighboring router byprepending its router id into the message. A router will wait for the reply for certain periodbefore declaring the link as ‘dead’. When there is a neighbor discovery, then these hello messageare used to monitor the health of the link. These hello packets are exchanged for every 10seconds. A router is flagged unreachable if it does not receive the response back in 40 seconds.All the network updates are flooded in the network rather than updating periodically.Link state flooding:Once the network is established, the routers are allowed to send the advertisements which LinkState Advertisements (LSA) to report any event. Her the event can be a link failure or anychange in the topology. Thus advertisement should be broadcasted to every neighbor in thenetwork. Each LSA is assigned with the sequence number which is a unique identifier to thatparticular update. Every LSA is stored in the link state database of the router and forwarded tothe neighboring router. If a router receives the same LSA which it already knows then it simplyignores.This is how the updates happen in the link state routing protocol. As the router does not wait forany periodical route updates, it simply broadcasts the update when it receives the LSA. Thismakes the Link state routing protocol converge faster when compared the distance vector routingprotocol. And also the LSA is attached with a unique identifier the routers have full knowledgeon the change in the network. Even though a router receives the same LSA from different routerit simply ignores and hence there won’t be any loops in the network.The application of the link state protocol is explained in OSPF protocol in the below section.21

Open Short Path First (OSPF):Open Short Path First (OSPF) protocol is the widely used Interior Gateway Protocol (IGP). It is apublic routing protocol which means it is not owned by any company like EIGRP (EnhanceInterior Gateway Routing Protocol) which is a Cisco owned routing protocol. OSPF is one of thebest Link state routing protocol. [9] As discussed earlier in link state routing protocol, router hasthe knowledge of topology and updates are not sent periodically. The updates are sent only whenthere is a link failure at any router or if there is any topology change.In an Autonomous System running with OSPF protocol, the whole region is divided intomultiple areas. This is done to decrease the traffic bursts in the network. Area 0 is called as thebackbone are which will be in touch with every other area in the network. Every router in theother areas are local to that particular area and have the routing tables to that particular network.Figure 8: OSPF Areas in an Autonomous System .html22

As seen in figure 8, every Area has an ABR which is Area Border Router. These routerssummarize the IP addresses for each area. There is also ASBR (Autonomous System BoundaryRouter). This router is connected to the other routing systems like BGP from another routingSystem which acts like a gateway router.There are 5 types of link state packets,Hello: It is used to maintain the neighbor relation with the adjacent routers.Database Description: It contains all the list of links and this used by the routers receiving inupdating the database.Link State Request: It is used by receivin

information. BGP rather than using a particular metric, it uses BGP attributes to select the best path. Once it selects the best path, then it starts sending the updates in the network. Every router implementing BGP in the network, configures this best path in its Routing Information Base.