Eine Anmeldung ist nicht mehr möglich.
Hier die Einteilung nach den neuen Themenblöcken:
Bearbeiter: Yue Zhao
Betreuer: Vinay Aggarwal
The limitations of BGP routing in the Internet are often blamed for poor end-to-end performance and prolonged connectivity interruptions. Recent work advocates using overlays to effectively bypass BGP's path selection in order to improve performance and fault tolerance. In this paper, we explore the possibility that intelligent control of BGP routes, coupled with ISP multihoming, can provide competitive end-to-end performance and reliability. Using extensive measurements of paths between nodes in a large content distribution network, we compare the relative benefits of overlay routing and multihoming route control in terms of round-trip latency, TCP connection throughput, and path availability. We observe that the performance achieved by route control together with multihoming to three ISPs (3-multihoming), is within 5-15% of overlay routing employed in conjunction 3-multihoming, in terms of both end-to-end RTT and throughput. We also show that while multihoming cannot offer the nearly perfect resilience of overlays, it can eliminate almost all failures experienced by a singly-homed end-network. Our results demonstrate that, by leveraging the capability of multihoming route control, it is not necessary to circumvent BGP routing to extract good wide-area performance and availability from the existing routing system.
Bearbeiter: Philipp Langer
Betreuer: Nils Kammenhuber
Empirical evidence suggests that reactive routing systems improve resilience to Internet path failures. They detect and route around faulty paths based on measurements of path performance. This paper seeks to understand why and under what circumstances these techniques are effective.
To do so, this paper correlates end-to-end active probing experiments, loss-triggered traceroutes of Internet paths, and BGP routing messages. These correlations shed light on three questions about Internet path failures: (1) Where do failures appear? (2) How long do they last? (3) How do they correlate with BGP routing instability?
Data collected over 13 months from an Internet testbed of 31 topologically diverse hosts suggests that most path failures last less than fifteen minutes. Failures that appear in the network core correlate better with BGP instability than failures that appear close to end hosts. On average, most failures precede BGP messages by about four minutes, but there is often increased BGP traffic both before and after failures. Our findings suggest that reactive routing is most effective between hosts that have multiple connections to the Internet. The data set also suggests that passive observations of BGP routing messages could be used to predict about 20% of impending failures, allowing re-routing systems to react more quickly to failures.
Measuring the Effects of Internet Path Faults on Reactive
Routing
Nick Feamster, David G. Andersen, Hari Balakrishnan, M. Frans
Kaashoek
ACM SIGMETRICS, San Diego, CA, June 2003.
http://nms.lcs.mit.edu/papers/failures-sigm2003.pdf
Bearbeiter: Steffen Bergmann
Betreuer: Jörg Wallerich
The Border Gateway Protocol (BGP) has two distinct modes of operation.\x{FFFD} External BGP (EBGP) exchanges reachability information between autonomous systems, while Internal BGP (IBGP) exchanges external reachability information within an autonomous system. We study several routing anomalies that are unique to IBGP because, unlike EBGP, forwarding paths and signaling paths are not always symmetric. In particular, we focus on anomalies that can cause the protocol to diverge, and those that can cause a router's chosen forwarding path to an egress point to be deflected by another router on that path. Deflections can greatly complicate the debugging of routing problems, and in the worst case multiple deflections can combine to form persistent forwarding loops. We define a correct IBGP configuration to be one that is anomaly free for every possible set of routes sent by neighboring autonomous systems. We show that determination of IBGP configuration correctness is NP-hard. However, we give simple sufficient conditions on network configurations that guarantee correctness.
On the correctness of IBGP configuration
Timothy G. Griffin, Gordon Wilfong
ACM SIGCOMM 2002 Computer Communication Review
http://www.acm.org/sigs/sigcomm/sigcomm2002/papers/ibgp.pdf
Bearbeiter: Daniel Weber
Betreuer: Olaf Maennel
This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are ``ideal'', we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.
Locating Internet Routing Instabilities
Anja Feldmann (TU München), Olaf Maennel (TU München),
Z. Morley Mao (U. Michigan), Arthur Berger (MIT/Akamai), Bruce Maggs
(CMU/Akamai)
Proceedings of Sigcomm 2004
http://www.acm.org/sigs/sigcomm/sigcomm2004/papers/p479-feldmann11.pdf
Bearbeiter: Gunnar Bornemann
Betreuer: Holger Dreger
The Domain Name System (DNS) is an essential part of the Internet infrastructure and provides fundamental services, such as translating host names into IP addresses for Internet communication. The DNS is vulnerable to a number of potential faults and attacks. In particular, false routing announcements can deny access to the DNS service or redirect DNS queries to a malicious impostor. Due to the hierarchical DNS design, a single fault or attack against the routes to any of the top level DNS servers can disrupt Internet services to millions of users. In this paper we propose a path- ltering approach to protect the routes to the critical top level DNS servers. Our approach exploits the high degree of redundancy in top level DNS servers and also exploits the observation that popular destinations, including top level DNS servers, are well connected via stable routes. Our path- lter restricts the potential top level DNS server route changes to be within a set of established paths. Heuristics derived from routing operations are used to adjust the potential routes over time. We tested our path- ltering design against BGP routing logs and the results show that the design can effectively ensure correct routes to top level DNS servers without impacting DNS service availability.
Protecting BGP Routes to Top Level DNS Servers
Lan Wang, Xiaoliang Zhao, Dan Pei, Randy Bush, Daniel Massey, Allison
Mankin, S. Felix Wu, Lixia Zhang
May 2003, Proceedings of the 23rd International Conference on
Distributed Computing Systems
http://www.cs.colostate.edu/~massey/pubs/conf/massey_icdcs03.pdf
Bearbeiter: Florian Bichlmaier
Betreuer: Robin Sommer
Internet end users and ISPs alike have little control over how packets are routed outside of their own AS, restricting their ability to achieve levels of performance, reliability, and utility that might otherwise be attained. While researchers have proposed a number of source-routing techniques to combat this limitation, there has thus far been no way for independent ASes to ensure that such traffic does not circumvent local traffic policies, nor to accurately determine the correct party to charge for forwarding the traffic. We present Platypus, an authenticated source routing system built around the concept of network capabilities. Network capabilities allow for accountable, fine-grained path selection by cryptographically attesting to policy compliance at each hop along a source route. Capabilities can be composed to construct routes through multiple ASes and can be delegated to third parties. Platypus caters to the needs of both end users and ISPs: users gain the ability to pool their resources and select routes other than the default, while ISPs maintain control over where, when, and whose packets traverse their networks. We describe how Platypus can be used to address several well-known issues in wide-area routing at both the edge and the core, and evaluate its performance, security, and interactions with existing protocols. Our results show that incremental deployment of Platypus can achieve immediate gains.
A System for Authenticated Policy-Compliant Routing
Barath Raghavan (UCSD), Alex C. Snoeren (UCSD)
Proceedings of SIGCOMM 2004
http://www.cs.ucsd.edu/~snoeren/papers/platypus-sigcomm04.pdf
Bearbeiter: Andreas Klinger
Betreuer: Gert Döring <gert (at) net.in.tum.de>
The desire to better understand global BGP dynamics has motivated several studies using active measurement techniques, which inject announcements and withdrawals of prefixes from the global routing domain. From these one can measure quantities such as the BGP convergence time. Previously, the route injection infrastructure of such experiments has either been temporary in nature, or its use has been restricted to the experimenters. The routing research community would benefit from a permanent and public infrastructure for such active probes. We use the term BGP Beacon to refer to a publicly documented prefix having global visibility and a published schedule for announcements and withdrawals. A BGP Beacon is to be used for the ongoing study of BGP dynamics, and so should be supported with a long-term commitment. We describe several BGP Beacons that have been set up at various points in the Internet. We then describe techniques for processing BGP updates when a BGP Beacon is observed from a BGP monitoring point such as Oregon s Route Views. Finally, we illustrate the use of BGP Beacons in the analysis of convergence delays, route flap damping, and update inter-arrival times.
BGP beacons
Z. Morley Mao, Randy Bush, Timothy G. Griffin, Matthew Roughan
Proceedings of the 2003 ACM SIGCOMM conference on Internet
measurement
http://www.eecs.umich.edu/~zmao/Papers/beacon.pdf
Bearbeiter: Harald Schiöberg
Betreuer: Olaf Maennel
Traceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to researchers and network operators. However, conventional approaches to mapping traceroute hops to AS numbers are not accurate enough. Address registries are often incomplete and out-of-date. BGP routing tables provide a better IP-to-AS mapping, though this approach has significant limitations as well. Based on our extensive measurements, about 10% of the traceroute paths have one or more hops that do not map to a unique AS number, and around 15% of the traceroute AS paths have an AS loop. In addition, some traceroute AS paths have extra or missing AS hops due to Internet eXchange Points, sibling ASes managed by the same institution, and ASes that do not advertise routes to their infrastructure. Using the BGP tables as a starting point, we propose techniques for improving the IP-to-AS mapping as an important step toward an AS-level traceroute tool. Our algorithms draw on analysis of traceroute probes, reverse DNS lookups, BGP routing tables, and BGP update messages collected from multiple locations. We also discuss how the improved IP-to-AS mapping allows us to home in on cases where the BGP and traceroute AS paths differ for legitimate reasons.
Towards an Accurate AS-Level Traceroute Tool
Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy Katz
ACM SIGCOMM 2003
http://www.acm.org/sigs/sigcomm/sigcomm2003/papers/p365-mao.pdf
Bearbeiter: Hao Qin
Betreuer: Vlad Manilici <vman at net.in.tum.de>
GNUnet ist ein System(unterbau) für ein sicheres Peer-to-Peer-Netzwerk. Eine der Hauptanwendungen, die auf GNUnet implementiert wurden, ist ein anonymes, vor Zensur geschütztes Filesharing. Das Ziel des GNUnet-Projektes ist die Verfügbarkeit einer sicheren Peer-to-Peer-Infrastruktur. Die gesamte Kommunikation in GNUnet wird authentifiziert und erfolgt über verschlüsselte Verbindungen. Das ökonomische Modell macht Angriffe auf das Netzwerk schwieriger, weil die Ökonomie benutzt werden kann, um den Ressourcenverbrauch zu steuern.
Bearbeiter: Benjamin Gufler
Betreuer: Arne Wichmann
We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.
Routing in a Delay Tolerant Network
Sushant Jain (U. Washington), Kevin Fall (Intel Research), Rabin Patra
(UC Berkeley)
Proceedings of Sigcomm 2004
http://www.acm.org/sigs/sigcomm/sigcomm2004/papers/p299-jain111111.pdf
Bearbeiter: Bernhard Amann
Betreuer: Dr. Manfred Jobmann
The phenomenon that rural residents and people with low incomes lag behind in Internet access is known as the ``digital divide.'' This problem is particularly acute in developing countries, where most of the world's population lives. Bridging this digital divide, especially by attempting to increase the accessibility of broadband connectivity,can be challenging. The improvement of wide-area connectivity is constrained by factors such as how quickly we can dig ditches to bury fibers in the ground; and the cost of furnishing "last-mile" wiring can be prohibitively high. In this paper, we explore the use of digital storage media transported by the postal system as a general digital communication mechanism. While some companies have used the postal system to deliver software and movies, none of them has turned the postal system into a truly generic digital communication medium supporting a wide variety of applications. We call such a generic system a Postmanet. Compared to traditional wide-area connectivity options, the Postmanet has several important advantages, including wide global reach, great bandwidth potential and low cost. Manually preparing mobile storage devices for shipment may appear deceptively simple, but with many applications, communicating parties and messages, manual management becomes infeasible, and systems support at several levels becomes necessary. We explore the simultaneous exploitation of the Internet and the Postmanet, so we can combine their latency and bandwidth advantages to enable sophisticated bandwidth-intensive applications.
Turning the Postal System into a Generic Digital Communication
Mechanism
Randolph Y. Wang (Princeton), Sumeet Sobti (Princeton), Nitin Garg (Princeton), Elisha Ziskind (Princeton), Junwen
Lai (Princeton), Arvind Krishnamurthy (Yale)
Proceedings of Sigcomm 2004
http://www.acm.org/sigs/sigcomm/sigcomm2004/papers/p402-wang.pdf
Zur... [Seminar-Homepage] [Lehrstuhl-Homepage]