The Internet is literally an “Inter-Network”, that is, a network of networks. Networks can be entities including Internet Service Providers (ISPs), universities and commercial enterprises. Every network or Autonomous System (AS) has individual requirements, restrictions and capabilities to transit data traffic. No central controlling body determines how ASes connect—instead contractual agreements are established between AS pairs to govern their relationship. It is not feasible for all ASes to be physically connected to all others. Consequently, some ASes provide transit between other ASes. Such a service usually results in remuneration from one or both ASes. Unlike centrally administered networks where all nodes in the network make generic, predictable decisions, each AS has the ability to select its best route based on its own proprietary commercial agreements. Such agreements are converted to a technical policy implemented in the Border Gateway Protocol (BGP). The ability to implement policies ensures the commercial viability of the Internet, but also makes the prediction of routes difficult and even more worrisome, conflicting policies can cause undesirable BGP states where no single AS has sufficient knowledge to understand what is happening [43]. Designing new clean-slate routing protocols is one approach to improving the predictability and reliability of the Internet. However, due to the Internet’s distributed political and administrative control, significant collaboration is required to implement a new routing protocol — especially when no new protocol currently proposed has sufficiently superior flexibility, scalability or robustness. The difficulty in implementing new and improved protocols is evident in the deployment of IPv6 [23]. Although the IPv6 standard has been defined for over a decade and offers a larger address space, better security and embedded quality of service in comparison to traditional IPv4, its deployment is limited to 1200 of over 30000 ASes in the Internet [66]. Hence, it is crucial practical solutions to current problems are evolved in addition to developing clean-slate techniques. Consequently, our approach is pragmatic — designing tangible solutions to practical problems that can be implemented immediately. In this thesis we examine and combine eBGP, iBGP, OSPF, Netflow and router configuration data to discover important aspects of routing. It is this investigation that instigated the development of a model of iBGP. iBGP is the version of BGP implemented within ASes to propagate routes between internal routers. It exists on a logical topology, however it interacts with the physical topology. It is this interaction which can cause persistent oscillation [49] — a system state where routers alter their decision ad infinitum. Detecting configurations which can cause this oscillation is NP-hard [49]. However, our model of iBGP introduced in this thesis benefits from the ‘designed’ structure of the iBGP topology to restrict the search space dramatically to one that is computationally feasible. iBGP data — which is collected to analyze router decisions — is often only collected on a subset of routers due to its massive storage requirements. In addition there is a substantial amount of correlation between router decisions. Our model of iBGP discovers the dependencies between router decisions and can consequently predict the decisions of those routers for which no measurements are available. It does not rely on any assumption of operator configuration, and subsequently is able to be applied in any network scenario — not just the one originally configured. It is this feature, together with the model’s ability to use any available measurement data that makes our technique ideal for network measurement and management applications. We found our model is efficient and accurate on the network of a large Tier-2 AS, where all but seven of over 12:7 million decisions were consistent with observed data. Further we were able to predict the decision of 85% of routers where observed data was unavailable. During our analysis, we also identified several minor configuration errors on operational routers when we predicted the “correct” outcome. The internal state of a network can be influenced by neighboring ASes. Peering agreements are closely guarded due to their commercially sensitivity. They are implemented in BGP in the form of policies and are difficult to infer with publicly available data sources. We examined the peering policies of over 100 ASes from the perspective of a large Tier-2 AS, finding 22% differ from the canonical peering policy outlined in many peering agreements. When a policy differes from the canonical peering policy, it may result in sub-optimal routing within the Tier-2 AS. We used our model of iBGP to firstly predict the decisions of all routers under the current peering policy, before determining the changes that would have occurred under a canonical peering policy. This analysis not only provided a metric for the routing impact of a peers’ non-canonical policy, but subsequently used in combination with traffic data allowed us to determine the influence of the peer on traffic flows. Our techniques described allow an AS to fully quantify the impact of a non-canonical peering policy and adapt business arrangements appropriately. Throughout our analysis of BGP data, we noticed several inconsistencies in the data. Although the results in the above work were insensitive to such inconsistencies, other applications requiring accurate, fine time-scale analysis of the routing state are much more sensitive. Consequently, we undertake a self-consistency check on the BGP data and examine the possible causes of such inconsistencies. We also present a mechanism to ‘clean’ the data to minimize the effects of any inconsistency. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1459175 / Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Science, 2009