Measurement Research On Large-scale Inter-domain Instability Events In The Internet

Measuring the detecting anomalous events in the B GP system have remained an active research topic.The research works in this domain are important in the fields of inter-domain routing fault avoidance,prediction,detection,and recovery,as well as network management and optimization,and routing protocol design,evaluation,and improvement.We find that most previous measurement works are based on aggregated data(e.g.,total update quantity,total quantity of updated IP prefix)from all used monitors.In this way,the difference between the data from different monitors are ignored.However,according to the features of BGP,the dynamics observed by each individual monitor could be highly localized.Therefore proposing methods and algorithms based on aggregated data may lead to misunderstanding BGP dynamics.Based on the discussion,we propose a method for detecting large-scale BGP instability events;it is a per-monitor method.The research content and contributions include:(1)Quantitatively analyze the distribution of BGP dynamics and the updates for traditional active prefixes.We find that the distribution of BGP dynamics is highly unbalanced.In particular,dynamics reflecting pathological behaviors are extremely highly localized.Moreover,the updates for a large portion of traditional active prefixes are highly localized.This dissertation proposes the concept of update visibility.Combined with update quantity,we define five types of active prefixes.We analyze the quantity trend,and the correlation between different types,etc.The measurement results show that using per-monitor method to measure BGP is important.(2)We propose the concept of large-scale BGP event(LBE).An LBE meets two conditions:visible to a large portion of the Internet,and affects a high quantity of prefixes.To depict LBE,we raise the concept of update visibility matrix.We formalize the problem of detecting LBE and prove it is NP-hard.Then we devise the GDA algorithm to solve it.We apply this method to a large amount of BGP updates.The measurement results show that some famous disruptive events in the Internet are significantly related to the detected LBEs.Besides,the method detects 101 LBEs that have remained unreported within 10 months in the 2013 dataset.(3)We raise a series of methods(major element analysis,AS path change analysis,Community change analysis,etc)to analyze the root cause and influence of an LBE.These methods are based on the type and content of BGP updates,as well as BGP routing tables and BGP community attributes' semantic data.We use these methods to deeply analyze 23 out of the LBEs detected in the 2013 dataset.(4)To accomplish the aforementioned measurement tasks,we develop an inter-domain dynamics measurement system.This system is able to handle TBs of data.It is robust because it has considered various anomalous situations.Besides,multi-aspect optimization makes this system suitable for measurement works where memory and computing resources are limited.