Skip content, jump to navigation.

Network Architectures: Internet Measurement (Seminar)

News / Aktuelles

up top

Agenda

Mittwoch, 25. Feb. 2009
10:00–10:15 Willkommen
10:17–10:40 A.1 Characterizing Files in the Modern Gnutella Network: A Measurement Study
Student/Bearbeiter: Xiaotai Yu [Ausarbeitung], [Präsentation]
10:56–11:23 A.2 Rarest First and Choke Algorithms Are Enough
Student/Bearbeiter: Björn Kalk [Ausarbeitung], [Präsentation]
11:40–13:05 Mittagspause
13:05–13:32 A.3 Leveraging BitTorrent for End Host Measurements
Student/Bearbeiter: Ralf Stange [Ausarbeitung], [Präsentation]
13:45–14:06 D.1 Unconstrained Endpoint Profiling (Googling the Internet)
Student/Bearbeiter: Florian Haemmerling [Ausarbeitung], [Präsentation]
14:23–14:45 D.4 I Tube, You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System
YouTube Traffic Characterization: A View From the Edge
Student/Bearbeiter: Irina Antonova [Ausarbeitung], [Präsentation]
15:01–15:27 B.2 The Flattening Internet Topology: Natural Evolution, Unsightly Barnacles or Contrived Collapse?
Student/Bearbeiter: Philipp Richter [Ausarbeitung], [Präsentation]
bis 15:41
Donnerstag, 26. Feb. 2009
13:00–13:45 D.3 nCap: Wire-speed Packet Capture and Transmission
Improving Passive Packet Capture: Beyond Device Polling
Student/Bearbeiter: Mohannad Alnablsi [Ausarbeitung], [Präsentation]
13:45–14:30 B.1 DisCarte: A Disjunctive Internet Cartographer
Student/Bearbeiter: Sebastian Schlunke [Ausarbeitung], [Präsentation]
Anschließend Diskussion über Vorträge allgemein – bis ca. 16:00

up top

Overview / Überblick

lecturer / Dozentin: Prof. Anja Feldmann, Ph.D.
Contact Person / Ansprechpartner: Olaf Maennel
event type / Veranstaltungstyp: advanced seminar / Hauptseminar
area / Gebiet: Operating and Communication Systems / Betriebs- und Kommunikationssysteme (BKS)
SWS: 2
ECTS / LP: 3
Time / Zeit: 25\26 Feb. 2009, 10:00 Uhr
Room / Raum: MA 841
Course ID / Veranstaltungsnr.: 0432 L 822
Audience / Hörerkreis main course students / Hauptstudium
Prerequisites / Voraussetzungen: intermediate diplom, profound knowledge in computer networks, good english for reading scientific papers /
Vordiplom, tiefgehendes Wissen in Rechnernetzen, gutes Englisch, um wissenschaftliche Artikel zu lesen
Exam / Prüfung: talk and paper / Vortrag und Ausarbeitung
Preparatory Meeting / Vorbesprechung: Fr, 17. Oct. 2008, 12:00 p.m. (noon)
Room: Auditorium 2, Ernst-Reuter-Platz 7 (Telefunkenhochhaus), 20th Floor/20. Stock
Deadline for Registration / Anmeldung : abgelaufen
(You are required to attend the preparation meeting 17.10., 12 p.m. / Anwesenheitspflicht bei der Vorbesprechung am 17.10., 12 Uhr)

Content / Inhalt

The Internet influences our life more and more: Many of us use electronic mail instead of writing with pen and paper; homebanking and ordering books over the web are in everyday life. Furthermore, the interconnectedness gets denser and the day is near when every coffee maker is programmable through the internet and every car connects to its manufacturer for diagnosis.

This seminar deals with recent findings and scientific research papers concerning Internet measurement. In general these topics are measuring and analysing special characteristics (e.g. throughput, delay, jitter, RTTs, topology) of Internet traffic.

Das Internet gewinnt mehr und mehr Einfluss in unserem Leben: Für viele von uns haben E-Mails Briefe aus Papier ersetzt; Homebanking und der Kauf von Büchern übers Web gehört zum Alltag. Zudem wird die Vernetzung immer dichter und der Tag ist nah, an dem jede Kaffeemachine übers Internet programierbar ist und jedes Auto sich übers Netz zu Diagnosezwecken mit dem Hersteller in Verbindung setzt.

Dieses Seminar behandelt aktuelle Erkenntnisse und wissenschaftliche Arbeiten zum Thema Internet Measurement. Hier geht es generell um Messungen von speziellen Charakteristiken des Internet (z.B. Durchsatz, Delay, Jitter, RTT, Topologie) bzw. dessen Verkehrs.

up top

Organisation

Intention of the seminar

  • practice to work with original literature

  • practice of professional/scientific talks

  • occupation with a small, definite and recent matter

General Guidelines

  • What is done as team work?

  • What is required for the paper?

  • What has to be considered for the talk and while writing the slides?

  • Hints for translations from english to german.

  • Criteria for the "Schein" (certificate).

Seminar certificate

To receive the seminar certificate we demand:

  • a successfull presentation/talk

  • a seminar paper accepted by us

  • continuous attendence and active participation and contribution (in the group meetings as well as during the presentations)

The seminar certificate will have a grade, which will be made from above mentioned criteria.

Zweck des Seminars

  • Übung des Umgangs mit Orginalliteratur

  • Übung von fachlichen Vorträgen

  • Beschäftigung mit einem kleinen, klar abgegrenzten und aktuellen Stoffgebiet

Allgemeine Richtlinien

Seminar Schein

Zum Seminar wird ein Schein vergeben. Wir erwarten dafür konkret:

  • erfolgreicher Vortrag

  • von uns akzeptierte Ausarbeitung

  • durchgängige Teilnahme mit aktiver Mitarbeit (sowohl in den Gruppentreffen als auch am eigentlichen Seminar)

Es werden benotete Scheine ausgestellt, wobei die Note sich aus den obigen Komponenten zusammensetzt.

up top

(Preliminary) schedule / (Vorläufiger) Zeitplan

When/Wann? What? Was? Time need /
Aufwand?
17.10.2007, 12:00 Preparatory Meeting: Presentation of the supervisors, topic groups and topics Vorbesprechung: Vorstellung der Betreuer, Themengruppen und Einzelthemen 2h
until/bis 23.10.2008 (14:00) Registration for the seminar is over. At least three topic wishes and the Matrikelnummer are required. The topics are allocated by lot! Anmeldung zum Seminar vorbei. Es müssen mindestens drei Themenwünsche und die Matrikelnummer angegeben werden. Die Themenvergabe wird ausgelost!
28.10.2008 Announcement of participant ↔ topic correlation in the web or per email Bekanntgabe der Zuordnung der Themen auf die Teilnehmer/innen im Web oder per E-Mail
until/bis 09.11.2008 elaborate the topic (search literature, sort it, read it – and if possible – understand it) Thema ausarbeiten (Literatur suchen, sortieren, lesen und – soweit es geht – verstehen) 20h
10.11.-14.11.2008 Meeting of every participant with his supervisor Treffen jedes/r Teilnehmers/in mit seinem/ihrem Betreuer 1h
until mid-Dec / bis Mitte Dezember summarize literature in a seminar paper (about 10 pages) Literatur in Form einer Seminarausarbeitung (ca. 10 Seiten) zusammenfassen. 20h
until/bis 15.12.2008 (09:00) send seminar paper to supervisor Seminarausarbeitung an Betreuer mailen
until/bis 05.01.2009 read and correct seminar paper of the other participants of the group Korrekturlesen der Seminarausarbeitungen der anderen Gruppenteilnehmer 5h
susequently / anschließend Group meeting: exchange comments and helpful hints with each other. Attendance is mandatory! Gruppentreffen: Dabei werden die gegenseitigen Kommentare besprochen. Anwesenheit ist verpflichtend! 2h
until/bis 16.01.2009 incorporate results of the group meeting in seminar paper and send the revised version to supervisor Ergebnisse des Gruppentreffens in Seminarausarbeitung einarbeiten und überarbeitete Fassung an Betreuer mailen 5h
until/bis 01.02.2009 Prepare slides and send them to supervisor Vortragsfolien vorbereiten und an Betreuer mailen 10h
02.02.-06.02.2009 Meeting with supervisor: discuss slides Treffen mit Betreuer zur Besprechung der Folien 1h
until/bis 14.02.2009 incoporate comments of supervisor in slides and send final version to supervisor Kommentare des Betreuers in Folien einarbeiten und endgütige Version abgeben 5h
Prepare and practice the talk Vorbereitung des Vortrags 5h
tbd Talks
Attendance to all talks is mandatory! Two days block course between 23. Feb. and 27. Feb. 2009. Dates to be determined on preparation meeting. 		Vorträge
Anwesenheit zu allen Vorträgen ist verpflichtend! Zwei Tage Blockveranstaltung zwischen dem 23. Feb. und dem 27. Feb. 2009. Tage werden bei der Vorbesprechung festgelegt. 		45min incl. Discussion per talk

up top

Topics / Themen

Block A: Peer-to-Peer Protocols

(Hide all abstracts & references / alle Zusammenfassungen und Referenzen ausblenden)

A.1 — Characterizing Files in the Modern Gnutella Network: A Measurement Study

Student/Bearbeiter: Xiaotai Yu; Supervisor/Betreuer: Oliver Hohlfeld;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

The Internet has witnessed an explosive increase in the popularity of Peer-to-Peer (P2P) file-sharing applications during the past few years. As these applications become more popular, it becomes increasingly important to characterize their behavior in order to improve their performance and quantify their impact on the network.

In this paper, we present a measurement study on characteristics of available files in the modern Gnutella system. We developed a new methodology to capture accurate "snapshots" of available files in a large scale P2P system. This methodology was implemented in a parallel crawler that captures the entire overlay topology of the system where each peer in the overlay is annotated with its available files. We have captured tens of snapshots of the Gnutella system and conducted three types of analysis on available files: (i) Static analysis, (ii) Topological analysis and (iii) Dynamic analysis. Our results reveal several interesting properties of available files in Gnutella that can be leveraged to improve the design and evaluations of P2P file-sharing applications.

A.2 — Rarest First and Choke Algorithms Are Enough

Student/Bearbeiter: Björn Kalks; Supervisor/Betreuer: Bernhard Ager;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

The performance of peer-to-peer file replication comes from its piece and peer selection strategies. Two such strategies have been introduced by the BitTorrent protocol: the rarest first and choke algorithms. Whereas it is commonly admitted that BitTorrent performs well, recent studies have proposed the replacement of the rarest first and choke algorithms in order to improve efficiency and fairness. In this paper, we use results from real experiments to advocate that the replacement of the rarest first and choke algorithms cannot be justified in the context of peer-to-peer file replication in the Internet.

We instrumented a BitTorrent client and ran experiments on real torrents with different characteristics. Our experimental evaluation is peer oriented, instead of tracker oriented, which allows us to get detailed information on all exchanged messages and protocol events. We go beyond the mere observation of the good efficiency of both algorithms. We show that the rarest first algorithm guarantees close to ideal diversity of the pieces among peers. In particular, on our experiments, replacing the rarest first algorithm with source or network coding solutions cannot be justified. We also show that the choke algorithm in its latest version fosters reciprocation and is robust to free riders. In particular, the choke algorithm is fair and its replacement with a bit level tit-for-tat solution is not appropriate. Finally, we identify new areas of improvements for efficient peer-to-peer file replication protocols.

A.3 — Leveraging BitTorrent for End Host Measurements

Student/Bearbeiter: Ralf Stange; Supervisor/Betreuer: Oliver Hohlfeld;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

Traditional methods of conducting measurements to end hosts require sending unexpected packets to measurement targets. Although existing techniques can ascertain end host characteristics accurately, their use in large-scale measure- ment studies is hindered by the fact that unexpected traffic can trigger alarms in common intrusion detection systems, often resulting in complaints from administrators. We describe BitProbes, a measurement system that works around this challenge. By coordinated participation in the popular peer-to-peer BitTorrent system, BitProbes is able to unobtrusively measure bandwidth capacity, latency, and topology information for 500,000 end hosts per week from only eight vantage points at the University of Washington. To date, our measurements have not generated a single complaint in spite of their wide coverage.

Block B: Topology and Backbone Networking

(Hide all abstracts & references / alle Zusammenfassungen und Referenzen ausblenden)

B.1 — DisCarte: A Disjunctive Internet Cartographer

Student/Bearbeiter: Sebastian Schlunke; Supervisor/Betreuer: Wolfgang Mühlbauer;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

Internet topology discovery consists of inferring the inter-router connectivity ('links') and the mapping from IP addresses to routers ('alias resolution'). Current topology discovery techniques use TTL-limited 'traceroute' probes to discover links and use direct router probing to resolve aliases. The often-ignored record route (RR) IP option provides a source of disparate topology data that could augment existing techniques, but it is difficult to properly align with traceroute-based topologies because router RR implementations are under-standardized. Correctly aligned RR and traceroute topologies have fewer false links, include anonymous and hidden routers, and discover aliases for routers that do not respond to direct probing. More accurate and feature-rich topologies benefit overlay construction and network diagnostics, modeling, and measurement. We present DisCarte, a system for aligning and cross-validating RR and traceroute topology data using observed engineering practices. DisCarte uses disjunctive logic programming (DLP), a logical inference and constraint solving technique, to intelligently merge RR and traceroute data. We demonstrate that the resultant topology is more accurate and complete than previous techniques by validating its internal consistency and by comparing to publiclyavailable topologies. We classify irregularities in router implementations and introduce a divide-and-conquer technique used to scale DLP to Internet-sized systems.

B.2 — The Flattening Internet Topology: Natural Evolution, Unsightly Barnacles or Contrived Collapse?

Student/Bearbeiter: Philipp Richter; Supervisor/Betreuer: Gregor Schaffrath;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

In this paper we collect and analyze traceroute measurements1 to show that large content providers (e.g., Google, Microsoft, Yahoo!) are deploying their own wide-area networks, bringing their networks closer to users, and bypassing Tier-1 ISPs on many paths. This trend, should it continue and be adopted by more content providers, could flatten the Internet topology, and may result in numerous other consequences to users, Internet Service Providers (ISPs), content providers, and network researchers.

D.2 — Avoiding traceroute anomalies with Paris traceroute

Student/Bearbeiter: Tillmann Fiehn; Supervisor/Betreuer: Wolfgang Mühlbauer;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

Traceroute is widely used, from the diagnosis of network problems to the assemblage of internet maps. However, there are a few serious problems with this tool, in particular due to the presence of load balancing routers in the network. This paper describes a number of anomalies that arise in nearly all traceroute-based measurements. We categorize them as "loops", "cycles", and "diamonds". We provide a new publicly-available traceroute, called Paris traceroute, which controls packet header contents to obtain a more precise picture of the actual routes that packets follow. This new tool allows us to find conclusive explanations for some of the anomalies, and to suggest possible causes for others.

Block C: WiFi and Mesh Networks

(Hide all abstracts & references / alle Zusammenfassungen und Referenzen ausblenden)

Block D: Tools and Methods

(Hide all abstracts & references / alle Zusammenfassungen und Referenzen ausblenden)

D.1 — Unconstrained Endpoint Profiling (Googling the Internet)

Student/Bearbeiter: Florian Haemmerling; Supervisor/Betreuer: Fabian Schneider;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

Understanding Internet access trends at a global scale, i.e., what do people do on the Internet, is a challenging problem that is typically addressed by analyzing network traces. However, obtaining such traces presents its own set of challenges owing to either privacy concerns or to other operational difficulties. The key hypothesis of our work here is that most of the information needed to profile the Internet endpoints is already available around us – on the web. In this paper, we introduce a novel approach for profiling and classifying endpoints. We implement and deploy a Google-based profiling tool, which accurately characterizes endpoint behavior by collecting and strategically combining information freely available on the web. Our 'unconstrained endpoint profiling' approach shows remarkable advances in the following scenarios: (i) Even when no packet traces are available, it can accurately predict application and protocol usage trends at arbitrary networks; (ii) When network traces are available, it dramatically outperforms state-of-the-art classification tools; (iii) When sampled flow-level traces are available, it retains high classification capabilities when other schemes literally fall apart. Using this approach, we perform unconstrained endpoint profiling at a global scale: for clients in four different world regions (Asia, South and North America and Europe). We provide the first-of-its-kind endpoint analysis which reveals fascinating similarities and differences among these regions.

D.3 — nCap: Wire-speed Packet Capture and Transmission / Improving Passive Packet Capture: Beyond Device Polling

Student/Bearbeiter: Mohannad Alnablsi; Supervisor/Betreuer: Bernhard Ager;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

With the increasing network speed, it is no longer possible to capture and transmit network packets at wire-speed using general-purpose operating systems. Many companies tried to tackle this problem by manufacturing costly network adapters able to keep up at high network speeds. This paper describes a new approach to wire-speed packet capture and transmission named nCap based on commercial network adapters rather than on custom network adapters and software.

Passive packet capture is necessary for many activities including network debugging and monitoring. With the advent of fast gigabit networks, packet capture is becoming a problem even on PCs due to the poor performance of popular operating systems. The introduction of device polling has improved the capture process quite a bit but not really solved the problem. This paper proposes a new approach to passive packet capture that combined with device polling allows packets to be captured and analyzed using the NetFlow protocol at (almost) wire speed on Gbit networks using a commodity PC.

D.4 — I Tube, You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System / YouTube Traffic Characterization: A View From the Edge

Student/Bearbeiter: Irina Antonova; Supervisor/Betreuer: Fabian Schneider;
(Hide abstract & reference / Zusammenfassung und Referenz ausblenden)

User Generated Content (UGC) is re-shaping the way people watch video and TV, with millions of video producers and consumers. In particular, UGC sites are creating new viewing patterns and social interactions, empowering users to be more creative, and developing new business opportunities. To better understand the impact of UGC systems, we have analyzed YouTube, the world's largest UGC VoD system. Based on a large amount of data collected, we provide an in-depth study of YouTube and other similar UGC systems. In particular, we study the popularity life-cycle of videos, the intrinsic statistical properties of requests and their relationship with video age, and the level of content aliasing or of illegal content in the system. We also provide insights on the potential for more efficient UGC VoD systems (e.g. utilizing P2P techniques or making better use of caching). Finally, we discuss the opportunities to leverage the latent demand for niche videos that are not reached today due to information filtering effects or other system scarcity distortions. Overall, we believe that the results presented in this paper are crucial in understanding UGC systems and can provide valuable information to ISPs, site administrators, and content owners with major commercial and technical implications.

This paper presents a tra±c characterization study of the popular video sharing service, YouTube. Over a three month period we observed almost 25 million transactions between users on an edge network and YouTube, including more than 600,000 video downloads. We also monitored the globally popular videos over this period of time. In the paper we examine usage patterns, file properties, popularity and referencing characteristics, and transfer behaviors of YouTube, and compare them to traditional Web and media streaming workload characteristics. We conclude the paper with a discussion of the implications of the observed characteristics. For example, we find that as with the traditional Web, caching could improve the end user experience, reduce network bandwidth consumption, and reduce the load on YouTube's core server infrastructure. Unlike traditional Web caching, Web 2.0 provides additional meta-data that should be exploited to improve the e®ectiveness of strategies like caching.

up top

Literature / Literatur

[KR01en]

B. Krishnamurthy and J. Rexford. Web Protocols and Practice: HTTP/1.1, Networking Protocols, Caching, and Traffic Measurement. Addison Wesley, Boston, MA, 2001. (english)

[KR07en]

James F. Kurose and Keith W. Ross. Computer Networking: A Top-Down Approach. Addison-Wesley, fourth edition, 2007. (englisch), online version (preliminary version of 1st edition, password will be given during the course)
Ressources: 2nd edition, 3rd edition

[KR02de]

James F. Kurose und Keith W. Ross. Computernetze: Ein Top-Down-Ansatz mit Schwerpunkt Internet. Pearson Studium (Prentice Hall), München, Deutschland, 2002. (deutsch)

[Tan00de]

Andrew S. Tanenbaum. Computernetzwerke. Pearson Studium (Prentice Hall), München, Deutschland, dritte revidierte Auflage, 2000. (deutsch)

[Tan03en]

Andrew S. Tanenbaum. Computer Networks. Prentice Hall Professional Technical Reference, Upper Saddle River, NJ, USA, fourth edition, 2003. (english)