Reasoning on BGP routing filters using tree automata

The Border Gateway Protocol (BGP) is the protocol used to distribute Internet routes between different organizations. BGP routing policies are very important because they enable organizations to enforce their business relationships by controlling route redistribution and route selection. In this pap...

Full description

Saved in:
Bibliographic Details
Published in:Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2014-06, Vol.65, p.232-254
Main Authors: Battaglia, Caroline, Bruyère, Véronique, Gauwin, Olivier, Pelsser, Cristel, Quoitin, Bruno
Format: Article
Language:English
Subjects:
Access methods and protocols, osi model
Applied sciences
BGP
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Internet access
Mathematical problems
Protocol
Prototypes
Route optimization
Routing policies
Routing protocols
Software
Studies
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Tree automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Border Gateway Protocol (BGP) is the protocol used to distribute Internet routes between different organizations. BGP routing policies are very important because they enable organizations to enforce their business relationships by controlling route redistribution and route selection. In this paper, we investigate the semantic of BGP policies. We aim to determine whether two policies are equivalent, that is, if given the same set of incoming routes, they will generate the same set of outgoing routes. We show how this problem can be solved using the tree automata theory and describe several optimizations. We also propose a prototype implementing this approach. The experimental results are very promising. They show the efficiency of our approach and the interest of using the tree automata theory in the context of BGP routing policies.
ISSN:1389-1286
1872-7069
DOI:10.1016/j.comnet.2014.01.001