BGP- BEST PATH ALGORITHM

Good Morning/Afternoon Everybody, I am going to converse about the Routing Algorithm that BGP uses, which is Best Path Algorithm. As we know, BGP is an Exterior Gateway Protocol. It selects a single best path to a destination, and inserts it in the IP routing table. IP datagrams are only forwarded based on routes in the IP table, NOT by the routes in the BGP table.

Since each distinct prefix is a unique destination, BGP will select and advertise only a single best path. To decide which is the ‘best path’, BGP uses an extensive tie-breaking algorithm. At each step, BGP seeks to break a tie between metrics. The selection process ends at the point where a tie between routes is broken by a better metric. The metrics used are as follows:

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

1. Generally speaking, the first path received is automatically the ‘best path’. Any further paths received are compared to this path to determine if the new path is ‘best’.

2.  Is the route VALID? So, In order to to be valid, the path should satisfy one of the points, which are:

The route must be synchronized with the Interior Gateway Protocol (unless synchronization is turned off).
The route must appear in the IP routing table (see previous bullet point).
The NEXT_HOP must be reachable.
The AS_PATHs received from an external AS must not contain the local AS, or they will be discarded.
The local routing policy must permit the route. If the neighbor is filtering the route, they won’t use it.
HIGHEST WEIGHT
Weight is a Cisco-proprietary setting and only exists on the router on which it   is configured. It is otherwise useless throughout an AS.

3. Highest LOCAL_PREF (used within an AS)

It is important to note that a path without LOCAL_PREF is considered to have had the value set with the bgp default local-preference command, or to have a value of 100 by default

4. Prefer LOCALLY ORIGINATED route (originated from this router)

5. Shortest AS-PATH

6. Lowest Origin Type:

      IGP ; EGP ; INCOMPLETE

 7.  Lowest MULTI-EXIT-DISCRIMINATOR (MED)

Note:  Be aware of these items

This comparison only occurs if the first (the neighbouring) AS is the same in the two paths. Any confederation sub-ASs are ignored.
In other words, MEDs are compared only if the first AS in the AS_SEQUENCE is the same for multiple paths. Any preceding AS_CONFED_SEQUENCE is ignored.
If bgp always-compare-med is enabled, MEDs are compared for all paths.
You must disable this option over the entire AS. Otherwise, routing loops can occur.
If bgp bestpath med-confed is enabled, MEDs are compared for all paths that consist only of AS_CONFED_SEQUENCE.
These paths originated within the local confederation.
THE MED of paths that are received from a neighbor with a MED of 4,294,967,295 is changed before insertion into the BGP table. The MED changes to to 4,294,967,294.
Paths received with no MED are assigned a MED of 0, unless you have enabled bgp bestpath med missing-as-worst .
If you have enabled bgp bestpath med missing-as-worst, the paths are assigned a MED of 4,294,967,294.
The bgp deterministic med command can also influence this step.

8.   Prefer eBGP route over iBGP route

9.  Lowest IGP metric to BGP NEXT_HOP

10. Prefer FIRST RECEIVED EXTERNAL ROUTE (prefer the OLDEST external PATH)

This step minimizes route-flap because a newer path does not displace an older one, even if the newer path would be the preferred route based on the next decision criteria.

Skip this step if any of these items is true:

o    You have enabled the bgp best path compare-routerid command.

Note: Cisco IOS Software Releases 12.0.11S, 12.0.11SC, 12.0.11S3, 12.1.3, 12.1.3AA, 12.1.3.T, and 12.1.3.E introduced this command.

o    The router ID is the same for multiple paths because the routes were received from the same router.

o    There is no current best path.

The current best path can be lost when, for example, the neighbor that offers the path goes down.

11. Prefer Lowest Router ID

The Cisco router ID is IP address of the router, which in turn is the highest IP address on the router, or its Loopback Interface if it has one.

12.  Minimum CLUSTER_ID length

If the originator or router ID is the same for multiple paths, prefer the path with the minimum cluster list length.

13.    Lowest neighbour address

This address is the IP address that is used in the BGP neighbour configuration. The address corresponds to the remote peer that is used in the TCP connection with the local router.

From this list, you can see it is impossible for two BGP routes to TIE each other and become equally preferred. As has been stated, BGP contains only a single best path to any given destination. BGP runs across the entire Internet, therefore it must manage to reduce the number of advertised routes in order to prevent the Internet from becoming flooded with route advertisement traffic. Thus, this algorithm is designed to eliminate all but 1 route to a destination.

COMPARISON OF ROUTING PROTOCOLS

RIP, RIP2, IGRP, EIGRP, OSPF

USE THIS TABLE FOR YOUR REFERENCE: SEE the text below this table.

RIP
RIP2
IGRP
EIGRP
OSPF

Classful protocol

Multi vendor

Distance Vector Protocol

Support only IP routed protocol

Slow convergence time

No VLSM(Variable length subnet masking)

Not suitable for Large and complex networks

Easier to implement

Does not support Authentication

Does not support Load sharing

Does not send masks in routing update

Does not support Auto summarisation

Routing updates not sent to a multicast IP address

Classless protocol

Multi vendor

Distance Vector Protocol

Support only IP routed protocol

Slow convergence time

VLSM

Not suitable for Large and complex networks

Easier to implement

Support Authentication

Does not support Load sharing

Sends masks in routing update

Support Auto summarisation

Routing updates sent to a multicast IP address

Classful protocol

Cisco Proprietary

(used only on cisco routers)

Distance Vector Protocol

Support only IP routed protocol

Faster Route convergence

No VLSM(Variable length subnet masking)

Not suitable for Large and complex networks

Easier to implement

Does not support Authentication

Support Load sharing

Does not send masks in routing update

Does not support Auto summarisation

Routing updates not sent to a multicast IP address

Classless protocol

Cisco Proprietary

(used only on cisco routers)

Dual-Diffusing Update Algorithm (Both Distance vector and link state)

Support all routed protocols

(IP,IPX, AppleTalk)

Fastest Route convergence

VLSM

Suitable for Large and complex networks

Easier to implement

Support Authentication

Support Load sharing

Sends masks in routing update

Support Auto summarisation

Routing updates  sent to a multicast IP address

Classless protocol

Multi vendor

Link State protocol

Support only IP routed protocol

Faster Route convergence

VLSM

Suitable for Large and complex networks

Difficult to implement

Support Authentication

Support Load sharing

Sends masks in routing update

Does not support Auto summarisation

Routing updates  sent to a multicast IP address

Always compare OSPF to RIPv2 and RIPv1 because these are open-standard. Thus, within an all Cisco-router environment, EIGRP would be the best choice.

Talking about Classless and Classful nature, RIP and IGRP are the protocols that are classful Protocols, whilst all others are Classless protocols.
Protocols IGRP, EIGRP are Cisco-Proprietary; they can only be used with Cisco devices. RIP, RIP2, OSPF are Multi-vendor compatible.
RIP, RIP2, IGRP are Distance Vector Protocols. This means they use Distance i.e. hop count as the metric to determine the best path. This protocol updates its neighbours of the topology changes and route-updates periodically.
OSPF is a Link State Protocol, which means it uses Speed, cost and congestion in the network to find the best suitable path. It uses Dijkstra algorithm. Routing updates are done only when there is a topology change, not periodically like distance vector protocols.

EIGRP is a DUAL (HYBRID) using both DVP and Link state Protocols.

RIP1 and RIP2 are slow converging, whereas IGRP, EIGRP, OSPF are fast converging, with EIGRP being the Fastest converging.
Due to slow convergence nature, RIPv1 and RIPv2 requires too much bandwidth, thus OSPF is preferred. Generally, Classless protocols support VLSM, sends subnet mask in routing update and support manual route summarization, whereas classful protocols do not.
Link State Protocol uses speed, cost and Variable Length Subnet Masks (VLSM) allows you to use different masks for each subnet, thereby using address space efficiently.
Talking about Auto summarization, RIP and IGRP does not support auto summarization, while others do.
OSPF is difficult to implement because, simply it has more features than other protocols.

Conclusion:

To conclude, Among the five protocols, IGRP, EIGRP are to be used only on Cisco device, in which EIGRP is the best with faster convergence and extra features. RIP is slow converging, so they require too much bandwidth, but in cases of smaller networks, it is wise to RIP protocols, as they are simpler to implement. In larger networks which require features like authentication, OSPF is the best choice, as it supports multi-vendor devices. EIGRP is the best on Cisco devices.

References

1. William. R CCIE (2003), Cisco® BGP-4 Command and Configuration Handbook (CCIE Professional Development), Cisco Press.

2. Russ White, Danny McPherson, Sangli Srihari (2004), Practical BGP, Addison-Wesley Professional.

3. Cisco Press Optimal Routing Design Jun 2005 Ebook-Ddu.pdf

4.  http://docstore.mik.ua/cisco/pdf/routing/BGPBestPathSelectionCriteria.pdf

5. William R Parkhurst, Bill Parkhurst, (2004) Routing-First Step, Cisco Press.

6. Priscilla Oppenheimer, (1999), Top down Network design, Cisco Press.

x

Hi!
I'm Niki!

Would you like to get a custom essay? How about receiving a customized one?

Check it out