BGP loop prevention with AS_PATH

Unanswered Question
Mar 25th, 2010

Just a curious thought about AS_PATH.  The way loop prevention works in BGP is that if I see my own AS in the AS_PATH attribute, then I discard the route.

My curiosity is this ... why did my neighbor send me the route in the first place?  He knows my AS number.  He could see the route had my AS in the AS_PATH attribute.  So why did he bother to send it to me, if he knew I would just discard it?

Kevin Dorrell

Luxembourg

I have this problem too.
0 votes
  • 1
  • 2
  • 3
  • 4
  • 5
Overall Rating: 5 (7 ratings)
Loading.
Giuseppe Larosa Thu, 03/25/2010 - 14:39

Hello Kevin,

I had sometimes the same thought.

Probably only the first AS (peer AS)  is checked not all of those that are in the path.

However, if this check was implemented the neigh allowas-in command could not be used to interconnect partitioned ASes

Hope to help

Giuseppe

Tharak Abraham Fri, 03/26/2010 - 00:02

Kevin,

Good one !

I feel this is how BGP is implemented.

If you go through the decision process, mainly the Adj-Rib in, the local Rib and the Adj-Rib out we'll get to know the idea how BGP process the routes and decides on the routes to be sent outbound.

It would be expensive to implement a per neighbor based Adj-Rib out, if my understanding is correct.

Its the BGP algorithm to include the loop free check in the routes it recieves and which is applicable to all BGP speakers !

Any more thoughts would be appreciated !!

Kevin Dorrell Fri, 03/26/2010 - 07:29

Thank you both for your replies.

Giuseppe, I had not considered the case of the partitioned AS.  I'll have to think that one through this evening, once I am out of the boiler-room.  In fact, I'll have to think through how a partitioned AS would work anyway.

I take the piont about the implementation detail, and it being costly to perform outbound filtering on a per-neighbor basis.  But sometimes you are doing that anyway.  Maybe they decided it would be quicker to send all the routes and let the peer sort it out.  Sort of ... is it more costly to send the extra redundant routes, or to spend CPU cycles pre-discarding a few of them?  Of course, the peer that receives the routes would still have to (double) check them anyway.

I'll have to do some experiments with this.  I should be able to emulate it with an AS_PATH filter on the outbound neighbor, or maybe with ORF configured on the inbound neighbor (if I can remember the details of how ORF works .. maybe it would not be possible)?

If I come up with anything interesting I'll post about it.

Kevin Dorrell

Luxembourg

marikakis Sun, 03/28/2010 - 06:54

Hi Kevin,

As RFC 4271 says, "AS loop detection is done by scanning the full AS path (as specified in the AS_PATH attribute), and checking that the autonomous system number of the local system does not appear in the AS path". Theoretically, an external peer of the local system could see loops involving the local system, but doesn't bother to check it on behalf of the local system at any point. We could say that's how BGP works. Now, why things work the way they do is usually another story. I don't personally know of a definitive answer to your question, but I am thinking of some possible reasons.

Giuseppe already mentioned a feature that would have trouble working if responsibility for the loop check of the local AS was assigned to its external peers. Had the external peers been doing loop check on behalf of the local AS, this feature (allowas-in) would need modifications to the configuration of multiple peers (instead of just changing the configuration of the local AS) in order to work, so it's not flexible I think (I assume that the loop check could somehow also be disabled on the peers).

You are kind of asking for an automatic implicit loop check feature, probably at the beginning of an out-filter (because route must be rejected if it includes a loop) or before out-filtering starts. Outgoing update process might be delayed in routers with many peers such ISP routers. Note that out-filters from end customer AS's towards the ISPs vary (and end customers do not send lots of routes towards the internet core), but out-filters in the opposite direction, from ISPs towards the end customer often involve specific sets (such as full, partial or default routes, typically organized in peer-groups) and are not so much dependent on the remote AS value, but more on the "type" of customer. Also, we are talking about a full scan of the AS path of all routes (with different procedure for each remote AS). A real-life filter usually causes only a partial scanning of the AS path involving the first few AS's in the path (and out-filters can also be grouped to avoid doing the same out-filtering task many times).

It seems logical to me for every AS to check for loops of their own AS (instead of loops on behalf of everybody else they peer with) from an authority, flexibility and distribution of load accross routers/scalability perspective. Generally, in BGP context, flexibility for each AS to create their own policy is preferred over proactive work, especially when the proactive work is done for the sake of other AS's. If the loop is a problem, then I think it is mainly a problem for the AS being involved in it, so I think this AS is the best authority to act on its resolution anyway. (BTW: If your upstream had done the loop check for you, would you feel confident and not repeat the same check on your router?)

In the end, how many such loops exist and how often do they appear? Such a check might complicate and slow down upstream routers in the common case of "no loops" for the sake of not wastefully sending some extra (potentially invalid) updates to the local AS in the less common case. As I see it, it's not just the extra work (and a few cpu cycles), but work that might also slow down the existing outgoing update tasks (the extra cpu cycles could be viewed as a base cost to pay for sending any route to a peer, even when no other out-filtering is needed, and this cost is a full AS path check for the peer's AS).

Kind Regards,
Maria

Jon Marshall Sun, 03/28/2010 - 08:49

I think Maria has hit the nail on the head with this.

Put simply within a BGP AS you are responsible for what routes are received and propogated within your AS and what routes are advertised from your AS. If neigboring AS are filtering routes to you based on your AS PATH being present you have now relinquished some of the responsibility for your AS which goes against the whole idea of an AS in the first place.

This explains why BGP was implemented the way it was ie. it is the responsibilty of the local AS to control what enters and leaves that AS in terms of route advertisements.

Jon

pauldzummo Fri, 10/01/2010 - 08:18

I don't see where anybody answered your actual question.  I won't go into too much detail, but here's the reason the advertisement is sent and it's up to the receiver to prevent the loop.

When a BGP speaker receives BGP routes, it runs through the BGP decision process, thus it has to inspect the entire ASPATH of every BGP route it receives to determine best path selection.  The determined best path routes are then installed into the FIB.  When it advertises routes, it takes the routes from the FIB and forwards them if the prefix meets it's forwarding rules.  In order for BGP to do ASPATH loop prevention from the sender side, it would have to inspect (again) the ASPATH of every BGP route from it's FIB to see if it matches the AS that it is advertising to.  Since this ASPATH inspection is already done when routes are received, BGP ASPATH loop prevention is added to that BGP decision process reducing the overhead on the CPU by not having to re-inspect the ASPATH for advertisements.

Yes, you can create filters that match ASPATH that require ASPATH inspection on outbound advertisements.  But the ASPATH is not inspected when deciding whether or not to advertise the route.

Peter Paluch Fri, 10/01/2010 - 11:48

Paul,

I don't see where 
anybody answered your actual question.  I won't go into too much detail,
 but here's the reason the advertisement is sent and it's up to the 
receiver to prevent the loop.

I believe that Maria and Jon did a pretty good job of answering Kevin's actual question. Have you read their ideas carefully?

Regarding your answer, I have to say I do not agree with your reasoning. You suggest the following:

In order for BGP to 
do ASPATH loop prevention from the sender side, it would have to inspect
 (again) the ASPATH of every BGP route from it's FIB to see if it 
matches the AS that it is advertising to.

This holds only for a naive BGP implementation that does not "look ahead". However, in a smart implementation, when analyzing a route's AS_PATH attribute, you can perform many decisions at that stage, including those which are not necessary for best path selection but which may influence the propagation of the route, and store the results for later use. Cisco's BGP implementation, for example, dynamically computes so-called update groups for which a single update is replicated, instead of evaluating each neighbor separately, and each route is associated with the update group it shall be advertised into. In my opinion, it would not be exceedingly difficult to add the AS check in the AS_PATH analysis stage to define whether a route shall be placed into the particular update group basing on the AS of the neighbor.

I tend to agree strongly with Jon's nice wrap up - the AS itself shall have the final say where are its routes going to be advertised, and which routes it is willing to accept. Also, even if my AS is peering to a different AS X, I do not have the right to assume that the AS number X is the only number of that AS - just think of migration scenarios which are using the neighbor local-as command to override the AS number for a particular neighbor. The AS visible under the ASN X may in reality be ASN Y and the entire logic of sender checking the neighbor's AS number would then be broken.

Best regards,

Peter

pauldzummo Fri, 10/01/2010 - 13:07

Peter, I agree with everything you, John, and Maria said regarding having the ability to determine what's allowed to enter your AS, except the part as to being the reason it performs this way in the programming of the code.  The software was written this way because this is the most efficient way for BGP to operate in it's default (naive) mode.  The Cisco feature support for allowas-in was not available until 1999.  BGP loop prevention has continued to operate this way since BGP1 as defined in RFC1105 in 1989.

Cisco (among other vendors) allow engineers to configure features that inspect the ASPATH as a sender, but it is not the default behavior because it is extra overhead on the CPU to inspect the ASPATH of every advertised prefix since this process already occurs when the routes are received.

marikakis Fri, 10/01/2010 - 14:29

Hi Paul,

Thanks for bringing this issue up again. You might be right that Kevin's question has not been completely answered, and that is probably the reason why Kevin himself hasn't marked it as such. In my previous post I did not claim to have a definitive answer to Kevin's question anyway.

Maybe I'm misunderstanding something from your post, but my understanding is that BGP decision process logically happens after inbound filtering and doesn't necessarily have to examine entire AS paths. If local preference is set for example, the AS path and it's length are ignored. Even if AS path is taken into account in that process, not the entire AS path needs examination and it typically boils down to consideration of the AS path length and not the entire AS path. An exception to this I can think of right now is the case where MEDs are considered, but still not the entire AS path needs examination.

I believe most of the arguments in this thread hold and I trust the very experienced members of the community to spot any problems in each others posts. I think the weakest argument is the one that suggests that loop detection is done on the receiver and not the sender because it is done on the receiver. This looks like a tautology and doesn't explain why things work the way they do. If loop detection was always implicitly done on the sending side, then receiver loop detection would not be strictly necessary. Still, I believe we all tend to agree that the transmit side loop detection, if implemented, would be an extra task to what is already being done, so the weak argument becomes stronger in this case (i.e. since it is done on the receiver, doing it on the sender might mean extra work and most members have said that already). Members have also tried to find other practical problems that might occur with default transmit side loop detection and I believe this was a good way to go (i.e. if a default causes problems or is not generally desirable between external peers, then it needs customization and should not be a default in the first place, regardless of whether it takes many or few cycles).

I'm sorry I don't have a lot of time these days to thoroughly read even my own previous post and understand what exactly I was thinking back then, so thank you Peter for examining it. I also hope you and others can also check if what I am saying right now makes any sense!

I do trust the below more than I trust my above sentences.

According to "BGP Design and Implementation" from cisco press (pages 95-96), transmit (TX) loop detection must be implemented manually and configuration applies to external peers only. Sample config:

router bgp 100

        ...

    neigh r.s.t.w remote-as 1

    neigh r.s.t.w filter-list 1 out

    ...

!

ip as-path access-list 1 deny _1_

ip as-path access-list 1 permit any

Book says that in some scenarios the tx-side loop detection in undesirable and specifically in MPLS VPN environments. It used to be the default when peer groups were not used, but was removed for MPLS-VPN support.

So, after some time I am able to appreciate more the value of Giuseppe's post in this thread. Sorry about that Giuseppe. Sometimes I need more time and perspective to see the error of my ways.

Kind Regards,

Maria

pauldzummo Fri, 10/01/2010 - 18:50

Maria,

I appreciate the hard work you and others put in your responses and thank  you for the background and references.  I did not  know at one time it was a default setting on the sender.  From what I've read thus far, the only default loop prevention mechanism on a sender is split horizon.  I guess that's another book I'll have to read.

By the way, this was my first post in this forum and in no way was I trying to challenge or discredit anybody else's response, nor am I trying to be argumentative.  I was trying to offer an answer and did not realize the thread was so old.  So my apologies to all if my post came across wrong.  I do a lot of research and deep dive into a lot of subjects.  That's how I stumbled across this thread initially. I also use references often so people have the resource and don't have to go on my word.

I appreciate the discussion because it's making me think and ultimately have a better understanding.  If this is bothersome for any of you, please let me know and I won't reply again, ending the discussion.  When I said that the initial question wasn't answered, I interpreted your responses as a reason it has stayed on the receiver, but not the reason it was implemented that way in code initially (hence the BGP1 RFC reference from 1989).  The reason it was implemented that way was because of processing, since ASPATH's had to be inspected on the ingress, creating another process to inspect at egress was looked at as processing overhead.  I will try to get you a reference once I can find it, I honestly did not make it up, but often times it's hard to remember where you actually read it.

One thing to note is that ASPATH inspection actually does take place before the BGP decision process.  According to the RFC I quoted and Cisco's documentation, before any metrics are compared, routes are first verified for validity.  Some paths are not considered as candidates for best path, with the ASPATH inspection taking place on the third step.  I put the link below with a snapshot of the portion pertinent to this subject.

http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094431.shtml

Assume that all paths that a router receives for a particular prefix       are arranged in a list. The list is similar to the output of the       show ip bgp longer-prefixes command. In this case, some paths are not considered as candidates for the best       path. Such paths typically do not have the valid flag in the output of the show ip bgp longer-prefixes command. Routers ignore paths in these circumstances:

  • Paths that are marked as not           synchronized in the show ip bgp           longer-prefixes output

  • Paths for which the NEXT_HOP is inaccessible

  • Paths from an external BGP (eBGP) neighbor if the local autonomous           system (AS) appears in the AS_PATH

    Such paths are denied upon ingress into the router and are not even           installed in the BGP Routing Information Base (RIB). The same applies to any           path that is denied by a routing policy that is implemented via access, prefix,           AS_PATH, or community lists, unless you have configured           soft-reconfiguration inbound for the           neighbor.

  • If you enabled bgp enforce-first-as and           the UPDATE does not contain the AS of the neighbor as the first AS number in           the AS_SEQUENCE

    In this case, the router sends a notification and closes the           session.

  • Paths that are marked as           (received-only) in the show ip bgp           longer-prefixes output

    The policy has rejected these paths. However, the router has stored           the paths because you have configured soft-reconfiguration           inbound for the neighbor that sends the           path.

      

marikakis Sat, 10/02/2010 - 01:26

Hi Paul,

By no means did I mean you should not post and I don't have the right to do such a thing. I was 100% honest when I thanked you for bringing the issue up again, because it caused me to look into it further and get closer to an answer. We have all been wrong once or more times in our posts in the forums. My reference to the experience of the members is a friendly warning that is 99% friendly and 1% warning. It is generally a good tactic in any discussion in the forums to leave some room for doubt no matter how sure you are your answer is the correct one (especially in issues that lack documentation), because another member can always prove you wrong. This community encourages people to post and after all there is nothing nearly as good in the forums as good technical argument (regardless of whether it is old or new). If we were discussing politics, religion or favorite baseball team for example, we would reached post number 99999999999... and wouldn't have reached a conclusion.

You have now your first 5 points from me, welcome to the forums and have fun!

Kind Regards,

Maria

Jon Marshall Sat, 10/02/2010 - 04:09

Paul

Just to echo what Maria has already said. Please continue to post into these forums. The more expertise we get the better for everyone. We are always trying to provide the best answers we can so the more people with experience who can provide input the more likely we are to get to the right answer.

Again, as Maria has already said, welcome to the forums.

Jon

Peter Paluch Sat, 10/02/2010 - 15:16

Hello everyone,

Maria and Jon have said everything that is necessary. Paul, please feel welcome and do not hesitate to discuss things with anybody here on NetPro! Just as Maria said, keep an open mind at all times because that is necessary to make a discussion fruitful and friendly.

Regarding your comment about my previous post and some reasons I have highlighted: I was not talking about allowas-in, just in case (I was mentioning the neighbor local-as command). Still, both these commands can be considered as only nuisances - I don't believe their existence or the need for their existence actually influenced the design of the BGP itself. Regarding the discussion about the effectiveness or overhead of the sender performing the AS_PATH check - I believe we have actually come to an important point: how far is a protocol (or its description) responsible for its own effective implementation? Clearly, some thinking about the effectiveness must be put into the protocol description, especially if it influences its principles and/or actions. But most RFCs I have read actually do not describe all the procedures necessary to implement a protocol - rather, they only describe its behavior and the implementation details are up to you. In BGP, for instance, the RFC 4271 formally talks about three types of databases - Adj-RIB-In, Adj-RIB-Out and Loc-RIB, with the Adj-RIB-In and Adj-RIB-Out being formally separate for each peer! Now, you could implement BGP in that way but it would certainly be a huge waste of resources. After all, the RFC 4271 is also clear about this:

   Although the conceptual model distinguishes between Adj-RIBs-In,
   Loc-RIB, and Adj-RIBs-Out, this neither implies nor requires that an
   implementation must maintain three separate copies of the routing
   information.  The choice of implementation (for example, 3 copies of
   the information vs 1 copy with pointers) is not constrained by the
   protocol.

What I am trying to say is that you are trying to infer a logic behind a protocol by looking on whether this or that reason would lead to an effective implementation. I personally believe that this approach may not lead to correct results. Of course, there can be a positive correlation between the effectiveness of a protocol's implementation and some of its characteristic traits, but at the same time, there is no guarantee.

You wrote:

One thing to note is that ASPATH inspection actually does take place 
before the BGP decision process.  According to the RFC I quoted and 
Cisco's documentation, before any metrics are compared, routes are first
 verified for validity.  Some paths are not considered as candidates for
 best path, with the ASPATH inspection taking place on the third step.  I
 put the link below with a snapshot of the portion pertinent to this 
subject.

You are correct but there is a difference between the individual validity checks: if a route is not synchronized, or its next hop is inaccessible, the route will not be considered for best path algorithm but it still will be installed in the BGP database. On the other hand, if the AS_PATH attribute contains the ASN of the local AS then the route will be dropped and not even installed into the BGP database. There is a difference between a route not considered for best path, and a route not even being admitted for installation into the BGP database. Note that the AS_PATH check is actually the first one performed, not the third - it can be easily shown using the debug ip bgp update - a route from our AS advertised back to our AS will not even be admitted from the UPDATE message. Thus, if not accepted, its synchronization status or next hop reachability cannot be verified (nor is it necessary).

You have also mentioned the split horizon. I am not sure if you mentioned that in relation to BGP but as far as I know, there is no such thing as split horizon in BGP. The RFC 4271 does not have any reference to such method and the BGP itself does not behave that way.

Best regards,

Peter

pauldzummo Sun, 10/03/2010 - 09:49

Maria, thank you for the advice.  I do have a habit of speaking in absolutes when many of our questions often have many answers.  I joined the forum because I expected a lot of intelligent discussion and I have been very impressed with the well thought out posts I've read thus far.

Peter, I thought the documentation was written in order of occurrence, where they had the ASPATH inspection as the third bullet.  I'm surprised to know the actual implementation is in a different order. Do you happen to know the full order of the validity checks?

In regards to split horizon, I'm sure you're familiar with it and it's function in distance vector protocols.  In regards to BGP, split horizon is the reason route reflection or confederations are necessary in IBGP implementations that are not fully meshed.  A BGP sender will not advertise any routes that were received from that same AS.  From what I understand, it also works for EBGP where AS 2 should never advertise a prefix with ASPATH [1 2 1] to AS 1, but the documentation on this is very limited and is almost always in reference to IBGP.  Keep in mind that the way this works is that a BGP sender does not inspect the ASPATH to complete this function.  The BGP sender looks at it's best known BGP routes advertising AS, and if it came from AS 1 it's excluded from announcing to AS 1.  This does not keep a sender from announcing routes with an ASPATH of [1 2 3 1] since AS 3 did not receive the advertisement from AS 1, thus the split horizon rule is not in affect.

For some reason, Cisco's site really doesn't offer much in the way of documentation that references this rule (only found one link that even references it, in a CCIP exam topic overview), but it is a loop detection mechanism used on the sender side.

http://www.cisco.com/web/learning/le3/current_exams/642-661.html

Configuring and Monitoring Route Reflectors

  • Given an existing IBGP network, configure and verify proper operation of route reflectors to modify IBGP split-horizon rules
marikakis Sun, 10/03/2010 - 09:51

Hi Peter,

Thanks for commenting on some points that I didn't previously. I am aware that my use of the rating system was more loose than generally accepted, but I sometimes do this to boost morale even for members with thousands of points such as you, Jon and Giuseppe (when you get some 1's or 2's for example). I hope this is not a problem. Paul seems really interested in the details of BGP. BGP is one of my favorite protocols. So, we have BGP in common Paul and hope to see you again in the BGP threads!

Kind Regards,

Maria

marikakis Sun, 10/03/2010 - 10:33

It seems Paul decided to come back a few minutes before I posted! Unfortunately, I am unable to follow this thread anymore. It needs a lot of thinking and I am running out of time with some things I have to do. I will hopefully be able to read the thread sometime in the near future.

Actions

This Discussion

Related Content