<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Aug 30, 2020 at 10:06 AM Charles Sprickman <<a href="mailto:spork@bway.net">spork@bway.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">(on -discuss)<div></div></div></blockquote><div><br></div><div>[...]</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div>Second thing, someone better versed in the intricacies of BGP better than I am, can you explain a bit about how we end up in a situation where L3 continues advertising withdrawn routes for more than an hour?<br></div><div><br></div><div>Thanks,</div><div><br></div><div>Charles<br><div><br></div></div></div></blockquote><div><br></div><div>Without naming a particular vendor, I'll relate a story from a few years ago.</div><div><br></div><div>It involved BGP communities; at a particular company, we'd made *very* extensive</div><div>use of BGP communities for identifying route type, route origin, backbone nodes </div><div>the route had passed through, propagation scope, special handling rules; all the </div><div>usual sort of stuff you really want to track through your network for controlling </div><div>where and when routes are used.</div><div><br></div><div>That was all fine and good.  But, to make it all automatable and scriptable, we'd </div><div>organized the BGP community number space as a bit field vector, with each </div><div>digit having a hierarchical meaning; think ASN.1 notation, but encapsulated </div><div>within BGP community values.  Wonderful for machine parsing and generating.</div><div>Tended to make for highly dense clusters within the BGP community number </div><div>space, however.</div><div><br></div><div>Turns out that wasn't great from the router vendor's perspective; they had </div><div>(erroneously) assumed BGP communities would generally be well distributed </div><div>through the number space, so doing a top level hash for storing communities, </div><div>with a linked list in each hash bucket on the off chance more than one value </div><div>hashed into the same bucket seemed reasonable.</div><div><br></div><div>And then it came face to face with our densely-clustered bit field vector </div><div>structure, and that hash function meant that there were a small number </div><div>of hash buckets with *very* long linked-lists of BGP communities in them</div><div>which had to be traversed for *every* route update.  It was taking *hours*</div><div>for BGP updates to get processed, as the router was applying the hash</div><div>function, hitting a particular bucket...and then walking a *very* long linked </div><div>list of entries within that bucket.</div><div><br></div><div>The vendor in question captured a bunch of data, realized they needed </div><div>a different hash function that could deal with highly-clustered data like </div><div>this without overloading a few buckets, and built a new version of code </div><div>for us to deploy.</div><div><br></div><div>BGP update propagation went from hours down to minutes again.</div><div><br></div><div>I have no idea what the trigger issue for the CenturyLink issue of </div><div>today is; that will take a post mortem deep dive on their part to</div><div>identify.</div><div><br></div><div>But *how* can it happen?</div><div><br></div><div>Well, this story is one example of how it could (and did) happen in </div><div>a fairly large network a few years ago.   ^_^;;</div><div><br></div><div>Thanks!</div><div><br></div><div>Matt</div><div> </div></div></div>