Inhalt des Dokuments
Topics for the Seminar on Internet Routing, WS 2010/11
Topics for the seminar on Internet Routing (WS
Themen für das Seminar über Internet Routing (WS 2010/11) .
- 4 — Metarouting
- 7 — Ant colonies for Adaptive Routing in Packet-switched Communications Networks
- 8 — Analytical and Numerical Investigation of Ant Behavior Under Crowded Conditions
- 11 — APT: A Practical Tunneling Architecture for Routing Scalability
- 13 — Incentive-Compatible Opportunistic Routing for Wireless Networks
- 18 — An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol
- 19 — A Measurement-based Study of the Skype Peer-to-Peer VoIP Performance
- 26 — Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-Peer Games
- 27 — Hierarchical structure and the prediction of missing links in networks
4 — Metarouting
Student/Bearbeiter: Matthias Rost;
Supervisor/Betreuer: Luigi Iannone
There is a shortage of routing protocols that meet the needs of network engineers. This has led to BGP being pressed into service as an IGP, despite its lack of convergence guarantees. The development, standardization, and deployment of routing protocols, or even minor changes to existing protocols, are very difficult tasks. We present an approach called Metarouting that defines routing protocols using a high-level and declarative language. Once an interpreter for a metarouting language is implemented on a router, a network operator would have the freedom to implement and use any routing protocol definable in the language. We enforce a clean separation of protocol mechanisms (link-state, path-vector, adjacency maintenance, and so on) from routing policy (how routes are described and compared). The Routing Algebra framework of Sobrinho  is used as the theoretical basis for routing policy languages. We define the Routing Algebra Meta-Language (RAML) that allows for the construction of a large family of routing algebras and has the key property that correctness conditions—guarantees of convergence with respect to the chosen mechanisms—can be derived automatically for each expression defining a new routing algebra.
- Timothy G. Griffin, Joao Luis Sobrinho. Metarouting . Sigcomm 2005.
7 — Ant colonies for Adaptive Routing in Packet-switched Communications Networks
Bystrov; Supervisor/Betreuer: Steve Uhlig
It is well-known that BGP, the current inter-domain routing protocol, has many deficiencies. This paper describes a hybrid link-state and path-vector protocol called HLP as an alternative to BGP that has vastly better scalability, isolation and convergence properties. Using current BGP routing information, we show that HLP, in comparison to BGP, can reduce the churn-rate of route updates by a factor 400 as well as isolate the effect of routing events to a region 100 times smaller than that of BGP. For a majority of Internet routes, HLP guarantees worst-case linear-time convergence. We also describe a prototype implementation of HLP on top of the XORP router platform. HLP is not intended to be a finished and final proposal for a replacement for BGP, but is instead offered as a starting point for debates about the nature of the next-generation inter-domain routing protocol.
- Gianni Di Caro, Marco Dorigo. Ant colonies for Adaptive Routing in Packet-switched Communications Networks . Lecture Notes in Computer Science 1998
8 — Analytical and Numerical Investigation of Ant Behavior Under Crowded Conditions
Student/Bearbeiter: Mirko Romano Palmer;
Supervisor/Betreuer: Benjamin Frank
Swarm intelligence is widely recognized as a powerful paradigm of self-organized optimization, with numerous examples of successful applications in distributed artificial intelligence. However, the role of physical interactions in the organization of traffic flows in ants under crowded conditions has only been studied very recently. The related results suggest new ways of congestion control and simple algorithms for optimal resource usage based on local interactions and, therefore, decentralized control concepts. Here, we present a mathematical analysis of such a concept for an experiment with two alternative ways with limited capacities between a food source and the nest of an ant colony. Moreover, we carry out microscopic computer simulations for generalized setups, in which ants have more alternatives or the alternative ways are of different lengths. In this way and by variation of interaction parameters, we can get a better idea, how powerful congestion control based on local repulsive interactions may be. Finally, we will discuss potential applications of this design principle to routing in traffic or data networks and machine usage in supply systems.
- Karsten Peters, Anders Johansson, Audrey Dussutour, Dirk Helbing. Analytical and Numerical Investigation of Ant Behavior Under Crowded Conditions . 2006
11 — APT: A Practical Tunneling Architecture for Routing Scalability
Student/Bearbeiter: Philipp Richter;
Supervisor/Betreuer: Luigi Iannone
The routing table has seen a rapid increase in size and dynamics in recent years, mostly driven by the growth of edge networks. This growth reflects two major limitations in the current architecture: (a) the conflict between provider-based addressing and edge networks' need for multihoming, and (b) flat routing's inability to provide isolation from edge dynamics. To address these limitations, we propose A Practical Tunneling Architecture (APT), a new routing architecture that enables the Internet routing system to scale independently from edge growth. APT partitions the Internet address space in two, one for the transit core and one for edge networks, allowing edge addresses to be removed from the routing table in the transit core. In order to tunnel packets between edge networks, APT provides an efficient mapping service between edge addresses and the addresses of their transit-core attachment points. We conducted an extensive performance evaluation of APT using trace data collected from routers at two major service providers. Our results show that APT can tunnel packets through the transit core by imposing a minimal delay on no more than 0.8% of all packets at the cost of introducing only one or a few new or repurposed devices per AS.
- Dan Jen, Michael Meisel, Dan Massey, Lan Wang, Beichuan Zhang, and Lixia Zhang. APT: A Practical Tunneling Architecture for Routing Scalability . UCLA Computer Science Dept. Technical Report #080004
13 — Incentive-Compatible Opportunistic Routing for Wireless Networks
Steinicke; Supervisor/Betreuer: Ruben Merz
User-contributed wireless mesh networks are a disruptive technology that may fundamentally change the economics of edge network access and bring the benefits of a computer network infrastructure to local communities at low cost, anywhere in the world. To achieve high throughput despite highly unpredictable and lossy wireless channels, it is essential that such networks take advantage of transmission opportunities wherever they emerge. However, as opportunistic routing departs from the traditional but less effective deterministic, shortest-path based routing, user nodes in such networks may have less incentive to follow protocols and contribute. In this paper, we present the first routing protocols in which it is incentive-compatible for each user node to honestly participate in the routing despite opportunistic transmissions. We not only rigorously prove the properties of our protocols but also thoroughly evaluate a complete implementation of our protocols. Experiments show that there is a 5.8%–58.0% gain in throughput when compared with an opportunistic routing protocol that does not provide incentives and users can act selfishly.
- Fan Wu, Tingting Chen, and Sheng Zhong (SUNY at Buffalo, USA); Li (Erran) Li (Bell Labs, Lucent Technologies, USA); and Y. Richard Yang (Yale University, US). Incentive-Compatible Opportunistic Routing for Wireless Networks .
18 — An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol
Student/Bearbeiter: Danish Samiullah;
Supervisor/Betreuer: Amir Mehmood
Skype is a peer-to-peer VoIP client developed by KaZaa in 2003. Skype claims that it can work almost seamlessly across NATs and firewalls and has better voice quality than the MSN and Yahoo IM applications. It encrypts calls end-to-end, and stores user information in a decentralized fashion. Skype also supports instant messaging and conferencing.
This report analyzes key Skype functions such as login, NAT and firewall traversal, call establishment, media transfer, codecs, and conferencing under three different network setups. Analysis is performed by careful study of Skype network traffic.
- Salman A. Baset and Henning Schulzrinne. An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol . 2004
19 — A Measurement-based Study of the Skype Peer-to-Peer VoIP Performance
Student/Bearbeiter: Theresa Enghardt;
Supervisor/Betreuer: Juhoon Kim
It has been increasingly popular to build voiceoverIP (VoIP) applications based on peertopeer (P2P) networks in the Internet. However, many such VoIP applications freeride the network bandwidth of Internet Service Providers (ISPs). Thus their success may come at a cost to ISPs, especially those on the edge of the Internet. In this paper, we study the VoIP quality of Skype, a popular P2Pbased VoIP application. Specifically, using largescale endtoend measurements, we first conduct a systematic analysis of Skype supernode network. We then investigate the impacts of the access capacity constraint and the AS policy constraint on the VoIP quality of Skype. We show that even when freeriding is no longer possible for only 20% of supernodes that are located in stub ISPs, the overall VoIP quality of Skype degrades significantly, and a large percentage of VoIP sessions will have unacceptable quality. This result clearly demonstrates the potential danger of building VoIP applications based on P2P networks without taking into account operational models of the Internet. We also study using time diversity in traffic patterns to reduce the impacts of the preceding constraints.
- Haiyong Xie, Yang Richard Yang. A Measurement-based Study of the Skype Peer-to-Peer VoIP Performance . IPTPS 2007
26 — Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-Peer Games
Student/Bearbeiter: Hannes Fiedler
Supervisor/Betreuer: Juhoon Kim
Without well-provisioned dedicated servers, modern fast-paced action games limit the number of players who can interact simultaneously to 16–32. This is because interacting players must frequently exchange state updates, and high player counts would exceed the bandwidth available to participating machines. In this paper, we describe Donnybrook, a system that enables epicscale battles without dedicated server resources, even in a fastpaced game with tight latency bounds. It achieves this scalability through two novel components. First, it reduces bandwidth demand by estimating what players are paying attention to, thereby enabling it to reduce the frequency of sending less important state updates. Second, it overcomes resource and interest heterogeneity by disseminating updates via a multicast system designed for the special requirements of games: that they have multiple sources, are latency-sensitive, and have frequent group membership changes. We present user study results using a prototype implementation based on Quake III that show our approach provides a desirable user experience. We also present simulation results that demonstrate Donnybrook's efficacy in enabling battles of up to 900 players.
- Ashwin Bharambe, John R. Douceur, Jacob R. Lorch, Thomas Moscibroda, Jeffrey Pang, Srinivasan Seshan, and Xinyu Zhuang. Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-Peer Games .
27 — Hierarchical structure and the prediction of missing links in networks
Spartinou; Supervisor/Betreuer: Giles Trédan
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (protein interaction networks, metabolic networks, or genetic regulatory networks), or communities in social networks. Here we present a general technique for inferring hierarchical structure from network data and demonstrate that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right-skewed degree distributions, high clustering coefficients, and short path lengths. We further show that knowledge of hierarchical structure can be used to predict missing connections in partially known networks with high accuracy, and for more general network structures than competing techniques. Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.
- Aaron Clauset,
Cristopher Moore, M.E.J. Newman. Hierarchical structure and the
prediction of missing links in networks .