This work investigates measurement strategies for link parameter estimation in Quantum Network Tomography (QNT), where network links are modeled as depolarizing quantum channels distributing Werner states. Three distinct measurement schemes are analyzed: local Z-basis measurements (LZM), joint Bell-state measurements (JBM), and pre-shared entanglement-assisted measurements (PEM). For each scheme, we derive the probability distributions of measurement outcomes and examine how noise in the distributed states influences estimation precision. Closed-form expressions for the Quantum Fisher Information Matrix (QFIM) are obtained, and the estimation precision is evaluated through the Quantum Cramer-Rao Bound (QCRB). Numerical analysis reveals that the PEM scheme achieves the lowest QCRB, offering the highest estimation accuracy, while JBM provides a favorable balance between precision and implementation complexity. The LZM method, although experimentally simpler, exhibits higher estimation error relative to the other schemes; however, it outperforms JBM in high-noise regimes for single-link estimation. We further evaluate the estimation performance on a four-node star network by comparing a JBM-only configuration with a hybrid configuration that combines JBM and LZM. When two monitors are used, the JBM-only strategy outperforms the hybrid approach across all noise regimes. However, with three monitors, it achieves a lower QCRB only in low-noise regimes with heterogeneous links. The results establish a practical basis for selecting measurement strategies in experimental quantum networks, enabling more accurate and scalable link parameter estimation under realistic noise conditions.

Computational offloading is a promising approach to overcome client device resource constraints by moving application computations to remote servers. With the advent of specialized hardware accelerators, client devices can now perform fast local processing of tasks such as machine learning inference, reducing the need for offloading. However, edge servers with accelerators also offer faster offloading performance than was previously possible. In this paper, we present an analytic and experimental comparison of on-device processing and edge offloading across accelerator, multi-tenant, and workload scenarios to understand when to use local processing versus offloading. We present models that leverage queuing theory to derive explainable closed-form equations for end-to-end latencies, yielding quantitative performance crossover predictions to guide adaptive offloading. We validate our models across various settings and show that they achieve a mean absolute percentage error of 2.2% compared to observed latencies. We further use these models to develop a resource manager for adaptive offloading and demonstrate its effectiveness in dynamic multi-tenant edge environments.

We introduce multipartite entanglement distribution protocols that use a quantum switch to deliver stabilizer states to a number of remote end users. As in existing schemes, the first step in our protocols involves Bell pair generation between the switch and each end user. However, unlike existing schemes that wait for all Bell pairs to be established before distributing the desired state -- for example, via a projective measurement -- our approach stores only a minimal subset of Bell pairs while processing every subsequent Bell pair immediately. In doing so, our protocols reduce the average Bell pair storage time compared to existing schemes, resulting in less cumulative noise as a direct consequence. On the theoretical side, our protocol design is grounded in the structure of vertex covers in graph states up to local complementation. Through a comprehensive numerical evaluation, we compare the fidelities of delivered states with those of a baseline scheme, for state sizes up to n = 50 qubits. Simulations also show that our protocols can achieve the critical fidelity threshold of 1/2 for multipartite entanglement in a wider range of depolarization rates and success probabilities of Bell-pair generation. Overall, our protocols always achieve an equal or higher fidelity of the distributed state, and can reduce infidelity by up to 45%.

Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1

We study the problem of quickest change detection (QCD) when the post-change distribution has parametric uncertainty. The generalized likelihood ratio (GLR) cumulative sum (CuSum) procedure is known to be asymptotically optimum in this setting. However, this rule requires significant memory and computational resources, making it difficult to implement in practice. To overcome this limitation, sliding window approaches, such as the window-limited GLR CuSum and window-limited adaptive CuSum tests, have been employed, where the test statistic is computed over a fixed window of the latest observations. We propose the K-Best rule which instead keeps track of K hypothesized change points that have the largest test statistic. This allows the hypothesized change points to reduce epistemic uncertainty over time, while restricting the number of hypothesized change points considered. We characterize the growth rate of the K-Best window necessary to achieve the detection performance of the GLR-CuSum rule and quantify the computational benefits over the existing windowing approaches.

Quantum networks (QNs) enable secure distributed quantum computing and sensing over next-generation optical communication networks by distributing entangled states over optical channels. However, quantum switches (QSs) in such QNs, which perform entanglement distribution, have limited resources, e.g., single-photon sources (SPSs) and quantum memories, which are sensitive to noise and losses. Efficient QS resource allocation is needed to minimize entanglement distribution delay. This paper proposes a QS resource allocation framework that jointly optimizes the average entanglement distribution delay and entanglement distillation operations to improve end-to-end (e2e) fidelity and meet user-specific rate and fidelity requirements. The proposed framework accounts for realistic QN noise and imperfections, deriving analytical expressions for quantum memory decoherence noise and resulting e2e fidelity after distillation. It also considers practical deployment factors, allowing QSs to control 1) nitrogen-vacancy (NV) center SPS types based on their isotopic decomposition, and 2) nuclear spin regions based on coupling strength and distance from NV center’s electron spin. The QS resource allocation optimization problem is solved using a simulated annealing algorithm. Simulation results show that the proposed framework manages to satisfy all users rate and fidelity requirements, unlike existing distillation-agnostic, minimal distillation, and physics-agnostic frameworks which do not perform distillation, perform minimal distillation, and do not control the physics-based NV center characteristics, respectively. Furthermore, the proposed framework results in significant reductions in the average e2e entanglement distribution delay, along with enhancements in the average e2e fidelity compared to the aforementioned existing frameworks.

We investigate the problem of covert quickest change detection in a continuous-time setting, where a Brownian motion experiences a drift change at an unknown time. Unlike classical formulations, we consider a covert adversary who adjusts the post-change drift$\mu = \mu (\gamma)$as a function of the false alarm constraint parameter$\gamma$, with the goal of remaining undetected for as long as possible. Leveraging the exact expressions for the average detection delay (ADD) and average time to false alarm (AT2FA) known for the continuous-time CuSum procedure, we rigorously analyze how the asymptotic behavior of ADD evolves as$\mu (\gamma) \to 0$with increasing$\gamma$. Our results reveal that classical detection delay characterizations no longer hold in this regime. We derive sharp asymptotic expressions for the ADD under various convergence rates of$\mu (\gamma)$, identify precise conditions for maintaining covertness, and characterize the total damage inflicted by the adversary. We show that the adversary achieves maximal damage when the drift scales as$\mu (\gamma) = \Theta (1/\sqrt{\gamma })$, marking a fundamental trade-off between stealth and impact in continuous-time detection systems.

Effective resource allocation in sensor networks, IoT systems, and distributed computing is essential for applications such as environmental monitoring, surveillance, and smart infrastructure. Sensors or agents must optimize their resource allocation to maximize the accuracy of parameter estimation. In this work, we consider a group of sensors or agents, each sampling from a different variable of a multivariate Gaussian distribution and having a different estimation objective. We formulate a sensor or agent’s data collection and collaboration policy design problem as a Fisher information maximization (or Cramer-Rao bound minimization) problem. This formulation captures a novel trade-off in energy use, between locally collecting univariate samples and collaborating to produce multivariate samples. When knowledge of the correlation between variables is available, we analytically identify two cases: (1) where the optimal data collection policy entails investing resources to transfer information for collaborative sampling, and (2) where knowledge of the correlation between samples cannot enhance estimation efficiency. When knowledge of certain correlations is unavailable, but collaboration remains potentially beneficial, we propose novel approaches that apply multi-armed bandit algorithms to learn the optimal data collection and collaboration policy in our sequential distributed parameter estimation problem. We illustrate the effectiveness of the proposed algorithms,DOUBLE-F, DOUBLE-Z, UCB-F,UCB-Z, through simulation.

Quantum networks (QNs) relying on free-space optical (FSO) quantum channels can support quantum applications in environments wherein establishing an optical fiber infrastructure is challenging and costly. However, FSO-based QNs require a clear line-of-sight (LoS) between users, which is challenging due to blockages and natural obstacles. In this paper, a reconfigurable intelligent surface (RIS)-assisted FSO-based QN is proposed as a cost-efficient framework providing a virtual LoS between users for entanglement distribution. A novel modeling of the quantum noise and losses experienced by quantum states over FSO channels defined by atmospheric losses, turbulence, and pointing errors is derived. Then, the joint optimization of entanglement distribution and RIS placement problem is formulated, under heterogeneous entanglement rate and fidelity constraints. This problem is solved using a simulated annealing metaheuristic algorithm. Simulation results show that the proposed framework effectively meets the minimum fidelity requirements of all users’ quantum applications. This is in stark contrast to baseline algorithms that lead to a drop of at least 84% in users’ end-to-end fidelities. The proposed framework also achieves a 63% enhancement in the fairness level between users compared to baseline rate maximizing frameworks. Finally, the weather conditions, e.g., rain, are observed to have a more significant effect than pointing errors and turbulence.

Reducing tail latency has become a crucial issue for optimizing the performance of online cloud services and distributed applications. In distributed applications, there are many causes of high end-to-end tail latency, including operating system delays, request re-ordering due to fan-out/fanin, and network congestion. Although recent research has focused on reducing tail latency for individual application components, such as by replicating requests and scheduling, in this paper, we argue for a holistic approach for reducing the end-to-end tail latency across application components. We propose TailClipper, a distributed scheduler that tags each arriving request with an arrival timestamp, and propagates it across the microservices' call chain. TailClipper then uses arrival timestamps to implement an oldest request first scheduler that combines global first-come first serve with a limited form of processor sharing to reduce end-to-end tail latency. In doing so, TailClipper can counter the performance degradation caused by request reordering in multi-tiered and microservices-based applications. We implement TailClipper as a userspace Linux scheduler and evaluate it using cloud workload traces and a real-world microservices application. Compared to state-of-the-art schedulers, our experiments reveal that TailClipper improves the 99th percentile response time by up to 81%, while also improving the mean response time and the system throughput by up to 54% and 29% respectively under high loads.

Edge computing is emerging as a complementary architecture to cloud computing to address some of its associated issues. One of the major advantages of edge computing is that edge data centers are usually much closer to users compared to traditional cloud data centers. Therefore, it is commonly believed that for developers of latency-sensitive applications, they can effectively reduce the overall end-to-end latency by simply transitioning from a cloud deployment to an edge deployment. However, as recent work has shown, the performance of an edge deployment is vulnerable to a couple of factors which under many practical scenarios can lead to edge servers providing worse end-to-end response time than cloud servers. This phenomenon is referred to as edge performance inversion. In this paper, we propose resource allocation and workload scheduling algorithms that actively prevent edge performance inversion. Our algorithms, named INVAR, are based on queueing theory results and optimization techniques. Evaluation results show that INVAR can find a near-optimal solution that outperforms the performance of a cloud deployment by an adjustable margin. Simulation results based on production workloads from Akamai data centers show that INVAR can outperform common heuristic-based edge deployment by 11% to 24% in real-world scenarios.

Stabilizer states are a prime resource for a number of applications in quantum information science, such as secret-sharing and measurement-based quantum computation. This motivates us to study the entanglement of noisy stabilizer states across a bipartition. We show that the spectra of the corresponding reduced states can be expressed in terms of properties of an associated stabilizer code. In particular, this allows us to show that the coherent information is related to the so-called syndrome entropy of the underlying code. We use this viewpoint to find stabilizer states that are resilient against noise, allowing for more robust entanglement distribution in near-term quantum networks. We specialize our results to the case of graph states, where the found connections with stabilizer codes reduces back to classical linear codes for dephasing noise. On our way we provide an alternative proof of the fact that every qubit stabilizer code is equivalent up to single-qubit Clifford gates to a graph code.

This paper studies a cooperative multi-agent multi-armed stochastic bandit problem where agents operate asynchronously – agent pull times and rates are unknown, irregular, and heterogeneous – and face the same instance of a K-armed bandit problem. Agents can share reward information to speed up the learning process at additional communication costs. We propose ODC, an on-demand communication protocol that tailors the communication of each pair of agents based on their empirical pull times. ODC is efficient when the pull times of agents are highly heterogeneous, and its communication complexity depends on the empirical pull times of agents. ODC is a generic protocol that can be integrated into most cooperative bandit algorithms without degrading their performance. We then incorporate ODC into the natural extensions of UCB and AAE algorithms and propose two communication-efficient cooperative algorithms. Our analysis shows that both algorithms are near-optimal in regret.

Enabling quantum switches (QSs) to serve requests submitted by quantum end nodes in quantum communication networks (QCNs) is a challenging problem due to the heterogeneous fidelity requirements of the submitted requests and the limited resources of the QCN. Effectively determining which requests are served by a given QS is fundamental to foster developments in practical QCN applications, like quantum data centers. However, the state-of-the-art on QS operation has overlooked this association problem, and it mainly focused on QCNs with a single QS. In this paper, the request-QS association problem in QCNs is formulated as a matching game that captures the limited QCN resources, heterogeneous application-specific fidelity requirements, and scheduling of the different QS operations. To solve this game, a swap-stable request-QS association (RQSA) algorithm is proposed while considering partial QCN information availability. Extensive simulations are conducted to validate the effectiveness of the proposed RQSA algorithm. Simulation results show that the proposed RQSA algorithm achieves a near-optimal (within 5%) performance in terms of the percentage of served requests and overall achieved fidelity, while outperforming benchmark greedy solutions by over 13%. Moreover, the proposed RQSA algorithm is shown to be scalable and maintain its near-optimal performance even when the size of the QCN increases.

Quantum switches are envisioned to be an integral component of future entanglement distribution networks. They can provide high quality entanglement distribution service to end-users by performing quantum operations such as entanglement swapping and entanglement purification. In this work, we characterize the capacity region of such a quantum switch under noisy channel transmissions and imperfect quantum operations. We express the capacity region as a function of the channel and network parameters (link and entanglement swap success probability), entanglement purification yield and application level parameters (target fidelity threshold). In particular, we provide necessary conditions to verify if a set of request rates belong to the capacity region of the switch. We use these conditions to find the maximum achievable end-to-end user entanglement generation throughput by solving a set of linear optimization problems. We develop a max-weight scheduling policy and prove that the policy stabilizes the switch for all feasible request arrival rates. As we develop scheduling policies, we also generate new results for computing the conditional yield distribution of different classes of purification protocols. The conclusions obtained in this work can yield useful guidelines for subsequent quantum switch designs.

Distributing quantum entanglements over long distances is essential for the realization of a global scale quantum Internet. Most of the prior work and proposals assume an on-demand distribution of entanglements which may result in significant network resource under-utilization. In this work, we introduce Quantum Overlay Networks (QONs) for efficient entanglement distribution in quantum networks. When the demand to create end-to-end user entanglements is low, QONs can generate and store maximally entangled Bell pairs (EPR pairs) at specific overlay storage nodes of the network. Later, during peak demands, requests can be served by performing entanglement swaps either over a direct path from the network or over a path using the storage nodes. We solve the link entanglement and storage resource allocation problem in such a QON using a centralized optimization framework. We evaluate the performance of our proposed QON architecture over a wide number of network topologies under various settings using extensive simulation experiments. Our results demonstrate that QONs fare well by a factor of 40% with respect to meeting surge and changing demands compared to traditional non-overlay proposals. QONs also show significant improvement in terms of average entanglement request service delay over non-overlay approaches.

This paper studies a cooperative multi-agent bandit scenario in which the rewards observed by agents are heterogeneous—one agent’s meat can be another agent’s poison. Specifically, the total reward observed by each agent is the sum of two values: an arm-specific reward, capturing the intrinsic value of the arm, and a privately-known agent-specific reward, which captures the personal preference/limitations of the agent. This heterogeneity in total reward leads to different local optimal arms for agents but creates an opportunity for \textit{free exploration} in a cooperative setting—an agent can freely explore its local optimal arm with no regret and share this free observation with some other agents who would suffer regrets if they pull this arm since the arm is not optimal for them. We first characterize a regret lower bound that captures free exploration, i.e., arms that can be freely explored have no contribution to the regret lower bound. Then, we present a cooperative bandit algorithm that takes advantage of free exploration and achieves a near-optimal regret upper bound which tightly matches the regret lower bound up to a constant factor. Lastly, we run numerical simulations to compare our algorithm with various baselines without free exploration.

Instant Messaging (IM) applications such as Signal, Telegram, and WhatsApp have become tremendously popular in recent years. Unfortunately, such IM services have been targets of governmental surveillance and censorship, as these services are home to public and private communications on socially and politically sensitive topics. To protect their clients, popular IM services deploy state-of-the-art encryption. Despite the use of advanced encryption, we show that popular IM applications leak sensitive information about their clients to adversaries merely monitoring their encrypted IM traffic, with no need for leveraging any software vulnerabilities of IM applications. Specifically, we devise traffic analysis attacks enabling an adversary to identify participants of target IM communications (e.g., forums) with high accuracies. We believe that our study demonstrates a significant, real-world threat to the users of such services. We demonstrate the practicality of our attacks through extensive experiments on real-world IM communications. We show that standard countermeasure techniques can degrade the effectiveness of these attacks. We hope our study will encourage IM providers to integrate effective traffic obfuscation into their software. In the meantime, we have designed a countermeasure system, called IMProxy that can be used by IM clients with no need for any support from IM providers. We demonstrate the effectiveness of IMProxy through simulation and experiments.

We study the behavior of epidemic routing in a delay tolerant network as a function of node density. Focusing on the probability of successful delivery to a destination within a deadline (PS), we show that PS experiences a phase transition as node density increases. Specifically, we prove that PS exhibits a phase transition when nodes are placed according to a Poisson process and allowed to move according to independent and identical processes with limited speed. We then propose four fluid approximations to evaluate the performance of epidemic routing in non-sparse networks. An ordinary differential equation (ODE) is proposed for supercritical networks based on approximation of the infection rate as a function of time. Other ODEs are based on the approximation of thepairwise infection rate. Two of them, one for subcritical networks and another for supercritical networks, use the pairwise infection rate as a function of the number of infected nodes. The other ODE uses pairwise infection rate as a function of time, and can be applied for both subcritical and supercritical networks achieving good accuracy. The ODE for subcritical networks is accurate when density is not close to the percolation critical density. Moreover, the ODEs that target only supercritical regime are accurate.

The growing demand for edge computing resources, particularly due to increasing popularity of Internet of Things (IoT), and distributed machine/deep learning applications poses a significant challenge. On the one hand, certain edge service providers (ESPs) may not have sufficient resources to satisfy their applications according to the associated service-level agreements. On the other hand, some ESPs may have additional unused resources. In this paper, we propose a resource-sharing framework that allows different ESPs to optimally utilize their resources and improve the satisfaction level of applications subject to constraints such as communication cost for sharing resources across ESPs. Our framework considers that different ESPs have their own objectives for utilizing their resources, thus resulting in a multi-objective optimization problem. We present an${N}$-person Nash Bargaining Solution (NBS) for resource allocation and sharing among ESPs with Pareto optimality guarantee. Furthermore, we propose a distributed, primal-dual algorithm to obtain the NBS by proving that the strong-duality property holds for the resultant resource sharing optimization problem. Using synthetic and real-world data traces, we show numerically that the proposed NBS based framework not only enhances the ability to satisfy applications’ resource demands, but also improves utilities of different ESPs.

This paper tackles a multi-agent bandit setting where M agents cooperate together to solve the same instance of a K-armed stochastic bandit problem. The agents are heterogeneous: each agent has limited access to a local subset of arms and the agents are asynchronous with different gaps between decision-making rounds. The goal for each agent is to find its optimal local arm, and agents can cooperate by sharing their observations with others. While cooperation between agents improves the performance of learning, it comes with an additional complexity of communication between agents. For this heterogeneous multi-agent setting, we propose two learning algorithms, CO-UCB and CO-AAE. We prove that both algorithms achieve order-optimal regret, which is $O\left({{\sum _{i:{{\bar \Delta }_i} > 0}}\log T/{{\tilde \Delta }_i}}\right)$, where ${\tilde \Delta _i}$ is the minimum suboptimality gap between the reward mean of arm i and any local optimal arm. In addition, a careful selection of the valuable information for cooperation, CO-AAE achieves a low communication complexity of O(log T). Last, numerical experiments verify the efficiency of both algorithms.

Online monitoring user cardinalities in graph streams is fundamental for many applications such as anomaly detection. These graph streams may contain edge duplicates and have a large number of user-item pairs, which makes it infeasible to exactly compute user cardinalities due to limited computational and memory resources. Existing methods are designed to approximately estimate user cardinalities, but their accuracy highly depends on complex parameters and they cannot provide anytime-available estimation. To address these problems, we develop novel bit/register sharing algorithms, which use a bit/register array to build a compact sketch of all users’ connected items. Our algorithms exploit the dynamic properties of the bit/register arrays (e.g., the fraction of zero bits in the bit array) to significantly improve the estimation accuracy, and have low time complexity$O(1)$to update the estimations for a new user-item pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. Furthermore, we extend our methods to detect super spreaders with large cardinalities in real-time. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Covert communication considers the ability of transmitter Alice to communicate reliably to receiver Bob without being detected by warden Willie. Previous work has generally considered a discrete-time model, and, in the standard Alice-Bob-Willie scenario, it has been shown that a discrete-time model captures the salient aspects of the underlying continuous-time covert communications system. However, in the presence of a jammer assisting Alice, where it has been shown in previous work that Alice can achieve a positive covert rate on a discrete-time model, we demonstrate here that a straightforward extension of the discrete-time construction to the continuous-time system does not guarantee a positive covert rate, hence indicating that the discrete-time model does not capture the salient aspects of the continuous-time system in such a scenario. This is because Willie is able to exploit excess bandwidth for co-channel interference suppression, as we demonstrate with an interference cancellation receiver. Hence, for the case when Alice is assisted by an uninformed jammer, we consider the continuous-time channel directly and study whether efficient covert communication can still be achieved against any possible receiver that Willie might employ. By presenting and characterizing an approach much different than that suggested by previous work for discrete-time systems in such a scenario, we establish that$\mathcal {O}(WT)$information bits can be transmitted covertly and reliably on a continuous-time channel of asymptotic bandwidth$W$in$T$seconds, regardless of the receiver that Willie employs. This is done for two separate scenarios: 1) when there is perfect frame synchronization between Alice and the jammer’s signals; 2) when there is no frame synchronization between Alice and the jammer’s signals. Numerical results are provided to validate the theory.

There is significant enthusiasm for the employment of Deep Neural Networks (DNNs) for important tasks in major wireless communication systems: channel estimation and decoding in orthogonal frequency division multiplexing (OFDM) systems, end-to-end autoencoder system design, radio signal classification, and signal authentication. Unfortunately, DNNs can be susceptible to adversarial examples, potentially making such wireless systems fragile and vulnerable to attack. In this work, by designing robust adversarial examples that meet key criteria, we perform a comprehensive study of the threats facing DNN-based wireless systems. We model the problem of adversarial wireless perturbations as an optimization problem that incorporates domain constraints specific to different wireless systems. This allows us to generate wireless adversarial perturbations that can be applied to wireless signals on-the-fly (i.e., with no need to know the target signals a priori), are undetectable from natural wireless noise, and are robust against removal. We show that even in the presence of significant defense mechanisms deployed by the communicating parties, our attack performs significantly better compared to existing attacks against DNN-based wireless systems. In particular, the results demonstrate that even when employing well-considered defenses, DNN-based wireless communication systems are vulnerable to adversarial attacks and call into question the employment of DNNs for a number of tasks in robust wireless communication.

Content delivery networks (CDNs) distribute much of today's Internet traffic by caching and serving users' contents requested. A major goal of a CDN is to improve hit probabilities of its caches, thereby reducing WAN traffic and user-perceived latency. In this paper, we develop a new approach for caching in CDNs that learns from optimal caching for decision making. To attain this goal, we first propose HRO to compute the upper bound on optimal caching in an online manner, and then leverage HRO to inform future content admission and eviction. We call this new cache design LHR. We show that LHR is efficient since it includes a detection mechanism for model update, an auto-tuned threshold-based model for content admission with a simple eviction rule. We have implemented an LHR simulator as well as a prototype within an Apache Traffic Server and the Caffeine, respectively. Our experimental results using four production CDN traces show that LHR consistently outperforms state of the arts with an increase in hit probability of up to 9% and a reduction in WAN traffic of up to 15% compared to a typical production CDN cache. Our evaluation of the LHR prototype shows that it only imposes a moderate overhead and can be deployed on today's CDN servers.

This paper studies a cooperative multi-armed bandit problem with $M$ agents cooperating together to solve the same instance of a $K$-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local.The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any $\textit{suboptimal}$ arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called $\texttt{CO-LCB}$ algorithm, whose regret is a function of aggregate action frequency of agents containing the $\textit{optimal}$ arm. We also show that the regret of $\texttt{CO-LCB}$ matches the regret lower bound up to a small factor.

Mobile edge computing seeks to provide resources to different delay-sensitive applications. This is a challenging problem as an edge cloud-service provider may not have sufficient resources to satisfy all resource requests. Furthermore, allocating available resources optimally to different applications is also challenging. Resource sharing among different edge cloud-service providers can address the aforementioned limitation as certain service providers may have resources available that can be “rented” by other service providers. However, edge cloud service providers can have different objectives orutilities. Therefore, there is a need for an efficient and effective mechanism to share resources among service providers, while considering the different objectives of various providers. We model resource sharing as a multi-objective optimization problem and present a solution framework based onCooperative Game Theory(CGT). We consider the strategy where each service provider allocates resources to its native applications first and shares the remaining resources with applications from other service providers. We prove that for a monotonic, non-decreasing utility function, the game is canonical and convex. Hence, thecoreis not empty and the grand coalition is stable. We propose two algorithms,Game-theoretic Pareto optimal allocation(GPOA) andPolyandrous-Polygamous Matching based Pareto Optimal Allocation(PPMPOA) that provide allocations from the core. Hence the obtained allocations areParetooptimal and the grand coalition of all the service providers is stable. Experimental results confirm that our proposed resource sharing framework improves utilities of edge cloud-service providers and application request satisfaction.

The Transmission Control Protocol (TCP) utilizes a congestion avoidance and control mechanism as a preventive measure against congestive collapse and as an adaptive measure in the presence of changing network conditions. The set of available congestion control algorithms is diverse, and while many have been studied from empirical and simulation perspectives, there is a notable lack of analytical work for some variants. To gain more insight into the dynamics of these algorithms, we: (1) propose a general modeling scheme consisting of a set of functional differential equations of retarded type (RFDEs) and of the congestion window as a function of time; (2) apply this scheme to TCP Reno and demonstrate its equivalence to a previous, well known model for TCP Reno; (3) show applications of the new framework to the widely-deployed congestion control algorithm TCP CUBIC, for which analytical models are few and limited; as well as to H-TCP, another high-speed congestion control algorithm; and (4) validate the model using simulations. Our modeling framework yields a fluid model for window- or rate-based congestion control variants. From a theoretical analysis of this model with TCP CUBIC, we discover that CUBIC is locally uniformly asymptotically stable - a property of the algorithm previously unknown. Through further analysis, we derive a sufficient condition for H-TCP's stability, but observe via a numerical analysis and simulations that H-TCP rarely converges to an equilibrium and is usually not asymptotically stable in practical high-speed settings.

Consensus-based distributed optimization methods have recently been advocated as alternatives to parameter server and ring all-reduce paradigms for large scale training of machine learning models. In this case, each worker maintains a local estimate of the optimal parameter vector and iteratively updates it by averaging the estimates obtained from its neighbors, and applying a correction on the basis of its local dataset. While theoretical results suggest that worker communication topology should have strong impact on the number of epochs needed to converge, previous experiments have shown the opposite conclusion. This paper sheds lights on this apparent contradiction and show how sparse topologies can lead to faster convergence even in the absence of communication delays.

The problem of quickest growing dynamic anomaly detection in sensor networks is studied. Initially, the observations at the sensors, which are sampled sequentially by the decision maker, are generated according to a pre-change distribution. At some unknown but deterministic time instant, a dynamic anomaly emerges in the network, affecting different sets of sensors as time progresses. The observations of the affected sensors are generated from a post-change distribution. It is assumed that the number of affected sensors increases with time, and that only the initial and the final size of the anomaly are known to the decision maker. The goal is to detect the emergence of the anomaly as quickly as possible while guaranteeing a sufficiently low frequency of false alarm (FA) events. This detection problem is posed as a stochastic optimization problem by using a delay metric that is based on the worst possible path of the anomaly. A detection rule is proposed that is asymptotically optimal as the mean time to false alarm goes to infinity. Finally, numerical results are provided to validate our theoretical analysis.

Video streaming commonly uses Dynamic Adaptive Streaming over HTTP (DASH) to deliver good Quality of Experience (QoE) to users. Videos used in DASH are predominantly encoded by single-layered video coding such as H.264/AVC. In comparison, multi-layered video coding such as H.264/SVC provides more flexibility for upgrading the quality of buffered video segments and has the potential to further improve QoE. However, there are two challenges for using SVC in DASH: (i) the complexity in designing ABR algorithms; and (ii) the negative impact of SVC's coding overhead. In this work, we propose a deep reinforcement learning method called Grad for designing ABR algorithms that take advantage of the quality upgrade mechanism of SVC. Additionally, we quantify the impact of coding overhead on the achievable QoE of SVC in DASH, and propose jump-enabled hybrid coding (HYBJ) to mitigate the impact. Through emulation, we demonstrate that Grad-HYBJ, an ABR algorithm for HYBJ learned by Grad, outperforms the best performing state-of-the-art ABR algorithm by 17% in QoE.

In this paper, we establish a framework for low probability of detection (LPD) communication from a sequential change-point detection (SCPD) perspective, where a transmitter, Alice, wants to hide her transmission to a receiver, Bob, from an adversary, Willie. The new framework facilitates modeling LPD communication and further evaluating its performance under the condition that Willie has no prior knowledge about when the transmission from Alice might start and that Willie wants to determine the existence of the communication as quickly as possible in a real-time manner. We consider three different sequential tests, i.e., the Shewhart, the cumulative sum (CUSUM), and the Shiryaev-Roberts (SR) tests, to model Willie's detection process. Communication is said to be covert if it ceases before being detected by Willie with high probability. Covert probability defined as the probability that Willie is not alerted during Alice's transmission is investigated. We formulate an optimization problem aiming at finding the transmit power and transmission duration so as to maximize the total amount of information that can be transmitted subject to a high covert probability. Under the Shewhart test, closed-form approximations of the optimal solutions are derived, which will approximate the solutions obtained from exhaustive search. As for the CUSUM and SR tests, we provide effective algorithms to search for the optimal solutions. Numeric results are presented to show the performance of LPD communication.

Covert communication conceals the existence of the transmission from a watchful adversary. We consider the fundamental limits for covert communications via packet insertion over packet channels whose packet timings are governed by a renewal process of rate λ. Authorized transmitter Jack sends packets to authorized receiver Steve, and covert transmitter Alice wishes to transmit packets to covert receiver Bob without being detected by watchful adversaries Willie 1 and Willie 2. Willies cannot authenticate the source of the packets or collaborate. Hence, each Willie looks for statistical anomalies in the packet stream from Jack to Steve to attempt detection of unauthorized packet insertion. First, we consider a special case where the packet timings are governed by a Poisson process and we show that Alice can covertly insert O(√λT) packets for Bob in a time interval of length T; conversely, if Alice inserts ω(√λT) packets, she will be detected by Willie 1 or Willie 2 with high probability. Then, we extend our results to general renewal channels and show that in a stream of N packets transmitted by Jack, Alice can covertly insert O(√N) packets; if she inserts ω(√N) packets, she will be detected by Willie 1 or Willie 2, with high probability.

Network flow fingerprinting can be used to de-anonymize communications on anonymity systems such as Tor by linking the ingress and egress segments of anonymized connections. Assume Alice and Bob have access to the input and the output links of an anonymous network, respectively, and they wish to collaboratively reveal the connections between the input and the output links without being detected by Willie who protects the network. Alice generates a codebook where each codeword is a unique fingerprint indicating a sequence of interpacket delays, and shares it only with Bob. To trace each flow, Alice selects a fingerprint and manipulates the packet timings of the flow to follow the packet timings suggested by the fingerprint, and Bob extracts the fingerprints from it after it passes through the network. We model the network as parallel M/M/1 queues where each queue is shared by a flow fifrom Alice to Bob and other flows independent of fi. Packet timings of the flows are governed by independent Poisson processes. Assuming all input flows have equal packet rates and that Bob observes only flows with fingerprints, we first present two scenarios: 1) Alice fingerprints all the flows and 2) Alice fingerprints a subset of the flows, unknown to Willie. Then, we extend the construction and analysis to the case of arbitrary flow rates and the case where Bob observes flows with and without fingerprints. For each scenario, we derive the number of flows that Alice and Bob can trace by fingerprinting.

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than η nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results.

Learning network representation has a variety of \napplications, such as network classification. Most existing work \nin this area focuses on static undirected networks and does not \naccount for presence of directed edges or temporal changes. \nFurthermore, most work focuses on node representations that \ndo poorly on tasks like network classification. In this paper, \nwe propose a novel network embedding methodology, gl2vec, \nfor network classification in both static and temporal directed \nnetworks. gl2vec constructs vectors for feature representation \nusing static or temporal network graphlet distributions and a \nnull model for comparing them against random graphs. We \ndemonstrate the efficacy and usability of gl2vec over existing \nstate-of-the-art methods on network classification tasks such as \nnetwork type classification and subgraph identification in several \nreal-world static and temporal directed networks. We argue that \ngl2vec provides additional network features that are not captured \nby state-of-the-art methods, which can significantly improve their \nclassification accuracy by up to 10% in real-world applications

A major threat to the Internet infrastructure and, more broadly, to its culture is posed by DDoS attacks. To mitigate their impact, detection should preferably occur close to the attack origin, e.g., at home-routers. However, these devices typically have limited resources and an approach that relies on packet inspection does not bode well with such devices.We propose a lightweight approach for DDoS detection that solely employs network interface byte and packet counts. To detect attacks with such a limited amount of information, our key insight consists in training classifiers to make use of workload data from 1,823 home-users augmented with attacks generated in a controlled environment. In our experiments, we selected seven attack vectors generated using Mirai and BASHLITE malwares. We then conduct a device-agnostic detection of attacks vectors, obtaining F1 scores typically higher than 0.99. To cope with the evolving nature of DDoS attacks, we also report results indicating the detection power of the proposed methodology when different attack vectors are used for training and testing.

In this paper we study the two inference problems of detection and reconstruction in the context of planted structures in sparse Erdős-Rényi random graphs $\mathcal G(n,\lambda/n)$ with fixed average degree $\lambda>0$. Motivated by a problem of communication security, we focus on the case where the planted structure consists in the addition of a tree graph. In the case of planted line graphs, we establish the following phase diagram for detection and reconstruction. In a low density region where the average degree $\lambda$ of the original graph is below some critical value $\lambda_c=1$, both detection and reconstruction go from impossible to easy as the line length $K$ crosses some critical value $K^*=\ln(n)/\ln(1/\lambda)$, where $n$ is the number of nodes in the graph. In a high density region where $\lambda>\lambda_c$, detection goes from impossible to easy as $K$ goes from $o(\sqrt{n})$ to $\omega(\sqrt{n})$. In contrast, reconstruction remains impossible so long as $K=o(n)$. We then consider planted $D$-ary trees of varying depth $h$ and $2\le D\le O(1)$. For these we identify a low-density region $\lambda<\lambda_D$, where $\lambda_D$ is the threshold for emergence of the $D$-core in Erdős-Rényi random graphs $\mathcal G(n,\lambda/n)$ for which the following holds. There is a threshold $h*=g(D)\ln(\ln(n))$ with the following properties. Detection goes from impossible to feasible as $h$ crosses $h*$. Interestingly, we show that only partial reconstruction is feasible at best for $h\ge h*$. We conjecture a similar picture to hold for $D$-ary trees as for lines in the high-density region $\lambda>\lambda_D$, but confirm only the following part of this picture: Detection is easy for $D$-ary trees of size $\omega(\sqrt{n})$, while at best only partial reconstruction is feasible for $D$-ary trees of any size $o(n)$. These results provide a clear contrast with the corresponding picture for detection and reconstruction of {\em low rank} planted structures, such as dense subgraphs and block communities. In the examples we study, there is i) an absence of hard phases for both detection and reconstruction, and ii) a discrepancy between detection and reconstruction, the latter being impossible for a wide range of parameters where detection is easy. The latter property does not hold for previously studied low rank planted structures.

The problem of quickest detection of significant events in networks is studied. A distributed setting is investigated, where there is no fusion center, and each node only communicates with its neighbors. After an event occurs in the network, a number of nodes are affected, which changes the statistics of their observations. The nodes may possibly perceive the event at different times. The goal is to design a distributed sequential detection rule that can detect when the event is "significant", i.e., the event has affected no less than η nodes, as quickly as possible, subject to false alarm constraints. A distributed algorithm is proposed, which is based on a novel combination of the alternating direction method of multipliers (ADMM) and average consensus approaches. Numerical results are provided to demonstrate the performance of the proposed algorithm.

As data-parallel applications process more complex data, the dependencies between computation jobs in a multi-stage job also become more complicated. However, most of the existing scheduling solutions primarily rely on total bytes sent (job size) to differentiate jobs where jobs with fewer? bytes sent are prioritized over the larger ones. This approach overlooks the fact that jobs may consist of multiple computation stages, and that the completion of a computation job stage depends on the completion of other jobs' stage. In this paper, we present a coflow scheduler of multi-stage jobs that minimizes the average job completion time. Our solution prioritizes jobs based on the multi-faceted characteristics of multi-stage job structure per stage, instead of total bytes sent. Our experiments show that our approach provides twice the performance of existing solutions on average and by four times in bursty traffic scenario.

Online monitoring user cardinalities (or degrees) in graph streams is fundamental for many applications. For example in a bipartite graph representing user-website visiting activities, user cardinalities (the number of distinct visited websites) are monitored to report network anomalies. These real-world graph streams may contain user-item duplicates and have a huge number of distinct user-item pairs, therefore, it is infeasible to exactly compute user cardinalities when memory and computation resources are limited. Existing methods are designed to approximately estimate user cardinalities, whose accuracy highly depends on parameters that are not easy to set. Moreover, these methods cannot provide anytime-available estimation, as the user cardinalities are computed at the end of the data stream. Realtime applications such as anomaly detection require that user cardinalities are estimated on the fly. To address these problems, we develop novel bit and register sharing algorithms, which use a bit array and a register array to build a compact sketch of all users' connected items respectively. Compared with previous bit and register sharing methods, our algorithms exploit the dynamic properties of the bit and register arrays (e.g., the fraction of zero bits in the bit array at each time) to significantly improve the estimation accuracy, and have low time complexity (O(1)) to update the estimations each time they observe a new useritem pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Many learning problems are formulated as minimization of some loss function on a training set of examples. Distributed gradient methods on a cluster are often used for this purpose. In this paper, we study how the variability of task execution times at cluster nodes affects the system throughput. In particular, a simple but accurate model allows us to quantity how the time to solve the minimization problem depends on the network of information exchanges among the nodes. Interestingly, we show that, even when communication overhead may be neglected, the clique is not necessarily the most effective topology, as commonly assumed in previous works.

We consider assignment policies that allocate resources to users, where both resources and users are located on a one-dimensional line (0, ∞). First, we consider unidirectional assignment policies that allocate resources only to users located to their left. We propose the Move to Right (MTR) policy, which scans from left to right assigning the nearest available resource located to the right of a user, and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy. While both policies among all unidirectional policies, minimize the expected distance traveled by a request, MTR is fairer. Moreover, we show that when user and resource locations are modeled by statistical point processes, and resources are allowed to satisfy more than one user, the spatial system under unidirectional policies can be mapped into bulk service queueing systems, thus allowing the application of many queueing theory results that yield closed form expressions. As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues. We also consider bidirectional policies where there are no directional restrictions on resource allocation and develop an algorithm for computing the optimal assignment which is more efficient than known algorithms in the literature when there are more resources than users. Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yields design guidelines beneficial for resource placement.

We propose a novel policy for data compression and caching in a wireless sensor network (WSN) that provably optimizes utility and cost jointly, providing a theoretical basis to understand the compression-caching tradeoff for data analytics in a WSN. Our optimization framework provides analytical answers to how much compression should be performed at each sensors, and where the data should be cached in the network. We propose a distributed algorithm to implement the optimal policy and adapt to the changes (e.g., cache size and request processes) in the network. We evaluate our approach through extensive simulations on WSNs.

Today's cloud data centers host a wide range of applications including data analytics, batch processing, and interactive processing. These applications require high throughput, low latency, and high reliability from the network. Satisfying these requirements in the face of dynamically varying network conditions remains a challenging problem. Multi-Path TCP (MPTCP) is a recently proposed IETF extension to TCP that divides a conventional TCP flow into multiple subflows so as to utilize multiple paths over the network. Despite the theoretical and practical benefits of MPTCP, its effectiveness for cloud applications and environments remains unclear as there has been little work to quantify the benefits of MPTCP for real cloud applications. We present a broad empirical study of the effectiveness and feasibility of MPTCP for data center and cloud applications, under different network conditions. Our results show that while MPTCP provides useful bandwidth aggregation, congestion avoidance, and improved resiliency for some cloud applications, these benefits do not apply uniformly across applications, especially in cloud settings.

Estimating distributions of node characteristics (labels) such as number of connections or citizenship of users in a social network via edge and node sampling is a vital part of the study of complex networks. Due to its low cost, sampling via a random walk (RW) has been proposed as an attractive solution to this task. Most RW methods assume either that the network is undirected or that walkers can traverse edges regardless of their direction. Some RW methods have been designed for directed networks where edges coming into a node are not directly observable. In this work, we propose Directed Unbiased Frontier Sampling (DUFS), a sampling method based on a large number of coordinated walkers, each starting from a node chosen uniformly at random. It applies to directed networks with invisible incoming edges because it constructs, in real time, an undirected graph consistent with the walkers trajectories, and its use of random jumps to prevent walkers from being trapped. DUFS generalizes previous RW methods and is suited for undirected networks and to directed networks regardless of in-edge visibility. We also propose an improved estimator of node label distribution that combines information from initial walker locations with subsequent RW observations. We evaluate DUFS, compare it to other RW methods, investigate the impact of its parameters on estimation accuracy and provide practical guidelines for choosing them. In estimating out-degree distributions, DUFS yields significantly better estimates of the head of the distribution than other methods, while matching or exceeding estimation accuracy of the tail. Last, we show that DUFS outperforms uniform sampling when estimating distributions of node labels of the top 10% largest degree nodes, even when sampling a node uniformly has the same cost as RW steps.

Recently exploring locally connected subgraphs (also known as motifs or graphlets) of complex networks attracts a lot of attention. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring usually use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we call a “ RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the original graph. To resolve this, we propose a framework Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. Experiments using large scale datasets show the accuracy and efficiency of our method.

In this paper, we consider the problem of allocating cache resources among multiple content providers. The cache can be partitioned into slices and each partition can be dedicated to a particular content provider or shared among a number of them. It is assumed that each partition employs the least recently used policy for managing content. We propose utility-driven partitioning, where we associate with each content provide a utility that is a function of the hit rate observed by the content provider. We consider two scenarios: (1) content providers serve disjoint sets of files and (2) there is some overlap in the content served by multiple content providers. In the first case, we prove that cache partitioning outperforms cache sharing as cache size and a number of contents served by providers go to infinity. In the second case, it can be beneficial to have separate partitions for overlapped content. In the case of two providers, it is usually always beneficial to allocate a cache partition to serve all overlapped content and separate partitions to serve the non-overlapped contents of both providers. We establish conditions when this is true asymptotically but also present an example where it is not true asymptotically. We develop online algorithms that dynamically adjust partition sizes in order to maximize the overall utility and prove that they converge to optimal solutions, and through numerical evaluations we show they are effective.

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.

Though the classical packet-level queueing theory, which treats each packet as an entry, has achieved a great success in network analysis, it can be inaccurate when directly applied to long-term evolution (LTE) networks. This is because arriving packets could be broken down at the LTE base station server across adjacent transmission time intervals (TTIs), which are the smallest scheduling time units in LTE networks. In this paper, we first propose an innovative bit-level queueing theory to address the challenges in performance analysis of LTE networks. To consider the randomness in packet arrivals and packet lengths, we propose two representative compound network traffic models-Poisson-Exponential (PE) and Zeta-Pareto (ZP) models-to approximate light-tailed and heavy-tailed network traffic, respectively. PE models are suitable for conventional voice and low-speed services, while ZP models, which compound power-law distributions, describe complicated high-speed network applications. We derive tail asymptotics for the distributions of the number of bit arrivals in one TTI and the corresponding waiting time. Based on the results in bit-level queueing theory, we present engineering applications that take into account user experience, including estimating the user experience rate (UER), the busy UER and hourly traffic volume. The theoretical results are then validated through extensive simulations. Our novel traffic estimation approach has been adopted by Wireless Product Line at Huawei for network capacity planning and also projected to International Telecommunication Union (ITU) to compose 5G standards.

Energy efficiency is a fundamental requirement of modern data communication systems, and its importance is reflected in much recent work on performance analysis of system energy consumption. However, most works have only focused on communication and computation costs, but do not account for caching costs. Given the increasing interest in cache networks, this is a serious limitation. In this paper, we consider the energy consumption trade-off between communication, computation, and caching (C3) under a Quality of Information (QoI) guarantee in a communication network. To attain this goal, we formulate an optimization problem to capture the C3 costs, which turns out to be a non-convex Mixed Integer Non-Linear Programming (MINLP) Problem. We then propose a variant of spatial branch and bound algorithm (V-SBB), that can achieve ε -global optimal solution to the original MINLP. We show numerically that V-SBB is more stable and robust than other candidate MINLP solvers under different network scenarios. More importantly, we observe that the energy efficiency under our C3 optimization framework improves by as much as 88% compared to any C2 optimization between communication and computation or caching.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

The Transmission Control Protocol (TCP) utilizes congestion avoidance and control mechanisms as a preventive measure against congestive collapse and as an adaptive measure in the presence of changing network conditions. The set of available congestion control algorithms is diverse, and while many have been studied from empirical and simulation perspectives, there is a notable lack of analytical work for some variants. To gain more insight into the dynamics of these algorithms, we: (1) propose a general modeling scheme consisting of a set of functional differential equations of retarded type (RFDEs) and of the congestion window as a function of time; (2) apply this scheme to TCP Reno and demonstrate its equivalence to a previous, well known model for TCP Reno; (3) show an application of the new framework to the widely-deployed congestion control algorithm TCP CUBIC, for which analytical models are few and limited; and (4) validate the model using simulations. Our modeling framework yields a fluid model for TCP CUBIC. From a theoretical analysis of this model, we discover that TCP CUBIC is locally uniformly asymptotically stable-a property of the algorithm previously unknown.

The design of caching algorithms to maximize hit probability has been extensively studied. In this paper, we associate each content with a utility, which is a function of either corresponding content hit rate or hit probability. We formulate a cache optimization problem to maximize the sum of utilities over all contents under stationary and ergodic request process. This problem is non-convex in general but we reformulate it as a convex optimization problem when the inter-request time (irt) distribution has a non-increasing hazard rate function. We provide explicit optimal solutions for some irt distributions, and compare the solutions of the hit-rate based (HRB) and hit probability based (HPB) problems. We also propose decentralized algorithms that can be implemented using limited information and are guaranteed to provide optimal solutions. We find that decentralized algorithms that solve HRB are more robust than decentralized HPB algorithms. Informed by these results, we further propose lightweight Poisson approximate decentralized and online algorithms that are accurate and efficient in achieving optimal hit rates and hit probabilities.

We consider the problem of optimally compressing and caching data across a communication network. Given the data generated at edge nodes and a routing path, our goal is to determine the optimal data compression ratios and caching decisions across the network in order to minimize average latency, which can be shown to be equivalent to maximizing the compression and caching gain under an energy consumption constraint. We show that this problem is NP-hard in general and the hardness is caused by the caching decision subproblem, while the compression sub-problem is polynomial-time solvable. We then propose an approximation algorithm that achieves a $(1-1/e)$-approximation solution to the optimum in strongly polynomial time. We show that our proposed algorithm achieve the near-optimal performance in synthetic-based evaluations. In this paper, we consider a tree-structured network as an illustrative example, but our results easily extend to general network topology at the expense of more complicated notations.

This paper has the following ambitious goal: to convince the reader that content caching is an exciting research topic for the future communication systems and networks. Caching has been studied for more than 40 years, and has recently received increased attention from industry and academia. Novel caching techniques promise to push the network performance to unprecedented limits, but also pose significant technical challenges. This tutorial provides a brief overview of existing caching solutions, discusses seminal papers that open new directions in caching, and presents the contributions of this special issue. We analyze the challenges that caching needs to address today, also considering an industry perspective, and identify bottleneck issues that must be resolved to unleash the full potential of this promising technique.

Welcome to the second part of the IEEE JSAC special issue on Caching for Communication Systems and Networks. The goal of this special issue is to present the multiple facets of caching, from information theory to networking and services, and explore the role of memory in communications. This is a very timely topic due to recent technological and theoretical advances summarized in the tutorial paper that appears in the first part of the issue[1].

Counting 3-, 4-, and 5-node graphlets in graphs is important for graph mining applications such as discovering abnormal/ evolution patterns in social and biology networks. In addition, it is recently widely used for computing similarities between graphs and graph classification applications such as protein function prediction and malware detection. However, it is challenging to compute these graphlet counts for a large graph or a large set of graphs due to the combinatorial nature of the problem. Despite recent efforts in counting 3-node and 4-node graphlets, little attention has been paid to characterizing 5-node graphlets. In this paper, we develop a computationally efficient sampling method to estimate 5-node graphlet counts. We not only provide a fast sampling method and unbiased estimators of graphlet counts, but also derive simple yet exact formulas for the variances of the estimators which are of great value in practice-the variances can be used to bound the estimates' errors and determine the smallest necessary sampling budget for a desired accuracy. We conduct experiments on a variety of real-world datasets, and the results show that our method is several orders of magnitude faster than the state-of-the-art methods with the same accuracy.

In covert communication, Alice tries to communicate with Bob without being detected by a warden Willie. When the distance between Alice and Bob becomes large compared with the distance between Alice and Willie(s), the performance of covert communication will be degraded. In this case, multi-hop message transmission via intermediate relays can help to improve the performance. Hence, in this paper, multi-hop covert communication over a moderate size network and in the presence of multiple collaborating Willies is considered. The relays can transmit covertly using either a single key for all relays or different independent keys at the relays. For each case, we develop efficient algorithms to find optimal paths with maximum throughput and minimum end-to-end delay between Alice and Bob. As expected, employing multiple hops significantly improves the ability to communicate covertly versus the case of a single-hop transmission. Furthermore, at the expense of more shared key bits, analytical results and numerical simulations demonstrate that the multi-hop covert communication with different independent keys at the relays has better performance than the multi-hop covert communication with a single key.

Covert communication conceals the transmission of the message from an attentive adversary. Recent work on the limits of covert communication in additive white Gaussian noise channels has demonstrated that a covert transmitter (Alice) can reliably transmit a maximum of O(√n) bits to a covert receiver (Bob) without being detected by an adversary (Warden Willie) in n channel uses. This paper focuses on the scenario where other “friendly” nodes distributed according to a two-dimensional Poisson point process with density m are present. We propose a strategy where the friendly node closest to the adversary, without close coordination with Alice, produces artificial noise. We show that this method allows Alice to reliably and covertly send O(min{n, mγ/2√n}) bits to Bob in n channel uses, where γ is the path-loss exponent. We also consider a setting where there are Nw collaborating adversaries uniformly and randomly located in the environment and show that in n channel uses, Alice can reliably and covertly send O(min{n, (mγ/2√n/Nwγ)}) bits to Bob when γ>2, and O(min{n, (m√n/Nw2log2Nw)}) when γ=2. Conversely, we demonstrate that no higher covert throughput is possible for γ>2.

Multi-Path TCP (MPTCP) is a new standardized transport protocol that enables devices to utilize multiple network interfaces. The default MPTCP path scheduler prioritizes paths with the smallest round trip time (RTT).In this work, we examine whether the default MPTCP path scheduler can provide applications the ideal aggregate bandwidth, i.e., the sum of available bandwidths of every paths. Our experimental results show that heterogeneous paths cause underutilization of the fast path, resulting in undesirable application behaviors such as lower streaming quality in a video than can be obtained using the available aggregate bandwidth. To solve this problem, we propose and implement a new MPTCP path scheduler, ECF (Earliest Completion First), that utilizes all relevant information about a path, not just RTT. We compare ECF with both the default and other MPTCP path schedulers, using both an experimental testbed and in-the-wild measurements. Our results show that ECF consistently utilizes all available paths more efficiently than other approaches under path heterogeneity, particularly for streaming video. In Web browsing workloads, ECF also does better in some scenarios and never does worse.

ide-area data transfers in high-performance computing infrastructures are increasingly being carried over dynamically provisioned dedicated network connections that provide high capacities with no competing traffic. We present extensive TCP throughput measurements and time traces over a suite of physical and emulated 10 Gbps connections with 0-366 ms round-trip times (RTTs). Contrary to the general expectation, they show significant statistical and temporal variations, in addition to the overall dependencies on the congestion control mechanism, buffer size, and the number of parallel streams. We analyze several throughput profiles that have highly desirable concave regions wherein the throughput decreases slowly with RTTs, in stark contrast to the convex profiles predicted by various TCP analytical models. We present a generic throughput model that abstracts the ramp-up and sustainment phases of TCP flows, which provides insights into qualitative trends observed in measurements across TCP variants: (i) slow-start followed by well-sustained throughput leads to concave regions; (ii) large buffers and multiple parallel streams expand the concave regions in addition to improving the throughput; and (iii) stable throughput dynamics, indicated by a smoother Poincare map and smaller Lyapunov exponents, lead to wider concave regions. These measurements and analytical results together enable us to select a TCP variant and its parameters for a given connection to achieve high throughput with statistical guarantees.

Dedicated wide-area network connections are increasingly employed in high-performance computing and big data scenarios. One might expect the performance and dynamics of data transfers over such connections to be easy to analyze due to the lack of competing traffic. However, non-linear transport dynamics and end-system complexities (e.g., multi-core hosts and distributed filesystems) can in fact make analysis surprisingly challenging. We present extensive measurements of memory-tomemory and disk-to-disk file transfers over 10 Gbps physical and emulated connections with 0-366 ms round trip times (RTTs). For memory-to-memory transfers, profiles of both TCP and UDT throughput as a function of RTT show concave and convex regions; large buffer sizes and more parallel flows lead to wider concave regions, which are highly desirable. TCP and UDT both also display complex throughput dynamics, as indicated by their Poincarέmaps and Lyapunov exponents. For diskto-disk transfers, we determine that high throughput can be achieved via a combination of parallel I/O threads, parallel network threads, and direct I/O mode. Our measurements also show that Lustre filesystems can be mounted over long-haul connections using LNet routers, although challenges remain in jointly optimizing file I/O and transport method parameters to achieve peak throughput.

Swarming systems, such as BitTorrent, are one of the most common solutions for scalable, robust and inexpensive content distribution. Although the service capacity of swarming systems has been studied for decades through modeling and analysis, there is a lack of experimental evidence about how the throughput of such systems behaves in under-provisioned regimes. The aim of this paper is to fill this gap. In this paper, we consider a closed-loop model to assess the throughput of peer-to-peer systems. Then, we show through controlled experiments using BitTorrent clients that some analytical findings recently reported in the literature, such as the missing piece syndrome, occur in practice. In particular, we indicate that when seeds have a small effective service capacity, or when seeds are intermittent, the throughput saturates as the population size grows. Finally, we discuss the implications of such findings on the modeling and design of swarming systems.

Large organizations often have users in multiple sites which are connected over the Internet. Since resources are limited, communication between these sites needs to be carefully orchestrated for the most benefit to the organization. We present a Mission-optimized Overlay Network (MON), a hybrid overlay network architecture for maximizing utility to the organization. We combine an offline and an online system to solve non-concave utility maximization problems. The offline tier, the Predictive Flow Optimizer (PFO), creates plans for routing traffic using a model of network conditions. The online tier, MONtra, is aware of the precise local network conditions and is able to react quickly to problems within the network. Either tier alone is insufficient. The PFO may take too long to react to network changes. MONtra only has local information and cannot optimize non-concave mission utilities. However, by combining the two systems, MON is robust and achieves near-optimal utility under a wide range of network conditions. While best-effort overlay networks are well studied, our work is the first to design overlays that are optimized for mission utility.

In-network content caching has been deployed in both the Internet and cellular networks to reduce content-access delay. We investigate the problem of developing optimal joint routing and caching policies in a network supporting in-network caching with the goal of minimizing expected content-access delay. Here, needed content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access content, users must thus decide whether to route their requests to a cache or to the back-end server. In addition, caches must decide which content to cache. We investigate two variants of the problem, where the paths to the back-end server can be considered as either congestion-sensitive or congestion-insensitive, reflecting whether or not the delay experienced by a request sent to the back-end server depends on the request load, respectively. We show that the problem of optimal joint caching and routing is NP-complete in both cases. We prove that under the congestion-insensitive delay model, the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify the structural property of the user-cache graph that makes the problem NP-complete. For the congestion-sensitive delay model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both cases within a $(1-1/e)$ factor from the optimal, and demonstrate a greedy solution that is numerically shown to be within 1% of optimal for small problem sizes. Through trace-driven simulations, we evaluate the performance of our greedy solutions to joint caching and routing, which show up to 50% reduction in average delay over the solution of optimized routing to least recently used caches.

We consider the problem of placing the minimum number of monitors in a dynamic network to identify additive link metrics from path metrics measured along cycle-free paths between monitors. Our goal is robust monitor placement, i.e., the same set of monitors can maintain network identifiability under topology changes. Our main contribution is a set of monitor placement algorithms with different performance-complexity tradeoffs that can simultaneously identify multiple topologies occurring during the network lifetime. In particular, we show that the optimal monitor placement is the solution to a generalized hitting set problem, for which we provide a polynomial-time algorithm to construct the input and a greedy algorithm to select the monitors with logarithmic approximation. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. Our secondary contribution is a dynamic triconnected decomposition algorithm to compute the input needed by the monitor placement algorithms, which is the first such algorithm that can handle edge deletions. Our evaluations on mobility-induced dynamic topologies verify the efficiency and the robustness of the proposed algorithms.

We investigate the capability of localizing node failures in communication networks from binary states (normal/failed) of end-to-end paths. Given a set of nodes of interest, uniquely localizing failures within this set requires that different observable path states associate with different node failure events. However, this condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our first contribution is a set of sufficient/necessary conditions for identifying a bounded number of failures within an arbitrary node set that can be tested in polynomial time. In addition to network topology and locations of monitors, our conditions also incorporate constraints imposed by the probing mechanism used. We consider three probing mechanisms that differ according to whether measurement paths are: (i) arbitrarily controllable; (ii) controllable but cycle-free; or (iii) uncontrollable (determined by the default routing protocol). Our second contribution is to quantify the capability of failure localization through: 1) the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized and 2) the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in 1) and 2) can be converted into the functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions. We demonstrate how measures 1) and 2) proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.

Recent work has established that when transmitter Alice wishes to communicate reliably to recipient Bob without detection by warden Willie, with additive white Gaussian noise (AWGN) channels between all parties, communication is limited to O(√n) bits in n channel uses. However, this assumes that Willie has an accurate statistical characterization of the channel. When Willie has uncertainty about such and his receiver is limited to a threshold test on the received power, Alice can transmit covertly with a power that does not decrease with n, thus conveying O(n) bits covertly and reliably in n uses of an AWGN channel. Here, we consider covert communication of O(n) bits in n channel uses while generalizing the environment and removing any restrictions on Willie's receiver. We assume that an uninformed “jammer” is present to help Alice, and we consider AWGN and block fading channels. In some scenarios, Willie's optimal detector is a threshold test on the received power. When the channel between the jammer and Willie has multiple fading blocks per codeword, a threshold test on the received power is not optimal. However, we establish that Alice can remain covert with a transmit power that does not decrease with n even when Willie employs an optimal detector.

Characterizing motif (i.e., locally connected sub-graph patterns) statistics is important for understanding complex networks such as online social networks and communication networks. Previous work made the strong assumption that the graph topology of interest is known in advance. In practice, sometimes researchers have to deal with the situation where the graph topology is unknown because it is expensive to collect and store all topological and meta information. Hence, typically what is available to researchers is only a snapshot of the graph, i.e., a subgraph of the graph. Crawling methods such as breadth first sampling can be used to generate the snapshot. However, these methods fail to sample a streaming graph represented as a high speed stream of edges. Therefore, graph mining applications such as network traffic monitoring use random edge sampling (i.e., sample each edge with a fixed probability) to collect edges and generate a sampled graph, which we called a “RESampled graph”. Clearly, a RESampled graph's motif statistics may be quite different from those of the underlying original graph. To resolve this, we propose a framework and implement a system called Minfer, which takes the given RESampled graph and accurately infers the underlying graph's motif statistics. We also apply Fisher information to bound the errors of our estimates. Experiments using large scale datasets show the accuracy and efficiency of our method.

In recent years, there has been a steady growth in network bandwidths. This is especially true in scientific and big data environments, where high bandwidth-delay products (BDPs) are common. It is well-understood that legacy TCP (e.g. TCP Reno) is not appropriate for such environments, and several TCP variants were developed to address this shortcoming. These variants, including CUBIC, STCP, and H-TCP, have been studied in some empirical contexts, and some analytical models exist for CUBIC and STCP. However, since these studies were conducted, BDPs further increased, and new bulk data transfer methods have emerged that utilize parallel TCP streams. In view of these new developments, it is imperative to revisit the question: `Which congestion control algorithms are best adapted to current networking environments?' In order to answer this question, (i) we create a general theoretical framework within which to develop mathematical models of TCP variants that account for finite buffer sizes, maximum window constraints, and parallel TCP streams; (ii) we validate the models using measurements collected over a high-bandwidth testbed and achieve low prediction errors; (iii) we find that CUBIC and H-TCP outperform STCP, especially when multiple streams are used.

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.

We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms.

Recently, the fundamental limits of covert, i.e., reliable-yet-undetectable, communication have been established for general memoryless channels and for lossy-noisy bosonic (quantum) channels with a quantum-limited adversary. The key import of these results was the square-root law (SRL) for covert communication, which states that O(√n) covert bits, but no more, can be reliably transmitted over n channel uses with O(√n) bits of secret pre-shared between communicating parties. Here we prove the achievability of the SRL for a general memoryless classical-quantum channel, showing that SRL covert communication is achievable over any quantum communication channel with a product-state transmission strategy. We leave open the converse, which, if proven, would show that even using entangled transmissions and entangling measurements, the SRL for covert communication cannot be surpassed over an arbitrary quantum channel.

We present diffusion-convolutional neural networks (DCNNs), a new model for graph-structured data. Through the introduction of a diffusion-convolution operation, we show how diffusion-based representations can be learned from graph-structured data and used as an effective basis for node classification. DCNNs have several attractive qualities, including a latent representation for graphical data that is invariant under isomorphism, as well as polynomial-time prediction and learning that can be represented as tensor operations and efficiently implemented on a GPU. Through several experiments with real structured datasets, we demonstrate that DCNNs are able to outperform probabilistic relational models and kernel-on-graph methods at relational node classification tasks.

Cumulative advantage (CA) refers to the notion that accumulated resources foster the accumulation of further resources in competitions, a phenomenon that has been empirically observed in various contexts. The oldest and arguably simplest mathematical model that embodies this general principle is the Pólya urn process, which finds applications in a myriad of problems. The original model captures the dynamics of competitions between two equally fit agents under linear CA effects, which can be readily generalized to incorporate different fitnesses and nonlinear CA effects. We study two statistics of competitions under the generalized model, namely duration (i.e., time of the last tie) and intensity (i.e., number of ties). We give rigorous mathematical characterizations of the tail distributions of both duration and intensity under the various regimes for fitness and nonlinearity, which reveal very interesting behaviors. For example, fitness superiority induces much shorter competitions in the sublinear regime while much longer competitions in the superlinear regime. Our findings can shed light on the application of Pólya urn processes in more general contexts where fitness and nonlinearity may be present.

Due to emerging applications such as cloud computing and big data analytics, modern information processing systems are growing increasingly large and complex. A critical issue concerns the throughput performance as the system grows in size. This paper models distributed information processing systems as fork and join queueing networks with blocking. We identify necessary and sufficient conditions for throughput scalability of such fork and join networks as they grow in size. Previous studies have either focused on special structured networks such as tandem or tree networks, or provided only necessary conditions for throughput scalability. In this paper, we show that such necessary conditions are not sufficient. We present a key topological concept called ``minimum level" of the underlying graph, and develop lower and upper bounds for the throughput of arbitrary FJQN/Bs. The bounds depend on network degree, minimum level, deterministic cycle time, buffer sizes, and service time distributions, but not on network size. We show that level-boundedness and degree-boundedness are necessary and sufficient conditions to guarantee that the throughput of an FJQN/B is bounded away from zero as network size goes to infinity.

Online video streaming through mobile devices has become extremely popular nowadays. YouTube, for example, reported that the percentage of its traffic streaming to mobile devices has soared from 6% to more than 40% over the past two years. Moreover, people are constantly seeking to stream high-quality videos for better experience while often suffering from limited bandwidth. With the rapid deployment of content delivery networks, popular videos are now replicated at different sites, and users can stream over-the-top videos from close-by sources with low latency. Aggregating bandwidth for high definition video streaming has become possible as mobile devices, nowadays, are equipped with multiple wireless interfaces (e.g., WiFi and 3G/4G). We propose a client-based video streaming solution, MSPlayer, that takes advantage of multiple video sources and leverages multiple network paths through different interfaces. MSPlayer reduces start-up latency and provides robust data transport with high video quality in mobile scenarios. We experimentally demonstrate our solution on a test bed and through the YouTube video service.

The heterogeneous cellular network (HCN) is a promising approach to the deployment of 5G cellular networks. This paper comprehensively studies physical layer security in a multitier HCN where base stations (BSs), authorized users, and eavesdroppers are all randomly located. We first propose an access threshold-based secrecy mobile association policy that associates each user with the BS providing the maximum truncated average received signal power beyond a threshold. Under the proposed policy, we investigate the connection probability and secrecy probability of a randomly located user and provide tractable expressions for the two metrics. Asymptotic analysis reveals that setting a larger access threshold increases the connection probability while decreases the secrecy probability. We further evaluate the network-wide secrecy throughput and the minimum secrecy throughput per user with both connection and secrecy probability constraints. We show that introducing a properly chosen access threshold significantly enhances the secrecy throughput performance of a HCN.

The recent square root law (SRL) for covert communication demonstrates that Alice can reliably transmit O(√n) bits to Bob in n uses of an additive white Gaussian noise (AWGN) channel while keeping ineffective any detector employed by the adversary; conversely, exceeding this limit either results in detection by the adversary with high probability or nonzero decoding error probability at Bob. This SRL is under the assumption that the adversary knows when Alice transmits (if she transmits); however, in many operational scenarios, he does not know this. Hence, here, we study the impact of the adversary's ignorance of the time of the communication attempt. We employ a slotted AWGN channel model with T(n) slots each containing n symbol periods, where Alice may use a single slot out of T(n). Provided that Alice's slot selection is secret, the adversary needs to monitor all T(n) slots for possible transmission. We show that this allows Alice to reliably transmit O(min{(n log T(n))1/2, n}) bits to Bob (but no more) while keeping the adversary's detector ineffective. To achieve this gain over SRL, Bob does not have to know the time of transmission provided T(n)cTn, cT= O(1).

Multi-Path TCP (MPTCP) is a new transport protocol that enables systems to exploit available paths through multiple network interfaces. MPTCP is particularly useful for mobile devices, which usually have multiple wireless interfaces. However, these devices have limited power capacity and thus judicious use of these interfaces is required.

There has been increasing interest in designing and developing highly scalable infrastructures to support the efficient distribution of content. This has led to the recent development of content-oriented network architectures that rely on on-demand caching. This paper addresses the question of how a cache provider can monetize its service. Standard cache management policies such as least recently used (LRU) treat different content in a strongly coupled manner that makes it difficult for a cache provider to design individualized contracts. We propose the use of timer-based caching for the purpose of designing contracts, which allow providers to monetize caching. We focus on on-demand request-based contracts that allow content providers (CPs) to negotiate contracts at the time that requests are made. We propose and analyze three variations, one where a contract is negotiated only at the time of a miss, and two where contracts are negotiated at the times of both misses and hits. The latter two differ from one another according to whether pricing is based on cache occupancy (time content spends in the cache) or on request rate. We conclude that the first one is least preferable and that the last one provides the provider greater opportunity for profit and greater flexibility to CPs.

Random walk-based graph sampling methods have become increasingly popular and important for characterizing large-scale complex networks. While powerful, they are known to exhibit problems when the graph is loosely connected, which slows down the convergence of a random walk and can result in poor estimation accuracy. In this work, we observe that many graphs under study, called target graphs, usually do not exist in isolation. In many situations, a target graph is often related to an auxiliary graph and an affiliation graph, and the target graph becomes better connected when viewed from these three graphs as a whole, or what we called a hybrid social-affiliation network. This viewpoint brings extra benefits to the graph sampling framework, e.g., when directly sampling a target graph is difficult or inefficient, we can efficiently sample it with the assistance of auxiliary and affiliation graphs. We propose three sampling methods on such a hybrid social-affiliation network to estimate target graph characteristics, and conduct extensive experiments on both synthetic and real datasets, to demonstrate the effectiveness of these new sampling methods.

We investigate the problem of optimal request routing and content caching in a heterogeneous network supporting in-network content caching with the goal of minimizing average content access delay. Here, content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access a piece of content, a user must decide whether to route its request to a cache or to the back-end server. Additionally, caches must decide which content to cache. We investigate the problem complexity of two problem formulations, where the direct path to the back-end server is modeled as i) a congestion-sensitive or ii) a congestion-insensitive path, reflecting whether or not the delay of the uncached path to the back-end server depends on the user request load, respectively. We show that the problem is NP-complete in both cases. We prove that under the congestion-insensitive model the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify a structural property of the user-cache graph that potentially makes the problem NP-complete. For the congestion-sensitive model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both models within a (1 - 1/e) factor of the optimal solution, and demonstrate a greedy algorithm that is found to be within 1% of optimal for small problem sizes. Through trace-driven simulations we evaluate the performance of our greedy algorithms, which show up to a 50% reduction in average delay over solutions based on LRU content caching.

Nowadays, online crowdsourcing services are quite common such as Amazon Mechanical Turk and Google Helpouts. For such online services, it is important to attract "workers" to provide high-quality solutions to the "tasks" outsourced by "requesters". We present a unified study of incentive and reputation mechanisms for online crowdsourcing systems. We first design an mechanism to incentivize workers provide their maximum effort, which allows multiple workers to solve a task, splits the reward among workers based on requester evaluations of the solution quality. We design a reputation mechanism, which ensures that low-skilled workers do not provide low-quality solutions by tracking workers' historical contributions, and penalizing those workers having poor reputation. We show that our incentive and reputation mechanisms are robust against human biases in solution quality evaluation.

Directed links -- representing asymmetric social ties or interactions (e.g., "follower-followee") -- arise naturally in many social networks and other complex networks, giving rise to directed graphs (or digraphs) as basic topological models for these networks. Reciprocity, defined for a digraph as the percentage of edges with a reciprocal edge, is a key metric that has been used in the literature to compare different directed networks and provide "hints" about their structural properties: for example, are reciprocal edges generated randomly by chance or are there other processes driving their generation? In this paper we study the problem of maximizing achievable reciprocity for an ensemble of digraphs with the same prescribed in- and out-degree sequences. We show that the maximum reciprocity hinges crucially on the in- and out-degree sequences, which may be intuitively interpreted as constraints on some "social capacities" of nodes and impose fundamental limits on achievable reciprocity. We show that it is NP-complete to decide the achievability of a simple upper bound on maximum reciprocity, and provide conditions for achieving it. We demonstrate that many real networks exhibit reciprocities surprisingly close to the upper bound, which implies that users in these social networks are in a sense more "social" than suggested by the empirical reciprocity alone in that they are more willing to reciprocate, subject to their "social capacity" constraints. We find some surprising linear relationships between empirical reciprocity and the bound. We also show that a particular type of small network motifs that we call 3-paths are the major source of loss in reciprocity for real networks.

Network tomography aims to infer the individual performance of networked elements (e.g., links) using aggregate measurements on end-to-end paths. Previous work on network tomography focuses primarily on developing estimators using the given measurements, while the design of measurements is often neglected. We fill this gap by proposing a framework to design probing experiments with focus on probe allocation, and applying it to two concrete problems: packet loss tomography and packet delay variation (PDV) tomography. Based on the Fisher Information Matrix (FIM), we design the distribution of probes across paths to maximize the best accuracy of unbiased estimators, asymptotically achievable by the maximum likelihood estimator. We consider two widely-adopted objective functions: determinant of the inverse FIM (D-optimality) and trace of the inverse FIM (A-optimality). We also extend the A-optimal criterion to incorporate heterogeneity in link weights. Under certain conditions on the FIM, satisfied by both loss and PDV tomography, we derive explicit expressions for both objective functions. When the number of probing paths equals the number of links, these lead to closed-form solutions for the optimal design; when there are more paths, we develop a heuristic to select a subset of paths and optimally allocate probes within the subset. Observing the dependency of the optimal design on unknown parameters, we further propose an algorithm that iteratively updates the design based on parameter estimates, which converges to the design based on true parameters as the number of probes increases. Using packet-level simulations on real datasets, we verify that the proposed design effectively reduces estimation error compared with the common approach of uniformly distributing probes.

In this paper, we study the secure multi-antenna transmission with artificial noise (AN) under slow fading channels coexisting with randomly located eavesdroppers. We provide a comprehensive secrecy performance analysis and system design/optimization under a stochastic geometry framework. Specifically, we first evaluate the secrecy outage performance, and derive a closed-form expression for the optimal power allocation ratio of the information signal power to the total transmit power that minimizes the secrecy outage probability (SOP). Subject to a SOP constraint, we then propose a dynamic parameter transmission scheme (DPTS) and a static parameter transmission scheme (SPTS) to maximize secrecy throughput, and provide explicit solutions on the optimal transmission parameters, including the wiretap code rates, the on-off transmission threshold and the power allocation ratio. Our results give new insight into secure transmission designs. For example, secrecy rate is a concave function of the power allocation ratio in DPTS, and AN plays a significant role under SOP constraints and in dense eavesdropper scenarios. In SPTS, transmission probability is a concave function of the power allocation ratio, and secrecy throughput is a quasi-concave function of the secrecy rate. Numerical results are demonstrated to validate our theoretical analysis.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large-scale nature of such networks, it is infeasible to enumerate all user pairs and thus sampling is used. In this article, we show that it is a great challenge for OSN service providers to characterize user pair relationships, even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, particularly for estimating similarity distribution of user pairs with constraints like existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, as an unbiased sampling technique like UVS is usually not allowed and exploring the OSN graph topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and RW techniques. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to three OSNs—Foursquare, Douban, and Xiami—and discover that significant homophily is present in these networks.

We present an argument in favor of forming coalitions of peers in a data swarming system consisting of peers with heterogeneous upload capacities. In this paper, a coalition refers to a set of peers that explicitly cooperate with other peers inside the coalition via choking, piece selection, and capacity allocation strategies. Furthermore, each peer in a coalition exchanges data with peers outside its coalition via distinct choking, piece selection, and capacity allocation strategies. We first propose a simple Random Choking strategy for peers inside a coalition and develop an analytical model for studying its performance. Our model accurately predicts a coalition's performance and shows that the proposed strategy helps a coalition achieve near-optimal performance. Furthermore, our model can be easily adapted to model a BitTorrent-like swarm. We show that our Random Choking strategy significantly outperforms Tit-for-Tat and Unchoke-All strategies proposed in prior work. We also introduce a simple piece selection strategy, which significantly improves data availability within a coalition as compared to Rarest-First strategy employed in BitTorrent systems. Using cooperative game theory, we prove the existence of stable coalitions when peer population is fixed and each peer has complete information of other peers' actions and payoffs. When peers are allowed to freely join or leave coalitions, we propose a Cooperation-Aware Better Response strategy that achieves convergence of the dynamic coalition formation process. Finally, using extensive simulations, we demonstrate that forming coalitions results in significant improvements in the overall performance of a data swarm.

System objects play different roles in a computer system and exhibit different degrees of importance with respect to system security. Identifying importance metrics can help us to develop more effective and efficient security protection methods. However, there is little previous work on evaluating the importance of objects from the perspective of security. In this paper, we propose a novel approach to evaluate the importance of various system objects based on a bipartite dependency network representation of access behaviors observed in a computer system. We introduce centrality metrics from network science to quantitatively measure the relative importance of system objects and reveal their inherent connections to security properties such as integrity and confidentiality. Furthermore, we propose importance-metric based models to characterize process behaviors and identify abnormal access patterns with respect to confidentiality and integrity. Extensive experimental results on one real-world dataset demonstrate that our model is capable of detecting 7,257 malware samples from 27,840 benign processes at 93.94% TPR under 0.1% FPR. Moreover, a selective protection scheme based on a partial behavioral model of important objects achieves comparable or even better results in malware detection when compared with complete behavior models. This demonstrates the feasibility of the devised importance metrics and presents a promising new approach to malware detection.

Online video streaming through mobile devices has become extremely popular nowadays. YouTube, for example, reported that the percentage of its traffic streaming to mobile devices has soared from 6% to more than 40% over the past two years. Moreover, people are constantly seeking to stream high quality video for better experience while often suffering from limited bandwidth. Thanks to the rapid deployment of content delivery networks (CDNs), popular videos are now replicated at different sites, and users can stream videos from close-by locations with low latencies. As mobile devices nowadays are equipped with multiple wireless interfaces (e.g., WiFi and 3G/4G), aggregating bandwidth for high definition video streaming has become possible.

The main duty of key management is to keep cryptographic keys in secret. However, it is difficulty to quantitatively assess that how well does a key management scheme protect the keys. In this paper, we propose to use reliability theory, which was mainly used to evaluate performance persistence for engineering systems, to estimate the performance of key management schemes. The reliability analysis leads to counter-intuitive results such as the widely deployed periodic key update scheme is ineffective when key thefts are possible. The analysis also shows that using password with an electronic security token for authentication is a strong security measure in the beginning but is unreliable in the long run. In general, the reliability analysis demonstrates that current key management schemes focus too much on postponing the first key theft from occurring but lack of considerations on quickly recovering stolen keys. In the later part of this paper, we discuss possible directions that may improve the reliability of key management schemes.

We investigate the problem of localizing node failures in a communication network from end-to-end path measurements, under the assumption that a path behaves normally if and only if it does not contain any failed nodes. To uniquely localize node failures, the measurement paths must show different symptoms under different failure events, i.e., for any two distinct sets of failed nodes, there must be a measurement path traversing one and only one of them. This condition is, however, impractical to test for large networks. Our first contribution is a characterization of this condition in terms of easily verifiable conditions on the network topology with given monitor placements under three families of probing mechanisms, which differ in whether measurement paths are (i) arbitrarily controllable, (ii) controllable but cycle-free, or (iii) uncontrollable (i.e., determined by the default routing protocol). Our second contribution is a characterization of the maximum identifiability of node failures, measured by the maximum number of simultaneous failures that can always be uniquely localized. Specifically, we bound the maximal identifiability from both the upper and the lower bounds which differ by at most one, and show that these bounds can be evaluated in polynomial time. Finally, we quantify the impact of the probing mechanism on the capability of node failure localization under different probing mechanisms on both random and real network topologies. We observe that despite a higher implementation cost, probing along controllable paths can significantly improve a network's capability to localize simultaneous node failures.

MPTCP is a new transport protocol that enables mobile devices to use several physical paths simultaneously through multiple network interfaces, such as WiFi and cellular. However, wireless path characteristics change frequently in mobile environments, causing challenges for MPTCP: For example, WiFi associated paths often become unavailable as devices move, since WiFi has intermittent connectivity caused by the short signal range and susceptibility to interference. In this work, we improve MPTCP to manage path usage based on the associated link status. This variant, called MPTCP-MA, uses MAC-Layer information to locally estimate path quality and connectivity. By suspending/releasing paths based on their quality, MPTCP-MA can more effectively utilize restored paths. We have implemented and deployed MPTCP-MA in Linux and Android. Our experimental results show that MPTCP-MA can efficiently utilize an intermittently available path, with Wifi throughput improvements of up to 72 percent.

We investigate the problem of placing a given number of monitors in a communication network to identify the maximum number of link metrics from end-to-end measurements between monitors, assuming that link metrics are additive, and measurement paths cannot contain cycles. Motivated by our previous result that complete identification of all link metrics can require a large number of monitors, we focus on partial identification using a limited number of monitors. The basis to our solution is an efficient algorithm for determining all identifiable links for a given monitor placement. Based on this algorithm, we develop a polynomial-time greedy algorithm to incrementally place monitors such that each newly placed monitor maximizes the number of additional identifiable links. We prove that the proposed algorithm is optimal for 2-vertex-connected networks, and demonstrate that it is near-optimal for several real ISP topologies that are not 2-vertex-connected. Our solution provides a quantifiable tradeoff between level of identifiability and available monitor resources.

Unlike standard security methods (e.g. encryption), low probability of detection (LPD) communication does not merely protect the information contained in a transmission from unauthorized access, but prevents the detection of a transmission in the first place. In this work we study the impact of secretly pre-arranging the time of communication. We prove that if Alice has AWGN channels to Bob and the warden, and if she and Bob can choose a single n symbol period slot out of T(n) such slots, keeping the selection secret from the warden (and, thus, forcing him to monitor all T(n) slots), then Alice can reliably transmit O(min{√n log T(n),n}) bits to Bob while keeping the warden's detector ineffective. The result indicates that only an additional log T(n) secret bits need to be exchanged between Alice and Bpob prior to communication to produce a multiplicative gain of √log T(n) in the amount of transmitted covert information.

With the rapid deployment of cellular net-works, modern mobile devices are now equipped with at least two interfaces (WiFi and 3G/4G). As multi-path TCP (MPTCP) has been standardized by the IETF, mobile users running MPTCP can access the Internet via multiple interfaces simultaneously to provide robust data transport and better throughput. However, as cellular networks exhibit large RTTs compared to WiFi, for small data transfers, the delayed startup of additional flows in the current MPTCP design can limit the use of MPTCP. For large data transfers, when exploiting both the WiFi and cellular networks, the inflated and varying RTTs of the cellular flow together with the small and stable RTTs of the WiFi flow can lead to performance degradation. In this paper, we seek to investigate the causes of MPTCP performance issues in wireless environments and will provide analyses and a solution for better performance.

Today, most devices have multiple network interfaces. Coupled with wide-spread replication of popular content at multiple locations, this provides substantial path diversity in the Internet. We propose Multi-source Multipath HTTP, mHTTP, which takes advantage of all existing types of path diversity in the Internet. mHTTP needs only client-side but not server-side or network modifications as it is a receiver-oriented mechanism. Moreover, the modifications are restricted to the socket interface. Thus, no changes are needed to the applications or to the kernel.

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and Online Social Networks (OSNs). Nowadays, the massive size of some critical networks—often stored in already overloaded relational databases—effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose sampling methods to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no precomputation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known datasets and show that, for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.

There has been a great deal of interest recently in load-balancing switches due to their simple architecture and high forwarding bandwidth. Nevertheless, the mis-sequencing problem of the original load-balancing switch hinders the performance of underlying TCP applications. Several load-balancing switch designs have been proposed to address this mis-sequencing issue. They solve this mis-sequencing problem at the cost of either algorithmic complexity or special hardware requirements. In this paper, we address the mis-sequencing problem by introducing a three-stage load-balancing switch architecture enhanced with an output load-balancing mechanism. This three-stage load-balancing switch achieves a high forwarding capacity while preserving the order of packets without the need of costly online scheduling algorithms. Theoretical analyses and simulation results show that this three-stage load-balancing switch provides a transmission delay that is upper-bounded by that of an output-queued switch plus a constant that depends only on the number of input/output ports, indicating the same forwarding capacity as an output-queued switch.

We investigate the problem of identifying individual link metrics in a communication network from end-to-end path measurements, under the assumption that link metrics are additive and constant. To uniquely identify the link metrics, the number of linearly independent measurement paths must equal the number of links. Our contribution is to characterize this condition in terms of the network topology and the number/placement of monitors, under the constraint that measurement paths must be cycle-free. Our main results are: 1) it is generally impossible to identify all the link metrics by using two monitors; 2) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; 3) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only facilitate efficient identifiability tests, but also enable an efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed algorithm achieves identifiability using a much smaller number of monitors than a baseline solution.

Online dating sites have become popular platforms for people to look for potential romantic partners. It is important to understand users' dating preferences in order to make better recommendations on potential dates. The message sending and replying actions of a user are strong indicators for what he/she is looking for in a potential date and reflect the user's actual dating preferences. We study how users' online dating behaviors correlate with various user attributes using a real-world dateset from a major online dating site in China. Our study provides a firsthand account of the user online dating behaviors in China, a country with a large population and unique culture. The results can provide valuable guidelines to the design of recommendation engine for potential dates.

We investigate the problem of identifying individual link performance metrics in a communication network by measuring end-to-end metrics of selected paths between monitors, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. In a previous work, we developed an algorithm that places the minimum number of monitors to identify all link metrics. However, even the minimum number can be large in some practical networks (e.g., 60% of all the nodes), suggesting high monitor deployment cost. In this paper, we study the dual problem where given a fixed number of monitors, we want to place them to maximize the number of identifiable link metrics, with concrete results for the case of two monitors. The significance of the two-monitor case is that all the tomographic computation can be performed at the destination monitor without shipping measurements to a central node, thus enabling endhost-based network monitoring. We develop an efficient algorithm to determine all identifiable links in an arbitrary network with a given placement of two monitors, based on which we propose an optimal two-monitor placement algorithm to maximize the number of identifiable links. Our evaluation on real ISP topologies shows that although a large number of monitors is needed to identify all link metrics, we can usually identify a substantial portion (up to 97%) of the links using a single pair of optimally placed monitors.

We investigate the problem of identifying individual link metrics in a communication network from accumulated end-to-end metrics over selected measurement paths, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. We know from linear algebra that all link metrics can be uniquely identified when the number of linearly independent measurement paths equals u, the number of links. It is, however, inefficient to collect measurements from all possible paths, whose number can grow exponentially in u, as the number of useful measurements (from linearly independent paths) is at most u. The aim of this paper is to develop efficient algorithms for constructing linearly independent measurement paths and calculating link metrics. We show that whenever there exists a set of u linearly independent measurement paths, there must exist a set of three pairwise independent spanning trees. We exploit this property to develop an algorithm that can construct u linearly independent, cycle-free paths between monitors without examining all candidate paths, whose complexity is quadratic in u. A further benefit of the proposed algorithm is that the generated paths satisfy a nested structure that allows linear-time computation of link metrics without explicitly inverting the measurement matrix. Our evaluations on both synthetic and real network topologies verify the superior efficiency of the proposed algorithms, which are orders of magnitude faster than benchmark solutions for large networks.

Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large scale nature of such networks, it is infeasible to enumerate all user pairs and so sampling is used. In this paper, we show that it is a great challenge even for OSN service providers to characterize user pair relationships even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, in particular, for estimating similarity distribution of user pairs with constraints such as existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, since an unbiased sampling technique such as UVS is usually not allowed, and exploring the OSN graph topology is expensive. To address these challenges, we present asymptotically unbiased sampling methods to characterize user pair properties based on UVS and RW techniques respectively. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to two Chinese OSNs, Doudan and Xiami, and discover significant homophily is present in these two networks.

With the popularity of mobile devices and the pervasive use of cellular technology, there is widespread interest in hybrid networks and on how to achieve robustness and good performance from them. As most smart phones and mobile devices are equipped with dual interfaces (WiFi and 3G/4G), a promising approach is through the use of multi-path TCP, which leverages path diversity to improve performance and provide robust data transfers. In this paper we explore the performance of multi-path TCP in the wild, focusing on simple 2-path multi-path TCP scenarios. We seek to answer the following questions: How much can a user benefit from using multi-path TCP over cellular and WiFi relative to using the either interface alone? What is the impact of flow size on average latency? What is the effect of the rate/route control algorithm on performance? We are especially interested in understanding how application level performance is affected when path characteristics (e.g., round trip times and loss rates) are diverse. We address these questions by conducting measurements using one commercial Internet service provider and three major cellular carriers in the US.

We investigate the problem of identifying individual link metrics in a communication network from end-to-end path measurements, under the assumption that link metrics are additive and constant. To uniquely identify the link metrics, the number of linearly independent measurement paths must equal the number of links. Our contribution is to characterize this condition in terms of the network topology and the number/placement of monitors, under the constraint that measurement paths must be cycle-free. Our main results are: (i) it is generally impossible to identify all the link metrics by using two monitors; (ii) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; (iii) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only allow efficient identifiability tests, but also enable an efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed algorithm achieves identifiability using a much smaller number of monitors than a baseline solution.

We consider the problem of endhost-based shortest path routing in a network with unknown, time-varying link qualities. Endhost-based routing is needed when internal nodes of the network do not have the scope or capability to provide globally optimal paths to given source-destination pairs, as can be the case in networks consisting of autonomous subnetworks or those with endhost-based routing restrictions. Assuming the source can probe links along selected paths, we formulate the problem as an online learning problem, where an existing solution achieves a performance loss (called regret) that is logarithmic in time with respect to (wrt) an offline algorithm that knows the link qualities. Current solutions assume coupled probing and routing; in contrast, we give a simple algorithm based on decoupled probing and routing, whose regret is only constant in time. We then extend our solution to support multi-path probing and cooperative learning between multiple sources, where we show an inversely proportional decay in regret wrt the probing rate. We also show that without the decoupling, the regret grows at least logarithmically in time, thus establishing decoupling as critical for obtaining constant regret. Although our analysis assumes certain conditions (i.i.d.) on link qualities, our solution applies with straightforward amendments to much broader scenarios where these conditions are relaxed. The efficacy of the proposed solution is verified by trace-driven simulations.

We consider the performance of information propagation through social networks in a scenario where each user has a budget of attention, that is, a constraint on the frequency with which he pulls content from neighbors. In this context we ask the question “when users make selfish decisions on how to allocate their limited access frequency among neighbors, does information propagate efficiently?” For the metric of average propagation delay, we provide characterizations of the optimal social cost and the social cost under selfish user optimizations for various topologies of interest. Three situations may arise: well-connected topologies where delay is small even under selfish optimization; tree-like topologies where selfish optimization performs poorly while optimal social cost is low; and “stretched” topologies where even optimal social cost is high. We propose a mechanism for incentivizing users to modify their selfish behaviour, and observe its efficiency in the family of tree-like topologies mentioned above.

We demonstrate the achievability of a square root limit on the amount of information transmitted reliably and with low probability of detection (LPD) over the single-mode lossy bosonic channel if either the eavesdropper's measurements or the channel itself is subject to the slightest amount of excess noise. Specifically, Alice can transmit O(√n) bits to Bob over n channel uses such that Bob's average codeword error probability is upper-bounded by an arbitrarily small δ > 0 while a passive eavesdropper, Warden Willie, who is assumed to be able to collect all the transmitted photons that do not reach Bob, has an average probability of detection error that is lower-bounded by 1/2 - ε for an arbitrarily small ε > 0. We analyze the thermal noise and pure loss channels. The square root law holds for the thermal noise channel even if Willie employs a quantum-optimal measurement, while Bob is equipped with a standard coherent detection receiver. We also show that LPD communication is not possible with coherent state transmission on the pure loss channel. However, this result assumes Willie to possess an ideal receiver that is not subject to excess noise. If Willie is restricted to a practical receiver with a non-zero dark current, the square root law is achievable on the pure loss channel.

In this paper, we investigate the problem of determining the routing that minimizes the maximum/average delivery time or the maximum/average delivery delay for a set of packets in a deterministic Delay Tolerant Network, i.e. in a network for which all the nodes' transmission opportunities are known in advance. While the general problem with multiple sources and multiple destinations is NP-hard, we present a polynomial time algorithm that can efficiently compute the optimal routing in the case of a single destination or of a single packet that needs to be routed to multiple destinations.

We present a square root limit on the amount of information transmitted reliably and with low probability of detection (LPD) over additive white Gaussian noise (AWGN) channels. Specifically, if the transmitter has AWGN channels to an intended receiver and a warden, both with non-zero noise power, we prove that o(√n) bits can be sent from the transmitter to the receiver in n channel uses while lower-bounding α + β ≥ 1-ε for any ε > 0, where α and β respectively denote the warden's probabilities of a false alarm when the sender is not transmitting and a missed detection when the sender is transmitting. Moreover, in most practical scenarios, a lower bound on the noise power on the channel between the transmitter and the warden is known and O(√n) bits can be sent in n LPD channel uses. Conversely, attempting to transmit more than O(√n) bits either results in detection by the warden with probability one or a non-zero probability of decoding error at the receiver as n→∞.

In this work we study the set size distribution estimation problem, where elements are randomly sampled from a collection of non-overlapping sets and we seek to recover the original set size distribution from the samples. This problem has applications to capacity planning and network theory. Examples of real-world applications include characterizing in-degree distributions in large graphs and uncovering TCP/IP flow size distributions on the Internet. We demonstrate that it is difficult to estimate the original set size distribution. The recoverability of original set size distributions presents a sharp threshold with respect to the fraction of elements that remain in the sets. If this fraction lies below the threshold, typically half of the elements in power-law and heavier-than-exponential-tailed distributions, then the original set size distribution is unrecoverable. We also discuss practical implications of our findings.

In this paper, we investigate how in-network aggregation approach impacts the target tracking quality in multi-hop wireless sensor networks under network delays. Specifically, we use the mean squared error (MSE) of the target location estimate to quantify the target tracking quality, and investigate how in-network aggregation affects the MSE. To obtain insights without being obscured by onerous mathematical details, we assume a Brownian motion mobility model for the target, Gaussian measurement noise for the sensors, and independent per-hop delays. Under the above assumptions, we first propose an aggregation scheme that preserves a sufficient statistic for optimal tracking under data aggregation at the intermediate nodes and arbitrary network delays. We then analytically study the impact of aggregation in three increasingly more complicated scenarios: single task tracking with only transmission delay, single task tracking with both transmission delay and queueing delay at intermediate nodes, and multi-task tracking. Our results demonstrate that in-network aggregation improves tracking quality in all three scenarios. Furthermore, our analysis provides guidelines on how to choose aggregation parameters in practice.

The capability of nodes to broadcast their message to the entire wireless network when nodes employ cooperation is considered. We employ an asymptotic analysis using an extended random network setting under an additive white Gaussian channel model with path loss, and show that the broadcast performance strongly depends on the path loss exponent of the medium. In particular, the probability of broadcasting in a 1-D infinite network is zero for path loss exponents larger than one, and is equal to a nonzero value for path loss exponents less than one. In 2-D infinite networks, the same behavior is observed for path loss exponents above and below two, respectively.

BitTorrent, the immensely popular file swarming system, suffers a fundamental problem: content unavailability. Although swarming scales well to tolerate flash crowds for popular content, it is less useful for unpopular content as peers arriving after the initial rush find it unavailable. In this paper, we present a model to quantify content availability in swarming systems. We use the model to analyze the availability and the performance implications of bundling, a strategy commonly adopted by many BitTorrent publishers today. We find that even a limited amount of bundling exponentially reduces content unavailability. For swarms with highly unavailable publishers, the availability gain of bundling can result in a net decrease in average download time. We empirically confirm the model's conclusions through experiments on PlanetLab using the Mainline BitTorrent client.

Neighbor discovery is an important first step in the initialization of a wireless ad hoc network. In this paper, we design and analyze several algorithms for neighbor discovery in wireless networks. Starting with a single-hop wireless network ofnnodes, we propose a Θ(nlnn) ALOHA-like neighbor discovery algorithm when nodes cannot detect collisions, and an order-optimal Θ(n) receiver feedback-based algorithm when nodes can detect collisions. Our algorithms neither require nodes to have a priori estimates of the number of neighbors nor synchronization between nodes. Our algorithms allow nodes to begin execution at different time instants and to terminate neighbor discovery upon discovering all their neighbors. We finally show that receiver feedback can be used to achieve a Θ(n) running time, even when nodes cannot detect collisions. We then analyze neighbor discovery in a general multihop setting. We establish an upper bound ofO(Δlnn) on the running time of the ALOHA-like algorithm, where Δ denotes the maximum node degree in the network andnthe total number of nodes. We also establish a lower bound of Ω(Δ+lnn) on the running time of any randomized neighbor discovery algorithm. Our result thus implies that the ALOHA-like algorithm is at most a factor min(Δ,lnn) worse than optimal.

In this paper, we investigate the benefits of applying a form of network coding known as random linear coding (RLC) to unicast applications in disruption-tolerant networks (DTNs). Under RLC, nodes store and forward random linear combinations of packets as they encounter each other. For the case of a single group of packets originating from the same source and destined for the same destination, we prove a lower bound on the probability that the RLC scheme achieves the minimum time to deliver the group of packets. Although RLC significantly reduces group delivery delays, it fares worse in terms of average packet delivery delay and network transmissions. When replication control is employed, RLC schemes reduce group delivery delays without increasing the number of transmissions. In general, the benefits achieved by RLC are more significant under stringent resource (bandwidth and buffer) constraints, limited signaling, highly dynamic networks, and when applied to packets in the same flow. For more practical settings with multiple continuous flows in the network, we show the importance of deploying RLC schemes with a carefully tuned replication control in order to achieve reduction in average delay, which is observed to be as large as 20% when buffer space is constrained.

We study the dynamic aspects of the coverage of a mobile sensor network resulting from continuous movement of sensors. As sensors move around, initially uncovered locations may be covered at a later time, and intruders that might never be detected in a stationary sensor network can now be detected by moving sensors. However, this improvement in coverage is achieved at the cost that a location is covered only part of the time, alternating between covered and not covered. We characterize area coverage at specific time instants and during time intervals, as well as the time durations that a location is covered and uncovered. We further consider the time it takes to detect a randomly located intruder and prove that the detection time is exponentially distributed with parameter 2\lambda r \bar{v}_s where \lambda represents the sensor density, r represents the sensor's sensing range, and \bar{v}_s denotes the average sensor speed. For mobile intruders, we take a game theoretic approach and derive optimal mobility strategies for both sensors and intruders. We prove that the optimal sensor strategy is to choose their directions uniformly at random between [0, 2\pi ). The optimal intruder strategy is to remain stationary. This solution represents a mixed strategy which is a Nash equilibrium of the zero-sum game between mobile sensors and intruders.

Vehicle-to-grid provides a viable approach that feeds the battery energy stored in electric vehicles (EVs) back to the power grid. Meanwhile, since EVs are mobile, the energy in EVs can be easily transported from one place to another. Based on these two observations, we introduce a novel concept called EV energy network for energy transmission and distribution using EVs. We present a concrete example to illustrate the usage of an EV energy network, and then study the optimization problem of how to deploy energy routers in an EV energy network. We prove that the problem is NP-hard and develop a greedy heuristic solution. Simulations using real-world data shows that our method is efficient.

We present achievable scaling results on the per-node secure throughput that can be realized in a large random wireless network of n legitimate nodes in the presence of m eavesdroppers of unknown location. We consider both one-dimensional and two-dimensional networks. In the one-dimensional case, we show that a per-node secure throughput of order 1/n is achievable if the number of eavesdroppers satisfies m = o(n/log n). We obtain similar results for the two-dimensional case, where a secure throughput of order 1/(√n log n) is achievable under the same condition. The number of eavesdroppers that can be tolerated is significantly higher than previous works that address the case of unknown eavesdropper locations. The key technique introduced in our construction to handle unknown eavesdropper locations forces adversaries to intercept a number of packets to be able to decode a single message. The whole network is divided into regions, where a certain subset of packets is protected from adversaries located in each region. In the one-dimensional case, our construction makes use of artificial noise generation by legitimate nodes to degrade the signal quality at the potential locations of eavesdroppers. In the two-dimensional case, the availability of many paths to reach a destination is utilized to handle collaborating eavesdroppers of unknown location.

In multi-hop wireless networks, per-hop forwarding strategies that optimize local transmissions can have a subtle impact on network performance. Motivated by a number of scenarios for improving signal strength or mitigating interference, we study a fundamental problem that arises in a wireless ad hoc network with directional transmission (e.g., using directional antennas), where nodes are randomly placed with their transmission footprints (each as a sector) aligned toward the destinations. Only the nodes located in the transmission footprint of a transmitter act as forwarders. Our study addresses connectivity of this setting. We first examine through simulation the percolation probability and the number of cross-area paths available to directional transmission, at different spread angles of transmission footprints. We observe that there is a critical spread angle, above which there is little impact on these properties. Analytically, we derive upper and lower bounds for the critical spread angle. Moreover, we show that with high probability there exist at least Ω(n/ log n) number of disjoint paths across a strip area of n × Θ(n), when the critical spread angle lies above the threshold. Our results provide insights on optimizing directional transmission in wireless ad hoc networks.

Although wireless networks have become ubiquitous, surprisingly few models of user-level mobility have been developed and validated against traces of measured user behavior. In this paper, we develop and validate a simple mixed queueing network model of user mobility among access points in a campus network. We identify two classes of users, an open and a closed class, corresponding to mobile users that visit the network for a short time before departure, and users that are always resident in the network during the observation period. Using CRAWDAD traces of user-access-point affiliation over time, we compare model-predicted performance with the performance actually observed in the traces, and find that such a mixed queueing model can indeed be used to accurately predict a number of performance measures of interest.

Despite recent efforts to characterize complex networks such as citation graphs or online social networks (OSNs), little attention has been given to developing tools that can be used to characterize directed graphs in the wild, where no pre-processed data is available. The presence of hidden incoming edges but observable outgoing edges poses a challenge to characterize large directed graphs through crawling, as existing sampling methods cannot cope with hidden incoming links. The driving principle behind our random walk (RW) sampling method is to construct, in real-time, an undirected graph from the directed graph such that the random walk on the directed graph is consistent with one on the undirected graph. We then use the RW on the undirected graph to estimate the outdegree distribution. Our algorithm accurately estimates outdegree distributions of a variety of real world graphs. We also study the hardness of indegree distribution estimation when indegrees are latent (i.e., incoming links are only observed as outgoing edges). We observe that, in the same scenarios, indegree distribution estimates are highly innacurate unless the directed graph is highly symmetrical.

Physical layer secrecy in wireless networks in the presence of eavesdroppers of unknown location is considered. In contrast to prior schemes, which have expended energy in the form of cooperative jamming to enable secrecy, we develop schemes where multiple transmitters send their signals in a cooperative fashion to confuse the eavesdroppers. Hence, power is not expended on “artificial noise”; rather, the signal of a given transmitter is protected by the aggregate interference produced by the other transmitters. We introduce a two-hop strategy for the case of equal path-loss between all pairs of nodes, and then consider its embedding within a multi-hop approach for the general case of an extended network. In each case, we derive an achievable number of eavesdroppers that can be present in the region while secure communication between all sources and intended destinations is ensured.

Energy is the most precious resource in wireless sensor networks. To ensure sustainable operations, wireless sensor systems need to harvest energy from environments. The time-varying environmental energy results in the dynamic change of the system's available energy. Therefore, how to dynamically schedule tasks to match the time-varying energy is a challenging problem. In contrast to traditional computing-oriented scheduling methods that focus on reducing computational energy consumption and meeting the tasks' deadlines, we present DEOS, a dynamic energy-oriented scheduling method, which treats energy as a first-class schedulable resource and dynamically schedules tasks based on the tasks' energy consumption and the system's real-time available energy. We extensively evaluate our system in indoor and outdoor settings. Results indicate that DEOS is extremely lightweight (e.g., energy consumption overhead in the worst case is only 0.039%) and effectively schedules tasks to utilize the dynamically available energy.

We present a square root limit on low probability of detection (LPD) communication over additive white Gaussian noise (AWGN) channels. Specifically, if a warden has an AWGN channel to the transmitter with non-zero noise power, we prove that o(√n) bits can be sent from the transmitter to the receiver in n AWGN channel uses with probability of detection by the warden less than e for any ϵ >; 0, and, if a lower bound on the noise power on the warden's channel is known, then O(√n) bits can be covertly sent in n channel uses. Conversely, trying to transmit more than O(√n) bits either results in detection by the warden with probability one or a non-zero probability of decoding error as n → ∞. Further, we show that LPD communication on the AWGN channel allows one to send a nonzero symbol on every channel use, in contrast to what might be expected from the square root law found recently in image-based steganography.

In this paper we study the behavior of a continuous time random walk (CTRW) on a stationary and ergodic time varying dynamic graph. We establish conditions under which the CTRW is a stationary and ergodic process. In general, the stationary distribution of the walker depends on the walker rate and is difficult to characterize. However, we characterize the stationary distribution in the following cases: i) the walker rate is significantly larger or smaller than the rate in which the graph changes (time-scale separation), ii) the walker rate is proportional to the degree of the node that it resides on (coupled dynamics), and iii) the degrees of node belonging to the same connected component are identical (structural constraints). We provide examples that illustrate our theoretical findings.

Information theoretic security has recently emerged as an effective physical layer approach to provide secure communications. The outage performance of such a secrecy communication system is considered in this paper, since it is an important criterion to measure whether users' predefined quality of service can be met. Provided that the legitimate receiver and eavesdropper have the same noise power, many existing secure schemes cannot achieve outage probability approaching zero, regardless of how large the transmission power is. By introducing cooperative transmission into secrecy communication systems, it will be shown here that outage probability approaching zero can be achieved. In particular, scenarios with single-antenna nodes and multiple-antenna nodes will both be addressed, and the optimal design of beamforming/precoding will be investigated. Explicit expressions of the achievable outage probability and diversity-multiplexing tradeoff will be developed to demonstrate the performance of the proposed cooperative secure transmission schemes, and numerical results are presented.

In this paper, we propose a classification scheme that differentiates Ethernet and WLAN TCP flows based on measurements collected passively at the edge of a network. This scheme computes two quantities, the fraction of wireless TCP flows and the degree of belief that a TCP flow traverses a WLAN inside the network, using an iterative Bayesian inference algorithm that we developed. We prove that this iterative Bayesian inference algorithm converges to the unique maximum likelihood estimate (MLE) of these two quantities. Furthermore, it has the advantage that it can handle any general K-classification problem given the marginal distributions of these classes. Numerical and experimental evaluations demonstrate that our classification scheme obtains accurate results. We apply this scheme to two sets of traces collected from two campus networks: one set collected from UMass in mid 2005 and the other collected from UConn in late 2010. Our technique infers that 4%-7% and 52%-55% of incoming TCP flows traverse an IEEE 802.11 wireless link in these two networks, respectively.

Video streaming represents a large fraction of Internet traffic. Surprisingly, little is known about the network characteristics of this traffic. In this paper, we study the network characteristics of the two most popular video streaming services, Netflix and YouTube. We show that the streaming strategies vary with the type of the application (Web browser or native mobile application), and the type of container (Silverlight, Flash, or HTML5) used for video streaming. In particular, we identify three different streaming strategies that produce traffic patterns from non-ack clocked ON-OFF cycles to bulk TCP transfer. We then present an analytical model to study the potential impact of these streaming strategies on the aggregate traffic and make recommendations accordingly.

We present an argument in favor of forming coalitions of peers in a data swarming system consisting of peers with different upload capacities. A coalition is a set of peers with the same upload capacity that explicitly cooperate with other peers inside the coalition via choking and capacity allocation strategies. Further, each peer interacts with other peers outside its coalition via potentially distinct choking and capacity allocation strategies. This paper focuses on the efficiency of different choking strategies, assuming that peers do not share data with other peers outside their coalitions. We first develop an analytical model that accurately predicts the performance of a coalition of peers adopting BitTorrent's Tit-for-Tat choking strategy. Our model highlights a number of inefficiencies of Tit-for-Tat strategy. Accordingly, we propose a random choking strategy, and show that it can help a coalition achieve near-optimal performance and it significantly outperforms not only Tit-for-Tat strategy but also unchoke-all strategy. Using cooperative game theory, we prove the existence of stable coalitions, and demonstrate the convergence of the dynamic coalition formation process when peers use our cooperation-aware better response strategy. Using extensive simulations, we demonstrate significant performance benefits due to coalition formation.

Low power ad hoc wireless networks operate in conditions where channels are subject to fading. Cooperative diversity mitigates fading in these networks by establishing virtual antenna arrays through clustering the nodes. A cluster in a cooperative diversity network is a collection of nodes that cooperatively transmits a single packet. There are two types of clustering schemes: static and dynamic. In static clustering all nodes start and stop transmission simultaneously, and nodes do not join or leave the cluster while the packet is being transmitted. Dynamic clustering allows a node to join an ongoing cooperative transmission of a packet as soon as the packet is received. In this paper we take a broad view of the cooperative network by examining packet flows, while still faithfully implementing the physical layer at the bit level. We evaluate both clustering schemes using simulations on large multi-flow networks. We demonstrate that dynamically-clustered cooperative networks substantially outperform both statically-clustered cooperative networks and classical point-to-point networks.

One of the challenges of wireless networks is to provide a reliable end-to-end path between two end hosts in the face of link and node outages. These can occur due to fluctuations in channel quality, node movement, or node failure. One mechanism that has been proposed is based on multipath routing, the idea being to establish two or more paths between the end hosts so that they always have a path between them with high probability in the face of outages. This naturally raises the question of how to discover these paths in an unknown, random wireless network to enable robust multipath routing. In order to answer this question, we model a random wireless network as a 2D spatial Poisson process. Based on the results of percolation highways in Franceschetti, et al., we present accurate conditions that enable robust multipath routing. If the number of hops of a path between the end hosts is n, then there exists a path between them in a strip of width proportional to log n. More precisely, there exist C log n disjoint paths in a strip of width a(C, p) · log n, where p is the probability that characterizes the availability of an individual wireless communication link. We derive tight bounds for the function a(C, p). This provides a useful guideline for the establishment of multiple paths in a real wireless network, namely that the width should grow logarithmically in the number of hops on the path between the hosts.

We present a new virtual indexing method for estimating host connection degrees for high speed links. It is based on the virtual connection degree sketch where a compact sketch of network traffic is built by generating the associated virtual bitmaps for each host. Each virtual bitmap consists of a fixed number of bits selected randomly from a shared bit array by a new method for recording the traffic flows of the corresponding host. The shared bit array is efficiently utilized by all hosts since its every bit is shared by the virtual bitmaps of multiple hosts. To reduce the “noise” contaminated in a host's virtual bitmaps due to sharing, we propose a new method to generate the “filtered” bitmap used to estimate host connection degree. Furthermore, it can be easily implemented in parallel and distributed processing environments. The experimental and testing results based on the actual network traffic show that the new method is accurate and efficient.

No abstract available.

The secure transmission of information in wireless networks without knowledge of eavesdropper channels or locations is considered. Two key mechanisms are employed: artificial noise generation from system nodes other than the transmitter and receiver, and a form of multi-user diversity that allows message reception in the presence of the artificial noise. We determine the maximum number of independently-operating and uniformly distributed eavesdroppers that can be present while the desired secrecy is achieved with high probability in the limit of a large number of system nodes. While our main motivation is considering eavesdroppers of unknown location, we first consider the case where the path-loss is identical between all pairs of nodes. In this case, a number of eavesdroppers that is exponential in the number of systems nodes can be tolerated. In the case of uniformly distributed eavesdroppers of unknown location, any number of eavesdroppers whose growth is sub-linear in the number of system nodes can be tolerated. The proposed approach significantly outperforms a power control approach based on standard multi-user diversity.

In this paper, we propose a model-based approach that uses periodic end-end probes to identify whether a “dominant congested link” exists along an end-end path. Informally, a dominant congested link refers to a link that incurs the most losses and significant queuing delays along the path. We begin by providing a formal yet intuitive definition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present a novel model-based approach for dominant congested link identification that is based on interpreting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for hidden Markov model (HMM) and Markov model with a hidden dimension (MMHD) to infer this virtual delay. Our validation using ns simulation and Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further provide an upper bound on the maximum queuing delay of the dominant congested link once we identify that such a link exists.

The back-pressure algorithm introduced in 1992 by Tassiulas and Ephremides is a well-known distributed and adaptive routing/scheduling algorithm where nodes only need the queue-length information of neighboring nodes to make routing decisions. Packets are adaptively routed in the network according to congestion information, which makes the algorithm resilient to traffic and topology changes. However, the back-pressure algorithm requires routers to maintain a separate queue for each destination, which precludes its implementation in large-scale networks. In this paper, we propose a distributed cluster-based back-pressure routing algorithm that retains the adaptability of back-pressure routing while significantly reducing the number of queues that have to be maintained at each node.

In this letter, we study the opportunistic use of relays for secret communications, and propose two transmission schemes that do not require the knowledge of the eavesdropper's channel state information. Both analytic and numerical results are provided.

In this paper, we study the application of cooperative diversity to wireless broadcast channels, a fundamental building block of wireless communication networks. Several cooperative broadcast protocols will be proposed, and information theoretic metrics are developed to facilitate performance evaluation. Provided that there is no direct S-D link, the proposed protocols can achieve a multiplexing gain close to one, whereas the traditional two-hop scheme can only achieve the diversity gain 1/2. Provided that there are direct S-D links, the proposed protocol can still outperform the comparable scheme, particularly at high multiplexing gains.

Estimating characteristics of large graphs via sampling is a vital part of the study of complex networks. Current sampling methods such as (independent) random vertex and random walks are useful but have drawbacks. Random vertex sampling may require too many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new m-dimensional random walk that uses m dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.

Neighbor discovery is essential for the process of self-organization of a wireless network, where almost all routing and medium access protocols need knowledge of one-hop neighbors. In this paper we study the problem of neighbor discovery in a static and synchronous network, where time is divided into slots, each of duration equal to the time required to transmit a hello message, and potentially, some sort of feedback message. Our main contributions lie in detailing the physical layer mechanism for how nodes in receive mode detect the channel status, describing algorithms at higher layers that exploit such a knowledge, and characterizing the significant gain obtained. In particular, we describe one possible physical layer architecture that allows receivers to detect collisions, and then introduce a feedback mechanism that makes the collision information available to the transmitters. This allows nodes to stop transmitting packets as soon as they learn about the successful reception of their discovery messages by the other nodes in the network. Hence, the number of nodes that need to transmit packets decreases over time. These nodes transmit with a probability that is inversely proportional to the number of active nodes in their neighborhood, which is estimated using the collision information available at the nodes. We show through analysis and simulations that our algorithm allows nodes to discover their neighbors in a significantly smaller amount of time compared to the case where reception status feedback is not available to the transmitters.

This work investigates reciprocity in peer-to-peer systems. The scenario is one where users arrive to the network with a set of contents and content demands. Peers exchange contents to satisfy their demands, following either a direct reciprocity principle (I help you and you help me) or indirect reciprocity principle (I help you and someone helps me). First, we prove that any indirect reciprocity schedule of exchanges, in the absence of relays, can be replaced by a direct reciprocity schedule, provided that users (1) are willing to download undemanded content for bartering purposes and (2) use up to twice the bandwidth they would use under indirect reciprocity. Motivated by the fact that, in the absence of relays, the loss of efficiency due to direct reciprocity is at most two, we study various distributed direct reciprocity schemes through simulations, some of them involving a broker to facilitate exchanges.

Many systems employ caches to improve performance. While isolated caches have been studied in-depth, multi-cache systems are not well understood, especially in networks with arbitrary topologies. In order to gain insight into and manage these systems, a low-complexity algorithm for approximating their behavior is required. We propose a new algorithm, termed a-Net, that approximates the behavior of multi-cache networks by leveraging existing approximation algorithms for isolated LRU caches. We demonstrate the utility of a-Net using both per- cache and network-wide performance measures. We also perform factor analysis of the approximation error to identify system parameters that determine the precision of a-Net.

This paper introduces a set of low-complexity algorithms that when coupled with link layer retransmission mechanisms, strengthen wireless communication security. Our basic idea is to generate a series of secrets from inevitable transmission errors and other random factors in wireless communications. Because these secrets are constantly extracted from the communication process in realtime, we call them dynamic secrets. Dynamic secrets have interesting security properties. They offer a complementary mechanism to existing security protocols. Even if the adversary exploits a vulnerability and steals the underlying system secret, security can be automatically replenished. In many scenarios, it is also possible to bootstrap a secure communication with the dynamic secrets.

Many emerging information processing applications require applying various fork and join type operations such as correlation, aggregation, and encoding/decoding to data streams in real-time. Each operation will require one or more simultaneous input data streams and produce one or more output streams, where the processing may shrink or expand the data rates upon completion. Multiple tasks can be co-located on the same server and compete for limited resources. Effective in-network processing and resource management in a distributed heterogeneous environment is critical to achieving better scalability and provision of quality of service. In this paper, we study the distributed resource allocation problem for a synchronous fork and join processing network, with the goal of achieving the maximum total utility of output streams. Using primal and dual based optimization techniques, we propose several decentralized iterative algorithms to solve the problem, and design protocols that implement these algorithms. These algorithms have different strengths in practical implementation and can be tailored to take full advantage of the computing capabilities of individual servers. We show that our algorithms guarantee optimality and demonstrate through simulation that they can adapt quickly to dynamically changing environments.

In a number of network scenarios (including military settings), mobile nodes are clustered into groups, with nodes within the same group exhibiting significant correlation in their movements. Mobility models for such networks should reflect this group structure. In this paper, we consider the problem of identifying the number of groups, and the membership of mobile nodes within groups, from a trace of mobile nodes. We present two clustering algorithms to determine the number of groups and their identities: k-means chain and spectral clustering. Different from traditional k-means clustering, k-means chain identifies the number of groups in a dynamic graph, using a chaining process to keep track of group trajectories over the entire trace. The second approach uses spectral clustering, which uses similarities between node pairs to cluster nodes into groups. We show that the number of groups and node membership can be accurately extracted from traces, particularly when the number of groups is small.

We investigate the scalability of a class of algorithms that exploit the dynamics of wireless fading channels to achieve secret communication in a large wireless network of n randomly located nodes. We describe a construction in which nodes transmit artificial noise to suppress eavesdroppers whose locations are unknown and ensure secrecy of messages transported across the network. Under a model in which eavesdroppers operate independently and under appropriate conditions on the achievable per-node throughput Ψ(n), we show that the network can tolerate Ω((1⁄√n(n))2c) eavesdroppers while ensuring that the aggregate rate at which eavesdroppers intercept packets goes to 0, where c is a constant such that 0 0. We also establish sufficient conditions on the number of eavesdroppers to achieve a non-zero throughput in our construction.

No abstract available.

This paper addresses the problem of distributed resource allocation in general fork and join processing networks. The problem is motivated by the complicated processing requirements arising from distributed data intensive computing. In such applications, the underlying data processing software consists of a rich set of semantics that include synchronous and asynchronous data fork and data join. The different types of semantics and processing requirements introduce complex interdependence between various data flows within the network.

The 11 papers in this special issue on mission critical networking are divided into three categories: quality of service issues (three papers); security issues (four papers); and configuration and data collection issues (four papers).

In this paper, we propose a spectrally efficient cooperative transmission protocol for multiple access scenarios. The key feature is to utilize multi-user diversity and fully exploit the dynamic nature of radio propagation. In particular, by carefully scheduling the multiple sources and relays' transmissions, a source with a poor connection to the destination can have higher priority to obtain help from a relay with better channel condition. As a result, the full diversity gain is achievable even though only a fraction of relays is scheduled to help each user. We developed an achievable diversity-multiplexing tradeoff for the proposed transmission protocol to assist performance evaluation. When the number of relays is large, the diversity-multiplexing tradeoff achieved by the proposed scheme can approximate the optimal multiple-input single-output upper bound. Both analytical and numerical results show that the proposed protocol outperform other comparable schemes in most conditions.

In this paper, cooperative transmission protocols are proposed for wireless broadcast channels, a fundamental building block of wireless communication networks. The concepts of cognitive radio and precoding have been introduced to broadcast channels in order to improve system performance. Information theoretic metrics, such as outage probability and diversity-multiplexing tradeoff, are developed to facilitate performance evaluation. In the absence of direct S-D links, the proposed protocols can achieve a multiplexing gain close to one, whereas the traditional two-hop scheme only achieves a diversity gain of 1/2. In the presence of direct S-D links, the proposed protocol can still outperform the comparable scheme, particularly at high multiplexing gains. Regarding to the channel state information (CSI) assumptions, in the absence of direct S-D links, the source does not need to know CSI, but it is assumed that the relays have access to their own incoming and outgoing channel information. In the presence of direct S-D links, the use of precoding requires an extra assumption that the global CSI is available at the source.

BitTorrent, the immensely popular file swarming system, suffers a fundamental problem: unavailability. Although swarming scales well to tolerate flash crowds for popular content, it is less useful for unpopular or rare files as peers arriving after the initial rush find the content unavailable.

We introduce a measurement-based optimization framework for topology control in dense 802.11 networks using sectorized antennas. We first formulate a topology control optimization problem, where nodes activate their sectorized antenna patterns to minimize network interference and maximize network capacity. In contrast to previous approaches, our formulation is based on a physical interference model that relies on received signal strength (RSS) measurements on multiple antenna patterns of each link. We then introduce a distributed measurement protocol to measure RSS of these antenna patterns and a greedy distributed topology control protocol that uses this information to achieve topologies of minimal interference. The protocols are experimentally evaluated on a dense 802.11 wireless testbed. Extensive measurements show that the protocols operate very close to optimal and yield significant increase in network throughput compared to omni-directional antennas. These results hold for various traffic scenarios in both wireless LAN and mesh network configurations.

In this paper, we propose a novel spectrally efficient cooperative transmission protocol for multiple access scenarios. Different to some existing cooperative multiple access schemes, the proposed scheme can exploit the availability of relays as an extra dimension to increase reception robustness. By carefully scheduling the multiple sources and relays' transmission, a source with a poor connection to the destination can have higher priority to obtain better help from relays. As a result, the full diversity gain can be achievable for each user although only a fraction of the all relays is scheduled to help him. An achievable diversity-multiplexing tradeoff (DMT) is developed for the proposed transmission protocol to assist performance evaluation. With a large number of relays, the DMT achieved by the proposed scheme can approximate the optimal multiple-input single-input upper bound. Both analytical and numerical results show that the proposed protocol can outperform comparative schemes in most conditions.

Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical {\em Coupon Collector's Problem}. Consequently, we show that each node discovers all its $n$ neighbors in an expected time equal to $ne (\ln n + c)$, for some constant $c$. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a $\ln n$ improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing $n$ results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.

The one tutorial and 22 papers in this special issue focus on geometry and random graph for the analysis and design of wireless networks. The papers are organized into five groups: Topology; Outage, throughput, capacity, and scaling laws; Connectivity and coverage; Co-existence of disparate wireless networks and cognitive radio; and Distributed algorithms.

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales with an increasing number of nodes n as lambda(n) = ominus(1/radic(n log n)), thus indicating that performance does not scale well. However, Gupta and Kumar did not consider network coding and wireless broadcasting, which recent works suggest have the potential to significantly improve throughput. Here, we establish bounds on the improvement provided by such techniques. For random networks of any dimension under either the protocol or physical model that were introduced by Gupta and Kumar, we show that network coding and broadcasting lead to at most a constant factor improvement in per node throughput. For the protocol model, we provide bounds on this factor. We also establish bounds on the throughput benefit of network coding and broadcasting for multiple source multicast in random networks. Finally, for an arbitrary network deployment, we show that the coding benefit ratio is at most O(log n) for both the protocol and physical communication models. These results give guidance on the application space of network coding, and, more generally, indicate the difficulty in improving the scaling behavior of wireless networks without modification of the physical layer.

Extensive research has demonstrated the potential improvement in physical layer performance when multiple radios transmit concurrently in the same radio channel. We consider how such cooperation affects the requirements for full connectivity and percolation in large wireless ad hoc networks. Both noncoherent and coherent cooperative transmission are considered. For one-dimensional (1-D) extended networks, in contrast to noncooperative networks, for any path loss exponent less than or equal to one, full connectivity occurs under the noncoherent cooperation model with probability one for any node density. Conversely, there is no full connectivity with probability one when the path loss exponent exceeds one, and the network does not percolate for any node density if the path loss exponent exceeds two. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any path loss exponent less than or equal to two, full connectivity is achieved for any node density. Conversely, there is no full connectivity when the path loss exponent exceeds two, but the cooperative network percolates for node densities above a threshold which is strictly less than that of the noncooperative network. A less conclusive set of results is presented for the coherent case. Hence, even relatively simple noncoherent cooperation improves the connectivity of large ad hoc networks.

This paper explores the use of rate adaptation in cellular networks to maximize throughput of long-lived TCP sessions. We focus on the problem of maximizing the throughput of TCP connections and propose a joint optimization of MAC and physical layer parameters with respect to TCP sending rate. In particular, we propose a simple TCP-aware channel scheduler that adapts the wireless channel rate to changes in the TCP sending rate and explore its performance for both single and multiple concurrent sessions. In the case of a single TCP session, we develop a fluid model of its steady-state behavior in such a system that adapts between two channel rates. Our results indicate that a two-rate scheme improves TCP throughput by 15% to 20% over a system that does not exploit rate adaptation and that little additional benefit accrues from the addition of a third channel rate. Finally, we extend the framework to scenarios where bandwidth is shared by multiple TCP sessions. We propose two channel allocation algorithms and explore their performance through simulation. Our results indicate that TCP throughput is relatively insensitive to either channel allocation algorithm and adaptive rate variation is the dominant factor in performance.

In this paper, we propose two online algorithms to detect 802.11 traffic from packet-header data collected passively at a monitoring point. These algorithms have a number of applications in real-time wireless LAN management, for instance, in detecting unauthorized access points and detecting/predicting performance degradations. Both algorithms use sequential hypothesis tests and exploit fundamental properties of the 802.11 CSMA/CA MAC protocol and the half-duplex nature of wireless channels. They differ in that one requires training sets, while the other does not. We have built a system for online wireless traffic detection using these algorithms and deployed it at a university gateway router. Extensive experiments have demonstrated the effectiveness of our approach: the algorithm that requires training provides rapid detection and is extremely accurate (the detection is mostly within 10 seconds, with very low false-positive and false-negative ratios), the algorithm that does not require training detects 60 percent to 76 percent of the wireless hosts without any false positives, and both algorithms are lightweight, with computation and storage overhead well within the capability of commodity equipment.

Motivated by the wide use of TCP for multimedia streaming in practice and the increasing availability of multipath between end hosts, we study multipath live streaming via TCP in this article. We first design a simple and practical TCP-based multipath streaming scheme, named Dynamic MPath-streaming (DMP-streaming) , which dynamically distributes packets over multiple paths by implicitly inferring the available bandwidths on these paths. To allow systematic performance study, we develop an analytical model for DMP-streaming and validate the model using extensive ns simulation and Internet experiments. We explore the parameter space of this model and find that DMP-streaming generally provides satisfactory performance when the aggregate achievable TCP throughput is 1.6 times the video bitrate, when allowing a few seconds of startup delay. Last, we comment on the benefits of using multipath versus single path for TCP-based streaming.

Recently proposed physical-layer network coding (PNC) has demonstrated the promise to significantly improve the throughput of wireless networks whose links can be modeled as additive white Gaussian noise (AWGN) channels. However, the extension to multipath channels is problematic, since the technique would then require both amplitude and phase compensation at each transmitter. Phase compensation requires accurate distributed phase tracking, whereas the required amplitude compensation is even more troubling, as it leads to an inefficient system that yields no diversity even in the presence of perfect channel estimates. Here, a system that avoids these limitations is obtained by reaching up one level higher in the network hierarchy and performing distributed relay selection with cognizance of the PNC technique that we will employ at the physical layer. Since the resulting scheme will achieve a form of selection diversity, we term it ldquonetwork coding with diversityrdquo (NCD). To facilitate performance evaluation, two information-theoretic metrics, the outage and ergodic capacity, are studied. Our analytical and simulation results show that the proposed protocol achieves more robust performance and higher system throughput than comparable schemes. Finally, the proposed network coding is extended to the context of cooperative multiple access channels, which yields a new cooperative protocol with larger outage and ergodic capacity compared with existing transmission schemes.

The histogram of network flow sizes is an important yet difficult metric to estimate in network monitoring. It is important because it characterizes traffic compositions and is a crucial component of anomaly detection methods. It is difficult to estimate because of its high memory and computational requirements. Existing algorithms compute fine grained estimates for each flow size, i.e. 1, 2,... up to the maximum number observed over a finite time interval. Our approach instead relies on the insight that, while many applications require fine grained estimates of small flow sizes, i.e. {1,2,...,k} with a small k, network operators are often only interested in coarse grained estimates of larger flow sizes. Thus, we propose an estimator that outputs a binned histogram of size distributions. Our estimator computes this histogram in O(k3 + log W) operations, where W is the largest flow size of interest to the network operator, while requiring only a few bits of memory per measured flow. This translates into more than 4 fold memory savings and an exponential speedup in the estimator as compared to previous works, greatly increasing the possibility of performing on-line estimation inside a router.

The capacity gain of network coding has been extensively studied in wired and wireless networks. Recently, it has been shown that network coding improves network reliability by reducing the number of packet retransmissions in lossy networks. However, the extent of the reliability benefit of network coding is not known. This paper quantifies the reliability gain of network coding for reliable multicasting in wireless networks, where network coding is most promising. We define the expected number of transmissions per packet as the performance metric for reliability and derive analytical expressions characterizing the performance of network coding. We also analyze the performance of reliability mechanisms based on rateless codes and automatic repeat request (ARQ), and compare them with network coding. We first study network coding performance in an access point model, where an access point broadcasts packets to a group of K receivers over lossy wireless channels. We show that the expected number of transmissions using ARQ, compared to network coding, scales as ominus (log K) as the number of receivers becomes large. We then use the access point model as a building block to study reliable multicast in a tree topology. In addition to scaling results, we derive expressions for the expected number of transmissions for finite multicast groups as well. Our results show that network coding significantly reduces the number of retransmissions in lossy networks compared to an ARQ scheme. However, rateless coding achieves asymptotic performance results similar to that of network coding.

Recent advances in computer technology and wireless communications have enabled the emergence of stream-based sensor networks. In such sensor networks, real-time data are generated by a large number of distributed sources. Queries are made that may require sophisticated processing and filtering of the data. A query is represented by a query graph. In order to reduce the data transmission and to better utilize resources, it is desirable to place operators of the query graph inside the network, and thus to perform in-network processing. Moreover, given that various queries occur with different frequencies and that only a subset of sensor data may actually be queried, caching intermediate data objects inside the network can help improve query efficiency. In this paper, we consider the problem of placing both operators and intermediate data objects inside the network for a set of queries so as to minimize the total cost of storage, computation, and data transmission. We propose distributed algorithms that achieve optimal solutions for tree-structured query graph topologies and general network topologies. The algorithms converge in Lmax(.HQ+ 1) iterations, where Lmaxis the order of the diameter of the sensor network, and Hq represents the depth of the query graph, defined as the maximum number of operations needed for a raw data to become a final data. For a regular grid network and complete binary tree query graph, the complexity is 0(radic(N)log2M), where N is the number of nodes in the sensor network and M is the number of data objects in a query graph. The most attractive features of these algorithms are that they require only information exchanges between neighbors, can be executed asynchronously, are adaptive to cost change and topology change, and are resilient to node or link failures.

We study scalable, distributed, and adaptive routing algorithms for communication networks. The back-pressure algorithm introduced in [21] is a well-known distributed and adaptive routing/scheduling algorithm where nodes only need the queue length information of neighboring nodes to make routing decisions, and packets are adaptively routed in the network according to congestion information, which makes the algorithm resilient to traffic and topology changes. However, the back-pressure algorithm requires routers to maintain a separate queue for each destination, which prevents its implementation in large-scale networks like the Internet. In this paper, we propose a cluster-based back-pressure routing algorithm, which retains the distributability and adaptability of back-pressure routing, while significantly reducing the number of queues that have to be maintained at each node. Since the cluster-based algorithm performs adaptive load-balancing in the network, it has the potential to eliminate the need for off-line traffic engineering in the Internet.

This paper studies the scaling laws of the data gathering capacity of large scale multihop wireless networks. Unlike the data communication paradigms studied in previous research, for example, the many-to-many, many-to-one, broadcast, and multicast paradigms, the data gathering capacity concerns the per source node throughput in a network where a subset of nodes send data to some designated destinations while other nodes serve as relays. This some-to-some communication paradigm is commonplace in many wireless networks, for example, wireless mesh networks and wireless sensor networks, and in some cases perhaps more prevalent than the other paradigms. We first derive the upper and constructive lower bounds for the data gathering capacity, and then examine their design and performance implications. Our results show that the data gathering capacity is constrained by different factors in several different scaling regimes of the number of source and destination nodes, exhibiting distinct scaling laws in those regimes. This work fills a gap in our understanding of the capacity of various communication paradigms, and can lead to better network planning and performance for data gathering wireless network applications.

Networks composed of mobile nodes inherently suffer from intermittent connections and high delays. Performance can be improved by adding supporting infrastructure, including base stations, meshes, and relays, but the cost-performance trade-offs of different designs is poorly understood. To examine these trade-offs, we have deployed a large-scale vehicular network and three infrastructure enhancement alternatives. The results of these deployments demonstrate some of the advantages of each kind of infrastructure; however, these conclusions can be applied only to other networks of similar characteristics, including size, wireless technologies, and mobility patterns. Thus we complement our deployment with a demonstrably accurate analytical model of large-scale networks in the presence of infrastructure. Based on our deployment and analysis, we make several fundamental observations about infrastructure-enhanced mobile networks. First, if the average packet delivery delay in a vehicular deployment can be reduced by a factor of two by adding x base stations, the same reduction requires 2x mesh nodes or 5x relays. Given the high cost of deploying base stations, relays or mesh nodes can be a more cost-effective enhancement. Second, we observe that adding small amount of infrastructure is vastly superior to even a large number of mobile nodes capable of routing to one another, obviating the need for mobile-to-mobile disruption tolerant routing schemes.

Connectivity and capacity are two measures for the performance of mobile ad hoc networks that have been studied extensively under standard point-to-point physical layer assumptions. However, extensive recent research at the physical layer has demonstrated the improvement in performance possible when multiple radios concurrently transmit in the same radio channel. In this paper, we consider how such physical layer cooperation improves the connectivity in wireless ad hoc networks. In particular, with noncoherent cooperation at the physical layer, we consider conditions on the node density λ (or, equivalently, the transmit power) for full connectivity and percolation for large networks in various dimensions and with various path loss exponents α. For one-dimensional (1-D) extended networks, in sharp contrast to noncooperative networks, we demonstrate that full connectivity can be realized under certain conditions. In particular, for any node density with path loss exponent α < 1, or for node density λ > 2 when α = 1, full connectivity occurs with probability one. Conversely, we demonstrate that, under noncoherent cooperation, there is no full connectivity with probability one when α < 1. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any node density with α < 2, or for node density λ Ū 5 when α = 2, full connectivity is achieved. Conversely, there is no full connectivity with probability one when α > 2, but we prove that, for α ≥ 4, the percolation threshold of the noncoherent cooperative network is strictly less than that of the noncooperative network. Analogous results are presented for dense networks. Hence, the main conclusion is that even relatively simple physical layer cooperation in the form of noncoherent power summing can substantially improve the connectivity of large ad hoc networks.

The current Internet consists of ten to twenty thousand different interconnected autonomous networks. In many cases these networks have negotiated cumbersome bilateral and multilateral agreements that constrain how data is allowed to flow from source to destination. For example, universities can communicate with each other through the Abilene network but must rely on other networks to communicate with non-academic entities such as Google. These agreements generally impose a loose hierarchy on the Internet with respect to the flow of data and information. The recent development of peer-to-peer file sharing technology, however, has the unintended effect of relaxing and voiding these agreements. This has resulted in a "flattening" of the Internet. In this talk we review the introduction of peer-to-peer (p2p) technology and examine the implications that it may have on the Internet over the next ten years. In particular, we examine the effects of p2p on economics for Internet service providers (ISPs), and the impact on how they manage and engineer their networks. We focus on one p2p technology, "swarming," as exemplified by BitTorrent, and examine how it could further flatten the Internet if it were to become the basis of a "universal swarm" and form the basis of a new data transfer architecture over the next ten years. Last, we present a research agenda centered on swarm technology to make this happen. We will focus in particular on interesting theoretical and algorithmic challenges that will arise with such an architecture.

This paper investigates the benefit of network coding for TCP traffic in a wireless mesh network. We implement network coding in a real 802.11a wireless mesh network and measure TCP throughput in such a network. Unlike previous implementations of network coding in mesh networks, we use off-the-shelf hardware and software and do not modify TCP or the underlying MAC protocol. Therefore, our implementation can be easily exported to any operational wireless mesh network with minimal modifications. Furthermore, the TCP throughput improvement reported in this paper is due solely to network coding and is orthogonal to other improvements that can be achieved by optimizing other system components such as the MAC protocol. We conduct extensive measurements to understand the relation between TCP throughput and network coding in different mesh topologies. We show that network coding not only reduces the number of transmissions by sending multiple packets via a single transmission but also results in a smaller loss probability due to reduced contention on the wireless medium. Unfortunately, due to asynchronous packet transmissions, there is often little opportunity to code resulting in small throughput gains. Coding opportunity can be increased by inducing small delays at intermediate nodes. However, this extra delay at intermediate nodes results in longer round-trip-times that adversely affect TCP throughput. Through experimentation, we find a delay in the range of 1 ms to 2 ms to maximize TCP throughput. For the topologies considered in this paper, network coding improves TCP throughput by 10% to 85%.

This talk overviews some of the highlights and success stories in the mathematical modeling and analysis of the Internet (and other networks). We will begin with Kleinrock's seminal work on modeling store and forward networks and its extensions, and end with the successful development of fluid models for the current Internet. The rest of the talk will focus on lessons learned from these endeavors and how modeling and analysis can and will play a role in the development of new networks (e.g., wireless networks, application-level networks). Finally, we conclude that one can have fun modeling networks while at the same time make a living.

We propose two unstructured file sharing games, unilateral and bilateral unstructured file sharing games, to study the interaction among self-interested players (users) of unstructured P2P file sharing applications. In a unilateral unstructured file sharing game, players compete for network resources (link bandwidth) by opening multiple connections to each other on multiple paths so as to maximize their individual benefits. A player always allows other players to connect to itself. Multiple concurrent connections are allowed on any path between a pair of players. Per-connection throughput is determined by the transport protocol implemented by users' computers. In a bilateral unstructured file sharing game, users adopt a Tit-for-Tat strategy, under which an active connection between two players is set up only when they both find it beneficial. Two players can set up at most one connection between themselves and bottlenecks occur only at upstream access links in a star network. For both games, we prove the existence of an equilibrium, quantify the efficiency losses of equilibria, and demonstrate the dynamic stability of equilibria in best-response or better-response dynamic game playing processes.

We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual's network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in networks, based on the knowledge used by the adversary. We show that the risks of these attacks vary greatly based on network structure and size. We propose a novel approach to anonymizing network data that models aggregate network structure and then allows samples to be drawn from that model. The approach guarantees anonymity for network entities while preserving the ability to estimate a wide variety of network measures with relatively little bias.

TCP is widely used in commercial multimedia streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored-media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

Motivated by the wide use of TCP for streaming in practice and the increasing availability of multipath between end hosts, we study multipath live streaming via TCP in this paper. We first design a simple and practical TCP-based multipath streaming scheme, named Dynamic MPath-streaming (DMP-streaming), which dynamically distributes packets over multiple paths by implicitly inferring the available bandwidths on these paths. To allow systematic performance study, we develop an analytical model for DMP-streaming and validate the model using extensive ns simulation and Internet experiments. We explore the parameter space of this model and find that DMP-streaming generally provides satisfactory performance when the aggregate achievable TCP throughput is 1.6 times the video bitrate, with a few seconds of startup delay. Last, we comment on the benefits of using multipath versus single path for TCP-based streaming.

Combining transport-layer congestion control with multi-path routing is a cross-layer approach that provides performance benefits over treating the layers separately. We phrase this as an optimisation problem, examine the case of data transfers, and show how a coordinated controller gives strictly better performance than an uncoordinated controller, which sets up parallel paths. For fixed demands, and the case of random-path selection, we show how coordinated control also achieves better load balancing than greedy least-loaded path selection. We then comment on adaptive path selection.

A fundamental problem in a large scale decentralized stream processing system is how to best utilize the available resources and admission control the bursty and high volume input streams so as to optimize overall system performance. We consider a distributed stream processing system consisting of a network of servers with heterogeneous capabilities that collectively provide processing services to multiple data streams. Our goal is to design a joint source admission control, data routing, and resource allocation mechanism that maximizes the overall system utility. Here resources include both link bandwidths and processor resources. The problem is formulated as a utility optimization problem. We describe an extended graph representation that unifies both types of resources seamlessly and present a novel scheme that transforms the admission control problem to a routing problem by introducing dummy nodes at sources. We then present a distributed gradient-based algorithm that iteratively updates the local resource allocation based on link data rates. We show that our algorithm guarantees optimality and demonstrate its performance through simulation.

Rogue (unauthorized) wireless access points pose serious security threats to local networks. In this paper, we propose two online algorithms to detect rogue access points using sequential hypothesis tests applied to packet-header data collected passively at a monitoring point. One algorithm requires training sets, while the other does not. Both algorithms extend our earlier TCP ACK-pair technique to differentiate wired and wireless LAN TCP traffic, and exploit the fundamental properties of the 802.11 CSMA/CA MAC protocol and the half duplex nature of wireless channels. Our algorithms make prompt decisions as TCP ACK-pairs are observed, and only incur minimum computation and storage overhead. We have built a system for online rogue-access-point detection using these algorithms and deployed it at a university gateway router. Extensive experiments in various scenarios have demonstrated the excellent performance of our approach: the algorithm that requires training provides rapid detection and is extremely accurate (the detection is mostly within 10 seconds, with very low false positive and false negative ratios); the algorithm that does not require training detects 60%-76% of the wireless hosts without any false positives; both algorithms are light-weight (with computation and storage overhead well within the capability of commodity equipment).

There is growing interest in designing high speed routers with small buffers that store only tens of packets. Recent studies suggest that TCP NewReno, with the addition of a pacing mechanism, can interact with such routers without sacrificing link utilization. Unfortunately, as we show in this paper, as workload requirements grow and connection bandwidths increase, the interaction between the congestion control protocol and small buffer routers produce link utilizations that tend to zero. This is a simple consequence of the inverse square root dependence of TCP throughput on loss probability. In this paper we present a new congestion controller that avoids this problem by allowing a TCP connection to achieve arbitrarily large bandwidths without demanding the loss probability go to zero. We show that this controller produces stable behavior and, through simulation, we show its performance to be superior to TCP NewReno in a variety of environments. Lastly, because of its advantages in high bandwidth environments, we compare our controller's performance to some of the recently proposed high performance versions of TCP including HSTCP, STCP, and FAST. Simulations illustrate the superior performance of the proposed controller in a small buffer environment.

In this paper we investigate the potential benefits of coordinated congestion control for multipath data transfers, and contrast with uncoordinated control. For static random path selections, we show the worst-case throughput performance of uncoordinated control behaves as if each user had but a single path (scaling like log(log(N))/log(N) whereNis the system size, measured in number of resources). Whereas coordinated control gives a throughput allocation bounded away from zero, improving on both uncoordinated control and on the greedy-least loaded path selection of e.g. Mitzenmacher. We then allow users to change their set of routes and introduce the notion of a Nash equilibrium. We show that with RTT bias (as in TCP Reno), uncoordinated control can lead to inefficient equilibria. With no RTT bias, both uncoordinated or coordinated Nash equilibria correspond to desirable welfare maximising states. Moreover, simple path reselection polices that shift to paths with higher net benefit can find these states.

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales (poorly) as lambda(n) = Theta (1 / radic(n log n)) with an increasing number of nodes n. However, Gupta and Kumar did not consider the possibility of network coding and broadcasting in their model, and recent work has suggested that such techniques have the potential to greatly improve network throughput. In [1], we have shown that for the protocol communication model of Gupta and Kumar [2], the multi-unicast throughput of schemes using arbitrary network coding and broadcasting in a two-dimensional random topology also scales as lambda(n) = Theta (1 / radic(n log n))1, thus showing that network coding provides no order difference improvement on throughput. Of course, in practice the constant factor of improvement is important; thus, here we derive bounds for the throughput benefit ratio -the ratio of the throughput of the optimal network coding scheme to the throughput of the optimal non-coding flow scheme. We show that the improvement factor is 1+ Delta / 1+Delta /2for 1D random networks, where Delta > 0 is a parameter of the wireless medium that characterizes the intensity of the interference. We obtain this by giving tight bounds (both upper and lower) on the throughput of the coding and flow schemes. For 2D networks, we obtain an upper bound for the throughput benefit ratio as alpha (n) les 2cDeltaradic(pi = 1+Delta/Delta) for large n, wnere cDelta= max {2, radic(Delta2+ 2Delta)}. This is obtained by finding an upper bound for the coding throughput and a lower bound for the flow throughput. We then consider the more general physical communication model as in Gupta and Kumar. We show that the coding scheme throughput in this case is upper bounded by Theta (1/n) for the 1D random network and by Theta(1/radic(n)) for the 2D case. We also show the flow scheme throughput for the ID case can achieve the same order throughput as the coding scheme. Combined with previous work on a 2D lower bound [3], we conclude that the throughput benefit ratio under the physical model is also bounded by a constant; thus, we have shown for both the protocol and physical model that the coding benefit in terms of throughput is a constant factor. Finally, we evaluate the potential coding gain from another important perspective - total energy efficiency - and show that the factor by which the total energy is decreased is upper bounded by 3.

In this paper, we investigate the problem of highly available, massive-scale file distribution in the Internet. To this end, we conduct a large-scale measurement study of BitTorrent, a popular class of systems that use swarms of actively downloading peers to assist each other in file distribution. The first generation of BitTorrent systems used a central tracker to enable coordination among peers, resulting in low availability due to the tracker's single point of failure. Our study analyzes the prevalence and impact of two recent trends to improve BitTorrent availability: (i) use of multiple trackers, and (ii) use of Distributed Hash Tables (DHTs), both of which also help to balance load better. The study considered more than 1,400 trackers and 24,000 DHT nodes (extracted from about 20,000 torrents) over a period of two months. We find that both trends improve availability, but for different and somewhat unexpected reasons. Our findings include: (i) multiple trackers improve availability, but the improvement largely comes from the choice of a single highly available tracker, (ii) such improvement is reduced by the presence of correlated failures, (iii) multiple trackers can significantly reduce the connectivity of the overlay formed by peers, (iv) the DHT improves information availability, but induces a higher response latency to peer queries.

We study the interaction among users of unstructured file sharing applications, who compete for available network resources (link bandwidth or capacity) by opening multiple connections on multiple paths so as to accelerate data transfer. We model this interaction with an unstructured file sharing game. Users are players and their strategies are the numbers of sessions on available paths. We consider a general bandwidth sharing framework proposed by Kelly [1] and Mo and Walrand [2], with TCP as a special case. Furthermore, we incorporate the Tit-for-Tat strategy (adopted by BitTorrent [3] networks) into the unstructured file sharing game to model the competition in which a connection can be set up only when both users find this connection beneficial. We refer to this as an overlay formation game. We prove the existence of Nash equilibrium in several variants of both games, and quantify the losses of efficiency of Nash equilibria. We find that the loss of efficiency due to selfish behavior is still unbounded even when the Tit-for-Tat strategy is believed to prevent selfish behavior.

We study a joint scheduling and coding problem for collecting multi-snapshots spatial data in a resource constrained sensor network. Motivated by a distributed coding scheme for single snapshot data collection [7], we generalize the scenario to include multi-snapshots and general coding schemes. Associating a utility function with the recovered data, we aim to maximize the expected utility gain through joint coding and scheduling.

We study traces taken from UMass DieselNet, a Disruption-Tolerant Network consisting of WiFi nodes attached to buses. As buses travel their routes, they encounter other buses and in some cases are able to establish pair-wise connections and transfer data between them. We analyze the bus-to-bus contact traces to characterize the contact process between buses and its impact on DTN routing performance. We find that the all-bus-pairs aggregated inter-contact times show no discernible pattern. However, the inter-contact times aggregated at a route level exhibit periodic behavior.Based on analysis of the deterministic inter-meeting times for bus pairs running on route pairs, and consideration of the variability in bus movement and the random failures to establish connections, we construct generative route-level models that capture the above behavior. Through trace-driven simulations of epidemic routing, we find that the epidemic performance predicted by traces generated with this finer-grained route-level model is much closer to the actual performance that would be realized in the operational system than traces generated using the coarse-grained all-bus-pairs aggregated model. This suggests the importance in choosing the rightlevel of model granularity when modelingmobility-related measures such as inter-contact times in DTNs.

In this paper we study the capacity of wireless ad hoc networks with infrastructure support of an overlay of wired base stations. Such a network architecture is often referred to as hybrid wireless network or multihop cellular network. Previous studies on this topic are all focused on the twodimensional disk model proposed by Gupta and Kumar in their original work on the capacity of wireless ad hoc networks. We further consider a one-dimensional network model and a two-dimensional strip model to investigate the impact of network dimensionality and geometry on the capacity of such networks. Our results show that different network dimensions lead to significantly different capacity scaling laws. Specifically, for a one-dimensional network of n nodes and b base stations, even with a small number of base stations, the gain in capacity is substantial, increasing linearly with the number of base stations as long as b log b ≤ n. However, a two-dimensional square (or disk) network requires a large number of base stations b = Ω ( √ n) before we see such a capacity increase. For a 2-dimensional strip network, if the width of the strip is at least on the order of the logarithmic of its length, the capacity follows the same scaling law as in the 2-dimensional square case. Otherwise the capacity exhibits the same scaling behavior as in the 1-dimensional network. We find that the different capacity scaling behaviors are attributed to the percolation properties of the respective network models.

No abstract available.

This paper investigates how the through put of a general fork-join queueing network with blocking behaves as the number of nodes increases to infinity while the processing speed and buffer space of each node stay unchanged. The problem is motivated by applications arising from distributed systems and computer networks. One example is large-scale distributed stream processing systems where TCP is used as the transport protocol for data transfer in between processing components. Other examples include reliable multicast in overlay networks, and reliable data transfer in ad hoc networks. Using an analytical approach, the paper establishes bounds on the asymptotic throughput of such a network. For a subclass of networks which are balanced, we obtain sufficient conditions under which the network stays scalable in the sense that the throughput is lower bounded by a positive constant as the network size increases. Necessary conditions of throughput scalability are derived for general networks. The special class of series-parallel networks is then studied in greater detail, where the asymptotic behavior of the throughput is characterized.

We propose Push-to-Peer, a peer-to-peer system to cooperatively stream video. The main departure from previous work is that content is proactively pushed to peers, and persistently stored before the actual peer-to-peer transfers. The initial content placement increases content availability and improves the use of peer uplink bandwidth. Our specific contributions are: (i) content placement and associated pull policies that allow the optimal use of uplink bandwidth; (ii) performance analysis of such policies in controlled environments such as DSL networks under ISP control; (iii) a distributed load balancing strategy for selection of serving peers.

As many people rely on e-mail communications for business and everyday life, Internet e-mail worms constitute one of the major security threats for our society. Unlike scanning worms such as Code Red or Slammer, e-mail worms spread over a logical network defined by e-mail address relationships, making traditional epidemic models invalid for modeling the propagation of e-mail worms. In addition, we show that the topological epidemic models presented by M. Boguna, et al. (2000) largely overestimate epidemic spreading speed in topological networks due to their implicit homogeneous mixing assumption. For this reason, we rely on simulations to study e-mail worm propagation in this paper. We present an e-mail worm simulation model that accounts for the behaviors of e-mail users, including e-mail checking time and the probability of opening an e-mail attachment. Our observations of e-mail lists suggest that an Internet e-mail network follows a heavy-tailed distribution in terms of node degrees, and we model it as a power-law network. To study the topological impact, we compare e-mail worm propagation on power-law topology with worm propagation on two other topologies: small-world topology and random-graph topology. The impact of the power-law topology on the spread of e-mail worms is mixed: E-mail worms spread more quickly on a power-law topology than on a small-world topology or a random-graph topology, but immunization defense is more effective on a power-law topology.

In many energy-rechargeable wireless sensor networks, sensor nodes must both sense data from the environment, and cooperatively forward sensed data to data sinks. Both data sensing and data forwarding (including data transmission and reception) consume energy at sensor nodes. We present a distributed algorithm for optimal joint allocation of energy between sensing and communication at each node to maximize overall system utility (i.e., the aggregate amount of information received at the data sinks). We consider this problem in the context of wireless sensor networks with directional, non-steerable antennas. We first formulate a joint data-sensing and data-routing optimization problem with both per-node energy-expenditure constraints, and traditional flow routing/conservation constraints. We then simplify this problem by converting it to an equivalent routing problem, and present a distributed gradient-based algorithm that iteratively adjusts the per-node amount of energy allocated between sensing and communication to reach the system-wide optimum. We prove that our algorithm converges to the maximum system utility. We quantitatively demonstrate the energy balance achieved by this algorithm in a network of small, energy-constrained X-band radars, connected via point- to-point 802.11 links with non-steerable directional antennas.

Packet sampling is widely used in network monitoring. Sampled packet streams are often used to determine flow-level statistics of network traffic. To date there is conflicting evidence on the quality of the resulting estimates. In this paper we take a systematic approach, using the Fisher information metric and the Cramér-Rao bound, to understand the contributions that different types of information within sampled packets have on the quality of flow-level estimates. We provide concrete evidence that, without protocol information and with packet sampling rate p = 0.005, any accurate unbiased estimator needs approximately 1016 sampled flows. The required number of sampled flows drops to roughly 104 with the use of TCP sequence numbers. Furthermore, additional SYN flag information significantly reduces the estimation error of short flows. We present a Maximum Likelihood Estimator (MLE) that relies on all of this information and show that it is efficient, even when applied to a small sample set. We validate our results using Tier-1 Internet backbone traces and evaluate the benefits of sampling from multiple monitors. Our results show that combining estimates from several monitors is 50% less accurate than an estimate based on all samples.

Abstract — Verifying the accuracy of a passive measurementsbased inference technique under all possible network scenarios is a difficult challenge- the measurement point has limited observability of events along the path, and monitored paths can exhibit a wide range of network properties (packet loss, reordering, end-end delay, route changes). In this paper, we propose and apply formal verification techniques to exhaustively verify the correctness of an inference technique. We apply this approach to the problem of inferring packet retransmissions and reorderings from passively observed packets at a single measurement point. We define classification rules for this inference problem and, through a combination of model-checking and formal reasoning, uncover all possible events in the network for which the rules produce incorrect inferences. Our work is novel in its use of formal verification tools for evaluating inference techniques in network measurements. I.

In the standard approach to studying connectivity, a physical layer is assumed that allows direct transmission between neighbors within some fixed distance. The graph resulting from connecting all such pairs of neighbors reveals clusters of nodes within which communication is possible. However, future wireless networks will provide a physical layer where nodes that are connected can collaboratively search for more connections via simultaneous RF transmission and reception, thus adding connections that are not possible in the traditional non-collaborative model. The purpose of this paper is to introduce this collaborative network model and to characterize its asymptotic connectivity properties for one characterization (noncoherent power summing) of the physical layer collaboration. In the case of sparse ad hoc networks, simulations show that an infinite cluster will emerge in the infinite two-dimensional plane at a node density roughly 20% of that required in non-collaborative ad hoc networks. In the case of dense ad hoc networks, the probability for the event that the network is connected goes to one asymptotically if the transmission area of each node is [4pi(4 log N)alpha/alpha+2(log log N+log 2)2/alpha+2]/N no less than , where N is the number of nodes in the network of unit area and a is the pathless exponent. Hence, significant gains in the asymptotic connectivity properties of the ad hoc network are obtained through collaboration.

2706-2717

2517-2527

2443-2454

2824-2835

TCP is the dominant transport protocol over both wired and wireless links. It is however, well known that TCP is not suitable for wireless networks and several solutions have been proposed to rectify this shortcoming. In this work, we explore cross-layer optimization of the rate adaptation feature of cellular networks to optimize throughput of a single long-lived TCP session. Modern cellular networks rate RF technology that allows them to dynamically vary the wireless channel rate in response to user demand and channel conditions. However, the set of data rates as well as the scheduler's rate adaptation policy are typically chosen to optimize throughput for inelastic applications. In order to optimize such a system for TCP, we propose a two state TCP-aware scheduler that switches between two chanrates as a function of the TCP sending rate. We develop a fluid model of the steady-state behavior of a TCP session in such a system and derive analytical expressions for TCP throughput that explicitly account for rate variability as well as the dependency between the scheduler and TCP. Using the model we choose RF layer parameters that, in conjunction with the TCP-aware scheduler, improve term throughput of a single TCP flow by 15.25%. We also compare our analytical results against those obtained from ns-2 simulations and confirm that our model indeed closely approximates TCP behavior in such an environment.

In many energy-constrained wireless sensor networks, nodes cooperatively forward correlated sensed data to data sinks. In order to reduce the communication cost (e.g. overall en-ergy) used for data collection, previous works have focused on specific coding schemes, such as Slepian-Wolf Code or Explicit Entropy Code. However, the minimum communi-cation cost under arbitrary coding/routing schemes has not yet been characterized. In this paper, we consider the prob-lem of minimizing the total communication cost of a wireless sensor network with a single sink. We prove that the min-imum communication cost can be achieved using Slepian-Wolf Code and Commodity Flow Routing when the link communication cost is a convex function of link data rate. Furthermore, we find it useful to introduce a new metric

In defending against various network attacks, such as distributed denial-of-service (DDoS) attacks or worm attacks, a defense system needs to deal with various network conditions and dynamically changing attacks. Therefore, a good defense system needs to have a built-in "adaptive defense" functionality based on cost minimization-adaptively adjusting its configurations according to the network condition and attack severity in order to minimize the combined cost introduced by false positives (misidentify normal traffic as attack) and false negatives (misidentify attack traffic as normal) at any time. In this way, the adaptive defense system can generate fewer false alarms in normal situations or under light attacks with relaxed defense configurations, while protecting a network or a server more vigorously under severe attacks. In this paper, we present concrete adaptive defense system designs for defending against two major network attacks: SYN flood DDoS attack and Internet worm infection. The adaptive defense is a high-level system design that can be built on various underlying nonadaptive detection and filtering algorithms, which makes it applicable for a wide range of security defenses

Network performance tomography involves correlating end-to-end performance measures over different network paths to infer the performance characteristics on their intersection. Multicast based inference of link-loss rates is the first paradigm for the approach. Existing algorithms generally require numerical solution of polynomial equations for a maximum-likelihood estimator (MLE), or iteration when applying the expectation maximization (EM) algorithm. The purpose of this note is to demonstrate a new estimator for link-loss rates that is computationally simple, being an explicit function of the measurements, and that has the same asymptotic variance as the MLE, to first order in the link-loss rates.

In the publish/subscribe paradigm, information is disseminated from publishers to subscribers that are interested in receiving the information. In practice, information dissemination is often restricted by policy constraints due to concerns such as security or confidentiality agreement. Meanwhile, to avoid overwhelming subscribers by the vast amount of primitive information, primitive pieces of information can be combined at so-called brokers in the network, a process called composition. Information composition provides subscribers the desirable ability to express interests in an efficiently selective way. In this paper, we formulate the min-cost event distribution problem in pub/sub systems with policy constraints and information composition. Our goal is to minimize the total cost of event transmission while satisfying policy constraints and enabling information composition. This optimization problem is shown to be NP-complete. Our simulation study shows that our heuristics work efficiently, especially in a policy-constrained system. We also find that by increasing the number of broker nodes in a pub/sub system, we are able to reduce the total cost of event delivery.

Peer-to-peer (P2P) anonymous communication systems are vulnerable to free-riders, peers that use the system while providing little or no service to others and whose presence limits the strength of anonymity as well as the efficiency of the system. Free-riding can be addressed by building explicit incentive mechanisms into system protocols to promote two distinct aspects of cooperation among peers-compliance with the protocol specification and the availability of peers to serve others. In this paper we study the use of payments to implement an incentive mechanism that attaches a real monetary cost to low availability. Through a game theoretic analysis, we evaluate the effectiveness of such an incentive, finding that peer availability can be significantly increased through the introduction of payments under many conditions. We also demonstrate how a payment-based incentive that preserves anonymity can be implemented and integrated with a popular class of P2P anonymity systems.

In pricing-based congestion control protocols it is common to assume that the rate of congestion feedback from the network is limited to a single bit per packet. To obtain a precise estimate of available bandwidth (as summarized by the congestion price) under the single-bit constraint, a session must consider feedback contained in a number of recently received packets. As more packets are considered, however, the estimate includes increasingly older information about the network state. We study this tradeoff between the quality and timeliness of feedback using control-theoretic approach, modeling the 'memory' incorporated into the price estimate as additional feedback delay. We show through analysis that obtaining arbitrary precision in the estimated price causes control instability, making it more difficult for a session to track its targeted optimal rate. Through continuous-time simulation of our model and packet-level simulations, we find that crude estimates of congestion price based on very few packets can yield good performance while allowing the session to operate far away from the boundary of instability. We also investigate the impact of estimation bias on protocol performance, showing that protocols use a form of integral control can compensate for biased price estimates.

In this paper, we consider the problem of finding an "efficient" and "robust" set of routes in the face of changing/uncertain traffic. The changes/uncertainty in exogenous traffic is characterized by multiple traffic matrices. Our goal is to find a set of routes that result in good average case performance over the set of traffic matrices, while avoiding bad worst case performance for any single traffic matrix. With multiple traffic matrices, previous work aims solely to optimize the average case performance Chun Zhang, et al., (2005), or the worst case performance David Applegate, et al., (2003). For a given set of traffic matrices, different sets of routes offer a different tradeoff between the average case and the worst case performance. In this paper, we quantify the performance of a routing configuration at both network level and link level. We propose a simple metric-a weighted sum of the average case and the worst case performance-to control the tradeoff between these two considerations. Despite of its simple form, this metric is very effective. We prove that optimizing routing using this metric has desirable properties, such as the average case performance being a decreasing, convex and differentiable function to the worst case performance. By extending previous work Chun Zhang, et al., (2005) Bernard Fortz, et al., (2002), we derive methods to find the optimal routes with respect to the proposed metric for two classes of intra-domain routing protocols: MPLS and OSPF/IS-IS. We evaluate our approach with data collected from an operational tier-I ISP. For MPLS, we find that there exists significant tradeoff (e.g., 15%-23% difference) between optimizing solely on the average case performance and solely on the worst case performance. Our approach can identify solutions that can dramatically improve the worst case performance (13%-15%) while only slightly sacrificing the average case performance (2.2%-3%), in comparison to that by optimizing solely on the average case performance. For OSPF/IS-IS, we still find a significant difference between the two optimization objectives, however, a fine-grained tradeoff is difficult to achieve due to the limited control that OSPF/IS-IS provide.

We present a game-theoretic study of the selfish behavior of TCP users when they are allowed to use multiple concurrent TCP connections so as to maximize their goodputs or other utility functions. We refer to this as the TCP connection game. A central question we ask is whether there is a Nash equilibrium in such a game, and if it exists, whether the network operates efficiently at such a Nash equilibrium. Combined with the well known PFTK TCP model (1998), we study this question for three utility functions that differ in how they capture user behavior. The bad news is that the loss of efficiency or price of anarchy can be arbitrarily large if users have no resource limitations and are not socially responsible. The good news is that, if either of these two factors is considered, efficiency loss is bounded. This may partly explain why there will be no congestion collapse if many users use multiple connections.

Trust negotiation is a process that establishes mutual trust by the exchange of digital credentials and/or guiding policies among entities who may have no pre-existing knowledge about each other. Motivated by the desire to disclose as little sensitive information as possible in practice, this paper investigates the problem of minimizing the "cost" of the credentials exchanged by a trust-negotiation protocol. A credential or a policy is assigned a weighted cost, referred to as its sensitivity cost. We formalize an optimization problem, namely the minimum sensitivity cost problem, whose objective is to minimize the total sensitivity costs of the credentials and policies disclosed during trust negotiation. We study the complexity of the minimal sensitivity cost problem and propose algorithms to solve the problem efficiently, for the cases that policies are cost-sensitive and cost-insensitive. A simple finite state machine model of trust-negotiation protocols is presented to model various trust-negotiation protocols, and to provide a quantitative evaluation of the number of exchange rounds needed to achieve a successful negotiation, and the probability of achieving a successful negotiation under various credential disclosure strategies.

Many network phenomena are well modeled as spreads of epidemics through a network. Prominent examples include the spread of worms and email viruses, and, more generally, faults. Many types of information dissemination can also be modeled as spreads of epidemics. In this paper we address the question of what makes an epidemic either weak or potent. More precisely, we identify topological properties of the graph that determine the persistence of epidemics. In particular, we show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, then the mean epidemic lifetime is of order log n, where n is the number of nodes. Conversely, if this ratio is smaller than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order e/sup na/, for a positive constant a. We apply these results to several network topologies including the hypercube, which is a representative connectivity graph for a distributed hash table, the complete graph, which is an important connectivity graph for BGP, and the power law graph, of which the AS-level Internet graph is a prime example. We also study the star topology and the Erdos-Renyi graph as their epidemic spreading behaviors determine the spreading behavior of power law graphs.

In this paper, we study the interaction between overlay routing and traffic engineering (TE) in a single autonomous system (AS). We formulate this interaction as a two-player non-cooperative non-zero sum game, where the overlay tries to minimize the delay of its traffic and the TE's objective is to minimize network cost. We study a Nash routing game with best-reply dynamics, in which the overlay and TE have equal status, and take turns to compute their optimal strategies based on the response of the other player in the previous round. We prove the existence, uniqueness and global stability of Nash equilibrium point (NEP) for a simple network. For general networks, we show that the selfish behavior of an overlay can cause huge cost increases and oscillations to the whole network. Even worse, we have identified cases, both analytically and experimentally, where the overlay's cost increases as the Nash routing game proceeds even though the overlay plays optimally based on TE's routing at each round. Experiments are performed to verify our analysis.

A number of mobility models have been proposed for the purpose of either analyzing or simulating the movement of users in a mobile wireless network. Two of the more popular are the random waypoint and the random direction models. The random waypoint model is physically appealing but difficult to understand. Although the random direction model is less appealing physically, it is much easier to understand. User speeds are easily calculated, unlike for the waypoint model, and, as we observe, user positions and directions are uniformly distributed. The contribution of this paper is to establish this last property for a rich class of random direction models that allow future movements to depend on past movements. To this end, we consider finite oneand two-dimensional spaces. We consider two variations, the random direction model with wrap around and with reflection. We establish a simple relationship between these two models and, for both, show that positions and directions are uniformly distributed for a class of Markov movement models regardless of initial position. In addition, we establish a sample path property for both models, namely that any piecewise linear movement applied to a user preserves the uniform distribution of position and direction provided that users were initially uniformly throughout the space with equal likelihood of being pointed in any direction.

There is increasing interest in concurrent passive monitoring of IP flows at multiple locations within an IP network. The common objective of such a distributed monitoring system is to sample packets belonging to a large fraction of IP flows in a cost-effective manner by carefully placing monitors and controlling their sampling rates. In this paper, we consider the problem of where to place monitors within the network and how to control their sampling. To address the tradeoff between monitoring cost and monitoring coverage, we consider minimum cost and maximum coverage problems under various budget constraints. We show that all of the defined problems are NP-hard. We propose greedy heuristics, and show that the heuristics provide solutions quite close to the optimal solutions through experiments using synthetic and real network topologies. In addition, our experiments show that a small number of monitors is often enough to monitor most of the traffic in an entire IP network.

The current best-effort Internet cannot readily provide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the quality of VoIP applications, and demonstrate its feasibility through the design and implementation of a prototype gateway. We argue for an application-driven path switching system that accounts for both network path characteristics and application-specific factors (e.g., codec algorithms, playout buffering schemes). We also develop an application path quality estimator based on the ITU-T E-model for voice quality assessment, and an application-driven path switching algorithm that dynamically adapts the time scales over which path switching decisions are made to maximize voice quality. Through network emulation and experiments over a wide-area multi-homed test bed, we show that, with sufficient path diversity, path switching can yield meaningful improvements in voice quality. Hence by exploiting the inherent path diversity of the Internet, application-driven path switching is a viable option in providing quality-of-service to applications.

We consider the problem of neighbor discovery in static wireless ad hoc networks with directional antennas. We propose several probabilistic algorithms in which nodes perform random, independent transmissions to discover their one-hop neighbors. Our neighbor discovery algorithms are classified into two groups, viz. Direct-Discovery Algorithms in which nodes discover their neighbors only upon receiving a transmission from their neighbors and Gossip-based algorithms in which nodes gossip about their neighbors' location information to enable faster discovery. We first consider the operation of these algorithms in a slotted, synchronous system and mathematically derive their optimal parameter settings. We show how to extend these algorithms for an asynchronous system and describe their optimal design. Analysis and simulation of the algorithms show that nodes discover their neighbors much faster using gossip-based algorithms than using direct-discovery algorithms. Furthermore, the performance of gossip-based algorithms is insensitive to an increase in node density. The efficiency of a neighbor discovery algorithm also depends on the choice of antenna beamwidth. We discuss in detail how the choice of beamwidth impacts the performance of the discovery process and provide insights into how nodes can configure their beamwidths.

Ethernet, wireless LAN, ADSL, cable modem and dialup are common access networks, but have dramatically different characteristics. Fast and accurate classification of access network type can improve protocol or application performance significantly. In this paper, we propose a simple and efficient end-end scheme to classify the type of an access network into three categories: Ethernet, wireless LAN and low-bandwidth connection. Our scheme is based on the intrinsic characteristics of the various access networks and utilizes the median and entropy of packet pair inter-arrival times. Extensive experiments show that our scheme obtains accurate classification results in a very short time (10 to 100 seconds).

Routing optimization is used to find a set of routes that minimizes cost (delay, utilization). Previous work has addressed this problem for the case of a known, static end-to-end traffic matrix. In the Internet, it is difficult to accurately estimate a traffic matrix, and the constantly changing nature of Internet traffic makes it costly to maintain optimal routing by responding to traffic changes. Thus, it is of interest to maintain a set of routes that are "good" for a number of different possible traffic scenarios. In this paper, we explore ways to find an optimal set of routes with multiple traffic matrices to minimize expected cost. We focus on two general approaches, source-destination routing and destination routing. In the case of source-destination routing, we extend existing methods with a single traffic matrix to solve the optimization problem with multiple traffic matrices: we extend the convex optimization solution methods for a single traffic matrix to the multiple traffic matrix case; we also extend the gradient-based solution methods for a single traffic matrix to the multiple traffic matrix case. However, the multiple traffic matrix case requires many more control variables. In the case of destination routing, we encounter many more differences from the single traffic matrix case. The loop-free property, which is valid for the single traffic matrix case, is no longer valid for the multiple traffic matrix case, and it is difficult to extend existing methods for a single traffic matrix to solve the optimization problem with multiple traffic matrices. We show that it is NP-complete even to determine the feasibility of multiple traffic matrices. We thus propose and evaluate a heuristic algorithm for this case.

Previous work on the coverage of mobile sensor networks focuses on algorithms to reposition sensors in order to achieve a static configuration with an enlarged covered area. In this paper, we study the dynamic aspects of the coverage of a mobile sensor network that depend on the process of sensor movement. As time goes by, a position is more likely to be covered; targets that might never be detected in a stationary sensor network can now be detected by moving sensors. We characterize the area coverage at specific time instants and during time intervals, as well as the time it takes to detect a randomly located stationary target. Our results show that sensor mobility can be exploited to compensate for the lack of sensors and improve network coverage. For mobile targets, we take a game theoretic approach and derive optimal mobility strategies for sensors and targets from their own perspectives.

When properly constructed, a modular multimedia system can satisfy a client's request in multiple ways by using different sequences of modules and by reusing existing streams within the system. Such flexibility in a multimedia server or proxy can provide a rich set of services to clients while efficiently utilizing system resources by choosing the best way to schedule (i.e. allocate resources for) new clients. However, it is difficult to optimally schedule clients in an online fashion as the problem is NP-complete. In this paper, we provide an efficient online algorithm to schedule client requests using a modular multimedia platform.

In this paper we introduce an innovation in differentiated services architecture consisting of adaptive two-level coloring at the edge and preferential marking at the core. We identify general properties of these two processes which, when met, guarantee a desirable fixed point for the network; i.e., one where aggregated flow rates meet or exceed given targets in an over-provisioned network. Specific mechanisms realizing the aforementioned properties lead to so-called active rate management controllers for edge coloring, and a preferentially-marking, active queue management controller at the core. We discuss stability of the fixed point for this network, and validate results using ns simulations.

After many Internet-scale worm incidents in recent years, it is clear that a simple self-propagating worm can quickly spread across the Internet and cause severe damage to our society. Facing this great security threat, we need to build an early detection system that can detect the presence of a worm in the Internet as quickly as possible in order to give people accurate early warning information and possible reaction time for counteractions. This paper first presents an Internet worm monitoring system. Then, based on the idea of "detecting the trend, not the burst" of monitored illegitimate traffic, we present a "trend detection" methodology to detect a worm at its early propagation stage by using Kalman filter estimation, which is robust to background noise in the monitored data. In addition, for uniform-scan worms such as Code Red, we can effectively predict the overall vulnerable population size, and estimate accurately how many computers are really infected in the global Internet based on the biased monitored data. For monitoring a nonuniform scan worm, especially a sequential-scan worm such as Blaster, we show that it is crucial for the address space covered by the worm monitoring system to be as distributed as possible.

Two approaches have been proposed for application level multicast on content addressable networks (CANs), implemented through tree-based and flooding-based methods. In this paper, we present simple analytical models for studying these two approaches. Using these models, we study the performance achieved by multicast groups as a function of their size, the variability in delays between neighbor nodes and the dimensionality of the underlying CAN. We see that at lower dimensions and lower group sizes the CAN flooding scheme performs better than the tree-based scheme. However as the dimensionality or the CAN increases and the group sizes increase the tree-based scheme performs better. We also propose and study a scheme for reducing delays in the tree based multicast scheme.

Email worms constitute one of the major Internet security problems. We present an email worm model that accounts for the behaviors of email users by considering email checking time and the probability of opening email attachments. Email worms spread over a logical network defined by email address relationship, which plays an important role in determining the spreading dynamics of an email worm. Our observations suggest that the node degrees of an email network are heavy-tailed distributed. We compare email worm propagation on three topologies: power law, small world and random graph topologies; and then study how the topology affects immunization defense on email worms. The impact of the power law topology on the spread of email worms is mixed: email worms spread more quickly on a power law topology than on a small world topology or a random graph topology, but immunization defense is more effective on a power law topology than on the other two.

In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and finds continuing applications in evaluating the representativeness of synthetic topology generators.

This work explores the feasibility of improving the performance of end-to-end data transfers between different sites through path switching. Our study is focused on both the logic that controls path switching decisions and the configurations required to achieve sufficient path diversity. Specifically, we investigate two common approaches offering path diversity multi-homing and overlay networks - and investigate their characteristics in the context of a representative wide-area testbed. We explore the end-to-end delay and loss characteristics of different paths and find that substantial improvements can potentially be achieved by path switching, especially in lowering end-to-end losses. Based on this assessment, we develop a simple path-switching mechanism capable of realizing those performance improvements. Our experimental study demonstrates that substantial performance improvements are indeed achievable using this approach.

Leader election is a very important problem, not only in wired networks, but in mobile, ad hoc networks as well. Existing solutions to leader election do not handle frequent topology changes and dynamic nature of mobile networks. We present a leader election algorithm that is highly adaptive to arbitrary (possibly concurrent) topological changes and is therefore well-suited for use in mobile ad hoc networks. The algorithm is based on finding an extrema and uses diffusing computations for this purpose. We show, using linear-time temporal logic, that the algorithm is "weakly" self-stabilizing and terminating. We also simulate the algorithm in a mobile ad hoc setting. Through our simulation study, we elaborate on several important issues that can significantly impact performance of such a protocol for mobile ad hoc networks such as choice of signaling, broadcast nature of wireless medium etc. Our simulation study shows that our algorithm is quite effective in that each node has a leader approximately 97-99% of the time in a variety of operating conditions.

Fluid models have been shown to he efficient and accurate in modelling large IP networks. However, unlike packet models, it is difficult to extract packet-level information from them. In this paper, we present a hybrid simulation method that maintains the performance advantage of fluid models while providing detailed packet level information for selected packet traffic flows. We propose two models to account for the interaction between background TCP traffic in a fluid network and foreground packet traffic of interest. The first assumes that the packet traffic poses a negligible load on the fluid network whereas the second accounts for the added load by transforming the packet traffic into fluid flows and solving the resulting enhanced fluid model. The first of these yields an efficient one pass solution algorithm whereas the second requires an additional pass to account for the packet traffic load. We establish the correctness of both approaches and present their implementation within ns-2. Comparisons between the hybrid models and a classical packet simulation show the two pass approach to be quite accurate and computationally efficient.

We propose a passive measurement methodology to infer and keep track of the values of two important variables associated with a TCP connection: the sender's congestion window (cwnd) and the connection round trip time (RTT). Together, these variables provide a valuable diagnostic of end-user-perceived network performance. Our methodology is validated via both simulation and concurrent active measurements, and is shown to be able to handle various flavors of TCP. Given our passive approach and measurement points within a Tier-1 network provider, we are able to analyze more than 10 million connections, with senders located in more than 45% of the autonomous systems in today's Internet. Our results indicate that sender throughput is frequently limited by a lack of data to send, that the TCP congestion control flavor often has minimal impact on throughput, and that the vast majority of connections do not experience significant variations in RTT during their lifetime

We study the coverage properties of large-scale sensor networks. Three coverage measures are defined to characterize the fraction of the area covered by sensors (area coverage), the fraction of sensors that can be removed without reducing the covered area (node coverage), and the capability of the sensor network to detect objects moving in the network (detectability), respectively. We approach the coverage problem from a theoretical perspective and explore the fundamental limits of the coverage of a large-scale sensor network. We characterize the asymptotic behavior of the coverage measures for a variety of sensor network scenarios. We find that the coverage of a sensor network exhibits different behaviors for different network configuration and parameters. Based on the analytical characterizations of the network coverage, we further discuss the implications to network planning and protocol performance of sensor networks.

TCP is widely used in commercial media streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

We present the design, implementation, and performance evaluation of AMPS --- a flexible, scalable proxy testbed that supports a wide and extensible set of next-generation proxy streaming services. AMPS employs a modular architecture and is built on top of a commodity Linux system. We study the performance of AMPS proxy using a server-proxy-client configuration in a switched-Gigabit LAN environment. We identify the CPU to be the system bottleneck. Through profiling study, we further identify the kernel network protocol processing and the Network Reception Module inside the proxy to be the most CPU-intensive components. We also quantify the maximum achievable throughput for two of the principal components of the proxy - the control plane and data plane, and characterize the end-to-end performance along the server-to-proxy-to-client path. We discuss lessons learned and the various optimizations made in the course of our study to improve system performance.

No abstract available.

TCP is widely used in commercial media streaming systems, with recent measurement studies indicating that a significant fraction of Internet streaming media is currently delivered over HTTP/TCP. These observations motivate us to develop analytic performance models to systematically investigate the performance of TCP for both live and stored media streaming. We validate our models via ns simulations and experiments conducted over the Internet. Our models provide guidelines indicating the circumstances under which TCP streaming leads to satisfactory performance, showing, for example, that TCP generally provides good streaming performance when the achievable TCP throughput is roughly twice the media bitrate, with only a few seconds of startup delay.

The high-bandwidth requirements and long-lived characteristics of digital video make transmission bandwidth usage a key limiting factor in the widespread streaming of such content over the Internet. A challenging problem is to develop bandwidth-efficient techniques for delivering popular videos to a large, asynchronous client population with time-varying demand characteristics. In this paper, we propose smooth workload adaptive broadcast to address the above issues. A key component of our scheme is Flexible Periodic Broadcast (FPB). By introducing a feedback control loop into FPB, and enhancing FPB using techniques such as parsimonious transmission, smooth workload adaptive broadcast provides instantaneous or near-instantaneous playback services and can smoothly adapt to workload changes. Furthermore, FPB, as proposed in this paper, is bandwidth efficient and exhibits the periodic smooth channel transition property.

We address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as hatching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resulting transmission cost. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in a predominantly unicast environment such as the Internet.

After the Code Red incident in 2001 and the SQL Slammer in January 2003, it is clear that a simple self-propagating worm can quickly spread across the Internet, infects most vulnerable computers before people can take effective countermeasures. The fast spreading nature of worms calls for a worm monitoring and early warning system. In this paper, we propose effective algorithms for early detection of the presence of a worm and the corresponding monitoring system. Based on epidemic model and observation data from the monitoring system, by using the idea of "detecting the trend, not the rate" of monitored illegitimated scan traffic, we propose to use a Kalman filter to detect a worm's propagation at its early stage in real-time. In addition, we can effectively predict the overall vulnerable population size, and correct the bias in the observed number of infected hosts. Our simulation experiments for Code Red and SQL Slammer show that with observation data from a small fraction of IP addresses, we can detect the presence of a worm when it infects only 1% to 2% of the vulnerable computers on the Internet.

In this paper, we study streaming multiple videos from a remote server to asynchronous clients through a group of proxies, using multicast on both the wide area server-proxy paths and the local area proxy-client paths. In this setting, we present an algorithm to determine the optimal cache allocation among videos at each proxy and develop an efficient streaming video distribution scheme. Our evaluations show the benefits of even a small proxy cache and quantify the gains from using multicast on the server-proxy paths.

Congestion control in TCP/AQM networks is expected to perform well for a wide-range of conditions, but recent advances in modeling and analysis indicate that present AQM (active queue management) schemes need an extra dose of adaptability to cope. The paper answers the call and proposes a self-tuning structure wherein AQM parameters are automatically tuned in response to on-line estimation of link capacity and traffic load. This approach is applicable to any AQM scheme that is parameterizable in terms of link capacity and TCP load. We describe this self-tuning structure, illustrate its application to PI (proportional-integral) and RED (random early detection) AQMs, provide stability analysis, and conduct ns simulations to compare with both fixed AQM schemes and the recently proposed adaptive RED.

Providing on-demand video streaming service over the Internet is a challenging task. In this paper, we propose DirectStream, a directory based peer-to-peer video streaming service that efficiently and cost-effectively provides video on-demand service with VCR operation support. We analytically and experimentally examine the system performance, and show that the proposed scheme can significantly reduce the workload posed on the server, and that it scales extremely well as the popularity of the video increases even if participating clients behave non-cooperatively. We propose a QoS parent selection algorithm to construct the appropriate peer-to-peer networks, and discuss how to provide continuous playback in the face of clients' early departures. Our study suggests that peer-to-peer networking is a promising technique to address scalability in on-demand streaming service.

In recent years there has been considerable research on new distributed hash tables (DHTs), improvements on existing DHTs, and DHT-enabled systems. However, little of it focuses on their differences [M. Castro et al., 2002]. To this purpose we introduce a simple modeling framework that allows us to mathematically model the search costs of most classes of DHTs. To illustrate the usefulness of this framework, we examine a class of DHTs, which includes tapestry and pastry, that we call dynamic PRR meshes (DPMs). In particular we examine how planned object duplication (POD) strategies affect the search costs of DPMs that employ them. We introduce 3 new DPMs that employ different POD strategies and compare them with the POD strategies that tapestry and pastry use. Through our model we discover cyclic behaviors in search costs over the number of nodes present in the DPM, the effects of variability in the underlying network and provide comparisons of the performance of all 5 DPMs.

The publish/subscribe (pub/sub) paradigm provides content-oriented data dissemination in which communication channels are established between content publishers and content subscribers based on a matching of subscribers interest in the published content provided - a process we refer to as "matchmaking". Once an interest match has been made, content forwarding state can be installed at intermediate nodes (e.g., active routers, application-level relay nodes) on the path between a content provider and an interested subscriber. In dynamic pub/sub applications, where published content and subscriber interest change frequently the signaling overhead needed to perform matchmaking can be a significant overhead. We first formalize the matchmaking process as an optimization problem, with the goal of minimizing the amount of matchmaking signaling messages. We consider this problem for both shared and per-source multicast data (content) distribution topologies. We characterize the fundamental complexity of the problem, and then describe several efficient solution approaches. The insights gained through our analysis are then embodied in a novel active matchmaker signaling protocol (AMSP). AMSP dynamically adapts to applications' changing publication and subscription requests through a link-marking approach. We simulate AMSP and two existing broadcast-based approaches for conducting matchmaking, and find that AMSP significantly reduces signaling overhead.

In this paper, we propose a model-based approach that uses periodic end-end probes to identify whether a "dominant congested link" exists along an end-end path. Informally, a dominant congested link refers to a link that incurs the most losses and significant queuing delays along the path. We begin by providing a formal yet intuitive definition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present and examine several novel model-based approaches for identifying a dominant congested link that are based on interpreting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for Hidden Markov Model (HMM) and Markov model with a hidden dimension to infer this virtual delay. Our validation using ns simulation and live Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further estimate the maximum queuing delay of the dominant congested link, once we identify that a dominant congested link exists.

One key component of recent pricing-based congestion control schemes is an algorithm for probabilistically setting the Explicit Congestion Notification bit at routers so that a receiver can estimate the sum of link congestion prices along a path. We consider two such algorithms - a well-known algorithm called Random Exponential Marking (REM) and a novel algorithm called Random Additive Marking (RAM). We show that if link prices are unbounded, a class of REM-like algorithms are the only ones possible. Unfortunately, REM computes a biased estimate of total price and requires setting a parameter for which no uniformly good choice exists in a network setting. However, we show that if prices can be bounded and therefore normalized, then there is an alternate class of feasible algorithms, of which RAM is representative and furthermore, only the REM-like and RAM-like classes are possible. For properly normalized link prices, RAM returns an optimal price estimate (in terms of mean squared error), outperforming REM even if the REM parameter is chosen optimally. RAM does not require setting a parameter like REM, but does require a router to know its position along the path taken by a packet. We present an implementation of RAM for the Internet that exploits the existing semantics of the time-to-live field in IP to provide the necessary path position information.

In this paper we present analytical techniques that can be used to better understand the behavior of malware, a generic term that refers to all kinds of malicious software programs propagating on the Internet, such as e-mail viruses and worms. We develop a modeling methodology based on Interactive Markov Chains that is able to capture many aspects of the problem, especially the impact of the underlying topology on the spreading characteristics of malware. We propose numerical methods to obtain useful bounds and approximations in the case of very large systems, validating our results through simulation. An analytic methodology represents a fundamentally important step in the development of effective countermeasures for future malware activity. Furthermore, we believe our approach can help to understand a wide range of "dynamic interactions on networks", such as routing protocols and peer-to-peer applications.

Peer-peer networking has recently emerged as a new paradigm for building distributed networked applications. We develop simple mathematical models to explore and illustrate fundamental performance issues of peer-peer file sharing systems. The modeling framework introduced and the corresponding solution methods are flexible enough to accommodate different characteristics of such systems. Through the specification of model parameters, we apply our framework to three different peer-peer architectures: centralized indexing, distributed indexing with flooded queries, and distributed indexing with hashing directed queries. Using our model, we investigate the effects of system scaling, freeloaders, file popularity and availability on system performance. In particular, we observe that a system with distributed indexing and flooded queries cannot exploit the full capacity of peer-peer systems. We further show that peer-peer file sharing systems can tolerate a significant number of freeloaders without suffering much performance degradation. In many cases, freeloaders can benefit from the available spare capacity of peer-peer systems and increase overall system throughput. Our work shows that simple models coupled with efficient solution methods can be used to understand and answer questions related to the performance of peer-peer file sharing systems.

Routers handle data packets from sources unresponsive to TCP's congestion avoidance feedback. We are interested in the impact these sources have on active queue management (AQM) control of long-lived TCP traffic. In this paper, we combine models of TCP/AQM dynamics with models of unresponsive traffic to analyze the effects on AQM performance.

We present a measurement study and classification methodology for out-of-sequence packets in TCP connections observed within the Sprint IP backbone. Such out-of-sequence packets can result from many causes including loss, looping, reordering, or duplication in the network. It is important to quantify and understand the causes of such out-of-sequence packets since they are one indication of the "health" of an end-end TCP connection. Our first contribution is methodological. Because we measure out-of-sequence packets at a single point in the backbone (rather than by sending and measuring end-end probe traffic at the sender or receiver), a new methodology is required to infer the causes of a connection's out-of-sequence packets based only on measurements taken in the "middle" of the connection. We thus describe techniques that classify the causes of observed out-of-sequence behavior based only on the previously- and subsequently-observed packets within a connection and knowledge of how TCP behaves. We show that using these simple techniques, it is possible to classify almost all out-of-sequence packets in our traces and that we can quantify the uncertainty in our classification. Our second contribution is the characterization of the out-of-sequence behavior itself. We analyze numerous several-hour packet-level traces from a set of OC-3 and OC-12 links for several million connections generated in nearly 4,300 unique ASs. Our measurements show a relatively consistent amount of out-of-sequence packets of approximately 5%. We find that few out-of-sequence packets result from pathological problems such as routing loops or in network duplication/reordering.

This paper involves the study of the throughput capacity of hybrid wireless networks. A hybrid network is formed by placing a sparse network of base stations in an ad hoc network. These base stations are assumed to be connected by a high-bandwidth wired network and act as relays for wireless nodes. They are not data sources nor data receivers. Hybrid networks present a tradeoff between traditional cellular networks and pure ad hoc networks in that data may be forwarded in a multihop fashion or through the infrastructure. It has been shown that the capacity of a random ad hoc network does not scale well with the number of nodes in the system. In this work, we consider two different routing strategies and study the scaling behavior of the throughput capacity of a hybrid network. Analytical expressions of the throughput capacity are obtained. For a hybrid network of n nodes and m base stations, the results show that if m grows asymptotically slower than √n, the benefit of adding base stations on capacity is insignificant. However, if m grows faster than √n, the throughput capacity increases linearly with the number of base stations, providing an effective improvement over a pure ad hoc network. Therefore, in order to achieve nonnegligible capacity gain, the investment in the wired infrastructure should be high enough.

One of the key infrastructure components in all telecommunication networks, ranging from the telephone network, to VC-oriented data networks, to the Internet, is its signaling system. Two broad approaches towards signaling can be identified: so-called hard-state and soft-state approaches. Despite the fundamental importance of signaling, our understanding of these approaches - their pros and cons and the circumstances in which they might best be employed - is mostly anecdotal (and occasionally religious). In this paper, we compare and contrast a variety of signaling approaches ranging from a "pure" soft state, to soft-state approaches augmented with explicit state removal and/or reliable signaling, to a "pure" hard state approach. We develop an analytic model that allows us to quantify state inconsistency in single- and multiple-hop signaling scenarios, and the "cost" (both in terms of signaling overhead, and application-specific costs resulting from state inconsistency) associated with a given signaling approach and its parameters (e.g., state refresh and removal timers). Among the class of soft-state approaches, we find that a soft-state approach coupled with explicit removal substantially improves the degree of state consistency while introducing little additional signaling message overhead. The addition of reliable explicit setup/update/removal allows the soft-state approach to achieve comparable (and sometimes better) consistency than that of the hard-state approach.

In this paper we describe an analytical approach for estimating the queuing delay distribution on an Internet link carrying realistic TCP traffic, such as that produced by a large number of finite-size connections transferring files whose sizes are taken from a long-tail distribution. The analytical predictions are validated against detailed simulation experiments and real network measurements. Despite its simplicity, our model proves to be accurate and robust under a variety of operating conditions, and offers novel insights into the impact on the network of long-tail flow length distributions. Our contribution is a performance evaluation methodology that could be usefully employed in network dimensioning and engineering.

In this paper we present a scalable model of a network of Active Queue Management (AQM) routers serving a large population of TCP flows. We present efficient solution techniques that allow one to obtain the transient behavior of the average queue lengths, packet loss probabilities, and average end-to-end latencies. We model different versions of TCP as well as different versions of RED, the most popular AQM scheme currently in use. Comparisons between our models andns simulation show our models to be quite accurate while at the same time requiring substantially less time to solve, especially when workloads and bandwidths are high. Categories and Subject Descriptors

Congestion control in TCP/AQM networks is expected to perform well for a wide-range of conditions, but recent advances in modeling and analysis indicate that present AQM schemes need an extra dose of adaptability to cope. This paper answers the call and proposes a self-tuning structure wherein AQM parameters are automatically tuned in response to on-line estimation of link capacity and traffic load. This approach is applicable to any AQM scheme that is parameterizable in terms of link capacity and TCP load. In this paper, we will describe this self-tuning structure, illustrate its application to PI and RED AQMs, provide stability analysis, and conduct ns simulations to compare with both fixed AQM schemes and the recently proposed adaptive RED.

Providing video on demand (VoD) service over the Internet in a scalable way is a challenging problem. In this paper, we propose P2Cast - an architecture that uses a peer-to-peer approach to cooperatively stream video using patching techniques, while only relying on unicast connections among peers. We address the following two key technical issues in P2Cast: (1) constructing an application overlay appropriate for streaming; and (2) providing continuous stream playback (without glitches) in the face of disruption from an early departing client. Our simulation experiments show that P2Cast can serve many more clients than traditional client-server unicast service, and that it generally out-performs multicast-based patching if clients can cache more than of a stream's initial portion. We handle disruptions by delaying the start of playback and applying the shifted forwarding technique. A threshold on the length of time during which arriving clients are served in a single session in P2Cast serves as a knob to adjust the balance between the scalability and the clients' viewing quality in P2Cast.

Controlling the rate of bulk data multicast to a large number of receivers is difficult, due to the heterogeneity among the end systems' capabilities and their available network bandwidth. If the data transfer rate is too high, some receivers will lose data, and retransmissions will be required. If the data transfer rate is too slow, an inordinate amount of time will be required to transfer the data. In this paper, we examine an approach toward rate-controlled multicast of bulk data in which the sender uses multiple multicast groups to transmit data at different rates to different subgroups of receivers. We present simple algorithms for determining the transmission rate associated with each multicast channel, based on static resource constraints, e.g., network bandwidth bottlenecks. Transmission rates are chosen so as to minimize the average time needed to transfer data to all receivers. Analysis and simulation are used to show that our policies for rate selection perform well for large and diverse receiver groups and make efficient use of network bandwidth. Moreover, we find that only a small number of multicast groups are needed to reap most of the possible performance benefits.

We present a proxy-assisted video delivery architecture that can simultaneously reduce the resources requirements at the central server and the service latency experienced by clients (i.e., end users). Under the proposed video delivery architecture, we develop and analyze two novel proxy-assisted video streaming techniques for on-demand delivery of video objects to a large number of clients. By taking advantage of the resources available at the proxy servers, these techniques not only significantly reduce the central server and network resource requirements, but are also capable of providing near-instantaneous service to a large number of clients. We optimize the performance of our video streaming architecture by carefully selecting video delivery techniques for videos of various popularity and intelligently allocating resources between proxy servers and the central server. Through empirical studies, we demonstrate the efficacy of the proposed proxy-assisted video streaming techniques.

The Code Red worm incident of July 2001 has stimulated activities to model and analyze Internet worm propagation. In this paper we provide a careful analysis of Code Red propagation by accounting for two factors: one is the dynamic countermeasures taken by ISPs and users; the other is the slowed down worm infection rate because Code Red rampant propagation caused congestion and troubles to some routers. Based on the classical epidemic Kermack-Mckendrick model, we derive a general Internet worm model called the two-factor worm model. Simulations and numerical solutions of the two-factor worm model match the observed data of Code Red worm better than previous models do. This model leads to a better understanding and prediction of the scale and speed of Internet worm spreading.

BGP routing table sizes have increased by an order of magnitude over the last six years. This dramatic growth can decrease packet forwarding speed and demand more router memory space. We explore the extent that various factors contribute to the routing table size and characterize the growth of each contribution. We begin with a measurement study using the routing tables of an Oregon route views server to determine the contributions of multi-homing, load balancing, address fragmentation, and failure-to-aggregate to routing table size. Address fragmentation makes the greatest contribution and it is three times those of multihoming or load balancing. The contribution of failure-to-aggregate is the least. Although multihoming and load balancing contribute less to routing table size than address fragmentation, we observe that their contributions grow faster than the routing table does and that load balancing has surpassed multihoming, becoming the fastest growing contributor. Moreover, we find that both load balancing and multihoming contribute to routing table growth by introducing more prefixes of length between 17 and 25, which are the fastest growing prefixes. Next, we examine the growth routable IP addresses, and conclude that their growth is much slower than that of routing table size. Lastly, we demonstrate that our findings based on views derived from the Oregon server are accurate through an evaluation using 15 additional routing tables collected from different locations in the Internet.

We compare four different approaches towards modeling frame-level errors in GSM channels. One of these, the Markov-based trace analysis (MTA) model, was developed for the purpose of modeling a GSM channel. The next two, k/sup th/-order Markov models and hidden Markov models (HMMs) have been widely used to model loss in wired networks. All three of these have difficulty modeling empirical GSM frame-level error traces. The MTA model and HMM predict frame error rates substantially different from that measured from the trace, and all three models have difficulty capturing the long term temporal correlation structure. We propose a fourth model, the extended ON/OFF model, which alternates between an ON (error-free) and an OFF (error-filled) state. The state holding times are taken from mixtures of geometric distributions. We show that this model, with mixtures of three or four geometric distributions, captures first order and second order statistics significantly better than the preceding three approaches.

Wireless links are characterized by high bit error rates and intermittent connectivity. This can result in significant degradation in the performance (goodput) of TCP over wireless networks since non-congestion related packet losses can be misinterpreted by TCP as indications of network congestion, resulting in unnecessary congestion control. In this paper, we propose a technique, TCP with adaptive forward error correction (TCP-AFEC), to improve TCP performance over wireless networks. TCP-AFEC combines the well-established performance characterization of TCP with an understanding of the link layer error control scheme to dynamically select the forward error correction (FEC) that maximizes TCP goodput according to the current channel condition. The benefit of coupling a characterization of TCP performance with link layer FEC to improve TCP goodput is demonstrated by comparing the performance of TCP-AFEC against those of TCP-SACK and Snoop. Simulation results show that TCP-AFEC outperforms TCP-SACK and Snoop for a wide range of wireless channel conditions.

The bandwidth-intensive and long-lived nature of high quality digital video makes it a challenging problem to transmit such video over the Internet. In this paper, we propose a scalable and flexible framework integrating proxy-based prefix caching with periodic broadcast of the suffix of a video from the server, for efficiently streaming a set of popular videos to a large number of asynchronous clients. We develop a methodology for (i) determining appropriate prefix and suffix transmission schemes based on a principle of decoupling the two transmissions from each other, and (ii) optimally allocating the proxy buffer space among the set of videos. A buffer allocation algorithm is presented that minimizes the aggregate bandwidth usage on the server-proxy path. Our studies show that our approach yields a buffer allocation close to the optimal solution minimizing both server-proxy and proxy-client path bandwidth usage for practical settings where the proxy-client path bandwidth is much cheaper than the long-haul server-proxy path bandwidth. When the proxy buffer is allocated to a set of videos using our scheme, a total buffer space of just 5-20% of the video repository is adequate to realize substantial reductions in the aggregate bandwidth usage on the server-proxy path.

No abstract available.

Recent work has shown that the node degree in the WWW induced graph and the autonomous system (AS) level Internet topology exhibit power laws. Since then, several algorithms have been proposed to generate such power law graphs. We evaluate the effectiveness of these generators to generate representative AS-level topologies. Our conclusions are mixed. Although they (mostly) do a reasonable job at capturing the power law exponent, they do less well in capturing the clustering phenomena exhibited by the Internet topology. Based on these results, we propose a variation of the recent incremental topology generator of R. Albert and A. Barabasi (see Phys. Rev. Letters, vol.85, p.5234-7, 2000) that is more successful at matching the power law exponent and the clustering behavior of the Internet. Last, we comment on the small world behavior of the Internet topology.

In this paper we propose a new paradigm for a Differentiated Service (DiffServ) network consisting of two-color marking at the edges of the network using token buckets coupled with differential treatment in the core. Using fluid-flow modelling, we present existence conditions for token-bucket rates and differential marking probabilities at the core that result in all edges receiving at least their minimum guaranteed rates. We then present an integrated DiffServ architecture comprising of an active rate management controller at the marking edge and a two-level active queue management controller at the core. The validity of the fluid flow model and performance of this new scheme are verified using ns simulations.

In this paper, we address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We develop a technique to analytically determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as batching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resultant transmission cost.. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in predominantly unicast environments such as the Internet.

In this paper we consider the problem of inferring link-level loss rates from end-to-end multicast measurements taken from a collection of trees. We give conditions under which loss rates are identifiable on a specified set of links. Two algorithms are presented to perform the link-level inferences for those links on which losses can be identified. One, the minimum variance weighted average (MVWA) algorithm treats the trees separately and then averages the results. The second, based on expectation-maximization (EM) merges all of the measurements into one computation. Simulations show that EM is slightly more accurate than MVWA, most likely due to its more efficient use of the measurements. We also describe extensions to the inference of link-level delay, inference from end-to-end unicast measurements, and inference when some measurements are missing.

Network tomography using multicast probes enables inference of loss characteristics of internal network links from reports of end-to-end loss seen at multicast receivers. We develop estimators for internal loss rates when reports are not available on all probes or from all receivers. This problem is motivated by the use of unreliable transport protocols, such as reliable transport protocol, to transmit loss reports to a collector for inference. We use a maximum-likelihood (ML) approach in which we apply the expectation maximization (EM) algorithm to provide an approximating solution to the the ML estimator for the incomplete data problem. We present a concrete realization of the algorithm that can be applied to measured data. For classes of models, we establish identifiability of the probe and report loss parameters, and convergence of the EM sequence to the maximum-likelihood estimator (MLE). Numerical results suggest that these properties hold more generally. We derive convergence rates for the EM iterates, and the estimation error of the MLE. Finally, we evaluate the accuracy and convergence rate through extensive simulations.

A set of applications such as Internet video broadcasts, corporate telecasts, and distance learning require the simultaneous streaming of video to a large population of viewers across the Internet. The high bandwidth requirements and the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques to efficiently stream video to a large number of disparate clients across a heterogeneous Internet. In this paper, we propose to multicast smoothed video over an application-level overlay network of proxies, and to differentially cache the video at the intermediate nodes (proxies) in the distribution tree, in order to reduce the network bandwidth requirements of video dissemination. We formulate the multicast smoothing problem as an optimization problem, and develop an algorithm for computing the set of transmission schedules for the tree that minimize the peak rate and rate variability, given buffer constraints at different nodes in the tree. We also develop an algorithm to compute the minimum buffer allocation in the entire tree, such that feasible transmission to all the clients is possible, when the tree has heterogeneous rate constraints. We show through trace-driven simulations that substantial benefits are possible from multicast smoothing and differential caching, and that these gains can be realized even with modest proxy caches.

1441-1443

We survey advances in theories and models for Internet quality of service (QoS). We start with the theory of network calculus, which lays the foundation for support of deterministic performance guarantees in networks, and illustrate its applications to integrated services, differentiated services, and streaming media playback delays. We also present mechanisms and architecture for scalable support of guaranteed services in the Internet, based on the concept of a stateless core. Methods for scalable control operations are also discussed. We then turn our attention to statistical performance guarantees and describe several new probabilistic results that can be used for a statistical dimensioning of differentiated services. Lastly, we review proposals and results in supporting performance guarantees in a best effort context. These include models for elastic throughput guarantees based on TCP performance modeling, techniques for some QoS differentiation without access control, and methods that allow an application to control the performance it receives, in the absence of network support.

Abstract—The use of multicast inference on end-to-end measurement has recently been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. In this paper, we propose three types of algorithm that use loss measurements to infer the underlying multicast topology: i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; ii) a maximum-likelihood (ML) estimator (MLE); and iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities. Index Terms—Communication networks, end-to-end measurement, maximum-likelihood (ML) estimation, multicast, statistical inference, topology discovery.

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant transaction scheduling policies are proposed. Informally, data-deadline is a deadline assigned to a transaction due to the temporal constraints of the data accessed by the transaction. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in realtime database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.

Many definitions of fairness for multicast networks assume that sessions are single rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multirate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multirate sessions, and show that all four fairness properties hold in a multirate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multirate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multirate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks.

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. We present techniques based on loss or delay observations at end hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. Our novel result is that such detection can be achieved for unicast flows, but the techniques can also be applied to multicast flows. We validate these techniques via queueing analysis, simulation and experimentation within the Internet. In addition, we demonstrate preliminary simulation results that show that the delay-based technique can determine whether two TCP flows are congested at the same set of resources. We also propose metrics that can be used as a measure of the amount of congestion sharing between two flows.

In many large scale data dissemination systems, a large number of information flows must be delivered to a large number of information receivers. However, because of differences in interests among receivers, not all receivers are interested in all of the information flows. Multicasting provides the opportunity to deliver a subset of the information flows to a subset of the receivers. With a limited number of multicast groups available, the channelization problem is to find an optimal mapping of information flows to a fixed number of multicast groups, and a subscription mapping of receivers to multicast groups so as to minimize a function of the total bandwidth consumed and the amount of unwanted information received by receivers. We formally define two versions of the channelization problem and subscription problem (a subcomponent of the channelization problem). We analyze the complexity of each version of the channelization problem and show that they are both NP-complete. We also find that the subscription problem is NP-complete when one flow can be assigned to multiple multicast groups. We also study and compare different approximation algorithms to solve the channelization problem, finding that one particular heuristic, flow-based-merge, finds good solutions over a range of problem configurations.

In this work we develop simple inference models based on finite capacity single server queues for estimating the buffer size and the intensity of cross traffic at the bottleneck link of a path between two hosts. Several pairs of moment-based estimators are proposed to estimate these two quantities. The best scheme is then identified through simulation.

In this paper we explore the use of end-to-end unicast traffic as measurement probes to infer link-level loss rates. We leverage on of earlier work that produced efficient estimates for link-level loss rates based on end-to-end multicast traffic measurements. We design experiments based on the notion of transmitting stripes of packets (with no delay between transmission of successive packets within a stripe) to two or more receivers. The purpose of these stripes is to ensure that the correlation in receiver observations matches as closely as possible what would have been observed if the stripe had been replaced by a notional multicast probe that followed the same paths to the receivers. Measurements provide good evidence that a packet pair to distinct receivers introduces considerable correlation which can be further increased by simply considering longer stripes. We then use simulation to explore how well these stripes translate into accurate link-level loss estimates. We observe good accuracy with packet pairs, with a typical error of about 1%, which significantly decreases as stripe length is increased to 4 packets.

We use a previously developed nonlinear dynamic model of TCP to analyze and design active queue management (AQM) control systems using random early detection (RED). First, we linearize the interconnection of TCP and a bottlenecked queue and discuss its feedback properties in terms of network parameters such as link capacity, load and round-trip time. Using this model, we next design an AQM control system using the RED scheme by relating its free parameters such as the low-pass filter break point and loss probability profile to the network parameters. We present guidelines for designing linearly stable systems subject to network parameters like propagation delay and load level. Robustness to variations in system loads is a prime objective. We present no simulations to support our analysis.

In this paper we study a previously developed linearized model of TCP and active queue management (AQM). We use classical control system techniques to develop controllers well suited for the application. The controllers are shown to have better theoretical properties than the well known RED controller. We present guidelines for designing stable controllers subject to network parameters like load level propagation delay etc. We also present simple implementation techniques which require a minimal change to RED implementations. The performance of the controllers are verified and compared with RED using ns simulations. The second of our designs, the proportional integral (PI) controller is shown to outperform RED significantly.

Network performance evaluation through traditional packet-level simulation is becoming increasingly difficult as today's networks grow in scale along many dimensions. As a consequence, fluid simulation has been proposed to cope with the size and complexity of such systems. This study focuses on analyzing and comparing the relative efficiencies of fluid simulation and packet-level simulation for several network scenarios. We use the "simulation event" rate to measure the computational effort of the simulators and show that this measure is both adequate and accurate. For some scenarios, we derive analytical results for the simulation event rate and identify the major factors that contribute to the simulation event rate. Among these factors, the "ripple effect" is very important since it can significantly increase the fluid simulation event rate. For a tandem queueing system, we identify the boundary condition to establish regions where one simulation paradigm is more efficient than the other. Flow aggregation is considered as a technique to reduce the impact of the "ripple effect" in fluid simulation. We also show that WFQ scheduling discipline can limit the "ripple effect", making fluid simulation particularly well suited for WFQ models. Our results show that tradeoffs between parameters of a network model determines the most efficient simulation approach.

Multimedia streaming applications can consume a significant amount of server and network resources. Periodic broadcast and patching are two approaches that use multicast transmission and client buffering in innovative ways to reduce server and network load, while at the same time allowing asynchronous access to multimedia steams by a large number of clients. Current research in this area has focussed primarily on the algorithmic aspects of these approaches, with evaluation performed via analysis or simulation. In this paper, we describe the design and implementation of a flexible streaming video server and client testbed that implements both periodic broadcast and patching, and explore the issues that arise when implementing these algorithms. We present measurements detailing the overheads associated with the various server components (signaling, transmission schedule computation, data retrieval and transmission), the interactions between the various components of the architecture, and the overall end-to-end performance. We also discuss the importance of an appropriate server video segment caching policy. We conclude with a discussion of the insights gained from our implementation and experimental evaluation.

No abstract available.

Multimedia applications require the transmission of real-time streams over a network. These streams often exhibit variable bandwidth requirements, and require high bandwidths and guarantees from the network. This creates problems when such streams are delivered over the Internet. To solve these problems, recently, a small set of differentiated services has been introduced. Among these, Premium Service is suitable for transmitting real-time stored stream (full knowledge of the stream characteristics). It uses a bandwidth allocation mechanism (BAM) based on the stream peak rate. Due to the variable bandwidth requirement, the peak rate BAM can waste large amount of bandwidth. In this paper we propose a new BAM that uses less bandwidth than the peak rate BAM, while providing the same service. Our BAM does not affect the real-time stream quality of service (QoS) and does not require any modification to the Premium Service Architecture. We also introduce several frame dropping mechanisms that further reduce bandwidth consumption subject to a QoS constraint when coupled with the above BAM. The proposed BAM and the dropping mechanisms are evaluated using Motion JPEG and MPEG videos and are shown to be effective in reducing bandwidth requirements. Further, since VCR operations are very useful in video streaming, we propose a mechanism that introduces these operations in our BAM. Through simulations we show the effectiveness of this mechanism.

In this paper, we propose and evaluate the performance of a continuous media delivery technique, called threshold-based multicast. Similar to patching, threshold-based multicast allows two clients that request the same video to share a channel without having to delay the earlier request. It ensures sharing by permitting the client with the later arrival time to join an ongoing multicast session initiated for the earlier request. However, threshold-based multicast does not allow a later arriving client to always join an ongoing multicast session. If it has been some time since the ongoing multicast session was started, a new multicast session is initiated. That is, a threshold is used to control the frequency at which new multicast sessions are started. We derive the optimal threshold that minimizes the server bandwidth required. Our analytical result shows that threshold-based multicast significantly reduces the server bandwidth requirement. Furthermore, we perform a simulation study demonstrating the performance gain of continuous media delivery by threshold-based multicast.

Data communication networks have been experiencing tremendous growth in size, complexity, and heterogeneity over the last decade. This trend poses a significant challenge to the design of scalable performance evaluation methodologies. In this paper we propose time-stepped hybrid simulation (TSHS) to deal with the scalability issue faced by traditional packet-level discrete event simulation methods. TSHS is a framework that offers the user the flexibility to choose the simulation time scale so as to trade off the computational cost of the simulation with its fidelity. Simulation speedup is achieved by evaluating the system at coarser time-scales. The potential loss of simulation accuracy when fine-time-scale behavior is evaluated at a coarser time-scale is studied both analytically and experimentally.

151-160

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. In this paper, we present techniques based on loss or delay observations at end-hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. We validate these techniques via queueing analysis, simulation, and experimentation within the Internet.

The Differentiated services (diffserv) architecture has been proposed as a scalable solution for providing service differentiation among flows without any per-flow buffer management inside the core of the network. It has been advocated that it is feasible to provide service differentiation among a set of flows by choosing an appropriate “marking profile” for each flow. In this paper, we examine (i) whether it is possible to provide service differentiation among a set of TCP flows by choosing appropriate marking profiles for each flow, (ii) under what circumstances, the marking profiles are able to influence the service that a TCP flow receives, and, (iii) how to choose a correct profile to achieve a given service level. We derive a simple, and yet accurate, analytical model for determining the achieved rate of a TCP flow when edge-routers use “token bucket” packet marking and core-routers use active queue management for preferential packet dropping. From our study, we observe three important results: (i) the achieved rate is not proportional to the assured rate, (ii) it is not always possible to achieve the assured rate and, (iii) there exist ranges of values of the achieved rate for which token bucket parameters have no influence. We find that it is not easy to regulate the service level achieved by a TCP flow by solely setting the profile parameters. In addition, we derive conditions that determine when the bucket size influences the achieved rate, and rates that can be achieved and those that cannot. Our study provides insight for choosing appropriate token bucket parameters for the achievable rates.

Wireless networks often employ network-based user agents as proxies for mobile users. In this paper, we consider the fundamental problem of designing migration policies for these user agents. We first introduce a general framework for analyzing user agent migration policies, and then highlight, through analysis and simulation, the numerous parameters and tradeoffs that dictate the design of migration policies. We evaluate these policies in the context of both homogeneous and heterogeneous networks, and in the presence and absence of processing overheads due to migration. Finally, we identify two simple threshold-based policies that deliver very good performance over a wide range of system parameters and configurations. To our knowledge, this is the first paper to propose and evaluate policies for migration of user agents.

We examine an approach for providing reliable, scalable multicast communication, involving the use of multiple multicast channels for reducing receiver processing costs and reducing network bandwidth consumption in a multicast session. In this approach a single multicast channel is used for the original transmission of packets. Retransmissions of packets are done on separate multicast channels, which receivers dynamically join and leave. We first show that protocols using an infinite number of multicast channels incur much less processing overhead at the receivers compared to protocols that use only a single multicast channel. This is due to the fact that receivers do not receive retransmissions of packets they have already received correctly. Next, we derive the number of unwanted redundant packets at a receiver due to using only a finite number of multicast channels, for a specific negative acknowledgment (NAK)-based protocol. We then explore the minimum number of multicast channels required to keep the cost of processing unwanted packets to a sufficiently low value. For an application consisting of a single sender transmitting reliably to many receivers we find that only a small number of multicast channels are required for a wide range of system parameters. In the case of an application where all participants simultaneously act as both senders and receivers a moderate number of multicast channels is needed. Finally, we present two mechanisms for implementing multiple multicast channels, one using multiple IP multicast groups and the other using additional router support for selective packet forwarding. We discuss the impact of both mechanisms on performance in terms of end-host and network resources.

The steady-state performance of a bulk transfer TCP flow (i.e., a flow with a large amount of data to send, such as FTP transfers) may be characterized by the send rate, which is the amount of data sent by the sender in unit time. In this paper we develop a simple analytic characterization of the steady-state send rate as a function of loss rate and round trip time (RTT) for a bulk transfer TCP flow. Unlike the models of Lakshman and Madhow (see IEE/ACM Trans. Networking, vol.5, p.336-50, 1997), Mahdavi and Floyd (1997), Mathis, Semke, Mahdavi and Ott (see Comput. Commun. Rev., vol.27, no.3, 1997) and by by Ott et al., our model captures not only the behavior of the fast retransmit mechanism but also the effect of the time-out mechanism. Our measurements suggest that this latter behavior is important from a modeling perspective, as almost all of our TCP traces contained more time-out events than fast retransmit events. Our measurements demonstrate that our model is able to more accurately predict TCP send rate and is accurate over a wider range of loss rates. We also present a simple extension of our model to compute the throughput of a bulk transfer TCP flow, which is defined as the amount of data received by the receiver in unit time.

An important concern for source-based multicast congestion control algorithms is the loss path multiplicity (LPM) problem that arises because a transmitted packet can be lost on one or more of the many end-to-end paths in a multicast tree. Consequently, if a multicast source's transmission rate is regulated according to loss indications from receivers, the rate may be completely throttled as the number of loss paths increases. In this paper, we analyze a family of additive increase multiplicative decrease congestion control algorithms and show that, unless careful attention is paid to the LPM problem, the average session bandwidth of a multicast session may be reduced drastically as the size of the multicast group increases. This makes it impossible to share bandwidth in a max-min fair manner among unicast and multicast sessions. We show that max-min fairness can be achieved however if every multicast session regulates its rate according to the most congested end-to-end path in its multicast tree. We present an idealized protocol for tracking the most congested path under changing network conditions, and use simulations to illustrate that tracking the most congested path is indeed a promising approach.

Excessive packet loss rates can dramatically decrease the audio quality perceived by users of Internet telephony applications. Previous results suggest that error control schemes using forward error correction (FEC) are good candidates for decreasing the impact of packet loss on audio quality. However, the FEC scheme must be coupled to a rate control scheme. Furthermore, the amount of redundant information used at any given point in time should also depend on the characteristics of the loss process at that time (it would make no sense to send much redundant information when the channel is loss free), on the end to end delay constraints (destination typically have to wait longer to decode the FEC as more FEC information is used), on the quality of the redundant information, etc. However, it is not clear given all these constraints how to choose the "best" possible redundant information. We address this issue, and illustrate the approach using an FEC scheme for packet audio standardized in the IETF. We show that the problem of finding the best redundant information can be expressed mathematically as a constrained optimization problem for which we give explicit solutions. We obtain from these solutions a simple algorithm with very interesting features, namely (i) the algorithm optimizes a subjective measure (such as the audio quality perceived at a destination) as opposed to an objective measure of quality (such as the packet loss rate at a destination), (ii) it incorporates the constraints of rate control and playout delay adjustment schemes, and (iii) it adapts to varying loss conditions in the network (estimated online with RTCP feedback). We have been using the algorithm, together with a TCP-friendly rate control scheme and we have found it to provide very good audio quality even over paths with high and varying loss rates. We present simulation and experimental results to illustrate its performance.

We explore the use of end-to-end multicast traffic as measurement probes to infer network internal characteristics. We have developed in an earlier paper a maximum likelihood estimator for packet loss rates on individual links based on losses observed by multicast receivers. This technique exploits the inherent correlation between such observations to infer the performance of paths between branch points in the multicast tree spanning the probe source and its receivers. We evaluate through analysis and simulation the accuracy of our estimator under a variety of network conditions. In particular, we report on the error between inferred loss rates and actual loss rates as we vary the network topology, propagation delay, packet drop policy, background traffic mix, and probe traffic type. In all but one case, estimated losses and probe losses agree to within 2 percent on average. We feel this accuracy is enough to reliably identify congested links in a wide-area internetwork.

In this paper we present methods to evaluate the benefit of using direct ATM connections (shortcuts) between IP nodes in IP over ATM networks, and we identify the combinations of IP and ATM network topologies where ATM shortcut benefits are likely to be high. We model an IP/ATM network with and without ATM shortcuts as two loss networks. We propose a metric for network performance comparison, the network load ratio, that gives the ratio of the number of flows accepted by two networks at the same network blocking probability. We derive an estimator of this metric, the asymptotic load ratio, that has low computational complexity. This estimator forms the basis of a methodology for network performance comparison. We use this method in simulation experiments using random networks. These experiments indicate that in many cases the utilization of an IP/ATM network increases proportionally to the decrease in the average path length when ATM shortcuts are used. We have also found that there is almost no correlation between the increase in network utilization (when using ATM shortcuts) and the IP to ATM node ratio.

We derive estimators and bounds that drive probabilistic polling algorithms for the estimation of the session size, n, of any potentially large scale multicast session. We base our analysis upon a mapping of polling mechanisms to the problem of estimating the parameter n of the binomial (n,p) distribution. From the binomial model, we derive an interval estimator for n, and we characterize the tradeoff between the estimator's quality and its overhead in a manner readily matched to application requirements. We derive other estimators and bounds that enable applications to treat as a tunable parameter the confidence that they will not exceed their overhead limits. We also suggest revised estimators and other improvements for the mechanisms proposed by Bolot, Turletti and Wakeman (1994), and Nonnenmacher and Biersack (see Proceedings of IEEE INFOCOM '98, Los Alamitos, California, IEEE Computer Society Press, 1998).

Packet delay and loss traces are frequently used by network engineers, as well as network applications, to analyze network performance. The clocks on the end-systems used to measure the delays, however, are not always synchronized, and this lack of synchronization reduces the accuracy of these measurements. Therefore, estimating and removing relative skews and offsets from delay measurements between sender and receiver clocks are critical to the accurate assessment and analysis of network performance. We introduce a linear programming-based algorithm to estimate the clock skew in network delay measurements and compare it with three other algorithms. We show that our algorithm has a time complexity of O(N), leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. We use traces of real Internet delay measurements to assess the algorithm, and compare its performance to that of three other algorithms. Furthermore, we show through simulation that our algorithm is unbiased, and that the sample variance of the skew estimate is better (smaller) than existing algorithms.

We propose and evaluate novel reliable multicast protocols that combine active repair service (a.k.a. local recovery) and parity encoding (a.k.a. forward error correction or FEC) techniques. We show that, compared to other repair service protocols, our protocols require less buffer inside the network, maintain the low bandwidth requirements of previously proposed repair service/FEC combination protocols, and reduce the amount of FEC processing at repair servers, moving more of this processing to the end-hosts. We also examine repair service/FEC combination protocols in an environment where loss rates differ across domains within the network. We find that repair services are more effective than FEC at reducing bandwidth utilization in such environments. Furthermore, adding FEC to a repair services protocol not only reduces buffer requirements at repair servers, but also reduces bandwidth utilization in domains with high loss, or in domains with large populations of receivers.

High latency and loss rates in the Internet make it difficult to stream audio and video without introducing a large playback delay. To address these problems, we propose a prefix caching technique whereby a proxy stores the initial frames of popular clips. Upon receiving a request for the stream, the proxy initiates transmission to the client and simultaneously requests the remaining frames from the server. In addition to hiding the delay, throughput, and loss effects of a weaker service model between the server and the proxy, this novel yet simple prefix caching technique aids the proxy in performing workahead smoothing into the client playback buffer. By transmitting large frames in advance of each burst, workahead smoothing substantially reduces the peak and variability of the network resource requirements along the path from the proxy to the client. We describe how to construct a smooth transmission schedule, based on the size of the prefix, smoothing, and playback buffers, without increasing client playback delay. Experiments with MPEG traces show how a few megabytes of buffer space at the proxy can substantially reduce the bandwidth requirements of variable-bit-rate video. Drawing on these results, we present guidelines for allocating buffer space for each stream, and how to effectively share buffer and bandwidth resources among multiple clients and streams.

A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. We propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, the optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.

Understanding and modelling packet loss in the Internet is especially relevant for the design and analysis of delay-sensitive multimedia applications. We present analysis of 128 hours of end-to-end unicast and multicast packet loss measurement. From these we selected 76 hours of stationary traces for further analysis. We consider the dependence as seen in the autocorrelation function of the original loss data as well as the dependence between good run lengths and loss run lengths. The correlation timescale is found to be 1000 ms or less. We evaluate the accuracy of three models of increasing complexity: the Bernoulli model, the 2-state Markov chain model and the k-th order Markov chain model. Out of the 38 trace segments considered, the Bernoulli model was found to be accurate for 7 segments, and the 2-state model was found to be accurate for 10 segments. A Markov chain model of order 2 or greater was found to be necessary to accurately model the rest of the segments. For the case of adaptive applications which track loss, we address two issues of on-line loss estimation: the required memory size and whether to use exponential smoothing or a sliding window average to estimate average loss rate. We find that a large memory size is necessary and that the sliding window average provides a more accurate estimate for the same effective memory size.

We present a novel video streaming technique called catching for on-demand delivery of “hot” (i.e., frequently accessed) video objects to a large number of clients. This technique not only significantly reduces the server and network resource requirements but also is capable of providing near-instantaneous service to a large number of clients. By combining this technique for delivery of “hot” video objects with controlled multicast [4] for delivery of “cold” video objects, we design an efficient video delivery scheme referred to as selective catching. Through empirical studies, we demonstrate the efficacy of the proposed video delivery schemes.

169-182

No abstract available.

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work

We study the problem of resource allocation and control for a network node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth tradeoff under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests that sources sharing a network node with finite bandwidth and buffer space divide into groups according to time scales defined by their leaky-bucket parameters. This time-scale separation determines the manner by which the buffer and bandwidth resources at the network node are shared among the sources. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexer using the "extremal" on-off, periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth tradeoff is again determined by a time-scale separation.

The burstiness of compressed video complicates the provisioning of network resources for emerging multimedia services. For stored video applications, the server can smooth the variable-bit-rate stream by transmitting frames into the client playback buffer in advance of each burst. Drawing on prior knowledge of the frame lengths and client buffer size, such bandwidth-smoothing techniques can minimize the peak and variability of the rate requirements while avoiding underflow and overflow of the playback buffer. However, in an internetworking environment, a single service provider typically does not control the entire path from the stored-video server to the client buffer. This paper presents efficient techniques for transmitting variable-bit-rate video across a portion of the route, from an ingress node to an egress node. We develop efficient techniques for minimizing the network bandwidth requirements by characterizing how the peak transmission rate varies as a function of the playback delay and the buffer allocation at the two nodes. We present an efficient algorithm for minimizing both the playback delay and the buffer allocation, subject to a constraint on the peak transmission rate. We then describe how to compute an optimal transmission schedule for a sequence of nodes by solving a collection of independent single-link problems, and show that the optimal resource allocation places all buffers at the ingress and egress nodes. Experiments with motion-JPEG and MPEG traces show the interplay between buffer space, playback delay, and bandwidth requirements for a collection of full-length video traces.

Controlling the rate of bulk data multicast to a large number of receivers is difficult due to the heterogeneity among the end-systems' capabilities and their available network bandwidth. If the data transfer rate is too high, some receivers will lose data, and retransmissions will be required. If the data transfer rate is too low, an inordinate amount of time will be required to transfer the data. In this paper, we examine an approach towards rate-controlled multicast of bulk data in which the sender uses multiple multicast groups to transmit data at different rates to different sub-groups of receivers. We present simple algorithms for determining the transmission rate associated with each multicast channel, based on static resource constraints, e.g., network bandwidth bottlenecks. Transmission rates are chosen so as to minimize the average time needed to transfer data to all receivers. Analysis and simulation are used to show that our policies for rate selection perform well for large and diverse receiver groups and make efficient use of network bandwidth. Moreover, we find that only a small number of multicast groups are needed to reap most of the possible performance benefits.

Local recovery approaches for reliable multicast have the potential to provide significant performance gains in terms of reduced bandwidth and delay, and higher system throughput. In this paper we examine two local recovery approaches-one server-based, and the other receiver-based, and compare their performance. The server-based approach makes use of specially designated hosts, called repair servers, co-located with routers inside the network. In the receiver-based approach, only the end hosts (sender and receivers) are involved in error recovery. Using analytical models, we first show that the two local recovery approaches yield significantly higher protocol throughput and lower bandwidth usage than an approach that does not use local recovery. Next, we demonstrate that server-based local recovery yields higher protocol throughput and lower bandwidth usage than receiver-based local recovery when the repair servers have processing power slightly higher than that of a receiver and several hundred kilobytes of buffer per multicast session.