David Hauweele, Bruno Quoitin, Cristel Pelsser, Randy Bush.

Abstract

The Border Gateway Protocol propagates routing information accross the Internet in an incremental manner. It only advertises to its peers changes in routing. However, as early as 1998, observations have been made of BGP announcing the same route multiple times, causing router CPU load, memory usage and convergence time higher than expected.

In this paper, by performing controlled experiments, we pinpoint multiple causes of duplicates, ranging from the lack of full RIB-Outs to the discrete processing of update messages. To mitigate these duplicates, we insert a cache at the output of the routers. We test it on public BGP traces and discuss the relation of the cache performance with the existence of bursts of updates in the trace.

Public review by Alberto Dainotti

“What do parrots and BGP routers have in common?“

“Nothing, of course.” — you might answer the question in this paper’s title.
“Since parrots simply repeat the sounds they hear, with no understanding of their meaning“. On the contrary, BGP speakers process the messages they receive and, hopefully, understand them before talking. However, a careful check of literature, may (or may not) make you reconsider the question:

• E. N. Colbert-White, M. A. Covington, D. M. Fragaszy,
  “Social Context Influences the Vocalizations of a Home-Raised African Grey Parrot (Psittacus erithacus erithacus)”
  Journal of Comparative Psychology, Online First Publication, March 7, 2011. doi: 10.1037/a0022097

Moving from the paper title to the content: the authors investigate the problem of redundant BGP update messages (duplicate updates) generated by BGP routers. This phenomenon would normally be prevented by the Adj-RIBs-Out, which “contains the routes for advertisement to specific peers by means of the local speaker’s UPDATE messages.” [RFC 4271]. However, the Adj-RIBs-Out is sometimes not fully implemented or disabled in order to save memory. Previous studies have shown that duplicates can reach percentages above 80% in busy times (showing similarity to parrots to a BGP peer) and be detrimental to operations by causing high CPU loads.

This study contributes to the problem in two ways: (i) it explains the origin of several types of duplicate occurrences; (ii) it demonstrates that a simple
cache, requiring less memory usage than the Adj-RIBs-Out, can significantly
mitigate the problem. Reviewers appreciated the novelty of the contributions but would have liked to see an exhaustive analysis and characterization of all the common causes of duplicates in real world traces. This work is only a first step in fully understanding all the dynamics involved in redundant BGP update messages.

Download the full article