The Problem with BGP
If we assume
- unbounded delay on BGP processing and propagation
- Full BGP mesh BGP peers
- Constrained shortest path first selection algorithm
BGP is O(N!), where N number of default-free BGP speakers
There exists possible ordering of messages such that BGP will explore all possible ASPaths of all possible lengths