iBGP policies; Internet topology; Route Collector; Bias
[en] A significant portion of what is known about Internet routing stems out from public BGP datasets. For this reason, numerous research efforts were devoted to (i) assessing the (in)completeness of the datasets, (ii) identifying biases
in the dataset, and (iii) augmenting data quality by optimally placing new collectors. However, those studies focused on techniques to extract information about the AS-level Internet topology.
In this paper, we show that considering different metrics influences the conclusions about biases and collector placement. Namely, we compare AS-level topology discovery with \iac inference. We find that the same datasets exhibit significantly diverse biases for these two metrics. For example, the sensitivity to the number and position of collectors is noticeably different. Moreover, for both metrics, the marginal utility of adding a new collector is strongly
localized with respect to the proximity of the collector. Our results suggest that the ``optimal'' position for new collectors can only be defined with respect to a specific metric, hence posing a fundamental trade-off for maximizing the utility of extensions to the BGP data collection infrastructure.
Author, co-author :
Donnet, Benoît ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorithmique des grands systèmes
On the Quality of BGP Route Collectors for iBGP Policy Inference
Publication date :
Event name :
Event place :
Event date :
du 2 juin 2014 au 4 juin 2014
Main work title :
Peer reviewed :
European Projects :
FP7 - 318627 - MPLANE - mPlane – an Intelligent Measurement Plane for Future Network and Application Management
Y. Rekhter, T. Li, and S. Hares, "A border gateway protocol 4 (BGP-4)," Internet Engineering Task Force, RFC 4271, January 2006.
M. Caesar and J. Rexford, "BGP routing policies in ISP networks," IEEE Network, vol. 19, no. 6, pp. 5-11, November-December 2005.
L. Cittadini, G. Di Battista, and S. Vissicchio, "Doing don'ts: Modifying BGP attributes within an autonomous system," in Proc. IEEE/IFIP Network Operations and Management Symposium (NOMS), April 2010.
B. Quoitin, S. Tandel, S. Uhlig, and O. Bonaventure, "Interdomain traffic engineering with redistribution communities," Computer Communications, vol. 27, no. 4, pp. 335-363, March 2004.
T. Griffin, F. B. Shepherd, and G. Wilfong, "The stable paths problem and interdomain routing," IEEE/ACM Transactions on Networking, vol. 10, no. 2, pp. 232-243, April 2002.
S. Vissicchio, L. Cittadini, and G. Di Battista, "On iBGP routing policies," IEEE/ACM Transactions on Networking, 2014, to appear.
T. Griffin and G. Wilfong, "On the correctness of iBGP configuration," ACM SIGCOMM Computer Communication Review, vol. 32, no. 4, pp. 17-29, October 2002.
D. Walton, A. Retana, E. Chen, and J. Scudder, "Advertisement of multiple paths in BGP," Internet Engineering Task Force, Internet Draft draft-ietf-idr-add-paths-09, October 2013.
A. Flavel, J. McMahon, a. Shaikh, M. Roughan, and N. Bean, "BGP route prediction within ISPs," Computer Communications, vol. 33, no. 10, pp. 1180-1190, June 2010r.
RIPE, "Routing information service (RIS)," see: http://www.ripe.net/ris.
University of Oregon, "Oregon routeviews project," see http://www.routeviews.org.
R. Oliveira, D. Pei, W. Willinger, B. Zhang, and L. Zhang, "The (in)completeness of the observed Internet AS-level structure," IEEE/ACM Transactions on Networking, vol. 18, no. 1, pp. 109-122, February 2010.
E. Gregori, A. Improta, L. Lenzini, L. Rossi, and L. Sani, "On the incompleteness of the AS-level graph: A novel methodology for BGP route collector placement," in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2012.
Z. Ying, Z. Zheng, Z. Morley, Y. C. Mao, B. Hu, and M. Maggs, "On the impact of route monitor selection," in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2007.
B. Donnet and O. Bonaventure, "On BGP communities," ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 55-59, April 2008.
T. Bates, E. Chen, and R. Chandra, "BGP route reflection: An alternative to full mesh internal BGP (iBGP)," Internet Engineering Task Force, RFC 4456, April 2006.
L. Blunk, M. Karir, and C. Labovitz, "Multi-threaded routing toolkit (MRT) routing information export format," Internet Engineering Task Force, RFC 6396, October 2011.
B. Donnet and T. Friedman, "Internet topology discovery: A survey," IEEE Communications Surveys and Tutorials, vol. 9, no. 4, pp. 2-15, December 2007.
N. Feamster and J. Rexford, "Network-wide prediction of BGP routes," IEEE/ACM Transactions on Networking, vol. 15, no. 2, pp. 253-266, April 2007.
W. M̈uhlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig, "Building an AS-topology model that captures route diversity," in Proc. ACM SIGCOMM, August 2006.
R. Bush, O. Maennel, M. Roughan, and S. Uhlig, "Internet Optometry: Assessing the Broken Glasses in Internet Reachability," in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2009.
V. Giotsas, S. Zhou, M. Luckie, and k. claffy, "Inferring multilateral peering agreements," in Proc. ACM CoNEXT, December 2013.
A. Dhamdhere and C. Dovrolis, "Ten years in the evolution of the Internet ecosystem," in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2008.
P. Barford, A. Bestavros, J. W. Byers, and M. Crovella, "On the marginal utility of network topology measurements," in Proc. Internet Measurement Workshop (IMW), November 2001.
G. G̈ursun, N. Ruchansky, E. Terzi, and M. Crovella, "Routing state distance: A path-based metric for network analysis," in Proc. ACM/USENIX Internet Measurement Conference (IMC), November 2012.
K. Chen, D. Choffnes, R. Potharaju, Y. Chen, F. Bustamante, D. Pei, and Y. Zhao, "Where the sidewalk ends: Extending the Internet AS graph using traceroutes from P2P users," in Proc. ACM SIGCOM CoNEXT, December 2009.
L. Gao, "On inferring autonomous system relationships in the Internet," IEEE/ACM Transactions on Networking, vol. 9, no. 6, pp. 733-745, December 2001.
A. Elmokashfi, A. Kvalbein, and C. Dovrolis, "BGP churn evolution: A perspective from the core," IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 571-584, April 2012.
L. Cittadini, W. Muhlbauer, S. Uhlig, R. Bush, P. Franois, and O. Maennel, "Evolution of Internet address space deaggregation: Myths and reality," IEEE Journal on Selected Areas in Communications, vol. 28, no. 8, pp. 1238-1249, October 2010.
M. Roughan, W. Willinger, O. Maennel, D. Perouli, and R. Bush, "10 lessons from 10 years of measuring and modeling the internet's autonomous systems," IEEE Journal on Selected Areas in Communications, vol. 29, no. 11, pp. 1810-1821, October 2011.