The Internet is typically perceived as one atomic entity. However, in reality, it is composed of roughly 30,000 networks called Antonomous System. The glue in the Internet, which provides connectivity, is the Border Gateway Protocol (BGP). The protocol itself is old and, in its basic form, relys on trust. This can be easily exploited by fraud or misconfigurations, causing parts of the Internet to be unreachable.

I’m currently preparing some classical BGP incidents for tomorrows Network Protocols and Architecture class. While I was looking form some of the classical BGP prefix hijacks that have been covered widely in the press, I found some nice presentation illustrating the incidents:

• First reported incident from 1997
• The Anatomy of a Leak: AS9121: Turkey pretended to be the Internet on December 24, 2005
• The Day the YouTube Died: Due to a censorship of YouTube, because of an anti-islam video (see a copy of the blocking order by the Pakistani government), Pakistan’s telcom pretended to be YouTube. This caused YouTube to be unreachable for up to two hours. This Animation video of BGPlay on YouTube nicely shows the creation of the blackhole.

Prefix hijacks are an classic and often exploited by Spammers (see slide 17 of our presentation, partly based on Feamster’s Sigcomm paper). An extension of this can be used to eavesdropp traffic by re-routing traffic.  A non-trivial evesdropping attack that requires trust from the used upstream provider was presented at DefCon 2008 (see the slides).

A solution can be found in Secure BGP. However, this approach is—like IPv6—not widely deployed.

Further resources:

• Internet Alert Registry
• “Haste ma’n netblock?”: Layer 8 based IP Address hijacking in the end of the days of IPv4
• BGPlay

Today was the first day of our two days blockseminar on Internet Measurement, in which I supervised two students. During the seminar, we addressed the following topics (papers) by talks held by students attending the seminar along with a discussion on the topic afterwards:

• Characterizing Files in the Modern Gnutella Network: A Measurement Study [Slides] [Student Paper] [Original Paper]
  Which files are shared on Gnutella and what are their characteristics? Besides studies that derived traces by hosting peers dedicated to provide measurement data, this paper describes data derived from crawls of the Gnutella network.
• Rarest First and Choke Algorithms Are Enough [Slides] [Student Paper] [Original Paper]
  This paper discusses why BitTorrent performs well and states that the Rarest First Algorithm and the Choke algorithm are enough to provide reasonable fairness, diversity of the content pieces and performance. Roughly speaking, Those are the key features that differentiate BitTorrent from other peer-to-peer file sharing protocols.
• Leveraging BitTorrent for End Host Measurements [Slides] [Student Paper] [Original Paper]
  How optimistic unchokes—provided by BitTorrent and essential for its functionality—can be exploited to perform end host measurements; a dedicated and modified BitTorrent client called BitProbes downloads two megabytes of data from peers—by acting as a freerider and not uploading downloaded data—and uses this communication for conducting host measurements.
  Some points that have been discussed: (1) the authors claim that downloading but not storing the data is enough to avoid legal issues. Is that really true? (2) During a sample 7 days crawl, the authors covered about 20% of the available autonomos systems (AS) in the Internet. What does this number mean? Is it a high coverage, or a low one? For the answe, one has to keep in mind that not all AS are likely to host BitTorrent clients (like enterprise networks).

• Unconstrained Endpoint Profiling (Googling the Internet) [Slides] [Student Paper] [Original Paper]
  How documents indexed by Google can be used to label IP addresses with applications run by a particular host
  The discussion mainly focused on the question whether the proposed method is really unconstrained as the title of the paper claims. Some key points: (1) The propsed method relys on Google, but the Google index varies (regional filtering etc.). (2) Existance of the deep web: not every available document is indexed by a particular search engine. (3) How dynamic are IP addresses? What if we want to label IPs of access providers which usually map to a set of users that used it in the past? (4) Can we trust data provided by the third parties (e.g. faked access log files etc.)?
  We agreed that this methodology seems good to discover trends but details have to be taken with a pinch of salt.
• I Tube, You Tube, Everybody Tubes: Analyzing the World’s Largest User Generated Content Video System [Slides] [Student Paper] [Original Paper1 Paper 2]
  What kind of videos are shared on YouTube and what is their access characteristics. See my blog post on this from October 2007.
• The Flattening Internet Topology: Natural Evolution, Unsightly Barnacles or Contrived Collapse? [Slides] [Student Paper] [Original Paper]
  This paper analyses a trend of big content provider building up WANs and tend to bypass Tier 1 providers to save transit costs and increase performance which flattens the Internet topology

For references to the original papers, the student papers (mostly in German) and slides, see the seminar webpage. The talks had a very high quality and the discussions were pretty interesting. So I’m really looking forward to day II.

The workshop is finally over and I’m back to Germany. All in all I have to say that IWQoS was a very interesting workshop, having contributions of a very high quality. I want to present a brief résumé  here, but I’m not giving an extensive review and thus recommend you to take a look at the program on your own.

• Two-state Markov models for describing transmission channels are still popular (e.g. used by Liu et al.)
• Algorithms in the field of Pre-Congestion Notification are subject to performance evaluations, which is a good thing in general as evaluations of RED active queue management have been published when RED was already widely deployed and thus were too late to be taken into account. It seems like this is not the case for PCN.
• An interesting contribution has been made to the field of profile based traffic classification in the work of Hu et al., where data mining techniques are applied to generate distinct behavioral application profiles. The authors present an evaluation of an rule set for BitTorrent and PPLive. In contrast to the techniques presented in our talk about Spam and Traffic Profiling techniques in 2006, this approach seems to be more flexible — at least at first sight.
• YouTube has been again subject to an extensive evaluation. In contrast to the papers presented at the Internet Measurement Conference in 2007, this paper discusses the social networks formed in YouTube and their small world character.
• The invited talk given by a colleague of David Hutchison entitled QoS: (Still) a Grand Challenged? reviewed the evolution of QoS techniques starting from ATM and Broadband ISDN. The conclusion drawn from this talk is that QoS is still a considerable challenge and security and resilience issues need to be taken more seriously, which seems to be reasonable.However, it remains to be seen whether the delivery of 100 MBit/s to the home really changes the world as much as highlighted in the talk. What is known to me about ADSL service providers is that most of the users are not extensively using the big pipe they pay for and rather stick with ocassionally using HTTP and checking their mail. In the first days of ADSL deployment, those access lines were extensively used by power users and thus resulted in a high increase of traffic in the core. However, traffic in the core increases much more slowly with a increasing number of ADSL users nowadays, as most of the users are not using their access link very extensively. I’m wondering if this will be similar for 100 Mbit/s access links in the future.