Geo-distributed network applications typically use relays to process and forward timely messages among clients. The state-of-the-art approaches greedily locate a relay that is closer to clients based on an overlay that favors neighbors in the immediate vicinity of the current node. Unfortunately, as clients are unknown a priori, the optimal relay is generally outside of the immediate vicinity of the current node. Consequently, the search process often terminates at a poor local minimum. In this paper, we address these challenges by designing and implementing a distributed relay-search system called MCR. In order to accurately locate a relay closer to clients, by observing that the latency space exhibits a proximity clustering phenomenon where nodes in the same cluster are typically within close proximity, we propose an overlay called MCRing that is aware of global proximity clusters. In order to scale well under dynamic relays, we maintain the proximity clusters via a gossiping-based clustering process. Furthermore, we propose a series of algorithms to accurately locate a relay that is closer to clients and satisfies the load constraints. We prove that the relay-search process achieves close to optimal results based on a doubling dimension-based analysis in an inframetric model. Finally, extensive evaluation via simulation and PlanetLab experiments shows that MCRing is able to locate near-optimal relays.

The detection of BGP prefix hijacking attacks has been the focus of research for more than a decade. However, the state-of-the-art techniques fall short of detecting more elaborate types of attack. To study such attacks, we devise a novel formalization of Internet routing, and apply this model to routing anomalies in order to establish a comprehensive attacker model. We use this model to precisely classify attacks and to evaluate their impact and detectability. We analyze the eligibility of attack tactics that suit an attacker's goals and demonstrate that related work mostly focuses on less impactful kinds of attacks. We further propose, implement, and test the Hijacking Event Analysis Program (HEAP), a new approach to investigate hijacking alarms. Our approach is designed to seamlessly integrate with the previous work in order to reduce the high rates of false alarms inherent to these techniques. We leverage several unique data sources that can reliably disprove malicious intent. First, we make use of an Internet routing registry to derive business or organizational relationships between the parties involved in an event. Second, we use a topology-based reasoning algorithm to rule out events caused by legitimate operational practice. Finally, we use Internet-wide network scans to identify SSL/TLS-enabled hosts, which helps to identify non-malicious events by comparing public keys prior to and during an event. In our evaluation, we prove the effectiveness of our approach, and show that day-to-day routing anomalies are harmless for the most part. More importantly, we use HEAP to assess the validity of publicly reported alarms. We invite researchers to interface with HEAP in order to crosscheck and narrow down their hijacking alerts.

Communication networks are complex systems whose operation relies on a large number of components that work together to provide services to end users. As the quality of these services depends on different parameters, understanding how each of them impacts the final performance of a service is a challenging but important problem. However, intervening on individual factors to evaluate the impact of the different parameters is often impractical due to the high cost of intervention in a network. It is, therefore, desirable to adopt a formal approach to understand the role of the different parameters and to predict how a change in any of these parameters will impact performance. The approach of causality pioneered by J. Pearl provides a powerful framework to investigate these questions. Most of the existing theory is non-parametric and does not make any assumption on the nature of the system under study. However, most of the implementations of causal model inference algorithms and most of the examples of usage of a causal model to predict intervention rely on assumptions such linearity, normality, or discrete data. In this article, we present a methodology to overcome the challenges of working with real-world data and extend the application of causality to complex systems in the area of telecommunication networks, for which assumptions of normality, linearity and discrete data do no hold. Specifically, we study the performance of TCP, which is the prevalent protocol for reliable end-to-end transfer in the Internet. Analytical models of the performance of TCP exist, but they take into account the state of network only and disregard the impact of the application at the sender and the receiver, which often influences TCP performance. To address this point, we take as application the file transfer protocol (FTP), which uses TCP for reliable transfer. Studying a well-understood protocol such as TCP allows us to validate our approach and compare its results to previous studies. We first present and evaluate our methodology using TCP traffic obtained via network emulation, which allows us to experimentally validate the prediction of an intervention. We then apply the methodology to real-world TCP traffic sent over the Internet. Throughout the article, we compare the causal approach for studying TCP performance to other approaches such as analytical modeling or simulation and and show how they can complement each other.

Bloom filters are frequently used to perform set queries that test the existence of some items. However, Bloom filters face a dilemma: the transmission bandwidth and the accuracy cannot be optimized simultaneously. This dilemma is particularly severe for transmitting Bloom filters to remote nodes when the network bandwidth is limited. We propose a novel Bloom filter BloomTree that consists of a tree-structured organization of smaller Bloom filters, each one using a set of independent hash functions. BloomTree spreads items across levels that are compressed to reduce the transmission bandwidth need. We investigate in detail under which conditions BloomTree performs better than the compressed Bloom filter and the standard Bloom filter.

BGP hijacking is a well known threat to the Internet routing infrastructure. There has been considerable interest in developing tools that detect prefix hijacking but such systems usually identify a large number of events, many of them being due to some benign BGP engineering practice or misconfiguration. Ramachandran et al. [1] and later Hu et al. [2] also correlated suspicious routing events with spam and claimed to have found evidence of spammers temporarily stealing prefixes to send spam. In an effort to study at large scale the existence and the prevalence of malicious BGP hijacks in the Internet we developed a system which (i) identifies hijacks using BGP, traceroute and IRR data and (ii) investigates traffic originating from the reported networks with spam and netflow data. In this paper we present a real case where suspicious BGP announcements coincided with spam and web scam traffic from corresponding networks. Through this case study we show that a correlation of suspicious routing events with malicious activities is insufficient to evidence harmful BGP hijacks. We thus question previously reported cases and conclude that identifying malicious BGP hijacks requires additional data sources as well as feedback from network owners in order to reach decisive conclusions.

One common way to search and access information available in the Internet is via a Web browser. When clicking on a Web page, the user expects that the page gets rendered quickly, otherwise he will lose interest and may abort the page load. The causes for a Webpage to load slowly are multiple and not easy to comprehend for an end-user. In this paper, we present FireLog, a plugin for the Firefox Web browser that relies on passive measurements during users' browsing, and helps identify why a web page loads slowly. We present details of our methodology and illustrate it in a case study with real users.

There exist many distributed storage systems tolerating failures of participating nodes. However, they require high amounts of metadata and do not focus on a user's need to easily recover a snapshot of their data. In this paper, we describe DistBack, a distributed back-up system that involves always-on home network gateways with the assistance of a reliable data center. We separate the system into swarms in order to ease monitoring and limit the scope of data requests. DistBack introduces index files which comprise metadata necessary to recover a snapshot. To increase efficiency, we embed small files into these index files. We show that this is reasonable due to the low amount of storage space they account for, which in our case is less than 0.1%. As a result, DistBack requires less metadata to relocate data. It supports snapshot based back-up and provides solutions for storing files of different sizes.

The endeavor of this work is to study the impact of content popularity in a large-scale Peer-to-Peer network, namely KAD. Based on an extensive measurement campaign, we pinpoint several deficiencies of KAD in handling popular content and provide a series of improvements to address such shortcomings. Our work reveals that keywords, which are associated with content, may become popular for two distinct reasons. First, we show that some keywords are intrinsically popular because they are common to many disparate contents: in such case we ameliorate KAD by introducing a simple mechanism that identifies stopwords. Then, we focus on keyword popularity that directly relates to popular content. We design and evaluate an adaptive load balancing mechanism that is backward compatible with the original implementation of KAD. Our scheme features the following properties: 1) it drives the process that selects the location of peers responsible to store references to objects, based on object popularity; 2) it solves problems related to saturated peers that would otherwise inflict a significant drop in the diversity of references to objects, and 3) if coupled with a load-aware content search procedure, it allows for a more fair and efficient usage of peer resources.

This paper investigates HTTP streaming traffic from an ISP perspective. As streaming traffic now represents nearly half of the residential Internet traffic, understanding its characteristics is important. We focus on two major video sharing sites, YouTube and DailyMotion.

Massively multiplayer online games have become popular in the recent years. Scaling with the number of users is challenging due to the low latency requirements of these games. Peer-to-peer techniques naturally address the scalability issues at the expense of additional complexity to maintain consistency among players.

Wuala is a popular online backup and file sharing system that has been successfully operated for several years. Very little is known about the design and implementation of Wuala. We capture the network traffic exchanged between the machines participating in Wuala to reverse engineer the design and operation of Wuala. When Wuala was launched, it used a clever combination of centralized storage in data centers for long-term backup with peer-assisted file caching of frequently downloaded files. Large files are broken up into transmission blocks and additional transmission blocks are generated using a classical redundancy coding scheme. Multiple transmission blocks are sent in parallel to different machines and reliability is assured via a simple Automatic Repeat Request protocol on top of UDP. Recently, however, Wuala has adopted a pure client/server based architecture. Our findings and the underlying reasons are substantiated by an interview with a co-founder of Wuala. The main reasons are lower resource usage on the client side, which is important in the case of mobile terminals, a much simpler software architecture, and a drastic reduction in the cost of data transfers originating at the data center.

Social virtual worlds such as Second Life (SL) are digital representations of the real world where human-controlled avatars evolve and interact through social activities. Understanding the characteristics of virtual worlds can be extremely valuable in order to optimize their design. In this paper, we perform an extensive analysis of SL. We exploit standard avatar capabilities to monitor the virtual world, and we emulate avatar behaviors in order to evaluate user experience. We make several surprising observations. We find that 30% of the regions are never visited during the six-day monitoring period, whereas less than 1% of the regions have large peak populations. Moreover, the vast majority of regions are static, i.e., objects are seldom created or destroyed. Interestingly, we show that avatars interact similarly to humans in real life, gathering in small groups of 2-10 avatars. We also show that user experience is poor. Most of the time, avatars have an incorrect view of their neighbor avatars, and inconsistency can last several seconds, impacting interactivity among avatars.

Peer to peer backup systems store data on “unreliable” peers that can leave the system at any moment. In this case, the only way to assure durability of the data is to add redundancy using either replication or erasure codes. Erasure codes are able to provide the same reliability as replication requiring much less storage space. Erasure coding breaks the data into blocks that are encoded and then stored on different nodes. However, when storage nodes permanently abandon the system, new redundant blocks must be created, which is referred to as repair. For “classical” erasure codes, generating a new block requires the transmission of k blocks over the network, resulting in a high repair traffic. Recently, two new classes of erasure codes, Regenerating Codes and Hierarchical Codes, have been proposed that significantly reduce the repair traffic. Regenerating Codes reduce the amount of data uploaded by each peer involved in the repair, while Hierarchical Codes reduce the number of nodes participating in the repair. In this article we propose to combine these two codes to devise a new class of erasure codes called ER-Hierarchical Codes that combine the advantages of both.

Network Protocol Reverse Engineering (NPRE) has played an increasing role in honeypot operations. It allows to automatically generate Statemodels and scripts being able to act as realistic counterpart for capturing unknown malware. This work proposes a novel approach in the field of NPRE. By passively listening to network traces, our system automatically derives the protocol state machines of the peers involved allowing the analyst to understand its intrinsic logic. We present a new methodology to extract the relevant fields from arbitrary binary protocols to construct a state model. We prove our methodology by deriving the state machine of documented protocols ARP, DHCP and TCP. We then apply it to Kademlia, the results show the usefulness to support binary reverse engineering processes and detect a new undocumented feature.

In distributed storage systems, erasure codes represent an attractive solution to add redundancy to stored data while limiting the storage overhead. They are able to provide the same reliability as replication requiring much less storage space. Erasure coding breaks the data into pieces that are encoded and then stored on different nodes. However, when storage nodes permanently abandon the system, new redundant pieces must be created. For erasure codes, generating a new piece requires the transmission of k pieces over the network, resulting in a k times higher reconstruction traffic as compared to replication. Dimakis proposed a new class of codes, called regenerating codes, which are able to provide both the storage efficiency of erasure codes and the communication efficiency of replication. However, Dimakis gave only a theoretical description of the codes without discussing implementation issues or computational costs. We have done a real implementation of random linear regenerating codes that allows us to measure their computational cost, which can be significant if the parameters are not chosen properly. However, we also find that there exist parameter values that result in a significant reduction of the communication overhead at the expense of a small increase in storage cost and computation, which makes these codes very attractive for distributed storage systems.

Applications such as Second Life require massive deployment of servers worldwide to support a large number of users. We investigate experimentally how Peer-to-Peer (P2P) communication could help cut the deployment cost and increase the scalability of Social Virtual Worlds such as Second Life. We design and build a communication infrastructure that distributes the management of the virtual world among user resources using a structured P2P network. Our communication infrastructure is implemented on the top of Kad, the P2P network that supports millions of eMule users. We then use avatar and object traces collected on Second Life to perform a realistic emulation of P2P Second Life over the Internet. We show that, despite using a standard P2P solution, P2P Second Life is mostly consistent, persistent and scalable. However, the latency avatars experience to recover from an inconsistent view of the virtual world can become disturbing for very large numbers of participants and objects. We analyze and discuss this limitation and give recommendation on how to design P2P Social Virtual Worlds.

Most tools designed to estimate the capacity of an Internet path require access on both end hosts of the path, which makes them difficult to deploy and use. In this paper we present a single-sided technique for measuring the capacity without the active cooperation of the destination host, focusing particularly on ADSL links. Compared to current methods used on broadband hosts, our approach generates two orders of magnitude less traffic and is much less intrusive. Our tool, DSLprobe, exploits the typical characteristics of ADSL, namely its bandwidth asymmetry and the relatively low absolute bandwidth, in order to measure both downlink and uplink capacities and to mitigate the impact of cross-traffic. To further improve the accuracy, we study different ways to detect and filter cross-traffic packets and we show how to recognize and overcome limited uplink capacities. We validate our tool both on controlled hosts and on a wide variety of Internet hosts. Finally, we present a case study of two large ADSL providers.

Social virtual worlds such as Second Life are digital representations of the real world where human-controlled avatars evolve and interact through social activities. Understanding the characteristics of existing virtual worlds can be extremely valuable to optimize their design. In this work we perform the first extensive analysis of Second Life. We have crawled around 13000 Regions over one month, and gathered information about objects, avatars, and server state. The analysis of our traces shows several surprising results. We find that 30% of the Regions are never visited during a six day period, whereas only few Regions have large peak populations. Moreover, the vast majority of Regions are static, i.e., objects are seldom created or destroyed. Interestingly, avatars interact similarly to humans in real life, gathering in small groups, visiting the same places and meeting the same avatars again, showing a highly predictable behavior. Based on these observations, we discuss several techniques to enhance Second Life or other similar social virtual worlds.

We analyze and compare various transport protocols in the context of wireless in-vehicle IP-based audio and video communication. We determine the most appropriate transport protocol and discuss its benefits for an application in the car. The analyses are accomplished based on the IEEE 802.11 standard. A testbed is used to measure and compare quality of service values such as throughput, jitter and media quality at the receiver. In the experiments, the traditional protocols TCP and UDP showed the best performance.

Redundancy is the basic technique to provide reliability in storage systems consisting of multiple components. A redundancy scheme defines how the redundant data are produced and maintained. The simplest redundancy scheme is replication, which however suffers from storage inefficiency. Another approach is erasure coding, which provides the same level of reliability as replication using a significantly smaller amount of storage. When redundant data are lost, they need to be replaced. While replacing replicated data consists in a simple copy, it becomes a complex operation with erasure codes: new data are produced performing a coding over some other available data. The amount of data to be read and coded is d times larger than the amount of data produced. This implies that coding has a larger computational and I/O cost, which, for distributed storage systems, translates into increased network traffic. Participants of peer-to-peer systems have ample storage and CPU power, but their network bandwidth may be limited. For these reasons existing coding techniques are not suitable for P2P storage. This work explores the design space between replication and the existing erasure codes. We propose and evaluate a new class of erasure codes, called hierarchical codes, which aims at finding a flexible trade-off that allows the reduction of the network traffic due to maintenance without losing the benefits given by traditional codes.

Many different distributed hash tables (DHTs) have been designed, but only few have been successfully deployed. The implementation of a DHT needs to deal with practical aspects (e.g. related to churn, or to the delay) that are often only marginally considered in the design. In this paper, we analyze in detail the content retrieval process in KAD, the implementation of the DHT Kademlia that is part of several popular peer-to-peer clients. In particular, we present a simple model to evaluate the impact of different design parameters on the overall lookup latency. We then perform extensive measurements on the lookup performance using an instrumented client. From the analysis of the results, we propose an improved scheme that is able to significantly decrease the overall lookup latency without increasing the overhead.

This paper proposes a new methodology to model the distribution of finite size content to a group of users connected through an overlay network.Our methodology describes the distribution process as a constrained stochastic graph process (CSGP), where the constraints dictated by the content distribution protocol and the characteristics of the overlay network define the interaction among nodes. A CSGP is a semi-Markov process whose state is described by the graph itself. CSGPs offer a powerful description technique that can be exploited by Monte Carlo integration methods to compute in a very efficient way not only the mean but also the full distribution of metrics such as the file download times or number of hops from the source to the receiving nodes.We model several distribution architectures based on trees and meshes as CSGPs and solve them numerically. We are able to study scenarios with a very large number of nodes and we can precisely quantify the performance differences between the treeand mesh-based distribution architectures.

Distributed Hash Tables (DHT) provide a framework for managing information in a large distributed network of nodes. One of the main challenges DHT systems must face is node churn, i.e., nodes can arrive and depart at any time. To assure that information published in a DHT remains available despite node churn is equivalent to building a reliable system out of unreliable components.

Distributed storage systems provide data availability by means of redundancy. To assure a given level of availability in case of node failures, new redundant fragments need to be introduced.

A Networked Virtual Environment (NVE) is a digital world where multiple participants interact via virtual characters called avatar. A popular application for NVEs is Second Life (SL)[5].

Distributed hash tables (DHTs) have been actively studied in literature and many different proposals have been made on how to organize peers in a DHT. However, very few DHT shave been implemented in real systems and deployed on alarge scale. One exception is KAD , a DHT based on Kademlia, which is part of eDonkey2000, a peer-to-peer file sharing system with several million simultaneous users. We have been crawling KAD continuously for about six months and obtained information about the total number of peers online and their geographical distribution.

This paper studies fundamental properties of stream-based content distribution services. We assume the presence of an overlay network (such as those built by P2P systems) with limited degree of connectivity, and we develop a mathematical model that captures the essential features of overlay-based streaming protocols and systems. The methodology is based on stochastic graph theory, and models the streaming system as a stochastic process, whose characteristics are related to the streaming protocol. The model captures the elementary properties of the streaming system such as the number of active connections, the different play-out delay of nodes, and the probability of not receiving the stream due to node failures/misbehavior. Besides the static properties, the model is able to capture the transient behavior of the distribution graphs, i.e., the evolution of the structure over time, for instance in the initial phase of the distribution process. Contributions of this paper include a detailed definition of the methodology, its comparison with other analytical approaches and with simulative results, and a discussion of the additional insights enabled by this methodology. Results show that mesh based architectures are able to provide bounds on the receiving delay and maintain rate fluctuations due to system dynamics very low. Additionally, given the tight relationship between the stochastic process and the properties of the distribution protocol, this methodology gives basic guidelines for the design of such protocols and systems.

Large-scale live media streaming is a challenge for traditional server-based approaches. To appropriately support big audiences, broadcasters must be able to allocate huge bandwidth and computational resources. The costs involved with such an infrastructure exclude all but the established content producers from exploiting the Internet as a distribution medium. Publishers of not-yet-popular content, unless they manage to properly predict their maximum audience size, will likely fail to dimension correctly their broadcast infrastructure. Peer-to-peer systems for live streaming allow the users to support content distribution by contributing their unused resources: this increases the scalability of the content distribution while reducing at the same time the economical burden on the streaming provider. This paper presents and evaluates PULSE, an unstructured mesh-based peer-to-peer system designed to support live streaming to large audiences under the arbitrary resource availability as is typically the case for the Internet. PULSE is a highly dynamic system: it constantly optimizes its mesh of data connections using a feedback-driven peer selection strategy that is based on pairwise incentives. We evaluate the behavior of PULSE under realistic scenarios via simulation and emulation, and present the advantages of our approach, namely a best-effort response to system-wide resource scarcity, high resilience to node churn, and good hop-count properties of the average data distribution paths.

We consider the case of a virtual world of peers that are organized in an overlay built by Delaunay Triangulation. Application layer routing is used to determine the path taken in the overlay between two peers. Application layer routing incurs a major delay penalty since it ignores the characteristics of the physical network topology.

We consider the problem of distributing a content of finite size to a group of users connected through an overlay network that is built by a peer-to-peer application. The goal is the fastest possible diffusion of the content until it reaches all the peers. Applications like Bit-Torrent or SplitStream are examples where the problem we study is of great interest. In order to represent the content diffusion process, we model the system as a stochastic graph process and define the constraints the graph evolution is subject to. The evolution of the graph is a semi-Markov process where the sojourn times are the rewards of interest for the computation of the time needed to complete the file distribution. We discuss the general properties of the constrained stochastic graphs and we show preliminary results obtained with an ad-hoc Monte-Carlo technique.

In this paper we investigate which is the most efficient architecture and protocol that can be used for file distribution. The focus of the analysis is to understand not only the parameters that influence the distribution process (constraints on the number of neighbors, bandwidth heterogeneity, etc.), but also the impact of the peer behavior, such as selfishness or neighbor selection strategies. The analysis also compares different tree- and mesh-based distribution architectures. We developed an ad-hoc Monte-Carlo technique that is able to analyze scenarios with millions of peers, a network size that traditional discrete- event simulators are not able to treat. The results give an accurate view of the fundamental protocol parameters and policies that impact on the final performance and allow designers to devise improved protocols.

With the widespread availability of inexpensive broadband Internet connections for home-users, a large number of bandwidth-intensive applications previously not feasible have now become practical. This is the case for multimedia live streaming, for which end-user's dial-up/ISDN modem connections once were the bottleneck. The bottleneck is now mostly found on the server side: the bandwidth required for serving many clients at once is large and thus very costly to the broadcasting entity. Peer-to-peer systems for on-demand and live streaming have proved to be an encouraging solution, since they can shift the burden of content distribution from the server to the users of the network. In this work we introduce PULSE, a P2P system for live streaming whose main goals are flexibility, scalability, and robustness. We present the fundamental concepts that stand behind the design of PULSE along with its intended global behavior, and describe in detail the main algorithms running on its nodes.

We present a distributed algorithm for the clustering of peers in a Networked Virtual Environment (NVE) that are organized using a peer-to-peer (P2P) network based on the Delaunay triangulation. The algorithm is dynamic in the sense that whenever a peer joins or leaves the NVE, the clustering will be adapted if necessary by either splitting a cluster or merging clusters. The main idea of the algorithm is to classify links between adjacent peers into short intra-cluster and long inter-cluster links. The advantages of clustering are multiple: clustering allows to limit queries to the peers of a cluster avoiding to flood the entire network. Since clusters can be seen as a level of abstraction that reduces the amount of information/detail exposed about the NVE, clustering allows for faster navigation in the NVE and reduces the number of messages a node receives when he travels through the NVE.

While the applications using the Internet have changed over time, TCP is still the dominating transport protocol that carries over 90% of the total traffic. Throughput is the key performance metric for long TCP connections. The achieved throughput results from the aggregate effects of the network path, the parameters of the TCP end points, and the application on top of TCP. Finding out which of these factors is limiting the throughput of a TCP connection -- referred to as TCP root cause analysis -- is important for end users that want to understand the origins of their problems, ISPs that need to troubleshoot their network, and application designers that need to know how to interpret the performance of the application. In this paper, we revisit TCP root cause analysis by first demonstrating the weaknesses of a previously proposed flight-based approach. We next discuss in detail the different possible limitations and highlight the need to account for the application behavior during the analysis process. The main contribution of this paper is a new approach based on the analysis of time series extracted from packet traces. These time series allow for a quantitative assessment of the different causes with respect to the resulting throughput. We demonstrate the interest of our approach on a large BitTorrent dataset.

This paper presents a dynamic and distributed algorithm for the clustering of peers in a Networked Virtual Environment (NVE) based on a fully distributed peer-to-peer (P2P) network.The main idea is to classify connections in short intra-cluster connections and long inter-cluster connections. The insertion of new peers or the deletion of existing peers can result in the merging of two clusters or the split of one cluster in two parts.

Peer-to-peer distributed hash table (DHT) systems make it simple to discover specific data when their complete identifiers - or keys - are known in advance. In practice, however, users looking up resources stored in peer-to-peer systems often have only partial information for identifying these resources. We describe techniques for indexing data stored in peer-to-peer DHT networks, and discovering the resources that match a given user query. Our system creates multiple indexes, organized hierarchically, which permit users to locate data even using scarce information, although at the price of a higher lookup cost. The data itself is stored on only one (or few) of the nodes. Experimental evaluation demonstrates the effectiveness of our indexing techniques on a distributed peer-to-peer bibliographic database with realistic user query workloads.

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.

No abstract available.

Recent studies of Internet traffic have shown that flow size distributions often exhibit a high variability property in the sense that most of the flows are short and more than half of the total load is constituted by a small percentage of the largest flows. In the light of this observation, it is interesting to revisit scheduling policies that are known to favor small jobs in order to quantify the benefit for small and the penalty for large jobs. Among all scheduling policies that do not require knowledge of job size, the least attained service (LAS) scheduling policy is known to favor small jobs the most. We investigate the M/G/1/LAS queue for both, load ? < 1 and ? = 1. Our analysis shows that for job size distributions with a high variability property, LAS favors short jobs with a negligible penalty to the few largest jobs, and that LAS achieves a mean response time over all jobs that is close to the mean response time achieved by SRPT.Finally, we implement LAS in the ns-2 network simulator to study its performance benefits for TCP flows. When LAS is used to schedule packets over the bottleneck link, more than 99% of the shortest flows experience smaller mean response times under LAS than under FIFO and only the largest jobs observe a negligible increase in response time. The benefit of using LAS as compared to FIFO is most pronounced at high load.

Popular content is frequently replicated in multiple servers or caches in the Internet to offload origin servers and improve end-user experience. However, choosing the best server is a nontrivial task and a bad choice may provide poor end user experience. In contrast to retrieving a file from a single server, we propose a parallel-access scheme where end users access multiple servers at the same time, fetching different portions of that file from different servers and reassembling them locally. The amount of data retrieved from a particular server depends on the resources available at that server or along the path from the user to the server. Faster servers deliver bigger portions of a file while slower servers deliver smaller portions. If the available resources at a server or along the path change during the download of a file, a dynamic parallel access automatically shifts the load from congested locations to less loaded parts (server and links) of the Internet. The end result is that users experience significant speedups and very consistent response times. Moreover, there is no need for complicated server selection algorithms and load is dynamically shared among all servers. The dynamic parallel-access scheme presented does not require any modifications to servers or content and can be easily included in browsers, peer-to-peer applications or content distribution networks to speed up delivery of popular content.

Using multicast delivery to multiple receivers reduces the aggregate bandwidth required from the network compared to using unicast delivery to each receiver. However, multicast is not yet widely deployed in the Internet. One reason is the lack of incentive to use multicast delivery. To encourage the use of multicast delivery, we define a new bandwidth-allocation policy, called LogRD, taking into account the number of downstream receivers. This policy gives more bandwidth to a multicast flow as compared to a unicast flow that shares the same bottleneck, without starving the unicast flows, however. The LogRD policy also provides an answer to the question on how to treat a multicast flow compared to a unicast flow sharing the same bottleneck. We investigate three bandwidth-allocation policies for multicast flows and evaluate their impact on both receiver satisfaction and fairness using a simple analytical study and a comprehensive set of simulations. The policy that allocates the available bandwidth as a logarithmic function of the number of receivers downstream of the bottleneck achieves the best tradeoff between receiver satisfaction and fairness.

Cache cooperation improves the performance of isolated caches, especially for caches with small cache populations. To make caches cooperate on a large scale and effectively increase the cache population, several caches are usually federated in caching architectures. We discuss and compare the performance of different caching architectures. In particular, we consider hierarchical and distributed caching. We derive analytical models to study important performance parameters of hierarchical and distributed caching, i.e., client's perceived latency, bandwidth usage, load in the caches, and disk space usage. Additionally, we consider a hybrid caching architecture that combines hierarchical caching with distributed caching at every level of a caching hierarchy. We evaluate the performance of a hybrid scheme and determine the optimal number of caches that should cooperate at each caching level to minimize client's retrieval latency.

Popular documents are frequently mirrored on multiple sites in an effort to share the load and reduce clients' retrieval latencies. However, choosing the best mirror site is a non-trivial task and a bad choice may give poor performance. We propose a scheme in which clients access multiple mirror sites in parallel to speedup document downloads while eliminating the problem of server selection. In our scheme, clients connect to mirror sites using unicast TCP connections and dynamically request different pieces of a document from different sites. The amount of data retrieved from a particular site varies depending on the network path/server conditions. Dynamic parallel-access can be easily implemented in the current Internet and does not require any modifications at the mirror sites. Using dynamic parallel-access, all clients experience dramatic speedups in downloading documents, and the load is shared among servers without the need for a server selection mechanism. Even in a situation where clients are connected through modem lines, dynamic parallel-access offers transmission rates at least as high as the fastest server.

A major challenge in the Internet is to deliver live audio/video content with a good quality and to transfer files to large number of heterogeneous receivers. Multicast and cumulative layered transmission are two mechanisms of interest to accomplish this task efficiently. However, protocols using these mechanisms suffer from slow convergence time, lack of inter-protocol fairness or TCP-fairness, and loss induced by the join experiments.

We examine the impact of the loss recovery mechanism on the performance of a reliable multicast protocol. Approaches for loss recovery in reliable multicast can be divided into two major classes: centralized (source-based) recovery and distributed recovery. For both classes we consider the state of the art: for centralized recovery, an integrated transport layer scheme using parity multicast for error recovery (hybrid ARQ type 2) as well as timer-based feedback suppression, and for distributed recovery, a scheme with local data multicast retransmission and feedback processing in a local neighborhood. We also evaluate the benefits of combining the two approaches into distributed error recovery (DER) with local retransmissions using a type 2 hybrid ARQ scheme. The schemes are evaluated for up to 10/sup 6/ receivers under different loss scenarios with respect to network bandwidth usage and completion time of a reliable transfer. We show that using DER with type 2 hybrid ARQ gives best performance in terms of bandwidth and latency. For networks, where local retransmission is not possible, we show that a centralized protocol based on type 2 hybrid ARQ comes close to the performance of a protocol with local retransmissions.

Large scale video servers are typically based on disk arrays that comprise multiple nodes and many hard disks. Due to the large number of components, disk arrays are susceptible to disk and node failures that can affect the server reliability. Therefore, fault tolerance must be already addressed in the design of the video server. For fault tolerance, we consider parity-based as well as mirroring-based techniques with various distribution granularities of the redundant data. We identify several reliability schemes and compare them in terms of the server reliability and per stream cost. To compute the server reliability, we use continuous time Markov chains that are evaluated using the SHARPE software package. Our study covers independent disk failures and dependent component failures. We propose a new mirroring scheme called Grouped One-to-One scheme that achieves the highest reliability among all schemes considered. The results of this paper indicate that dividing the server into independent groups achieves the best compromise between the server reliability and the cost per stream. We further find that the smaller the group size, the better the trade-off between a high server reliability and a low per stream cost.

Using multicast delivery to multiple receivers reduces the aggregate bandwidth required from the network compared to using unicast delivery to each receiver. To encourage the use of multicast delivery, a higher amount of bandwidth should be allocated to a multicast row as compared to a unicast row that share the same bottleneck, but without starving the unicast flow. We investigate three bandwidth allocation policies for multicast flows and evaluate their impact on the bandwidth received by the individual receivers. The policy that allocates the available bandwidth as a logarithmic function of the number of receivers downstream of the bottleneck achieves the best trade-off between maximizing the receiver satisfaction and keeping fairness high.

We investigate the scalability of feedback in multicast communication and propose a new method of probabilistic feedback based on exponentially distributed timers. By analysis and simulation for up to 10/sup 6/ receivers, we show that feedback implosion is avoided while feedback latency is low. The mechanism is robust against the loss of feedback messages and works well in case of homogeneous and heterogeneous delays. We apply the feedback mechanism to reliable multicast and compare it to existing timer-based feedback schemes. Our mechanism achieves lower negative acknowledgment character (NAK) latency for the same performance in terms of NAK suppression. No topological information of the network is used, and data delivery is the only support required from the network. The mechanism adapts to a dynamic number of receivers and leads to a stable performance for implosion avoidance and feedback latency.

We investigate the scalability of feedback in multicast communication and propose a new method of probabilistic feedback based on exponentially distributed timers. By analysis and simulation for up to 10/sup 6/ receivers we show that feedback implosion is avoided while feedback latency is low. The mechanism is robust against the loss of feedback messages and robust against homogeneous and heterogeneous delays. We apply the feedback mechanism to reliable multicasting and compare it to existing timer-based feedback schemes. Our mechanism achieves lower NAK (loss signaling) latency for the same performance in terms of NAK suppression. It is scalable, the amount of state at every group member is independent of the number of receivers. No topological information of the network is used and data delivery is the only support required from the network. It adapts to the number of receivers and leads therefore to a constant performance for implosion avoidance and feedback latency.

We examine the impact of the loss recovery mechanisms on the performance of a reliable multicast protocol. Approaches to reliable multicast can be divided into two major classes: source-based recovery, and distributed recovery. For both classes we consider the state of the art: for source-based recovery, a type 2 hybrid ARQ scheme with parity retransmission; for distributed recovery, a scheme with local multicast retransmission and local feedback processing. We further show the benefits of combining the two approaches and consider a type 2 hybrid ARQ scheme with local retransmission. The schemes are compared for up to 10/sup 6/ receivers under different loss scenarios with respect to network bandwidth usage and completion time of a reliable transfer. We show that the protocol based on local retransmissions via type 2 hybrid ARQ performs best for bandwidth and latency. For networks, where local retransmission is not possible, we show that a protocol based on type 2 hybrid ARQ comes close to the performance of a protocol with local retransmissions.

We investigate how forward error correction (FEC) can be combined with automatic repeat request (ARQ) to achieve scalable reliable multicast transmission. We consider the two scenarios where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses ARQ, and where FEC and ARQ are both integrated into a single layer that uses the retransmission of parity data to recover from the loss of original data packets. To evaluate the performance improvements due to FEC, we consider different loss rates and different types of loss behavior (spatially or temporally correlated loss, homogeneous or heterogeneous loss) for up to 10/sup 6/ receivers. Our results show that introducing FEC as a transparent layer below ARQ can improve multicast transmission efficiency and scalability. However, there are substantial additional improvements when FEC and ARQ are integrated.

Our aim is to investigate reliable transmission for multicast communication and explore its relationship to multicast routing. We derive two characterizations that enable the comparison of routing algorithms and error recovery mechanisms with respect to the multicast tree topology, namely the probability mass function of successful receptions and the expected number of retransmissions needed to deliver a packet from the source to all receivers. We also give a tight approximation of the computationally expensive expected number of retransmissions. These expressions allow to explore the relationship between routing and error recovery for multicast communication. We finally evaluate the impact of routing algorithms on the performance of reliable multicast transmission and give a realistic generic model for a multicast tree.

We investigate how FEC (Forward Error Correction) can be combined with ARQ (Automatic Repeat Request) to achieve scalable reliable multicast transmission. We consider the two scenarios where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses ARQ, and where FEC and ARQ are both integrated into a single layer that uses the retransmission of parity data to recover from the loss of original data packets.To evaluate the performance improvements due to FEC, we consider different types of loss behaviors (spatially or temporally correlated loss, homogeneous or heterogeneous loss) and loss rates for up to 106 receivers. Our results show that introducing FEC as a layer below ARQ can improve multicast transmission efficiency and scalability and that there are substantial additional improvements when the two are integrated.

The loss behavior of a cell multiplexer and the performance of forward error correction (FEC) for two homogeneous and one heterogeneous traffic scenarios are discussed. The loss behavior depends on the statistics of the source and on the traffic scenario. Simulation results indicate that the percentage of cells lost in a block is geometrically distributed. Using these results a mathematical model for the performance of FEC is developed, and the effectiveness of FEC for the three traffic scenarios is computed. It is shown that FEC is not effective for the two homogeneous scenarios. However, FEC reduces the loss rate for the video sources by several orders of magnitude for a heterogeneous scenario consisting of video and burst sources.>

The effects on performance of adding the selective retransmission feature to the IEEE 802.2 type-2 logical link protocol are discussed. Simulation results indicate that selective retransmission significantly improves the performance in case of overload and performs as well as an enhancement that was suggested by W. Bux and D. Grillo (see ibid., vol.COM-33, p.1058-65, 1985).>

If the packet loss rate in a network is higher than the loss rate requested by an application, the transport protocol must make up for the difference in loss rate. In high bandwidth delay-product networks the latency introduced by retransmission-based error recovery schemes may be too high for applications with latency constraints. In this case, Forward Error Correction (FEC) can be used. FEC allows recovery from loss without retransmission. The amount of loss recovered strongly depends on the loss behavior of the network. FEC works best if losses are dispersed in time.

This bibliography covers the various aspects of network interconnection. It contains a list of papers, documents, and books dealing with interconnection at different layers of the ISO OSI reference model and covers topics such as interconnection among various types of networks, backbone networks, standardization efforts, interconnection techniques, formal approaches, network management, protocol issues, addressing and naming, routing, performance evaluation, gateway implementations, and existing products.>

The author investigates the effects on performance of three different modifications to the IEEE 802.2 LCC type 2 protocol (further referred to as ORIG) in an internetwork environment consisting of three IEEE 802.5 token-ring networks connected via bridges to a backbone ring. The modifications are: (1) selective reject of lost or erroneous frames; (2) acknowledgement accumulation with a static threshold value; and (3) acknowledgement accumulation with a dynamic threshold value. The prime performance measures are throughput and mean end-to-end delay. It is found that modifications (1) and (3) yield a significant improvement in performance under a high traffic load as compared to ORIG and that modification (2) increases the throughput at the cost of a higher mean end-to-end delay.>