Detecting BGP instability using Recurrence Quantification Analysis (RQA)

The Border Gateway Protocol (BGP) is the default Internet routing protocol that manages connectivity among Autonomous Systems (ASes). Although BGP disruptions are rare, when they occur the consequences can be very damaging. Consequently there has been considerable effort aimed at understanding what is normal and abnormal BGP traffic and, in so doing, enable potentially disruptive anomalous traffic to be identified quickly. In this paper, we make two contributions. We show that over time BGP messages from BGP speakers have deterministic, recurrence and non-linear properties, then build on this insight to introduce the idea of using Recurrence Quantification Analysis (RQA) to detect BGP instability. RQA can be used to provide rapid identification of traffic anomalies that can lead to BGP instability. Furthermore, RQA is able to detect abnormal behaviours that may pass without observation.

I. Introduction

The Border Gateway Protocol (BGP) is the current interdomain routing protocol that maintains and exchanges network reachability information between Autonomous Systems (ASes). BGP was developed at a time when information provided by an AS could be assumed to be accurate. Consequently, it includes few security mechanisms [1]. Although propagation of inaccurate information via BGP is fortunately rare, when an AS, either deliberately or accidentally propagates incorrect information, the consequences can be very serious. The process of detecting abnormal data in a series of BGP update messages represents a challenge for researchers and operators, especially during unstable periods, as routing data is complex, noisy, and voluminous. To compound the challenge, single events such as link failure can produce multiple update messages, affect routing decisions, and erroneously propagate incorrect destination prefixes [2].