Below are three possible MSc projects at NLnet Labs (Amsterdam; but working most of the time in Twente may be possible). Contact person for these assignment at the UT is Pieter-Tjerk de Boer, p.t.deboer@utwente.nl . ----------------------------------------------------------------------- ==================== MSC. PROJECT I ==================== Analysis of Growth and Stability of the Internet Routing Infrastructure Problem Description ------------------- Inter-domain routing in the Internet takes place between autonomous routing domains, also known as autonomous systems (AS). In the Internet, an autonomous system is a collection of IP networks and routers under the control of one entity (e.g., company, organization, Internet Service Providers (ISPs), ...) that presents a common routing policy to the Internet. Inter-domain routing is implemented using the Border Gateway Protocol (BGP), which exchanges reachability information within and between autonomous systems. Effectively, BGP is a peer-to-peer protocol that distributes routing information and keeps routing tables up-to-date. Although BGP's fairly simple principle of exchanging information, the protocol shows complex behavior. A subject that puzzles network researchers for sometime now is the "flatness of BPG". In the past 10 years, the growth of the Internet (in AS networks and IP prefixes) showed some exponential trends. In the same period, the number of prefixes updates per day has remained almost constant. This is very fortunate, although the size of the Internet doubled, we still receive the same number of updates per time period, which doesn't burn the hardware of today. Project Plan ------------ As a first step to deepen our understanding of the problem, a (simulation) model for Internet inter-domain routing has been developed. The model and simulation has been developed in a previous MSc. project. To understand and explain the "flatness of BGP", it would be very interesting to analyse and test some hypotheses on the BGP simulator we have developed over the years with help from VU MSc. students. The observation of stable number of prefix updates (constant background noise) was first made by Geoff Huston, Chief scientist of APNIC. Questions that arise: are the unstable prefixes a fixed set of prefixes, are they equally noisy; and what are the characteristics of this "noise"? Why hasn't the number of unstable prefixes grown in line with the growth in the table size? What is limiting this behaviour of the routing system? Why 20-50K unstable prefixes per day? Why not 100K? Or 5K? What is bounding this observed behaviour? Answers to these questions may give insight in the fundamental scalability and stability characteristics of the current Internet. Given the project results and analysis of the observations, we can aim for a publication in a conference proceeding or a journal. APNIC chief scientist Geoff Huston (an acclaimed expert in this area) has a personal interest in this topic, and is willing to collaborate or help with studying and analysing the problem. ==================== MSC. PROJECT II ==================== Modeling and Analysis of Hierarchical Networks with Byzantine Robustness Problem Description ------------------- In a paper by Radia Perlman and Charlie Kaufman [1], a hierarchical model for networks with Byzantine robustness is presented. This model extends previous work on network protocols resilient to Byzantine failures, that guarantee that nodes A and B can communicate, provided that at least one honest path connects them. The hierarchical model scales to large networks and additionally to guaranteed delivery of packets with some fair bandwidth, it also has the ability to limit the number of simultaneous sources it is receiving from and limit receipt of traffic to the rate at which the destination is capable to process. Project Plan ------------ In the hierarchical network model with Byzantine robustness, management of the switch/router resources is required to provide the guarantees of packet delivery and traffic rate limit on a per-flow basis. This flow resource management is important to achieve both the above defined guarantees and the scalability of the model to large networks. To assess the scalability behavior, and the packet delivery and rate limiting guarantees, a simulation model of the hierarchical network with Byzantine robustness (HNBR) can be developed. With this simulation model different strategies can be evaluated, for example using metrics like efficiency and effectiveness, the scalability of the approach for different network sizes and topologies (network hierarchies), etc. In the project we aim for a conference/journal publication in collaboration with Radia Perlman. This of course, given the obtained project results and analysis. References ---------- [1] Radia Perlman and Charlie Kaufman, "Hierarchical Networks with Byzantine Robustness", COMSNETS 2011. ==================== MSC. PROJECT III ==================== Load Splitting of Network Traffic Flows (Multipath Routing) Problem Description ------------------- Currently, we are in a situation where the network tries to keep packets in order. Although out-of-order packet receipt shouldn't be a problem for IP layer 3 protocols, e.g., TCP could handle this, bad performance or actually failure (?) can be a result. Still for performance, we want to spread traffic among lots of paths. There are various strategies for keeping packets in order over parallel paths. One of the more successful approaches identifies (TCP) flows and switches forward packets within a flow to the same port interface. Project Plan ------------ Flow-based forwarding in switches/routers is based on (destination, source, protocol type, TCP ports) tuples in the forwarding table. There is a claim that for better spreading of traffic load, a central entity knows what all the flows are, such that it can carefully place them. However, given the highly dynamic behavior of traffic volumes, it seems that switches are in a better position to load-split traffic than a central fabric manager. The switch can split path based on local queues and congestion, and can rehash the flows to spread the load. To evaluate, compare, and understand the traffic utilization for different load split strategies, a simulation model and implementation has to be realized. With the simulation, the alternatives of the perfect knowledge central entity, and the various (more) distributed flow load splitting strategies can be evaluated and analyzed. Interesting question is whether local queue information is sufficient, or do we need 1 hop or n hop congestion information? There are costs incurred to find out congestion information n hops away.