In routerless network-on-chip (NoC), any pair of cores are directly connected via at least one isolated ring, such that high-cost routers can be entirely abandoned. In this paper, we focus on the problem of designing a set of rings that guarantee the connectivity and minimize the average hop count for all core pairs. We propose the first optimal integer linear programing (ILP) to design rings for any n×m chips under any given wiring constraint, i.e., the maximum number of wires allowed between any adjacent cores. Numerical results show that our ILP performs much better and is more flexible than the existing algorithms. But our ILP is time-consuming to solve and future work should focus on reducing its complexity.

We consider an N×N input-queued switch with N dedicated unicast virtual output queues (VOQs) and one shared multicast queue (MQ) at each input port. An efficient two-bit single-iteration (2BSI) scheduling algorithm is proposed to concurrently schedule both unicast and multicast traffic. In the request phase, a two-bit request message is used to indicate not only the type of the request (unicast/multicast) but also its importance (strong/weak). In the grant phase, multicast request is granted first, then strong unicast request, and finally weak unicast request. To minimize inconsistencies in the distributed arbitration process, the notion of preferred unicast/multicast relationship is adopted to desynchronize/synchronize the arbitration decisions made by different inputs/outputs. As compared to the existing schedulers, our 2BSI is one of the simplest algorithms to implement, and yet extensive simulation results show that it provides one of the best delay-throughput performances.

We consider scheduling mixed unicast and multicast traffic with variable-size packets in an input-queued switch. When variable-size packets arrive at a switch input port, they will be segmented into cells (fixed-size packets), sent across the switch fabric, and reassembled at outputs. A scheduling algorithm should focus on optimizing packet performance rather than cell performance. In this paper, packet-mode scheduling is adopted such that cells of the same packet are sent back-to-back in consecutive slots. For efficiency, an iterative scheduling algorithm called three-bit single-iteration (3BSI) is proposed to concurrently schedule both unicast and multicast traffic. To the best of our knowledge, 3BSI is the first packet-mode scheduling algorithm for handling mixed traffic with variable-size packets. Despite its simplicity, extensive simulation shows that 3BSI provides excellent delay-throughput performance.

Literature on coflow-aware packet scheduling for input-queued switches is limited. Yet most of them are offline algorithms, requiring (unrealistic) a priori knowledge of all coflows and solving (time-consuming) linear programming (LP) problems for determining their expected coflow completion times (CCTs). In this paper, we propose an efficient online packet scheduling algorithm called Critical Line First (CLF). In CLF, coflows are ordered based on their easy-to-find ideal CCTs, or would-be-CCTs. In scheduling, coflows with the smallest would-be-CCTs are considered first; for each coflow chosen, packets on most heavily loaded rows/columns, i.e., critical lines, of the coflow traffic matrix are scheduled first. To avoid starvation, we propose to limit the number of times a coflow can be preempted by other coflows. Extensive simulation results show that our CLF outperforms all existing algorithms.

In Internet mapping, IP address space is divided into a set of client aggregation units, which are the finest-grained units for global load balancing. Choosing the proper level of aggregation is a complex problem, which determines the number of aggregation units that a mapping system has to maintain and client redirection. In this paper, using Internet-wide measurements provided by a commercial global load balancing service provider, we show that even for the best existing client aggregation, almost 17% of clients have latency more than 50 ms apart from the average latency of clients in the same aggregation unit. To address this, we propose a data-driven client aggregation, AP-atoms, which can trade off scalability for accuracy and adapt for changing network conditions. Since AP-atoms are obtained from the passive measurements of existing traffic between server providers and clients, no extra measurement overheads are incurred. Our experiments show that by using the same scale of client aggregations, AP-atoms can reduce the number of widely dispersed clients by almost $2\times $ and the 98th percentile difference in clients' latencies by almost 100 ms.

We focus on designing efficient integrated schedulers for handling mixed unicast and multicast traffic. We consider an input-queued switch with a multicast-capable switch fabric. At each input port of the switch, there are N dedicated unicast VOQs and one shared multicast queue (MQ). An existing approach to the design of integrated scheduler (i.e., a sequential scheduler) is to run two component schedulers, one for multicast and one for unicast, sequentially in each time slot. To minimize the head-of-line blocking of multicast traffic, the multicast scheduler always runs first. But sequentially running two schedulers in each time slot is challenging, especially when the slot duration is small. In this paper, we first propose a pipelined integration of the two component schedulers (i.e., a pipelined scheduler), which allows twice the amount of time for each scheduler to execute. We then extend an existing single-bit- single-iteration unicast scheduler to ensure that even in the presence of multicast traffic, unicast traffic will be starvation-free. This is achieved by giving unicast traffic priority over multicast periodically. Finally, we present arguably the first single-bit-single-iteration multicast scheduling algorithm. Extensive simulation results show that our pipelined scheduler is efficient and provides delay-throughput performance comparable to the sequential scheduler.

A probabilistic quorum system (PQS) allows distributed services to be replicated on only a subset (quorum) of servers. The replicas can be kept consistent with high levels of assurance as long as any two quorums intersect with very high probability. PQS thus provides a means to trade off levels of consistency against the scalability and efficiency of a quorum system. When quorums are constructed by choosing members of the subset uniformly at random, the non-intersection probability can be easily computed. On a distributed system with n servers, uniform sampling is often conducted using random walk of length O(log n). To collect multiple uniform samples naively would require as many random walks. A number of works have relied on analytical results based on the Chernoff bound to reduce the number of random walks needed to collect multiple samples. Controlled flooding is another efficient method to collect multiple samples. In this paper we evaluate both methods analytically and found that quorums formed using either method cannot satisfy the non-intersection probability bound associated with quorum formed by uniform sampling. Our contributions are: (1) to show that overlay topology can be constructed to cache multiple random walks, (2) to show that repeated use of this cache to obtain multiple uniform samples leads to degradation of sample uniformity over time, and (3) to propose and evaluate graph re-wiring as a simple method to keep the cache fresh, to take advantage of overhead reduction of random walk caching while alleviating the degradation in sample uniformity.

In a data center with TCP/IP communications, it is generally believed that packet-based load balancing is not suitable because the associated packet out-of-order problem will significantly lower the network utilization. In this paper, we first show that if packet-based load balancing is performed properly in a fat-tree based data center, the packet out-of-order problem is not as severe as most researchers believed. This is due to the fact that multiple (minimal) paths between any given pair of servers in a fat-tree are of the same hop count. If packets are evenly routed onto different paths, they will experience similar delay performance. As a result, the packet out-of-order arrivals at the receiver are usually within a small sequence number range. Notably, the fast retransmit (FR) algorithm in TCP will be triggered for resending the “lost” packet if three duplicate ACKs are received (i.e. FR threshold is three). To provide leeway for out-of-order packet arrivals due to packet-based load balancing, we propose to judiciously increase the FR threshold. Simulation results show that FR threshold values between 6 and 9 can effectively suppress unnecessary fast retransmits and at the same time, the impact to real packet losses is minimal. Compared to a flow-based load balancing scheme, we found that our packet-based load balancing with modified TCP consistently provides higher goodput and noticeably smaller delay.

Live broadcast over a peer-to-peer (P2P) network imposes a unique set of challenges to a digital rights management (DRM) system. Highly correlated service request arrivals at the start of a live event require peak-load provisioning if clients acquire licenses at playback time. Distributing the license management load across a P2P network requires the digital rights management system to ensure the integrity of both digital rights, the protection of client privacy and, at the same time, system scalability. In this paper we describe the requirements imposed on a digital rights management system in distributing live broadcast over a P2P network and present our design of such a system to meet the above challenges. We discuss the system's operation under a number of threat models and how to extend the system to further improve scalability and support network digital video recording (DVR). We close the paper after presenting some scalability results collected from a production P2P live broadcast network using our DRM design.

Live broadcast over a P2P (peer-to-peer) network imposes a unique set of challenges to a digital rights management system. Highly correlated service request arrivals at the start of a live event require peak-load provisioning if clients acquire licenses at playback time. Distributing the license management load across a P2P network requires the digital rights management system to ensure the integrity of both digital rights, the protection of client privacy and, at the same time, system scalability. In this paper we describe the requirements imposed on a digital rights management system in distributing live broadcast over a P2P network and present our design of such a system to meet the above challenges. We discuss the system's operation under a number of threat models and how to extend the system to further improve scalability. We close the paper after presenting some scalability results collected from a production P2P live broadcast network using our DRM design.

A number of commercial peer-to-peer (P2P) systems for live streaming have been introduced in recent years. The behavior of these popular systems has been extensively studied in several measurement papers. Due to the proprietary nature of these commercial systems, however, these studies have to rely on a “black-box” approach, where packet traces are collected from a single or a limited number of measurement points, to infer various properties of traffic on the control and data planes. Although such studies are useful to compare different systems from the end-user's perspective, it is difficult to intuitively understand the observed properties without fully reverse-engineering the underlying systems. In this paper, we describe the network architecture of Zattoo, one of the largest production live streaming providers in Europe at the time of writing, and present a large-scale measurement study of Zattoo using data collected by the provider. To highlight, we found that even when the Zattoo system was heavily loaded with as high as 20 000 concurrent users on a single overlay, the median channel join delay remained less than 2-5 s, and that, for a majority of users, the streamed signal lags over-the-air broadcast signal by no more than 3 s.

Television transmitted over IP (IPTV) presents numerous opportunities for users as well as service providers, and has attracted significant interest from business and research communities in recent years. Among the emerging IPTV delivery architectures, the peer-to-peer based delivery mechanism is considered attractive due to the relative ease of service deployment. However, the question of how well P2PTV applications would support a growing number of users has not been fully investigated so far. In this paper, we try to address this question by studying scalability and efficiency factors in a typical P2P based live streaming network. Through the use of the data provided by a production P2PTV system, we carry out simulations whose results show that there are still hurdles to overcome before P2P based live streaming could become widely used.

A number of commercial peer-to-peer systems for live streaming, such as PPLive, Joost, LiveStation, SOPCast, TVants, etc. have been introduced in recent years. The behavior of these popular systems has been extensively studied in several measurement papers. Due to the proprietary nature of these commercial systems, however, these studies have to rely on a "black-box" approach, where packet traces are collected from a single or a limited number of measurement points, to infer various properties of traffic on the control and data planes. Although such studies are useful to compare different systems from end-user's perspective, it is difficult to intuitively understand the observed properties without fully reverse-engineering the underlying systems. Our paper presents a large-scale measurement study of Zattoo, one of the largest production live streaming providers in Europe, using data collected by the provider. To highlight, we found that even when the Zattoo system was heavily loaded with as high as 20,000 concurrent users on a single overlay, the median channel join delay remained less than 2 to 5 seconds, and that, for a majority of users, the streamed signal lags over-the-air broadcast signal by no more than 3 seconds. To motivate the measurement study, we also present a description of the Zattoo network architecture.

A P2PTV system allows users to watch live video streams redistributed by other users via a peer-to-peer (P2P) network. In an ideal world, each peer in a P2P network would be able to redistribute more bytes than it receives. A P2PTV system built from such peers can support a virtually unlimited number of peers; with only a single copy of content stream injected into the network, it can redistribute the content to all peers. Two factors in the development of the Internet prevented the realization of this scenario: the deployment of asymmetric access networks and the adoption of NAT boxes. For real-time live streaming, such peer asymmetry and incompatibility is a limiting factor on the P2P network scalability. We first develop a basic formal analysis of the effect of bandwidth asymmetry on P2P network scalability. Then we present several characteristics of peer asymmetry as measured on the Zattoo P2PTV network. Our simulation results, driven by the measured peer characteristics, confirm that we cannot rely on P2P network alone to distribute live streaming content on today's Internet.

Compared with file-sharing and distributed hash table (DHT) network, P2P video streaming is more vulnerable to denial of service (DoS) attacks because of its high bandwidth demand and stringent time requirement. This paper studies the design of DoS resilient streaming networks using credit systems. We propose a novel framework-ripple-stream-to improve DoS resilience of P2P streaming. Ripple-stream leverages existing credit systems to introduce credit constraints in overlay construction such that malicious nodes are pushed to the fringe of overlays. Combining credit constraints with overlay optimization techniques, ripple-stream can achieve both DoS resilience and overlay efficiency

Abstract — Internet connectivity at the AS level, defined in terms of pairwise logical peering relationships, is constantly evolving. This evolution is largely a response to economic, political, and technological changes that impact the way ASs conduct their business. We present a new framework for modeling this evolutionary process by identifying a set of criteria that ASs consider either in establishing a new peering relationship or in reassessing an existing relationship. The proposed framework is intended to capture key elements in the decision processes underlying the formation of these relationships. We present two decision processes that are executed by an AS, depending on its role in a given peering decision, as a customer or a peer of another AS. When acting as a peer, a key feature of the AS’s corresponding decision model is its reliance on realistic inter-AS traffic demands. To reflect the enormous heterogeneity among customer or peer ASs, our decision models are flexible enough to accommodate a wide range of AS-specific objectives. We demonstrate the potential of this new framework by considering different decision models in various realistic “what if ” experiment scenarios. We implement these decision models to generate and study the evolution of the resulting AS graphs over time, and compare them against observed historical evolutionary features of the Internet at the AS level. I.

Knowing network topology is becoming increasingly important for a number of applications such as server placement (E. Cronin et al., 2002) and traceback of DDoS attacks (D. Song and A. Perrig, 2001), Recent works in modeling the Internet topology and constructing network maps have focused on the connectivity aspect. This paper describes our study on incorporating connectivity, latency, and routing information all into a network map based on a large set of traceroute data. We introduce a model for constructing such a network map. We evaluate our network map based on various Internet routing models proposed in the literature. The evaluation shows that, for those traceroute data that we are able to evaluate, at least 85% of computed hop-counts and latencies are within a factor of two of the actual values. Furthermore, we show that a flat routing model based on hop-count performs as well as more complicated routing models.

Network-overlay construction today assumes two-way communication capability - each host can initiate outgoing connections as well as accepting incoming connections. This is often not true on the current Internet due to several reasons, for example, the use of network address translation (NAT) and firewalls. Our experiments with eDonkey and Gnutella file-sharing systems reveal that as many as 36% of the hosts may be guarded - not accepting incoming connections. This presents a challenge to overlay construction because not all hosts are capable of receiving and forwarding requests. We propose an overlay optimization called e* to help existing overlay protocols overcome the reachability problem. Furthermore, e* builds very efficient overlay networks in terms of latency. Under realistic scenarios involving guarded hosts, e* can reduce the average overlay latency by 28-61% compared with existing protocols.

We call end-hosts behind network address translator (NAT) gateways or firewalls guarded hosts, and otherwise open hosts. In this paper, we empirically measure the prevalence of guarded hosts in two popular peer-to-peer file sharing systems, eDonkey and Gnutella, and study the characteristics of their shared files. By performing passive and active probes, we found that about 25-36% of eDonkey and Gnutella users reside on guarded hosts and that the ratio of files shared by guarded hosts is also non-trivial. When discounting guarded hosts, we found that a popular file's availability, i.e., the number of copies available for download, decreases by 25-30%. Our measurement study testifies to the significant impact guarded hosts may have on the performance of current peer-to-peer file sharing systems, and points to a need to consider their presence when designing next generation peer-to-peer systems.

Streaming media transfers over the Internet are expected to behave in a TCP-friendly manner while reacting slower to congestion than TCP. For this purpose, a number of slowly-responsive congestion control protocols have been developed. In this paper, we present our study on the media-friendliness of TFRC, one of the recently developed slowly-responsive congestion control mechanisms. With both simulation and Internet experiments, we show that TFRC is not necessarily smooth enough to be "media-friendly". We also discuss our approach to improve a congestion control mechanism's media-friendliness.

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it.We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use FSS.

Several Internet mapping and topology discovery applications inspect multiple IP (Internet protocol) addresses to discover Internet address regions that are alive, i.e., contain IP addresses that elicit replies to probes. Currently, the traditional approach in examining these IP addresses is completely random, uses exhaustive scan, or focuses on a common wisdom of checking the first IP in each address region. In this paper, we first formalize the discovery process, then we provide an efficient solution to the problem of declaring an address prefix (AP) alive by discovering a reachable host within its addressable range. We develop and evaluate an optimal discovery path that prioritizes and orders probes to a small subset of IP addresses within each AP. Using our optimal discovery path technique, we show that examining a maximum of 11 different IP addresses within each AP successfully reveals the aliveness of more than 90% of the APs.

The Internet distance map service (IDMaps) [P. Francis, S. Jamin, C. Jin, D. Raz, Y. Shavitt, and L. Zhang, 2001] provides distance estimates between any pair of hosts connected to the Internet. The IDMaps system comprises two component types: tracers that measure distance between IP address prefixes, and servers that collect measurement results and answer distance queries. The distance information protocol (DIP) is used for tracers to report measured distance data to servers. The dynamics on the Internet topology, the distributed nature of autonomous tracers and servers, and the vast size of the data set require that DIP provide highly adaptive and scalable data dissemination from tracers to servers. DIP is a soft-state announce/listen protocol and scales independently from the total amount of measurement data by all tracers. DIP achieves its scalability through combination of staged timers, positive feedback, and feedback suppression techniques, which enable DIP to disseminate only the most useful measurement data to servers in a dynamic way. Simulations verified DIP's scalability and adaptability under various network conditions.

An important aspect of improving streaming application performance is the streaming quality evaluation process. In this paper we introduce a set of alternative objective streaming video quality metrics, which are suitable for large scale deployment. Derived from an existent media application, our metrics are designed to capture the application behaviors disrupting the streaming video quality. We also present a set of experiments to demonstrate the effectiveness of these metrics.

Switch-trees are peer-to-peer algorithms for building and improving end-host multicast trees. Nodes switch parents to reduce tree cost or lower source-member latency. A node switches parents by disconnecting from its parent and reconnecting to a new parent. If the new parent is well chosen, the performance of the tree is improved overall. We look at the performance of switch-trees using the following metrics: cost, latency, link stress and number of switches. Simulations show switch-tree algorithms can build trees of hundreds of nodes at less than twice the optimal cost. In addition, we describe our implementation of a switch-tree protocol. Experiments show that our protocol builds low-cost trees in practice.

C. Faloutsos et al. (see Proc. ACM SIGCOMM, 1999) found that the inter autonomous system (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of A.-L. Barabasi and R. Albert (see Science, p.509-512, 1999) and its application to network topology generation in the work of A. Medina et al. (see Proc. MASCOTS, 2001) have explored a promising class of models that yield strict power-law vertex degree distributions. We re-examine the BGP (border gateway protocol) measurements that form the basis for the results reported by Faloutsos et al. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (original maps) typically miss 20-50% or even more of the physical links in AS maps constructed using additional sources (extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed by Barabasi and Albert. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed by Barabasi and Albert.

While the advantages of multicast delivery over multiple unicast deliveries is undeniable, the deployment of the IP multicast protocol has been limited to "islands" of network domains under single administrative control. Deployment of inter-domain multicast delivery has been slow due to both technical and administrative reasons. In this paper we propose a Host Multicast Tree Protocol (HMTP) that (1) automates the interconnection of IP-multicast enabled islands and (2) provides multicast delivery to end hosts where IP multicast is not available. With HMTP, end-hosts and proxy gateways of IP multicast-enabled islands can dynamically create shared multicast trees across different islands. Members of an HMTP multicast group self-organize into an efficient, scalable and robust multicast tree. The tree structure is adjusted periodically to accommodate changes in group membership and network topology. Simulation results show that the multicast tree has low cost, and data delivered over it experiences moderately low latency.

Following the long-held belief that the Internet is hierarchical, the network topology generators most widely used by the Internet research community, Transit-Stub and Tiers, create networks with a deliberately hierarchical structure. However, in 1999 a seminal paper by Faloutsos et al. revealed that the Internet's degree distribution is a power-law. Because the degree distributions produced by the Transit-Stub and Tiers generators are not power-laws, the research community has largely dismissed them as inadequate and proposed new network generators that attempt to generate graphs with power-law degree distributions.Contrary to much of the current literature on network topology generators, this paper starts with the assumption that it is more important for network generators to accurately model the large-scale structure of the Internet (such as its hierarchical structure) than to faithfully imitate its local properties (such as the degree distribution). The purpose of this paper is to determine, using various topology metrics, which network generators better represent this large-scale structure. We find, much to our surprise, that network generators based on the degree distribution more accurately capture the large-scale structure of measured topologies. We then seek an explanation for this result by examining the nature of hierarchy in the Internet more closely; we find that degree-based generators produce a form of hierarchy that closely resembles the loosely hierarchical nature of the Internet.

For the past two years,there has been a significant increase in research activities related to studying and modeling the Internet's topology, especially at the level of autonomous systems (ASs). A closer look at the measurements that form the basis for all these studies reveals that the data sets used consist of the BGP routing tables collected by the Oregon route server (henceforth, the Oregon route-views) [1]. So far, there has been anecdotal evidence and an intuitive understanding among researchers in the field that BGP-derived AS connectivity is not complete. However, as far as we know, there has been no systematic study on quantifying the completeness of currently known AS-level Internet topologies. Our main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology. One of the main contributions of this paper is in developing a methodology that enables quantitative investigations into issues related to the (in)completeness of BGP-derived AS maps.

Web content providers and content distribution network (CDN) operators often set up mirrors of popular content to improve performance. Due to the scale and decentralized administration of the Internet, companies have a limited number of sites (relative to the size of the Internet) where they can place mirrors. We formalize the mirror placement problem as a case of constrained mirror placement, where mirrors can only be placed on a preselected set of candidates. We study performance improvement in terms of client round-trip time (RTT) and server load when clients are clustered by the autonomous systems (AS) in which they reside. Our results show that, regardless of the mirror placement algorithm used, for only a surprisingly small range of values there is an increase in the number of mirror sites (under the constraint) effective in reducing the client to server RTT and server load. In this range, we show that greedy placement performs the best.

Internet service providers and infrastructural companies often employ mirrors of popular content to decrease client download time and server load. Due to the immense scale of the Internet and decentralized administration of the networks, companies have a limited number of sites (relative to the size of the Internet) where they can place mirrors. Mirrors of popular content are usually replicated on every site to maximize reachability to clients. We study the performance improvements as the number of mirrors increases under different placement algorithms subject to the constraint that mirrors can be placed only at certain locations. Although there are extensive theoretical studies on center placement and, analytical and empirical studies on Web cache placement, we are not aware of any published literature on mirror placement especially in the case of constrained mirror placement. Our results show that increasing the number of mirror sites under the constraint is effective in reducing client download time and reducing server load only for a surprisingly small range of values regardless of the mirror placement algorithm.

There is an increasing need to quickly and efficiently learn network distances, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, Internet content providers often place data and server mirrors throughout the Internet to improve access latency for clients, and it is necessary to direct clients to the nearest mirrors based on some distance metric in order to realize the benefit of the mirrors. We suggest a scalable Internet-wide architecture, called IDMaps, which measures and disseminates distance information on the global Internet. Higher level services can collect such distance information to build a virtual distance map of the Internet and estimate the distance between any pair of IP addresses. We present our solutions to the measurement server placement and distance map construction problems in IDMaps. We show that IDMaps can indeed provide useful distance estimations to applications such as nearest mirror selection.

Relaxed real time services that do not provide guaranteed loss rates or delay bounds are of considerable interest in the Internet, since these services can achieve higher utilization than hard real time services while still providing adequate service to adaptive real-time applications. Achieving this higher level of utilization depends on an admission control algorithm that does not rely on worst-case bounds to guide its admission decisions. Measurement-based admission control is one such approach, and several measurement-based admission control algorithms have been proposed in the literature. In this paper, we use simulations to compare the performance of several of these algorithms. We find that all of them achieve nearly the same utilization for a given packet loss rate, and that none of them are capable of accurately meeting loss targets.

The IDMaps project aims to provide a distance map of the Internet from which relative distances between hosts on the Internet can be gauged. Many distributed systems and applications can benefit from such a distance map service, for example, a common method to improve user-perceived performance of the Internet is to place data and server mirrors closer to clients. When a client tries to access a mirrored server, which mirror should it access? With IDMaps, the closest mirror can be determined based on distance estimates between the client and the mirrors. In this paper we investigate both graph theoretic methods and ad hoc heuristics for instrumenting the Internet to obtain distance maps. We evaluate the efficacy of the resulting distance maps by comparing the determinations of the closest replica using known topologies against those obtained using the distance maps.

Current HTTP servers process requests using a first-come first-serve queuing policy. What this implies is that the WWW server must process each request as it arrives. The result is that the more requests a client makes, the more replies the server will generate in response. Unfortunately, the bandwidth of the network and the processing capabilities of the server are often limited resulting in an aggressive client, or sets of clients, consuming the majority of the server's resources, limiting other clients' ability to use their fair allocation. While the traditional behavior of a Web server works efficiently for a Web site that is non-discriminating towards all clients, guaranteeing service for preferred clients from the server itself is not yet possible. This paper describes the algorithm we have designed and implemented on the Apache HTTP server, which has been shown to be effective in allocating configurable fixed percentages of bandwidth across numerous simultaneous clients, independent of the aggressiveness of the clients' requests.

The advent of electronic commerce and personal communications on the Internet has heightened concern over lack of privacy and security. Network services providing a wide range of security related guarantees are increasingly based on public key certificates. A fundamental problem inhibiting the wide acceptance of existing certificate distribution services is the lack of a scalable certificate revocation mechanism. We argue in this paper that the resource requirements of extant revocation mechanisms place a significant burden on certificate servers and network resources. We propose a novel mechanism called windowed revocation that satisfies the security policies and requirements of existing mechanisms and, at the same time, reduces the burden on certificate servers and network resources. We include a proof of correctness of windowed revocation and analyze worst case performance scenarios.

There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal content Web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggest an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area.

We compare the performance of four admission control algorithms-one parameter-based and three measurement-based-for controlled-load service. The parameter-based admission control ensures that the sum of reserved resources is bounded by the capacity. The three measurement-based algorithms are based on measured bandwidth, acceptance region and equivalent bandwidth. We use simulation on several network scenarios to evaluate the link utilization and adherence to service commitment achieved by these four algorithms.

Many designs for integrated services networks offer a bounded delay packet delivery service to support real-time applications. To provide a bounded delay service, networks must use admission control to regulate their load. Previous work on admission control mainly focused on algorithms that compute the worst case theoretical queueing delay to guarantee an absolute delay bound for all packets. In this paper, we describe a measurement-based admission control algorithm (ACA) for predictive service, which allows occasional delay violations. We have tested our algorithm through simulations on a wide variety of network topologies and driven with various source models, including some that exhibit long-range dependence, both in themselves and in their aggregation. Our simulation results suggest that measurement-based approach combined with the relaxed service commitment of predictive service enables us to achieve a high level of network utilization while still reliably meeting the delay bound.

Many designs for integrated service networks offer a bounded delay packet delivery service to support real-time applications. To provide bounded delay service, networks must use admission control to regulate their load. Previous work on admission control mainly focused on algorithms that compute the worst case theoretical queueing delay to guarantee an absolute delay bound for all packets. In this paper we describe a measurement-based admission control algorithm for predictive service, which allows occasional delay violations. We have tested our algorithm through simulations on a wide variety of network topologies and driven with various source models, including some that exhibit long-range dependence, both in themselves and in their aggregation. Our simulation results suggest that, at least for the scenarios studied here, the measurement-based approach combined with the relaxed service commitment of predictive service enables us to achieve a high level of network utilization while still reliably meeting the delay bound.

In this paper, we characterize wide-area network applications that use the TCP transport protocol.We also describe a new way to model the wide-area traffic generated by a stub network.We believe the fmffic model presented here will be useful in studying congestion control, routing algorithms, and other resource management schemes for existing and future networks.Our model is based on trace analysis of TCP/IP widearea intemetwork traffic.We collected the TCP/IP packet headers of USC, UCB, and Bellcore networks at the point they connect with their respective regional access networks.We then wrote a handful of programs to analyze the traces.Our model characterizes individual TCP conversations by the distributions ofi number of bytes transfemed, duration, number of packets transferred, packet size, and packet interarrival time.Our trace analysis shows that both interactive and bulk transfer traffic from all sites reflect a large number of short conversations.Similarly, it shows that a very large percentage of traffic is bidirectional, even for bulk transfer.We observed that interactive applications send significantly different amounts of data in each direction of a conversation, and that interarrival times for interactive applications closely follow a constant plus exponential model.Half of the conversations are directed to a handful of networks, but the other half are directed to hundreds of networks.Many of these observations contradict commonly held beliefs regarding wide-area traffic.