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.