Situational Awareness at Internet Scale – Detection of Extremely Rare Crisis Periods

It would valuable to have early warning of disruptions to the Internet. One aspect of Internet function is the Border Gateway Protocol (BGP), which handles the delivery of packets between various autonomous domains. In particular, autonomous routers use BGP communications for “announcements ” and “withdrawals”, that is, to announce the detected availability or unavailability of various Internet routes. Certain statistics of these announcements and withdrawals might be useful in dis-tinguishing between normal and abnormal operation of the Internet[3]. Practical use of these statistics in real-time monitoring is stymied, however, by the need for robust pattern recognition methods that can operate under conditions of extreme skew. In other words, the disruptions, though critical when they occur, nonetheless are occuring only a tiny fraction of the time: in the last decade of Internet activity, there has been roughly twenty cumulative days of “disruption”, an incidence rate of 0.5%. This problem of imbalanced data afflicts many applications, and is becoming even more prevalent as data volumes grow. “Bagged ” ensembles of decision trees have been shown to be a simple, robust an