A path vector algorithm Essay
A path vector algorithm
The Border Gateway Protocol is known as a robust and scalable routing algorithm. The routing tables used by the border gateway routers running BGP control data transmission on over 90,000 routes. The operation of a BGP algorithm begins when a BGP session is initiated. At the time of session initiation, BGP a sends a complete update on routing attributes to the other relevant routers. Thereafter, the BGP will only communicate updates on routing attributes when there is some change in the value of the attributes.
This efficiency in how the routers running BGP ‘advertise’ their attributes is the main reason BGP can scale to handle the growth in the infrastructure of the Internet. With this information on the topology of the internet, each router encountered by the data packet can either accept or change the calculated transmission path based on changes in the path attributes. The communication between different routers using BGP is established through the Transmission Control Protocol (TCP), which allows the two routers to exchange streams of data.
A TCP session must be established every time a BGP session is established. The communication between routers uses 5 message types. The Open message type allows the routers to identify themselves confirm that they are compatible with one another. The Update message type communicates the current attributes of the local network topology, or if this is already known, then only changes are communicated. The KeepAlive message type is a message to confirm to the other routers that the communicating router is operating normally and that the session should continue.
If a KeepAlive message is not received periodically within a pre-specified time interval, the session will be ended. A Notification message type communicates that an error in data transmission has occurred. This type of message will end a BGP session. The last type of message is a Route-Refresh message. This message requests that communicating routers retransmit the full table of attributes without having to start a new BGP session. It is of interest to consider the attributes of the transmission paths that are communicated between routers and how this information is used to decide the transmission path.
The most common path attributes considered by BGP are the Autonomous System (AS) Path, the Local Preference, the Multi-Exit Discriminators (MED), the Weight, the Community, and the Origin Attribute. The AS Path is the list of autonomous systems that a data transmission could traverse. Each AS is assigned an integer between 1 and 65535. The AS origin of the data is given on the far right hand side of the list while the integer on the far left hand side is the last AS before the destination AS.
In general, the longer the AS path is, then the less desirable the path is. It is also possible to force data transmission or exclude data transmission from a certain AS by specifying the AS number in the BGP algorithm. The Local Preference attribute controls the path that data traffic will use to leave an AS. This can be used to set up a hierarchy of exit paths for a given AS. The Multi-Exit Discriminator (MED) attribute is used to control the path that data traffic can use to enter an AS.
Thus the Local Preference and MED provide local network administrators control over the border router and this information must be communicated with the surrounding AS border routers. The weight attribute is a Cisco-defined metric local to a specific router. The data transmission path with the higher weight is generally preferred over a route with a lighter weight. Communities are groupings of AS’s. This grouping assists in the tagging of AS addresses for later use in routing policies.
The grouping may be based on geographic characteristics such as a given city or a given continent. The origin attribute simply identifies the originating AS and how the information about the origin has been communicated. Once these attributes have been communicated, BGP will select a single path as the best path. Once the path is selected, BGP places the prescribed path in a “routing table” and communicates this information to the neighbouring routers. The data is then transmitted along the path to the neighbouring router with the best path.
The criteria that BGP uses to select the best path is: • If the path specifies a transmission to an inaccessible router, then disregard the update on the best path. • Choose the path with the largest weight. • If the weights on multiple paths are the same, choose the path with the largest local preference. • If the local preferences are the same for paths of data transmission outside the AS, choose the path that was originated by BGP running on this router. • If no route was originated, choose the route with the shortest AS path.
• If all paths have the same AS path length, choose the path having the origin communicated by the lowest ranked protocol (where IGP is lower than EGP, and EGP is lower than incomplete). • If the ranks of the origin communication are the same, choose the path with the lowest multi-exit exit discriminator (MED) attribute. • If the paths have the same multi-exit discriminator rank, choose the external path over the internal path. • If the paths still have the same rank, choose the path through the closest IGP neighbour. • Choose the path with the lowest IP address, as specified by the BGP router ID.
University/College: University of Arkansas System
Type of paper: Thesis/Dissertation Chapter
Date: 17 May 2017