Although neural networks have demonstrated significant success in various reinforcement-learning tasks, even the highest-performing deep models often fail to generalize. As an alternative, object-oriented approaches offer a promising path towards better efficiency and generalization; however, they typically address narrow problem classes and require extensive domain knowledge. To overcome these limitations, we introduce QORA, an algorithm that constructs models expressive enough to solve a variety of domains, including those with stochastic transition functions, directly from a domain-agnostic object-based state representation. We also provide a novel benchmark suite to evaluate learners’ generalization capabilities. In our test domains, QORA achieves 100% predictive accuracy using almost four orders of magnitude fewer observations than a neural-network baseline, demonstrates zero-shot transfer to modified environments, and adapts rapidly when applied to tasks involving previously unseen object interactions. Finally, we give examples of QORA’s learned rules, showing them to be easily interpretable.

In this paper, we consider applications that read sequential data from n input files and write the result into m output files, which encompasses many types of external-memory sorting, database join/group queries, and MapReduce computation. We call this I/O model bowtie streaming and develop novel algorithms for modeling its throughput, maximizing sequential run lengths, and obtaining optimal multi-pass split/merge factors under non-trivial stream-switching (i.e., seek) delay. Based on these developments, we build a platform called Tuxedo for general bowtie computation and show that it is able to perform external-memory sorting with a million times fewer attempted seeks than Hadoop and two orders of magnitude fewer than highly optimized external-memory frameworks STXXL and nsort.

In the age of big data, many graph algorithms are now required to operate in external memory and deliver performance that does not significantly degrade with the scale of the problem. One particular area that frequently deals with graphs larger than RAM istriangle listing, where the algorithms must carefully piece together edges from multiple partitions to detect cycles. In recent literature, two competing proposals (i.e., Pagh and PCF) have emerged; however, neither one is universally better than the other. Since little is known about the I/O cost of PCF or how these methods compare to each other, we undertake an investigation into the properties of these algorithms, model their I/O cost, understand their shortcomings, and shed light on the conditions under which each method defeats the other. This insight leads us to develop a novel framework we call Trigon that surpasses the I/O performance of both previous techniques in all graphs and under all RAM conditions.

Mergesort is a popular algorithm for sorting real-world workloads as it is immune to data skewness, suitable for parallelization using vectorized intrinsics, and relatively simple to multi-thread. In this paper, we introduce Origami , an in-memory merge-sort framework that is optimized for scalar, as well as all current SIMD (single-instruction multiple-data) CPU architectures. For each vector-extension set (e.g., SSE, AVX2, AVX-512), we present an in-register sorter for small sequences that is up to 8× faster than prior methods and a branchless streaming merger that achieves up to a 1.5× speed-up over the naive merge. In addition, we introduce a cache-residing quad-merge tree to avoid bottlenecking on memory bandwidth and a parallel partitioning scheme to maximize thread-level concurrency. We develop an end-to-end sort with these components and produce a highly utilized mergesort pipeline by reducing the synchronization overhead between threads. Single-threaded Origami performs up to 2× faster than the closest competitor and achieves a nearly perfect speed-up in multi-core environments.

Recent work in OS fingerprinting has focused on overcoming random distortion in network and user features during Internet-scale SYN scans. These classification techniques work under an assumption that all parameters of the profiled network are known a-priori – the likelihood of packet loss, the popularity of each OS, the distribution of network delay, and the probability of user modification to each default TCP/IP header value. However, it is currently unclear how to obtain realistic versions of these parameters for the public Internet and/or customize them to a particular network being analyzed. To address this issue, we derive a non-parametric Expectation-Maximization (EM) estimator, which we callFaulds, for the unknown distributions involved in single-probe OS fingerprinting and demonstrate its significantly higher robustness to noise compared to methods in prior work. We apply Faulds to a new scan of 67M webservers and discuss its findings.

Many applications in data analytics, information retrieval, and cluster computing process huge amounts of information. The complexity of involved algorithms and massive scale of data require a programming model that can not only offer a simple abstraction for inputs larger than RAM, but also squeeze maximum performance out of the available hardware. While these are usually conflicting goals, we show that this does not have to be the case for sequentially-processed data, i.e., in streaming applications. We develop a set of algorithms called Vortex that force the application to generate access violations (i.e., page faults) during processing of the stream, which are transparently handled in such a way that creates an illusion of an infinite buffer that fits into a regular C/C++ pointer. This design makes Vortex by far the simplest-to-use and fastest platform for various types of streaming I/O, inter-thread data transfer, and key shuffling. We introduce several such applications -- file I/O wrapper, bounded producer-consumer pipeline, vanishing array, key-partitioning engine, and novel in-place radix sort that is 3-4 times faster than the best prior approaches.

Discovering triangles in large graphs is a well-studied area; however, both external-memory performance of existing methods and our understanding of the complexity involved leave much room for improvement. To shed light on this problem, we first generalize the existing in-memory algorithms into a single framework of 18 triangle-search techniques. We then develop a novel external-memory approach, which we call Pruned Companion Files (PCF), that supports operation of all 18 algorithms, while significantly reducing I/O compared to the common methods in this area. After finding the best node-traversal order, we build an implementation around it using SIMD instructions for list intersection and PCF for I/O. This method runs 5-10 times faster than the available implementations and exhibits orders of magnitude less I/O. In one of our graphs, the program finds 1 trillion triangles in 237 seconds using a desktop CPU.

Since inception, DNS has used a TTL-based replication scheme that allows the source (i.e., an authoritative domain server) to control the frequency of record eviction from client caches. Existing studies of DNS predominantly focus on reducing query latency and source bandwidth, both of which are optimized by increasing the cache hit rate. However, this causes less-frequent contacts with the source and results in higher staleness of retrieved records. Given high data-churn rates at certain providers (e.g., dynamic DNS, CDNs) and importance of consistency to their clients, we propose that cache models include the probability of freshness as an integral performance measure. We derive this metric under general update/download processes and present a novel framework for measuring its value using remote observation (i.e., without access to the source or the cache). Besides freshness, our methods can estimate the inter-update distribution of DNS records, cache hit rate, distribution of TTL, and query arrival rate from other clients. Furthermore, these algorithms do not require any changes to the existing infrastructure/protocols.

With the proliferation of web spam and infinite autogenerated web content, large-scale web crawlers require low-complexity ranking methods to effectively budget their limited resources and allocate bandwidth to reputable sites. In this work, we assume crawls that produce frontiers orders of magnitude larger than RAM, where sorting of pending URLs is infeasible in real time. Under these constraints, the main objective is to quickly compute domain budgets and decide which of them can be massively crawled. Those ranked at the top of the list receive aggressive crawling allowances, while all other domains are visited at some small default rate. To shed light on Internet-wide spam avoidance, we study topology-based ranking algorithms on domain-level graphs from the two largest academic crawls: a 6.3B-page IRLbot dataset and a 1B-page ClueWeb09 exploration. We first propose a new methodology for comparing the various rankings and then show that in-degree BFS-based techniques decisively outperform classic PageRank-style methods, including TrustRank. However, since BFS requires several orders of magnitude higher overhead and is generally infeasible for real-time use, we propose a fast, accurate, and scalable estimation method called TSE that can achieve much better crawl prioritization in practice. It is especially beneficial in applications with limited hardware resources.

Recent work in OS fingerprinting has focused on overcoming random distortion in network and user features during Internet-scale SYN scans. These classification techniques work under an assumption that all parameters of the profiled network are known a-priori -- the likelihood of packet loss, the popularity of each OS, the distribution of network delay, and the probability of user modification to each default TCP/IP header value. However, it is currently unclear how to obtain realistic versions of these parameters for the public Internet and/or customize them to a particular network being analyzed. To address this issue, we derive a non-parametric Expectation-Maximization (EM) estimator, which we call Faulds, for the unknown distributions involved in single-probe OS fingerprinting and demonstrate its significantly higher robustness to noise compared to methods in prior work. We apply Faulds to a new scan of 67M webservers and discuss its findings.

In the age of big data, many graph algorithms are now required to operate in external memory and deliver performance that does not significantly degrade with the scale of the problem. One particular area that frequently deals with graphs larger than RAM is triangle listing, where the algorithms must carefully piece together edges from multiple partitions to detect cycles. In recent literature, two competing proposals (i.e., Pagh and PCF) have emerged; however, neither one is universally better than the other. Since little is known about the I/O cost of PCF or how these methods compare to each other, we undertake an investigation into the properties of these algorithms, model their I/O cost, understand their shortcomings, and shed light on the conditions under which each method defeats the other. This insight leads us to develop a novel framework we call Trigon that surpasses the I/O performance of both previous techniques in all graphs and under all RAM conditions.

Triangle listing has been a long-standing problem, with many heuristics, bounds, and experimental results, but not much asymptotically accurate complexity analysis. To address this issue, we introduce a novel stochastic framework, based on Glivenko-Cantelli results for functions of order statistics, that allows modeling cost of in-memory triangle enumeration in families of random graphs. Unlike prior work that usually studies the O(.) notation, we derive the exact limits of CPU complexity of all vertex/edge iterators under arbitrary acyclic orientations as graph size n → ∞. These results are obtained in simple closed form as functions of the degree distribution. This allows us to establish optimal orientations for all studied algorithms, compare them to each other, and discover the best technique within each class.

Network applications commonly maintain local copies of remote data sources in order to provide caching, indexing, and data-mining services to their clients. Modeling performance of these systems and predicting future updates usually requires knowledge of the inter-update distribution at the source, which can only be estimated through blind sampling-periodic downloads and comparison against previous copies. In this paper, we first introduce a stochastic modeling framework for this problem, where updates and sampling follow independent point processes. We then show that all previous approaches are biased unless the observation rate tends to infinity or the update process is Poisson. To overcome these issues, we propose four new algorithms that achieve various levels of consistency, which depend on the amount of temporal information revealed by the source and capabilities of the download process.

Maintaining and updating signature databases are tedious tasks that normally require a large amount of user effort. The problem becomes harder when features can be distorted by observation noise, which we call volatility. To address this issue, we propose algorithms and models to automatically generate signatures in the presence of noise, with a focus on single-probe stack fingerprinting, which is a research area that aims to discover the operating system of remote hosts using their response to a TCP SYN packet. Armed with this framework, we construct a database with 420 network stacks, label the signatures, develop a robust classifier for this database, and fingerprint 66M visible webservers on the Internet. We compare the obtained results against Nmap and discover interesting limitations of its classification process that prevent correct operation when its auxiliary probes (e.g., TCP rainbow, TCP ACK, and UDP to a closed port) are blocked by firewalls.

Discovering triangles in large graphs is a well-studied area, however, both external-memory performance of existing methods and our understanding of the complexity involved leave much room for improvement. To shed light on this problem, we first generalize the existing in-memory algorithms into a single framework of 18 triangle-search techniques. We then develop a novel external-memory approach, which we call Pruned Companion Files (PCF), that supports operation of all 18 algorithms, while significantly reducing I/O compared to the common methods in this area. After finding the best node-traversal order, we build an implementation around it using SIMD instructions for list intersection and PCF for I/O. This method runs 5-10 times faster than the best available implementation and exhibits orders of magnitude less I/O. In one of our graphs, the program finds 1 trillion triangles in 237 seconds using a desktop CPU.

Maintaining and updating signature databases is a tedious task that normally requires a large amount of user effort. The problem becomes harder when features can be distorted by observation noise, which we call volatility. To address this issue, we propose algorithms and models to automatically generate signatures in the presence of noise, with a focus on stack fingerprinting, which is a research area that aims to discover the operating system (OS) of remote hosts using TCP/IP packets. Armed with this framework, we construct a database with 420 network stacks, label the signatures, develop a robust classifier for this database, and fingerprint 66M visible webservers on the Internet.

We analyze synchronization issues between two point processes, one modeling data churn at an information source and the other periodic downloads to its replica (e.g., search engine, web cache, distributed database). Due to pull-based synchronization, the replica experiences recurrent staleness, which translates into some form of penalty stemming from its reduced ability to perform consistent computation and/or provide up-to-date responses to customer requests. We model this system under non-Poisson update/refresh processes and obtain sample-path averages of various metrics of staleness cost, generalizing previous results and exposing novel problems in this field.

Traditional TCP/IP fingerprinting tools (e.g., nmap) are poorly suited for Internet-wide use due to the large amount of traffic and intrusive nature of the probes. This can be overcome by approaches that rely on a single SYN packet to elicit a vector of features from the remote server. However, these methods face difficult classification problems due to the high volatility of the features and severely limited amounts of information contained therein. Since these techniques have not been studied before, we first pioneer stochastic theory of single-packet OS fingerprinting, build a database of 116 OSs, design a classifier based on our models, evaluate its accuracy in simulations, and then perform OS classification of 37.8M hosts from an Internet-wide scan.

We analyze synchronization issues arising between two stochastic point processes, one of which models data churn at an information source and the other periodic downloads from its replica (e.g., search engine, web cache, distributed database). Due to lazy (pull-based) synchronization, the replica experiences recurrent staleness, which translates into some form of penalty stemming from its reduced ability to perform consistent computation and/or provide up-to-date responses to customer requests. We model this system under non-Poisson update/refresh processes and obtain sample-path averages of various metrics of staleness cost, generalizing previous results and exposing novel problems in this field.

Network applications commonly maintain local copies of remote data sources in order to provide caching, indexing, and data-mining services to their clients. Modeling performance of these systems and predicting future updates usually requires knowledge of the inter-update distribution at the source, which can only be estimated through blind sampling - periodic downloads and comparison against previous copies. In this paper, we first introduce a stochastic modeling framework for this problem, where the update and sampling processes are both renewal. We then show that all previous approaches are biased unless the observation rate tends to infinity or the update process is Poisson. To overcome these issues, we propose four new algorithms that achieve various levels of consistency, which depend on the amount of temporal information revealed by the source and capabilities of the download process.

Many BigData applications (e.g., MapReduce, web caching, search in large graphs) process streams of random key-value records that follow highly skewed frequency distributions. In this work, we first develop stochastic models for the probability to encounter unique keys during exploration of such streams and their growth rate over time. We then apply these models to the analysis of LRU caching, MapReduce overhead, and various crawl properties (e.g., node-degree bias, frontier size) in random graphs.

Exponential growth of the web continues to present challenges to the design and scalability of web crawlers. Our previous work on a high-performance platform called IRLbot [28] led to the development of new algorithms for realtime URL manipulation, domain ranking, and budgeting, which were tested in a 6.3B-page crawl. Since very little is known about the crawl itself, our goal in this paper is to undertake an extensive measurement study of the collected dataset and document its crawl dynamics. We also propose a framework for modeling the scaling rate of various data structures as crawl size goes to infinity and offer a methodology for comparing crawl coverage to that of commercial search engines.

We revisit link lifetimes in random P2P graphs under dynamic node failure and create a unifying stochastic model that generalizes the majority of previous efforts in this direction. We not only allow nonexponential user lifetimes and age-dependent neighbor selection, but also cover both active and passive neighbor-management strategies, model the lifetimes of incoming and outgoing links, derive churn-related message volume of the system, and obtain the distribution of transient in/out degree at each user. We then discuss the impact of design parameters on overhead and resilience of the network.

MapReduce is a highly acclaimed programming paradigm for large-scale information processing. However, there is no accurate model in the literature that can precisely forecast its run-time and resource usage for a given workload. In this paper, we derive analytic models for shared-memory MapReduce computations, in which the run-time and disk I/O are expressed as functions of the workload properties, hardware configuration, and algorithms used. We then compare these models against trace-driven simulations using our high-performance MapReduce implementation.

We consider pull-based data synchronization issues between a source and its replicas in P2P networks. Under continuous information change and lazy synchronization, these systems are highly susceptible to serving outdated content, which negatively affects their performance and user satisfaction. To understand these scenarios, we first introduce a novel model of interaction between two stochastic point processes - updates at the source and downloads at the replica - and derive the probability that a random query against the replica retrieves fresh content. Unlike prior work, we assume non-Poisson dynamics and determine statistical properties of the replication process that make it perform better for a given download rate. The second half of the paper applies these results to several more difficult algorithms - cascaded replication, cooperative caching, and redundant querying from the clients. Surprisingly, we discover that optimal cooperation involves just a single peer and that redundant querying can hurt the ability of the system to handle load (i.e., may lead to lower scalability).

Prior work has shown that resilience of random P2P graphs under dynamic node failure can be improved by age-biased neighbor selection that delivers outbound edges to more reliable users with higher probability. However, making the bias too aggressive may cause the group of nodes that receive connections to become small in comparison to graph size. As they become overloaded, these peers are forced to reject future connection requests, which leads to potentially unbounded join delays and high traffic overhead. To investigate these issues, we propose several analytical models for understanding the interplay between resilience and degree. We formulate a Pareto-optimal objective for this tradeoff, introduce new metrics of resilience and degree, analyze them under Pareto lifetimes, and discover that traditional techniques can be highly suboptimal in this setting. We then show evidence that optimization can be solved by a family of step-functions, which connect outgoing edges to uniformly random users whose age exceeds some threshold.

Traditional TCP/IP fingerprinting tools (e.g., nmap) are poorly suited for Internet-wide use due to the large amount of traffic and intrusive nature of the probes. This can be overcome by approaches that rely on a single SYN packet to elicit a vector of features from the remote server; however, these methods face difficult classification problems due to the high volatility of the features and severely limited amounts of information contained therein. Since these techniques have not been studied before, we first pioneer stochastic theory of single-packet OS fingerprinting, build a database of 116 OSes, design a classifier based on our models, evaluate its accuracy in simulations, and then perform OS classification of 37.8M hosts from an Internet-wide scan.

Previous analytical results on the resilience of unstructured P2P systems have not explicitly modeled heterogeneity of user churn (i.e, difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a unifying model of heterogeneous user churn and derive the distribution of the various metrics observed in prior experimental studies. We also show that the arrival process of in-edges to each user converges to Poisson when system size tends to infinity, model transient behavior of in-degree, and apply these results to obtain the joint in/out-degree isolation probability.

We revisit link lifetimes in random P2P graphs under dynamic node failure and create a unifying stochastic model that generalizes the majority of previous efforts in this direction. We not only allow non-exponential user lifetimes and age-dependent neighbor selection, but also cover both active and passive neighbor-management strategies, model the lifetimes of incoming and outgoing links, derive churn-related message volume of the system, and obtain the distribution of transient in/out degree at each user. We then discuss the impact of design parameters on overhead and resilience of the network.

This paper develops a high-performance, Internet-wide service discovery tool, which we call IRLscanner, whose main design objectives have been to maximize politeness at remote networks, allow scanning rates that achieve coverage of the Internet in minutes/hours (rather than weeks/months), and significantly reduce administrator complaints. Using IRLscanner and 24-h scans, we perform 21 Internet-wide experiments using six different protocols (i.e., DNS, HTTP, SMTP, EPMAP, ICMP, and UDP ECHO), demonstrate the usefulness of ACK scans in detecting live hosts behind stateless firewalls, and undertake the first Internet-wide OS fingerprinting. In addition, we analyze the feedback generated (e.g., complaints, IDS alarms) and suggest novel approaches for reducing the amount of blowback during similar studies, which should enable researchers to collect valuable experimental data in the future with significantly fewer hurdles.

Traffic monitoring and estimation of flow parameters in high-speed routers have recently become challenging as the Internet grew in both scale and complexity. In this paper, we focus on a family of flow-size estimation algorithms we call Residual-Geometric Sampling (RGS), which generates a random point within each flow according to a geometric random variable and records all remaining packets in a flow counter. Our analytical investigation shows that previous estimation algorithms based on this method exhibit bias in recovering flow statistics from the sampled measurements. To address this problem, we derive a novel set of unbiased estimators for RGS, validate them using real Internet traces, and show that they provide an accurate and scalable solution to Internet traffic monitoring.

Intrusion Detection Systems (IDS) have become ubiquitous in the defense against virus outbreaks, malicious exploits of OS vulnerabilities, and botnet proliferation. As attackers frequently rely on host scanning for reconnaissance leading to penetration, IDS is often tasked with detecting scans and preventing them. However, it is currently unknown how likely an IDS is to detect a given Internet-wide scan pattern and whether there exist sufficiently fast scan techniques that can remain virtually undetectable at large-scale. To address these questions, we propose a simple analytical model for the window-expiration rules of popular IDS tools (i.e., Snort and Bro) and utilize a variation of the Chen-Stein theorem to derive the probability that they detect some of the commonly used scan permutations. Using this analysis, we also prove the existence of stealth-optimal scan patterns, examine their performance, and contrast it with that of well-known techniques.

This paper builds a generic modeling framework for analyzing the edge-creation process in dynamic random graphs in which nodes continuously alternate between active and inactive states, which represent churn behavior of modern distributed systems. We prove that despite heterogeneity of node lifetimes, different initial out-degree, non-Poisson arrival/failure dynamics, and complex spatial and temporal dependency among creation of both initial and replacement edges, a superposition of edge-arrival processes to a live node under uniform selection converges to a Poisson process when system size becomes sufficiently large. Due to the convoluted dependency and non-renewal nature of various point processes, this result significantly advances classical Poisson convergence analysis and offers a simple analytical platform for future modeling of networks under churn in a wide range of degree-regular and -irregular graphs with arbitrary node lifetime distributions.

This paper offers a novel look at using a dimensionality-reduction technique called simhash to detect similar document pairs in large-scale collections. We show that this algorithm produces interesting intermediate data, which is normally discarded, that can be used to predict which of the bits in the final hash are more susceptible to being flipped in similar documents. This paves the way for a probabilistic search technique in the Hamming space of simhashes that can be significantly faster and more space-efficient than the existing simhash approaches. We show that with 95% recall compared to deterministic search of prior work, our method exhibits 4-14 times faster lookup and requires 2-10 times less RAM on our collection of 70M web pages.

With the proliferation of web spam and questionable content with virtually infinite auto-generated structure, large-scale web crawlers now require low-complexity ranking methods to effectively budget their limited resources and allocate the majority of bandwidth to reputable sites. To shed light on Internet-wide spam avoidance, we study the domain-level graph from a 6.3B-page web crawl and compare several agnostic topology-based ranking algorithms on this dataset. We first propose a new methodology for comparing the various rankings and then show that in-degree BFS-based techniques decisively outperform classic PageRank-style methods. However, since BFS requires several orders of magnitude higher overhead and is generally infeasible for real-time use, we propose a fast, accurate, and scalable estimation method that can achieve much better crawl prioritization in practice, especially in applications with limited hardware resources.

Traffic monitoring and estimation of flow parameters in high speed routers have recently become challenging as the Internet grew in both scale and complexity. In this paper, we focus on a family of flow-size estimation algorithms we call Residual-Geometric Sampling (RGS), which generates a random point within each flow according to a geometric random variable and records all remaining packets in a flow counter. Our analytical investigation shows that previous estimation algorithms based on this method exhibit certain bias in recovering flow statistics from the sampled measurements. To address this problem, we derive a novel set of unbiased estimators for RGS, validate them using real Internet traces, and show that they provide an accurate and scalable solution to Internet traffic monitoring.

Previous analytical work on the resilience of P2P networks has been restricted to disconnection arising from simultaneous failure of all neighbors in routing tables of participating users. In this paper, we focus on a different technique for maintaining consistent graphs-Chord's successor sets and periodic stabilizations-under both static and dynamic node failure. We derive closed-form models for the probability that Chord remains connected under both types of node failure and show the effect of using different stabilization interval lengths (i.e., exponential, uniform, and constant) on the probability of partitioning in Chord.

Several models of user churn, resilience, and link lifetime have recently appeared in the literature; however, these results do not directly apply to classical Distributed Hash Tables (DHTs) in which neighbor replacement occurs not only when current users die, but also when new users arrive into the system, and where replacement choices are often restricted to the successor of the failed zone in the DHT space. To understand neighbor churn in such networks, which we call switching DHTs, this paper proposes a simple, yet accurate, model for capturing link dynamics in structured P2P systems and obtains the distribution of link lifetimes for fairly generic DHTs. Similar to, our results show that deterministic networks (e.g., Chord, CAN) unfortunately do not extract much benefit from heavy-tailed user lifetimes since link durations are dominated by small remaining lifetimes of newly arriving users that replace the more reliable existing neighbors. We also examine link lifetimes in randomized DHTs equipped with multiple choices for each link and show that selecting the best neighbor in these scenarios is rather complicated as it depends on the desired load balancing, link resilience, and overhead. We offer insight into the various selection algorithms, their performance, and possibilities for improvement.

This paper develops a high-performance, Internet-wide service discovery tool, which we call IRLscanner, whose main design objectives have been to maximize politeness at remote networks, allow scanning rates that achieve coverage of the Internet in minutes/hours (rather than weeks/months), and significantly reduce administrator complaints. Using IRLscanner and 24-hour scans, we perform 21 Internet-wide experiments using 6 different protocols (i.e., DNS, HTTP, SMTP, EPMAP, ICMP and UDP ECHO), demonstrate the usefulness of ACK scans in detecting live hosts behind stateless firewalls, and undertake the first Internet-wide OS fingerprinting. In addition, we analyze the feedback generated (e.g., complaints, IDS alarms) and suggest novel approaches for reducing the amount of blowback during similar studies, which should enable researchers to collect valuable experimental data in the future with significantly fewer hurdles.

Bandwidth estimation plays an important role in characterizing Internet paths. Existing approaches can be classified into measurement tools [3],[6],[9],[10],[16],[17],[23],[29], which usually have extensive simulations, but no convergence analysis for general cross-traffic, and theoretical models [5],[14],[19],[20],[22], which usually have provable convergence, but no practical implementation. Another issue in related work is the unknown performance of certain proposed algorithms in real networks where delay measurements are not perfect due to various OS and hardware-related timing irregularities [26]. We address the former issue by developing a measurement tool PRC-MT that not only achieves asymptotic accuracy in multi-path networks with arbitrary cross-traffic, but also simultaneously measures the capacity and available bandwidth of the tight link. We address the latter issue by performing a comparison study of existing tools in Emulab and assessing their susceptibility to timing irregularities of end-hosts. Our results show that PRC-MT outperforms all existing tools in terms of accuracy, achieves similar convergence delay, and does not require any manual configuration. We also find that interrupt moderation may cause existing tools (such as Pathload [10], Pathchirp [27], and CapProbe[16]) to become quite inaccurate in certain network configurations and exhibit behavior completely different from that in ns2 [28].

Existing algorithms for utilizing high-capacity nodes in heterogeneous P2P systems (e.g.) often require unrealistically large node degree and high maintenance overhead in P2P networks with highly diverse node capacities and high churn. In this paper, we propose an unstructured P2P system that addresses these issues. We first prove that the overall throughput of search queries in a heterogeneous network is maximized if and only if traffic load through each node is proportional to its capacity. We then propose a system that achieves this traffic distribution by biasing search walks using the Metropolis-Hastings algorithm without requiring any special underlying topology. We finish the paper by comparing our method with Gia, where we find in simulation that the former outperforms the latter under all studied conditions, two novel saturation metrics introduced in this paper, and such end-to-end parameters as query success rate, latency, and query-hits.

Characterizing user churn has become an important topic in studying P2P networks, both in theoretical analysis and system design. Recent work has shown that direct sampling of user lifetimes may lead to certain bias (arising from missed peers and round-off inconsistencies) and proposed a technique that estimates lifetimes based on sampled residuals. In this paper, however, we show that under non-stationary arrivals, which are often present in real systems, residual-based sampling does not correctly reconstruct user lifetimes and suffers a varying degree of bias, which in some cases makes estimation completely impossible. We overcome this problem using two contributions: a novel non-stationary ON/OFF churn model and an unbiased randomized residual sampling technique for measuring user lifetimes. The former allows correlation between ON/OFF periods of the same user and exhibits different join rates during the day. The latter spreads sampling points uniformly during the day and uses a novel estimator to reconstruct the underlying lifetime distribution. We finish the paper with experimental measurements of Gnutella and discussing reduction in overhead compared to direct sampling methods.

This paper presents a frame-level hybrid framework for modeling MPEG-4 and H.264 multi-layer variable bit rate (VBR) video traffic. To accurately capture long-range-dependent and short-range-dependent properties of VBR sequences, we use wavelets to model the distribution of I-frame sizes and a simple time-domain model for P/B frame sizes. However, unlike previous studies, we analyze and successfully model both inter-GOP (group of pictures)andintra-GOP correlation in VBR video and build an enhancement-layer model using cross-layer correlation. Simulation results demonstrate that our model effectively preserves the temporal burstiness and captures important statistical features (e.g., the autocorrelation function and the frame-size distribution) of original traffic. We also show that our model possesses lower complexity and has better performance than the previous methods in both single- and multi-layer sequences.

This article shares our experience in designing a Web crawler that can download billions of pages using a single-server implementation and models its performance. We first show that current crawling algorithms cannot effectively cope with the sheer volume of URLs generated in large crawls, highly branching spam, legitimate multimillion-page blog sites, and infinite loops created by server-side scripts. We then offer a set of techniques for dealing with these issues and test their performance in an implementation we call IRLbot. In our recent experiment that lasted 41 days, IRLbot running on a single server successfully crawled 6.3 billion valid HTML pages (7.6 billion connection requests) and sustained an average download rate of 319 mb/s (1,789 pages/s). Unlike our prior experiments with algorithms proposed in related work, this version of IRLbot did not experience any bottlenecks and successfully handled content from over 117 million hosts, parsed out 394 billion links, and discovered a subset of the Web graph with 41 billion unique nodes.

In this paper, we propose an endpoint-based anomaly detection scheme that detects computer worms by comparing the current traffic patterns of each host to the corresponding benign traffic profile of the host. To detect deviations in the traffic patterns, we employ the information-theoretic Kullback-Leibler (K-L) divergence measure which estimates the distance between the distribution of source/destination ports engaged in current communication and that observed in the legitimate host traffic collected earlier. We use a small subset of traces obtained from endpoints in home, university, and office environments to build benign traffic profiles of studied endpoints. Endpoint traces are then infected with both real and simulated worms to examine the performance of our detection mechanism. To perform automated, real-time worm detection, we use Support Vector Machines (SVMs) that are trained using the K-L divergence values. Our results show that the proposed worm detector provides almost 100% detection with negligible false- alarm rates and significantly surpasses the accuracy of existing anomaly detectors.

Distance estimation and topological proximity in the Internet have recently emerged as important problems for many distributed applications [1], [10], [11], [19], [29], [31], [40], [41], [44]. Besides deploying tracers and using virtual coordinates, distance is often estimated using end-to-end methods such as King [13] that rely on the existing DNS infrastructure. However, the question of accuracy in such end-to-end estimation and its ability to produce a large-scale map of Internet delays has never been examined. We undertake this task below and show that King suffers from non-negligible error when DNS zones employ geographically diverse authoritative servers or utilize forwarders, both of which are very common in the existing Internet. We also show that King requires insertion of numerous unwanted DNS records in caches of remote servers (which is called cache pollution) and requires large traffic overhead when deployed in large-scale. To overcome these limitations, we propose a new framework we call Turbo King (T-King) that obtains end-to-end delay samples without bias in the presence of distant authoritative servers and forwarders, while consuming half the bandwidth needed by King and reducing the impact of cache pollution by several orders of magnitude. We finish the paper by evaluating Turbo King in several experiments.

We examine the asymptotic behavior of degree correlation (i.e., the joint degree distribution of adjacent nodes) in several scale-free topology generators GED [13], PLRG [1], GLP [10], BA [3], AB [2]. We present a unifying analytical framework that allows tractable analysis of degree correlation in all studied models and derive asymptotic formulas of two degree correlation metrics - assortativity and clustering. Our results indicate that all studied generators become uncorrelated as graph size increases, which is inconsistent with time-invariance of these metrics in real networks such as the Internet [36], [48], [50]. Since the class of degree-based generators is incapable of reproducing evolving characteristics of the Internet, we study three other models that evolve graphs using different rules than preference of degree (e.g., based on random walks [50], optimization [17], and geometry [23]) and show using simulations that these models are much more viable alternatives for replicating the complex structure of Internet-like graphs.

Several models of user churn, resilience, and link lifetime have recently appeared in the literature [12], [13], [34], [35]; however, these results do not directly apply to classical distributed hash tables (DHTs) in which neighbor replacement occurs not only when current users die, but also when new user arrive into the system, and where replacement choices are often restricted to the successor of the failed zone in the DHT space. To understand neighbor churn in such networks, this paper proposes a simple, yet accurate, model for capturing link dynamics in structured P2P systems and obtains the distribution of link lifetimes for fairly generic DHTs. Similar to [8], our results show that deterministic networks (e.g., Chord [28], CAN [24]) unfortunately do not extract much benefit from heavy-tailed user lifetimes since link durations are dominated by small remaining lifetimes of newly arriving users that replace the more reliable existing neighbors. We also examine link lifetimes in randomized DHTs equipped with multiple choices for each link and show that users in such systems should prefer neighbors with smaller zones rather than larger age as suggested in prior work [13], [30]. We finish the paper by demonstrating the effectiveness of the proposed min-zone neighbor selection for heavy-tailed user lifetime distributions with the shape parameter alpha obtained from recent measurements [4], [31].

Previous analytical work [15], [16] on the resilience of P2P networks has been restricted to disconnection arising from simultaneous failure of all neighbors in routing tables of participating users. In this paper, we focus on a different technique for maintaining consistent graphs - Chord's successor sets and periodic stabilizations - under both static and dynamic node failure. We derive closed-form models for the probability that Chord remains connected under both types of node failure and show the effect of using different stabilization interval lengths (i.e., exponential, uniform, and constant) on the probability of partitioning in Chord.

Innovative efforts to provide a clean-slate design of congestion control for future high-speed heterogeneous networks have recently led to the development of explicit congestion control. These methods (N. Dukkipati, et al., Jun. 2005), (S. Jain, et al., June 2007), (D. Katabi, et al., Aug. 2002), (Y. Zhang, et al., April 2006) rely on multi-byte router feedback and aim to contribute to the design of a more scalable Internet of tomorrow. However, experimental evaluation and deployment experience with these approaches, especially in high- capacity networks and multi-link settings, is still missing from the literature. This paper aims to fill this void and investigate the behavior of these methods in single and multi-link topologies involving real systems and gigabit networks. We implement four recent protocols XCP (D. Katabi, et al., Aug. 2002), JetMax (Y. Zhang, et al., April 2006), RCP (N. Dukkipati, et al., Jun. 2005) and PIQI-RCP (S. Jain, et al., June 2007) in the existing Linux TCP/IP stack (Linux) in a manner that is transparent to applications and conduct experiments in Emulab using a variety of network configurations. Our experiments not only confirm the known behavior of these methods, but also demonstrate their previously undocumented properties.

Most existing criteria [3], [5], [8] for sizing router buffers rely on explicit formulation of the relationship between buffer size and characteristics of Internet traffic. However, this is a non-trivial, if not impossible, task given that the number of flows, their individual RTTs, and congestion control methods, as well as flow responsiveness, are unknown. In this paper, we undertake a completely different approach that uses control- theoretic buffer-size tuning in response to traffic dynamics. Motivated by the monotonic relationship between buffer size and loss rate and utilization, we design a mechanism called Adaptive Buffer Sizing (ABS), which is composed of two Integral controllers for dynamic buffer adjustment and two gradient-based components for intelligent parameter training. We demonstrate via ns2 simulations that ABS successfully stabilizes the buffer size at its minimum value under given constraints, scales to a wide spectrum of flow populations and link capacities, exhibits fast convergence rate and stable dynamics in various network settings, and is robust to load changes and generic Internet traffic (including FTP, HTTP, and non-TCP flows). All of these demonstrate that ABS is a promising mechanism for tomorrow's router infrastructure and may be of significant interest for the ongoing collaborative research and development efforts (e.g., GENI and FIND) in reinventing the Internet.

This paper shares our experience in designing a web crawler that can download billions of pages using a single-server implementation and models its performance. We show that with the quadratically increasing complexity of verifying URL uniqueness, BFS crawl order, and fixed per-host rate-limiting, current crawling algorithms cannot effectively cope with the sheer volume of URLs generated in large crawls, highly-branching spam, legitimate multi-million-page blog sites, and infinite loops created by server-side scripts. We offer a set of techniques for dealing with these issues and test their performance in an implementation we call IRLbot. In our recent experiment that lasted 41 days, IRLbot running on a single server successfully crawled 6.3 billion valid HTML pages ($7.6$ billion connection requests) and sustained an average download rate of 319 mb/s (1,789 pages/s). Unlike our prior experiments with algorithms proposed in related work, this version of IRLbot did not experience any bottlenecks and successfully handled content from over 117 million hosts, parsed out 394 billion links, and discovered a subset of the web graph with 41 billion unique nodes.

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the paper by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultrapeer lifetimes in a network of 6.4 million users and 60 million links. Our experimental results show that ultrapeer lifetimes are Pareto with shape a alpha ap 1.1; however, link lifetimes exhibit much lighter tails with alpha ap 1.9.

Previous analytical studies [12], [18] of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted graphs demonstrates that for lifetimes with infinite variance, the system monotonically increases its resilience as its age and size grow. Specifically, we show that the probability of isolation converges to zero as these two metrics tend to infinity. We finish the paper with simulations in finite-size graphs that demonstrate the effect of this result in practice.

Recent research has created a significant interest [18], [19] in the design and development of a new global-scale communication network that can overcome the limitations of the current Internet. Among the many directions for improving networking technology, recent pursuit to design better flow control has led to the emergence of explicit congestion control methods that solicit active feedback from intermediate routers [5], [11], [22], [25], [26]. As a step towards understanding these methods, we analyze stability and transient performance of Rate Control Protocol (RCP) [5], which is a recent method that aims to emulate processor sharing and achieve quick flow completion. However, we find that RCP can become unstable in certain topologies and may exhibit very high buffering requirements at routers. To address these limitations, we propose a new controller called Proportional Integral Queue Independent RCP (PIQI-RCP), prove its stability under heterogeneous delay, and use ns2 simulations, as well as Linux experiments, to show that the new method has significantly better transient dynamics (i.e., much smaller link-capacity overshoot) and better stability properties in single-and multi-bottleneck scenarios.

In this paper, we show that end-host based congestion prediction is more accurate than previously characterized. However, it may not be possible to entirely eliminate the uncertainties in congestion prediction. To address these uncertainties, we propose Probabilistic Early Response TCP (PERT). PERT emulates the behavior of AQM/ECN, in the congestion response function of end-hosts. We present fluid-flow analysis of PERT/RED and PERT/PI, versions of PERT that emulate router-based RED and PI controllers. Our analysis shows that PERT/RED has better stability behavior than router-based RED. We also present results from ns-2 simulations to show the practical feasibility of PERT. The scheme presented here is general and can be used for emulating other AQM algorithms.

In this paper, we explore multi-hop bandwidth estimation assuming arbitrary cross-traffic at each node and develop a new probing method called Envelope that can asymptotically estimate not only the available bandwidth but also the raw capacity of the tight link. Envelope is based on a multi-link recursive extension of unbiased single-hop estimators proposed in the past (e.g., [14]) and a variation of the packet-cartouche technique [6]. Through extensive simulations, we evaluate Envelope in various network settings and cross-traffic conditions and find that it can measure tight-link bandwidth characteristics with accuracy that significantly surpasses that of the existing methods. We also find that Envelope can measure non-tight links in certain path and cross-traffic configurations.

Previous analytical results on the resilience of un-structured P2P systems have not explicitly modeled heterogeneity of user churn (i.e., difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a generic model of heterogeneous user churn, derive the distribution of the various metrics observed in prior experimental studies (e.g., lifetime distribution of joining users, joint distribution of session time of alive peers, and residual lifetime of a randomly selected user), derive several closed-form results on the transient behavior of in-degree, and eventually obtain the joint in/out degree isolation probability as a simple extension of the out-degree model in [13].

Abstract — In this paper, we seek to understand the intrinsic reasons for the well-known phenomenon of heavy-tailed degree in the Internet AS graph and argue that in contrast to traditional models based on preferential attachment and centralized optimization, the Pareto degree of the Internet can be explained by the evolution of wealth associated with each ISP. The proposed topology model utilizes a simple multiplicative stochastic process that determines each ISP’s wealth at different points in time and several “maintenance ” rules that keep the degree of each node proportional to its wealth. Actual link formation is determined in a decentralized fashion based on random walks, where each ISP individually decides when and how to increase its degree. Simulations show that the proposed model, which we call Wealth-based Internet Topology (WIT), produces scale-free random graphs with tunable exponent α and high clustering coefficients (between 0.35 and 0.5) that stay invariant as the size of the graph increases. This evolution closely mimics that of the Internet observed since 1997. I.

Abstract — Recent surge of interest towards congestion control that relies on single-router feedback (e.g., XCP [12], RCP [1], [5], MaxNet [24], EMKC [28], VCP [26]) suggests that such systems may offer certain benefits over traditional models of additive packet loss [13]. Besides topology-independent stability and faster convergence to efficiency/fairness [24], it was recently shown [28] that any stable single-router system with a symmetric Jacobian tolerates arbitrary fixed, as well as time-varying, feedback delays. Although delay-independence is an appealing characteristic, the EMKC system developed in [28] exhibits undesirable equilibrium properties and slow convergence behavior. To overcome these drawbacks, we propose a new method called JetMax and show that it admits a low-overhead implementation inside routers (three additions per packet), overshoot-free transient and steady state, tunable link utilization, and delay-insensitive flow dynamics. The proposed framework also provides capacity-independent convergence time, where fairness and utilization are reached in the same number of RTT steps for a link of any bandwidth. Given a 1 mb/s, 10 gb/s, or googol (10 100) bps link, the method converges to within 1 % of the stationary state in 6 control intervals. We finish the paper by comparing JetMax’s performance to that of existing methods in ns2 simulations and discussing its Linux implementation.

End-to-end packet-pair probing has been used as one of the primary mechanisms to measure bottleneck capacity, cross-traffic intensity, and available bandwidth of end-to-end Internet paths. However, there has been lacking an understanding of what types of information about the path are sampled by packet-pairs and how they are encoded in the corresponding output dispersions. In this paper, we answer these questions by deriving the expression of individual output spacings (i.e., dispersions) in the context of multihop paths and general bursty cross-traffic arrivals. Based on these results, we examine stochastic properties of the sampled signals and derive the statistical mean of the output interpacket spacings as a recursive function of the input spacing. We show that the result is different from what has been obtained in prior work using fluid cross-traffic models and that this discrepancy has a significant adverse impact on the accuracy of packet-pair bandwidth measurement techniques

Rate-distortion (R-D) modeling of video coders has always been an important issue in video streaming; however, few of the traditional R-D models and their performance have been closely examined in the context of scalable (FGS-like) video. To overcome this shortcoming, the first half of the paper models rate-distortion of DCT-based fine-granular scalable coders and derives a simple operational R-D model for Internet streaming applications. Experimental results demonstrate that this R-D result, an extension of the classical R-D formula, is very accurate within the domain of scalable coding methods exemplified by MPEG-4 FGS and H.264 progressive FGS. In the second half of the paper, we examine congestion control and dynamic rate-scaling algorithms that achieve smooth visual quality during streaming using the proposed R-D model. In constant bitrate (CBR) channels, our R-D based quality-control algorithm dramatically reduces PSNR variation between adjacent frames (to less than 0.1 dB in sample sequences). Since the Internet is a changing environment shared by many sources, even R-D based quality control often cannot guarantee nonfluctuating PSNR in variable-bitrate (VBR) channels without the help from an appropriate congestion controller. Thus, we apply recent utility-based congestion control methods to our problem and show how a combination of this approach and our R-D model can benefit future streaming applications

In this paper, we analyze the problem of network disconnection in the context of large-scale P2P networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. We start by applying classical results from random graph theory to show that a large variety of deterministic and random P2P graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. This simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a P2P network develops isolated nodes, and therefore partitions, under both types of node failure. We finish the paper by demonstrating that our models match simulations very well and that dynamic P2P systems are extremely resilient under node churn as long as the neighbor replacement delay is much smaller than the average user lifetime.

This paper presents a frame-level hybrid framework for modeling H.264 and MPEG-4 multi-layer variable bit rate (VBR) video traffic. In this work, the base layer is modeled using a combination of wavelet and time-domain methods and the enhancement layer is linearly predicted from the base layer using the cross-layer correlation. Unlike previous studies, we analyze and successfully model both inter-GOP and intra-GOP correlation in VBR sequences. To accurately capture long-range dependent (LRD) and short-range dependent (SRD) properties of VBR traffic, we use wavelets to model the distribution of I-frame sizes and a simple time-domain model for P/B frame sizes. Simulation results demonstrate that our model effectively preserves the temporal burstiness and captures important statistical features (e.g., the autocorrelation function and the frame-size distribution) of original traffic. We also show that our model has better performance than the previous methods in both single and multi-layer sequences.

Although packet-pair probing has been used as one of the primary mechanisms to measure bottleneck capacity, cross-traffic intensity, and available bandwidth of end-to-end Internet paths, there is still no conclusive answer as to what information about the path is contained in the output packet-pair dispersions and how it is encoded. In this paper, we address this issue by deriving closed-form expression of packet-pair dispersion in the context of a single-hop path and general bursty cross-traffic arrival. Under the assumptions of cross-traffic stationarity and ASTA sampling, we examine the statistical properties of the information encoded in inter-packet spacings and derive the asymptotic average of the output packet-pair dispersions as a closed-form function of the input dispersion. We show that this result is different from what was obtained in prior work using fluid cross-traffic models and that this discrepancy has a significant impact on the accuracy of packet-pair bandwidth estimation.

Forward-error correction (FEC) is used in many streaming applications for protecting multimedia data over lossy network paths. However, studies in the literature [1, 3, 4] report conflicting results on the benefits of FEC. To address this uncertainty, we study the performance of FEC-based streaming and provide additional insight into how FEC overhead rate affects the performance of scalable video streaming under dynamically changing network packet loss. Through analytical investigation, we derive the relationship between packet loss, FEC overhead, and utility of received video, and propose a simple control mechanism that adjusts the amount of FEC based on packet loss information. We find that our FEC control allows the application to maintain high end-user utility and achieve better quality of video at the receiver.

To understand how high rates of churn and random departure decisions of end-users affect connectivity of P2P networks, this paper investigates resilience of random graphs to lifetime-based node failure and derives the expected delay before a user is forcefully isolated from the graph and the probability that this occurs within his/her lifetime. Our results indicate that systems with heavy-tailed lifetime distributions are more resilient than those with light-tailed (e.g., exponential) distributions and that for a given average degree, k-regular graphs exhibit the highest resilience. As a practical illustration of our results, each user in a system with n = 100 billion peers, 30-minute average lifetime, and 1-minute node-replacement delay can stay connected to the graph with probability 1 - 1 n using only 9 neighbors. This is in contrast to 37 neighbors required under previous modeling efforts. We finish the paper by showing that many P2P networks are almost surely (i.e., with probability 1-o(1)) connected if they have no isolated nodes and derive a simple model for the probability that a P2P system partitions under churn.

This paper examines graph-theoretic properties of existing peer-to-peer networks and proposes a new infrastructure based on optimal-diameter de Bruijn graphs. Since generalized de Bruijn graphs exhibit very short average distances and high resilience to node failure, they are well suited for distributed hash tables (DHTs). Using the example of Chord, CAN, and de Bruijn, we study the routing performance, graph expansion, clustering properties, and bisection width of each graph. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture optimal diameter routing infrastructure.

Video streaming is becoming an increasingly important part of the present Internet. To guarantee a high-quality streaming environment to end users, many video applications require a strict form of network QoS that is not available in the present Internet. Thus, to supplement the best-effort model of existing networks, we study a new video streaming framework that allows applications to mark their own packets with different priority and use multiqueue congestion control inside routers to effectively drop the less-important packets during buffer overflows. We describe priority AQM algorithms that provide "optimal" performance to video applications under arbitrary network loss and study a variation of Kelly's congestion control in combination with our framework. We call the combined architecture PELS - partitioned enhancement layer streaming.

After the emergence of numerous Internet streaming applications, rate-distortion (R-D) modeling of scalable video encoders has become an important issue. In this paper, we examine the performance of existing R-D models in scalable coders by using the example of MPEG-4 FGS and PFGS and propose a novel R-D model based on approximation theory. Experimental results demonstrate that the proposed model is very accurate and significantly outperforms those in previous work.

Traffic models play an important role in network simulation and performance analysis. This paper presents a frame-level hybrid framework for modeling variable bitrate (VBR) video traffic. To accurately capture long-range dependent (LRD) and short-range dependent (SRD) properties of video traffic, we incorporate elements of wavelet-domain analysis into classical time-domain modeling found in prior work. However, unlike previous studies, we analyze and successfully model both inter-GOP and intra-GOP correlation. Through the use of QQ plots and leaky-bucket simulations, we evaluate the accuracy of our approach and demonstrate that the autocorrelation function and the frame-size distribution of synthetic traffic match those of the original traffic very well. The leaky-bucket simulation also demonstrates that our model effectively preserves the temporal burstiness of the original video and can be used to predict buffer overflow probabilities and network packet loss.

In this paper, we examine the problem of estimating the capacity of bottleneck links and available bandwidth of endto -end paths under non-negligible cross-traffic conditions. We present a simple stochastic analysis of the problem in the context of a single congested node and derive several results that allow the construction of asymptotically-accurate bandwidth estimators. We first develop a generic queuing model of an Internet router and solve the estimation problem assuming renewal cross-traffic at the bottleneck link. Noticing that the renewal assumption on Internet flows is too strong, we investigate an alternative filtering solution that asymptotically converges to the desired values of the bottleneck capacity and available bandwidth under arbitrary (including non-stationary) cross-traffic. This is one of the first methods that simultaneously estimates both types of bandwidth and is provably accurate. We finish the paper by discussing the impossibility of a similar estimator for paths with two or more congested routers.

In this paper, we take the sample-path approach in analyzing the asymptotic behavior of single-hop bandwidth estimation under bursty cross-traffic and show that these results are provably different from those observed under fluid models of prior work. This difference, which we call the probing bias, is one of the previously unknown factors that can cause measurement inaccuracies in available bandwidth estimation. We present an analytical formulation of "packet probing," based on which we derive several major properties of the probing bias. We then experimentally observe the probing bias and investigate its quantitative relationship to several deciding factors such as probing packet size, probing train length, and cross-traffic burstiness. Both our analytical and experimental results show that the probing bias vanishes as the packet-train length or packet size increases. The vanishing rate is decided by the burstiness of cross-traffic.

In this paper, we analyze how feedback delays a#ect stability, oscillations, and packet loss of several classes of congestion controllers used or proposed for video streaming in the current/future Internet (including window-based AIMD, rate-based AIMD, Scalable TCP, and TFRC). Our results indicate that window-based protocols in this list incur significantly less packet loss under delayed feedback than their rate-based counterparts, which explains their better overall performance observed in practice [12]. At the same time, we show that even TCP's congestion control is far from ideal from the control-theoretic point of view and leads to amplified oscillations when queuing delays increase. We conclude with an observation that multimedia in the future Internet is not likely to enjoy oscillation-free congestion control unless the network deploys some form of AQM.

Recent research efforts to design better Internet transport protocols combined with scalable Active Queue Management (AQM) have led to significant advances in congestion control. One of the hottest topics in this area is the design of discrete congestion control algorithms that are asymptotically stable under heterogeneous feedback delay and whose control equations do not explicitly depend on the RTTs of end-flows. In this paper, we show that max-min fair congestion control methods with a stable symmetric Jacobian remain stable under arbitrary feedback delay (including heterogeneous directional delays) and that the stability condition of such methods does not involve any of the delays. To demonstrate the practicality of the obtained result, we change the original controller in Kelly's work [14] to become robust under random feedback delay and fixed constants of the control equation. We call the resulting framework Max-min Kelly Control (MKC) and show that it offers smooth sending rate, exponential convergence to efficiency, and fast convergence to fairness, all of which make it appealing for future high-speed networks.

Balancing peer-to-peer graphs, including zone-size distributions, has recently become an important topic of peer-to-peer (P2P) research [1], [2], [6], [19], [31], [36]. To bring analytical understanding into the various peer-join mechanisms, we study how zone-balancing decisions made during the initial sampling of the peer space affect the resulting zone sizes and derive several asymptotic results for the maximum and minimum zone sizes that hold with high probability.

In this paper, we present a wavelet-based despeckling method for synthetic aperture radar images and derive a Bayesian wavelet shrinkage factor to estimate noise-free wavelet coefficients. To preserve edges during despeckling, we apply a modified ratio edge detector to the original image and use the obtained edge information in our despeckling framework. Experimental results demonstrate that our method compares favorably to several other despeckling methods on test images.

In this paper, we analyze statistical and rate-distortion (R-D) properties of MPEG-4 fine-granular scalability (FGS), which has recently become an important scalable compression framework and a de-facto standard for Internet video streaming. We first propose a novel statistical model of DCT residue that accurately captures the properties of the input to the MPEG-4 FGS enhancement layer. Our results show that FGS residue concentrates a lot of probability mass near zero and cannot be accurately modeled by Gaussian or Laplacian distributions. We then model the distortion of each bitplane based on the proposed statistical framework and further demonstrate that our R-D model significantly outperforms current distortion models.

Internet streaming applications usually have strict requirements on bandwidth, delay, and packet loss, while the current best-effort Internet does not provide any Quality-of-Service (QoS) guarantees to end flows. To achieve a higher level of QoS for the end user, Fine-granular Scalability (FGS), which has both strong error-resilience and flexibility during streaming over variable-bandwidth channels, has been accepted as a standard coding scheme for the video streaming profile in MPEG-4 [19]. Note that FGS and its extensions (e.g., progressive FGS) can also be used in the emerging video coding standards such as H.26L. This paper investigates rate-distortion (R-D) models of FGS coders and shows how such models can be used in a simple rate control framework for FGS streaming over the Internet. In terms of congestion control, we examine advantages and drawbacks of Kelly's proportional-fairness framework [12] and investigate its practical use both in the best-effort and AQM-enabled Internet. Our simulation results show that the developed R-D models provide fundamental insight into the structure of FGS coders and that constant-quality streaming is possible as long as the number of end flows competing at each bottleneck resource remains fairly stationary.

This paper examines graph-theoretic properties of existing peer-to-peer architectures and proposes a new infrastructure based on optimal diameter de Bruijn graphs. Since generalized de Bruijn graphs possess very short average routing distances and high resilience to node failure, they are well suited for structured peer-to-peer networks. Using the example of Chord, CAN, and de Bruijn, we first study routing performance, graph expansion, and clustering properties of each graph. We then examine bisection width, path overlap, and several other properties that affect routing and resilience of peer-to-peer networks. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture ODRI -- Optimal Diameter Routing Infrastructure.

We study several properties of binary-feedback congestion control in rate-based applications. We first derive necessary conditions for generic binary-feedback congestion control to converge to fairness monotonically (which guarantees asymptotic stability of the fairness point) and show that AIMD is the only TCP-friendly binomial control with monotonic convergence to fairness. We then study the steady-state behavior of binomial controls with n competing flows on a single bottleneck. Our main result here shows that combined probing for new bandwidth by all flows results in significant overshoot of the available bandwidth and rapid (often super-linear as a function of n) increase in packet loss. We also show that AIMD has the best scalability and lowest packet-loss increase among all TCP-friendly binomial schemes. We conclude the paper by deriving the conditions necessary to achieve constant packet loss regardless of the number of competing flows, n, and, in both simulation and streaming experiments, examine one new scheme, called ideally scalable congestion control, with such constant packet loss.

This paper presents an extensive statistical study and analysis of the effects of channel delays in the current (best-effort) Internet on underflow events in MPEG-4 video streaming. Two types of network delays are considered: end-to-end round-trip delays and delay jitter. Our data were collected in a seven-month real-time streaming experiment, which was conducted between a number of unicast dialup clients in more than 600 major USA cities and a backbone video server. Among other findings, our analysis shows that startup delays approximately 15-20 times the average roundtrip time (RTT) are required for the client to avoid 90% of late packets caused by delay jitter. Meanwhile, startup delays of only 3-4 times the average RTT are needed to achieve lost-packet recovery rates of 90% or more. Hence, a key finding of our study is that delay jitter represents a more challenging problem for video streaming applications than round-trip delays. We also show that the probability density function (PDF) of RTT samples, which are associated with retransmitted video packets, can be modeled using a Pareto distribution. This observation indicates that the upper tail of the RTT PDF decays slower than reported in earlier studies.

Emerging real-time streaming applications often rely on rate-based flow control. However, congestion control for rate-based applications is typically dismissed as being not viable due to the common notion that "open-loop" congestion control is simply "difficult." This paper sheds new light on the performance of binomial NACK-based (i.e., rate-based) congestion control and measures the amount of "difficulty" inherently present in such protocols. Even though previous work proposed several new congestion control methods for real-time streaming, our analysis shows that traditional additive-increase, multiplicative-decrease (AIMD) schemes possess the best packet-loss scalability among all proposed TCP-friendly schemes, especially when used in rate-based applications. We further confirmed our analytical results in a number of experiments using MPEG-4 Fine-Granular Scalable (FGS) streaming over a Cisco testbed.

This paper examines the problem of real-time estimation of the capacity, which is also known as the bottleneck bandwidth, of a network path using end-to-end measurements in a video streaming application. We utilize two basic packet-pair bandwidth-sampling methods and show how they can be applied in real-time to the video traffic. We then examine the performance of both sampling methods in a number of tests conducted using an MPEG-4 congestion-controlled streaming application over a Cisco network under a variety of conditions (including high link utilization scenarios). In addition, we study two simple estimation techniques, which can be applied in real-time to the collected samples, and show their performance in the same Cisco network with each of the sampling methods. We focus here on low-complexity and simple estimators that can be used in real-time by a wide range of receivers. We find that the sampling methods combined with the best estimator maintain very accurate estimates for the majority of the corresponding session in a variety of scenarios and could in fact be used by the application for congestion control in video over the Internet.

Typically, NACK-based congestion control is dismissed as being not viable due to the common notion that "open-loop" congestion control is simply "difficult." Emerging real-time streaming applications, however, often rely on rate-based flow control and would benefit greatly from scalable NACK-based congestion control. This paper sheds new light on the performance of NACK-based congestion control and measures the amount of "difficulty" inherently present in such protocols. We specifically focus on increase-decrease (I-D) congestion control methods for real-time, rate-based streaming. First, we introduce and study several new performance measures that can be used to analyze the class of general I-D congestion control methods. These measures include monotonicity of convergence to fairness and packet-loss scalability (explained in the paper). Second, under the assumptions that the only feedback from the network is packet loss, we show that AIMD is the only TCP-friendly method with monotonic convergence to fairness. Furthermore, we find that AIMD possesses the best packet-loss scalability among all TCP-friendly binomial schemes and show how poorly all of the existing methods scale as the number of flows is increased. Third, we show that if the flows can obtain the knowledge of an additional network parameter (i.e., the bottleneck bandwidth), the scalability of AIMD can be substantially improved. We conclude the paper by studying the performance of a new scheme, called ideally-scalable congestion control (ISCC), both in simulation and a NACK-based MPEG-4 streaming application over a Cisco testbed.

Abstract – In this paper, we analyze the dynamics of a sevenmonth real-time streaming experiment, which was conducted between a number of unicast dialup clients, connecting to the Internet through access points in more than 600 major U.S. cities, and a backbone video server. During the experiment, the clients streamed low-bitrate MPEG-4 video sequences from the server over paths with more than 5,000 distinct Internet routers. We describe the methodology of the experiment and the architecture of our NACK-based streaming application, study end-to-end dynamics of 16 thousand ten-minute sessions (85 million packets), and analyze the behavior of the following network parameters: packet loss, round-trip delay, and packet reordering. We also study the impact of these parameters on the quality of real-time streaming (i.e., the number of underflow events). I.

This paper presents a trace-driven simulation study of three classes of retransmission timeout (RTO) estimators in the context of low-bitrate real-time streaming over the Internet. We explore the viability of employing retransmission timeouts in NACK-based real-time streaming applications that support multiple retransmission attempts per lost packet. In such applications, real-time RTO estimation plays a major role (i.e., poor RTO estimation results in a larger number of duplicate packets and sometimes more frequent underflow events). Our study is based on trace data collected during a number of real-time streaming tests conducted between our dialup clients in all 50 states of the U.S. (including 653 major U.S. cities) and our backbone video server during a seven-month period. First, we define a generic performance measure for assessing the quality of hypothetical RTO estimators based on the samples of the round-trip delay (RTT) recorded in the trace data. Second, using this performance measure, we evaluate the class of TCP-like estimators, find the most optimal estimator given our performance measure, and establish power laws that describe the tradeoff between the optimal number of duplicate packets and the optimal timeout waiting time. Third, we introduce a new class of RTO estimators based on delay jitter and show that they perform significantly better than TCP-like estimators in NACK-based applications. Finally, we gain a major insight into the RTT process by establishing which tuning parameters of an RTO estimator make it optimal given our performance measure and our experimental data, and give our explanation of the observed phenomena.

From a graph-theoretical perspective, the problem of constructing multicast distribution paths, modeled as 'Steiner trees', is NP-complete. So, many heuristics-based algorithms are available to generate near-optimal trees. Typically, an algorithm first assigns the edge costs for all links, and then examines various candidate paths for interconnecting a given set of nodes. This strategy does not work well for the evolving multimedia application configurations (such as audio-video and image distributions) where it is often necessary to construct multiple distribution paths, viz., one per media data stream. This is because the overlapping of multiple tree segments over a common link forces the link cost to change, based on the delay and bandwidth characteristics of data streams flowing over these segments. Accordingly, algorithms that hitherto have assumed non-varying link costs during various phases of a run now need to take into account the variability of link costs as candidate trees with different levels of path overlapping are examined in a given run. In other words, as an algorithm runs by examining various paths, the link costs change. The paper embarks on a study of heuristics-based algorithms to tackle this 'modified Steiner tree' problem. The algorithms allow more cost-efficient routing of data than feasible otherwise with a classical treatment of the 'Steiner tree' problem.

Real-time transmission of video over networks with no QoS guarantees (e.g., the Internet) is increasingly becoming an important application area in multimedia communications. One of the key challenges in this area is maintaining continuous decoding and playback at the receiver despite severe network impairments such as high packet-loss-ratios, packet-delay-variations, and unbounded roundtrip delays. A popular solution to this problem is to introduce large buffering delays at the receiver to (partially) compensate for the network impairments. This solution, however, is not a viable option for clients with limited resources and for applications requiring minimal delays. We advocate a new approach to this challenge. We derive a new set of encoder buffer constraints taking into consideration network impairments. We show how these new constraints can significantly reduce (or possibly eliminate) underflow and overflow events at the decoder while enabling the receiver to maintain its ideal decoder buffer size and buffering-delay requirements (needed for video transmission under ideal conditions). We present the results of more than 40 hours of video transmission over the (real) Internet. These results demonstrate the advantages and limitations (asymptotic behavior) of our proposed encoder-buffer constraints.

Many multicast routing protocols consider only the unicast shortest paths between every pair of source and destination in a group (often based on the number of hops) to setup a multicast tree, such as DVMRP and CBT. Furthermore, they do not offer the ability to consider the resource savings possible in the presence of multiple data flows sharing common paths in a tree, such as CBT and PIM. These aspects hamper resource-efficient routing. In this light, our paper describes flow-based resource allocation control in multicast tree setups. Our proposed model has two aspects: (i) exploring alternate paths to connect a joining user to a tree, should the unicast shortest path not have sufficient bandwidth to sustain the new data flow; and (ii) downstream resource allocation to merge a new data flow with the on-going flows in a tree. (i). Requires 'multi-path connectivity' information at routers in the network, while (ii) requires flow aggregation information to be exchanged between on-tree routers. The model is evaluated by simulation studies. The proposed model can be useful in integrated service networks that contain both low and high bandwidth links, such as future Internet.