Generative models have shown promising results in capturing human mobility characteristics and generating synthetic trajectories. However, it remains challenging to ensure that the generated geospatial mobility data is semantically realistic, including consistent location sequences, and reflects real-world characteristics, such as constraining on geospatial limits. We reformat human mobility modeling as an autoregressive generation task to address these issues, leveraging the Generative Pre-trained Transformer (GPT) architecture. To ensure its controllable generation to alleviate the above challenges, we propose a geospatially-aware generative model, MobilityGPT. We propose a gravity-based sampling method to train a transformer for semantic sequence similarity. Then, we constrained the training process via a road connectivity matrix that provides the connectivity of sequences in trajectory generation, thereby keeping generated trajectories in geospatial limits. Lastly, we proposed to construct a preference dataset for fine-tuning MobilityGPT via Reinforcement Learning from Trajectory Feedback (RLTF) mechanism, which minimizes the travel distance between training and the synthetically generated trajectories. Experiments on real-world datasets demonstrate MobilityGPT’s superior performance over state-of-the-art methods in generating high-quality mobility trajectories that are closest to real data in terms of origin-destination similarity, trip length, travel radius, link, and gravity distributions. We release the source code and reference links to datasets athttps://github.com/ammarhydr/MobilityGPT

Active learning is a promising strategy for reducing annotation burdens in medical image segmentation, particularly for tasks like skin lesion segmentation, where expert annotations are costly and time-intensive. However, existing methods suffer from cold-start issues and inefficient sample selection. This paper introduces a novel active learning framework called Task-Aligned Iterative Active Learning (TAIAL) that employs clustering and entropy ranking on a progressively refined feature space to select active samples that balance diversity, informativeness, and uncertainty. Coupled with a self-supervised initialization step, TAIAL provides an effective solution for both the cold-start problem and sample selection. Extensive experiments on the ISIC17 dataset demonstrate that TAIAL achieves early-stage sample selection performance, representing a 32% improvement over random sampling and an average improvement of 27% over other active learning schemes. In the later stage, it reaches 98.7% of fully supervised performance with only 38.4% labeled data, outperforming baseline methods. Our approach provides a scalable and efficient active learning paradigm for annotation-constrained medical imaging applications.

Autism Spectrum Disorder (ASD) presents significant challenges in early diagnosis and intervention, impacting children and their families. With prevalence rates rising, there is a critical need for accessible and efficient screening tools. Leveraging machine learning (ML) techniques, in particular Temporal Action Localization (TAL), holds promise for automating ASD screening. This paper introduces a self-attention based TAL model designed to identify ASD-related behaviors in infant videos. Unlike existing methods, our approach simplifies complex modeling and emphasizes efficiency, which is essential for practical deployment in real-world scenarios. Importantly, this work underscores the importance of developing computer vision methods capable of operating in naturilistic environments with little equipment control, addressing key challenges in ASD screening. This study is the first to conduct end-to-end temporal action localization in untrimmed videos of infants with ASD, offering promising avenues for early intervention and support. We report baseline results of behavior detection using our TAL model. We achieve 70% accuracy for look face, 79% accuracy for look object, 72% for smile and 65% for vocalization.

Current image anonymization techniques, largely focus on localized pseudonymization, typically modify identifiable features like faces or full bodies and evaluate anonymity through metrics such as detection and re-identification rates. However, this approach often overlooks information present in the entire image post-anonymization that can compromise privacy, such as specific locations, objects/items, or unique attributes. Acknowledging the pivotal role of human judgment in anonymity, our study conducts a thorough analysis of perceptual anonymization, exploring its spectral nature and its critical implications for image privacy assessment, particularly in light of regulations such as the General Data Protection Regulation (GDPR). To facilitate this, we curated a dataset specifically tailored for assessing anonymized images. We introduce a learning-based metric, PerceptAnon, which is tuned to align with the human Perception of Anonymity. PerceptAnon evaluates both original-anonymized image pairs and solely anonymized images. Trained using human annotations, our metric encompasses both anonymized subjects and their contextual backgrounds, thus providing a comprehensive evaluation of privacy vulnerabilities. We envision this work as a milestone for understanding and assessing image anonymization, and establishing a foundation for future research. The codes and dataset are available in https://github.com/SonyResearch/gdpr_perceptanon.

Unsupervised Domain Adaptation (UDA) aims to leverage the labeled source domain to solve the tasks on the unlabeled target domain. Traditional UDA methods face the challenge of the tradeoff between domain alignment and semantic class discriminability, especially when a large domain gap exists between the source and target domains. The efforts of applying large-scale pre-training to bridge the domain gaps remain limited. In this work, we propose that Vision-Language Models (VLMs) can empower UDA tasks due to their training pattern with language alignment and their large-scale pre-trained datasets. For example, CLIP and GLIP have shown promising zero-shot generalization in classification and detection tasks. However, directly fine-tuning these VLMs into downstream tasks may be computationally expensive and not scalable if we have multiple domains that need to be adapted. Therefore, in this work, we first study an efficient adaption of VLMs to preserve the original knowledge while maximizing its flexibility for learning new knowledge. Then, we design a domain-aware pseudo-labeling scheme tailored to VLMs for domain disentanglement. We show the superiority of the proposed methods in four UDA-classification and two UDA-detection benchmarks, with a significant improvement (+9.9%) on DomainNet.

Differentially-private (DP) Generative Adversarial Networks (GAN) can be used to protect the privacy of training data and support public downstream learning tasks with synthetic data. However, typical DP mechanisms add noise to the training process and can lead to various convergence problems. We propose HE-GAN, a DP generative framework that eliminates noise addition by using Exponential Mechanism (EM) on the privacy-factor-adjusted posterior predictive distribution of a classifier trained on the private data. EM is more general than many other DP mechanisms including Laplacian and Gaussian mechanisms. EM’s reliance on sampling the output space also prevents the DP noise from corrupting the training process. However, there are two challenges: first, sampling the posterior distribution of the private discriminative classifier may not be able to produce high-quality synthetic samples. Instead, we sample from the latent space of a publicly-trained GAN to optimize the private posterior. Second, we use the highly effective Hamiltonian Monte Carlo (HMC) method for latent space sampling. We perform experiments on MNIST and Fashion-MNIST under public-private splits. Results show that HE-GAN can achieve downstream classification accuracy on par with or better than state-of-the-art scheme over a wide range of privacy budgets.

Traditional Unsupervised Domain Adaptation (UDA) leverages the labeled source domain to tackle the learning tasks on the unlabeled target domain. It can be more challenging when a large domain gap exists between the source and the target domain. A more practical setting is to utilize a large-scale pre-trained model to fill the domain gap. For example, CLIP shows promising zero-shot generalizability to bridge the gap. However, after applying traditional fine-tuning to specifically adjust CLIP on a target domain, CLIP suffers from catastrophic forgetting issues where the new domain knowledge can quickly override CLIP’s pre-trained knowledge and decreases the accuracy by half. We propose Catastrophic Forgetting Measurement (CFM) to adjust the learning rate to avoid excessive training (thus mitigating the catastrophic forgetting issue). We then utilize CLIP’s zero-shot prediction to formulate a Pseudo-labeling setting with Adaptive Debiasing in CLIP (PADCLIP) by adjusting causal inference with our momentum and CFM. Our PADCLIP allows end-to-end training on source and target domains without extra overhead. We achieved the best results on four public datasets, with a significant improvement (+18.5% accuracy) on DomainNet.

Dicrotic Notch (DN), one of the most significant and indicative features of the arterial blood pressure (ABP) waveform, becomes less pronounced and thus harder to identify as a matter of aging and pathological vascular stiffness. Generalizable and automatic DN identification for such edge cases is even more challenging in the presence of unexpected ABP waveform deformations that happen due to internal and external noise sources or pathological conditions that cause hemodynamic instability. We propose a physics-aware approach, named Physiowise (PW), that first employs a cardiovascular model to augment the original ABP waveform and reduce unexpected deformations, then apply a set of predefined rules on the augmented signal to find DN locations. We have tested the proposed method on in-vivo data gathered from 14 pigs under hemorrhage and sepsis study. Our result indicates 52% overall mean error improvement with 16% higher detection accuracy within the lowest permitted error range of 30 ms. An additional hybrid methodology is also proposed to allow combining augmentation with any application-specific user-defined rule set.

Human mobility trajectories provide valuable information for developing mobility applications, as they contain diverse and rich information about the users. User mobility data is valuable for various applications such as intelligent transportation systems (ITS), commercial business models, and disease-spread models. However, such spatio-temporal traces may pose a threat to user privacy. GPS trajectories in their raw form are not suitable for transportation studies, as they require matching locations with nearest road links — a process called map-matching. This paper presents a differential privacy (DP)-based map-matching algorithm, called DPMM, that generates link-level location trajectories in a privacy-preserving manner to protect users’ origin destinations (OD) and travel paths. OD privacy is achieved by injecting Planar Laplace noise to the user OD GPS points. Travel-path privacy is provided with randomized travel path construction using exponential DP mechanism. The injected noise level is selected adaptively, by considering the link density of the location and the functional category of the localized links. For path privacy, our mechanism samples waypoints and selects candidate paths between waypoints. DPMM provides privacy effectively with respect to link density instead of other trajectory samples in the database compared to other privacy mechanisms. Compared to the different baseline models our DP-based privacy model offers closer query responses to the raw data in terms of individual and aggregate trajectory-level statistics with an average at absolute deviation from the baseline for individual statistics on ϵ = 1.0. Beyond individual trajectory statistics, the DPMM outperforms the other benchmark DP-based mechanisms on different aggregate statistics with up to 8x improvement in utility.

The advancement of deep neural networks (DNNs) motivates the deployment in various domains, including image classification, disease diagnoses, voice recognition, etc. Since some tasks that DNN undertakes are very sensitive, the label information is confidential and contains a commercial value or critical privacy. This paper demonstrates that DNNs also bring a new security threat, leading to the leakage of label information of input instances for the DNN models. In particular, we leverage the cache-based side-channel attack (SCA), i.e., Flush-Reload on the DNN (victim) models, to observe the execution of computation graphs, and create a database of them for building a classifier that the attacker can use to decide the label information of (unknown) input instances for victim models. Then we deploy the cache-based SCA on the same host machine with victim models and deduce the labels with the attacker's classification model to compromise the privacy and confidentiality of victim models. We explore different settings and classification techniques to achieve a high attack success rate of stealing label information from the victim models. Additionally, we consider two attacking scenarios: binary attacking identifies specific sensitive labels and others while multi-class attacking targets recognize all classes victim DNNs provide. Last, we implement the attack on both static DNN models with identical architectures for all inputs and dynamic DNN models with an adaptation of architectures for different inputs to demonstrate the vast existence of the proposed attack, including DenseNet 121, DenseNet 169, VGG 16, VGG 19, MobileNet v1, and MobileNet v2. Our experiment exhibits that MobileNet v1 is the most vulnerable one with 99% and 75.6% attacking success rates for binary and multi-class attacking scenarios, respectively.

Embedded systems for edge computing are getting more powerful, and some are equipped with a GPU to enable on-device deep neural network (DNN) learning tasks such as image classification and object detection. Such DNN-based applications frequently deal with sensitive user data, and their architectures are considered intellectual property to be protected. We investigate a potential avenue of fingerprinting attack to identify the (running) DNN model architecture family (out of state-of-the-art DNN categories) on CPU-GPU edge devices. We exploit a stealthy analysis of aggregate system-level side-channel information such as memory, CPU, and GPU usage available at the user-space level. To the best of our knowledge, this is the first attack of its kind that does not require physical access and/or sudo access to the victim device and only collects the system traces passively, as opposed to most of the existing reverse-engineering-based DNN model architecture extraction attacks. We perform feature selection analysis and supervised machine learning-based classification to detect the model architecture. With a combination of RAM, CPU, and GPU features and a Random Forest-based classifier, our proposed attack classifies a known DNN model into its model architecture family with 99% accuracy. Also, the introduced attack is so transferable that it can detect an unknown DNN model into the right DNN architecture category with 87.2% accuracy. Our rigorous feature analysis illustrates that memory usage (RAM) is a critical feature for such fingerprinting. Furthermore, we successfully replicate this attack on two different CPU-GPU platforms and observe similar experimental results that exhibit the capability of platform portability of the attack. Also, we investigate the robustness of the proposed attack to varying background noises and a modified DNN pipeline. Besides, we exhibit that the leakage of model architecture family information from this stealthy attack can strengthen an adversarial attack against a victim DNN model by 2×.

Despite recent promising results on semi-supervised learning (SSL), data imbalance, particularly in the unlabeled dataset, could significantly impact the training performance of a SSL algorithm if there is a mismatch between the expected and actual class distributions. The efforts on how to construct a robust SSL framework that can effectively learn from datasets with unknown distributions remain limited. We first investigate the feasibility of adding weights to the consistency loss and then we verify the necessity of smoothed weighting schemes. Based on this study, we propose a self-adaptive algorithm, named Smoothed Adaptive Weighting (SAW). SAW is designed to enhance the robustness of SSL by estimating the learning difficulty of each class and synthesizing the weights in the consistency loss based on such estimation. We show that SAW can complement recent consistency-based SSL algorithms and improve their reliability on various datasets including three standard datasets and one gigapixel medical imaging application without making any assumptions about the distribution of the unlabeled set.

There is an increasing trend in the use of wireless communication along with new traffic signal control (TSC) algorithms to leverage and accommodate connected and autonomous vehicles. However, this development has increased the potential for cyber-attacks on TSC that can undermine the benefits of these new algorithms. An advanced persistent adversary can learn the behavior of TSC algorithms and launch attacks to preferentially get green time and/or to create traffic congestion in one intersection which can spread to the entire network. In this paper, we consider backpressure-based (BP-based) TSC algorithms and compare their performance under two misinformation attacks - 1) time spoofing attack in which vehicles alter their arrival times at the intersection and 2) ghost vehicle attack in which vehicles disconnect the wireless communication and thereby hide from the TSC. We show that these misinformation can influence the signal phases determined by BP-based TSC algorithms. We consider an adversary that determines a set of arriving vehicles to be attack vehicles from many candidate sets (attack strategies) in order to maximize the number of disrupted signal phases. We show that by formulating the problem as a 0/1 Knapsack problem, the adversary can explore the space of attack strategies and determine the optimal strategy that maximally compromises the performance in terms of average delay and fairness. We propose two protection algorithms, namely, auction-based (APA) and hybrid-based (HPA) algorithms and show that they are able to mitigate the impacts of the misinformation attacks.

The adoption of virtualization and cloud computing technologies have revolutionized how services and applications can be developed, deployed, and operated to achieve better elasticity, flexibility, and scalability. Multiple stakeholders can be involved for providing online services; each of them plays one or more roles (i.e., service operator, application vendor, and infrastructure provider) to create a customized operating model based on the business requirements. The operating model changes from one business to another, and it may even change at different stages of the same business. A trusted relationship among stakeholders for secure information exchange is the key to enable such flexibility. However, traditional usage compliance methods (e.g., in-person audit, dynamic licensing, and subscription) lack explicit trust among involved parties and the flexibility and scalability to support dynamic sizing of services and applications with low overhead. In this work, we argue the need for a new trust framework to manage application usage rights and propose Metered Boot to provide trusted, capacity/usage-based usage rights management for services and applications deployed in virtualized environments. Metered Boot decouples application workload instantiation for service operators, usage rights governance for application vendors, and resource provisioning for infrastructure providers. We leverage cryptoprocessors (e.g., Trusted Platform Module (TPM)) on commodity servers to generate trusted proofs which are managed by efficient cryptographic construction, Merkle hash tree, for usage rights compliance. We integrated our framework with OpenStack and demonstrate that Metered Boot is able to achieve high scalability and low overhead for instantiating virtual network functions (VNFs).

The available bandwidth (ABW) of a network path is a crucial metric for various applications, such as traffic engineering, congestion control, multimedia streaming, and path selection in software-defined wide-area networks (SDWAN). In recent years, a new class of measurement methods have been proposed to estimate the available bandwidth, decreasing-chirp-train methods. However, the performance and limitations of this new class of methods are neither well studied nor fairly compared beyond simulation studies. In this work, we implement Voyager, a modular framework that allows us to conduct a fair and thorough comparison of how a variety of modern bandwidth estimation methods perform under different network paths and traffic conditions. We shed light on the characteristics and limitations of the internal algorithms of various methods, and propose two new methods. We investigate the impact of various bottleneck types and traffic types, and we explore the performance of these methods on high speed links where interrupt coalescence can cause measurement noise. We finally test Voyager on long-distance Internet links and with live traffic and report our findings.

One major source of air pollution is automobile emissions in urban areas. Although hybrid and fully electric vehicles are started to gain popularity, the majority of vehicles are still fuel-based. With the rapid advancement of artificial intelligence (AI) and automation based controllers, there have been numerous studies applying such learning-based techniques to Intelligent Transportation Systems (ITS). Combining deep neural networks with reinforcement learning (RL) models called DRL has shown promising results when applied to urban Traffic Signal Control (TSC) for adaptive adjustment of traffic light schedules. Centralized and decentralized DRL-based controller models are proposed in literature to optimize the total system travel time. However, the associated impact of such learning-based TSCs to the air quality remains unexplored. In this paper, we examine the impact of DRL-based TSCs on the environment in terms of fuel consumption and CO2 emission. We studied a major DRL approach called advantage actor-critic (A2C) using multi-agent settings on a synthetic multi-intersection network and on a real traffic network of San Francisco downtown with 24 hours traffic dataset. Our initial results indicate that learning based DRL methods achieved the lowest air pollution level on synthetic networks even with a simple delay-based reward function. However, DRL-based TSC performs slightly worse than rule-based adaptive TSCs (max-pressure control) in the San Francisco network.

Early diagnosis of Autism Spectrum Disorder (ASD) is crucial for best outcomes to interventions. In this paper, we present a machine learning (ML) approach to ASD diagnosis based on identifying specific behaviors from videos of infants of ages 6 through 36 months. The behaviors of interest include directed gaze towards faces or objects of interest, positive affect, and vocalization. The dataset consists of 2000 videos of 3-minute duration with these behaviors manually coded by expert raters. Moreover, the dataset has statistical features including duration and frequency of the above mentioned behaviors in the video collection as well as independent ASD diagnosis by clinicians. We tackle the ML problem in a two-stage approach. Firstly, we develop deep learning models for automatic identification of clinically relevant behaviors exhibited by infants in a one-on-one interaction setting with parents or expert clinicians. We report baseline results of behavior classification using two methods: (1) image based model (2) facial behavior features based model. We achieve 70% accuracy for smile, 68% accuracy for look face, 67% for look object and 53% accuracy for vocalization. Secondly, we focus on ASD diagnosis prediction by applying a feature selection process to identify the most significant statistical behavioral features and a over and under sampling process to mitigate the class imbalance, followed by developing a baseline ML classifier to achieve an accuracy of 82% for ASD diagnosis.

Software-Defined Networking (SDN) provides programmable, flexible and fine-grained traffic control capability, which paves the way for realizing dynamic and high-performance traffic measurement and traffic engineering. In the SDN paradigm, the traffic forwarding and measurement strategies are realized through flow tables stored in the Tenantry Content Addressable Memories (TCAM) of SDN switches. However, the number of TCAM entries in SDN switches is limited. In this paper, we aim to jointly optimize the Traffic Matrix Measurement (TMM) and Traffic Engineering (TE) process under the TCAM capacity and flow aggregation constraints in software-defined networks. We first formulate the joint optimization problem as a Mixed Integer Linear Programming (MILP) model. Then to get an initial traffic matrix for the joint optimization problem, we propose a simple flow rule generation strategy named Maximum Load Rule First (MLRF) to efficiently generate feasible flow rules, which are used to provide direct measurements for the traffic matrix measurement problem. At last, to solve the joint optimization efficiently, we propose two efficient heuristic algorithms named Traffic Matrix Measurement First (TMMF) and Traffic Engineering First (TEF), respectively. TMMF and TEF can generate feasible flow rules for realizing TMM and TE strategies. Our evaluations on real network topologies and traffic traces verify that by jointly optimizing the TMM and TE strategies, both TMMF and TEF can significantly improve TMM accuracy and TE objective (i.e., load balancing) with limited TCAM resource.

Troubleshooting a vehicle often requires some form of customer service; to help guide a customer towards a resolution. Consumer reporting of faulty vehicular components can be made via a telephone- based service call, or gathered through telemetry via embedded intelligent transportation systems (ITS). During data transmission, free text is created in the dialogue between the customer and the service representative. While free text is generated, key details of the discussion can be extracted and recorded. This paper describes methods used to process the recorded free text data. This method can help classify and direct the call to the correct channel of support tools and resources. An anonymous customer service report consisting of 75,000 calls was used for feature extraction. Five thousands of the calls were used in supervised learning to support data classifications. The matrix of data was evaluated for accuracy and repeated to minimize error and increase accuracy. By incorporating hand-crafted features using domain expertise, our natural language processing (NLP) based approach can achieve 85 percent accuracy in classifying the service calls.

Learning and exploring the connectivity of unknown networks represent an important problem in practical applications of communication networks and social-media networks. Modeling large-scale networks as connected graphs is highly desirable to extract their connectivity information among nodes to visualize network topology, disseminate data, and improve routing efficiency. This paper investigates a simple measurement model in which a small subset of source nodes collect hop distance information from networked nodes in order to generate a virtual coordinate system (VCS) for networks of unknown topology. We establish the VCS to define logical distance among nodes based on principal component analysis and to determine connectivity relationship and effective routing methods. More importantly, we present a robust analytical algorithm to derive the VCS against practical issues of missing and corrupted measurements. We also develop a connectivity inference method which classifies nodes into layers based on the hop distances and derives partial information on network connectivity.

Cloudification of edge to core infrastructure has led to new and rich application and service deployment and operational models. These ecosystems have complex relationships between the application vendors, infrastructure operators and application users. Traditional licensing and compliance enforcement methods such as those based on in person audits and dynamic issuing of license keys inhibit the resource provisioning and consumption flexibility offered by cloudified services due to scalability and management overheads. In this work, we argue the need for a trusted framework for application usage rights compliance. This new architecture named "Metered Boot" provides a way to realize trusted, capacity/usage based rights compliance for service deployments that allows decoupling of usage rights governed by application vendors from the resource provisioning by the infrastructure provider. We have built a Metered Boot prototype for a particular usecase of NFV usage rights compliance.

We consider the problem of detecting heavy hitters and hierarchical heavy hitters among a large number of traffic flows modeled as random processes with unknown and potentially heavy-tailed distributions. The objective is an active inference strategy that determines, sequentially, which aggregated flow on the IP-prefix tree to probe in order to minimize the sample complexity under a reliability constraint. We propose an active inference strategy that induces a biased random walk on the flow aggregation tree based on confidence bounds of sample statistics. We then establish its order optimality in terms of both the size of the search space (i.e., the number of traffic flows) and the reliability requirement. The result also finds applications in noisy group testing and adaptive sampling with noisy response.

Content popularity prediction has been extensively studied due to its importance and interest for both users and hosts of social media sites like Facebook, Instagram, Twitter, and Pinterest. However, existing work mainly focuses on modeling popularity using a single metric such as the total number of likes or shares. In this work, we propose Diffusion-LSTM, a memory-based deep recurrent network that learns to recursively predict the entire diffusion path of an image through a social network. By combining user social features and image features, and encoding the diffusion path taken thus far with an explicit memory cell, our model predicts the diffusion path of an image more accurately compared to alternate baselines that either encode only image or social features, or lack memory. By mapping individual users to user prototypes, our model can generalize to new users not seen during training. Finally, we demonstrate our model»s capability of generating diffusion trees, and show that the generated trees closely resemble ground-truth trees.

Learning network topology from partial knowledge of its connectivity is an important objective in practical scenarios of communication networks and social-media networks. Representing such networks as connected graphs, exploring and recovering connectivity information between network nodes can help visualize the network topology and improve network utility. This work considers the use of simple hop distance measurement obtained from a fraction of anchor/source nodes to reconstruct the node connectivity relationship for large scale networks of unknown connection topology. Our proposed approach consists of two steps. We first develop a tree-based search strategy to determine constraints on unknown network edges based on the hop count measurements. We then derive the logical distance between nodes based on principal component analysis (PCA) of the measurement matrix and propose a binary hypothesis test for each unknown edge. The proposed algorithm can effectively improve both the accuracy of connectivity detection and the successful delivery rate in data routing applications.

Various Online Social Network (OSN) based applications depend on the interactions between users to disseminate information and recruit more users. The temporal evolution of adoption or cascade process of new products, applications or ideas is important to advertisers, OSN operators and application developers. Interactions between users are represented by massive directed graphs, so graph sampling methods were proposed to capture their properties. Existing graph sampling methods, such as a simple random walk, however, are ill- suited for capturing this and other dynamic properties of the graph. We propose ForestStream, a measurement method that relies on a combination of sampling and streaming with the goal of capturing the statistical properties of cascades in OSN graphs. We demonstrate our method's accuracy over existing methods in inferring the cascade statistics, with a low memory usage.

Estimation of building occupancy has emerged as an important research problem with applications ranging from building energy efficiency, control and automation, safety, communication network resource allocation, etc. In this research work, we propose the estimation of occupancy using non-intrusive information that is already available from existing sensing modes, namely, number of WiFi devices, electrical energy demand and water consumption rate. Using data collected from 76 buildings in a university campus, we study the feasibility of multi-modal fusion between the three data sources for estimating fine-grained occupancy. In order to make the estimation model scalable, we propose three different clustering schemes to identify similarity in building characteristics and training per-cluster occupancy estimation models. The presented multi-modal fusion estimation framework achieves a mean absolute percentage error of 13.22% and we find that leveraging all three modalities provide an improvement of 48% in accuracy as compared to WiFi-only occupancy estimation. Our evaluation also shows that clustering buildings greatly increases the scalability of the proposed approach through significant reduction in training overhead, while providing an accuracy comparable to exhaustive, per-building estimation models.

To achieve growth in the user base of online social networks--(OSN) based applications, word-of-mouth diffusion mechanisms, such as user-to-user invitations, are widely used. This article characterizes the adoption and cascading process of OSN-based applications that grow via user invitations. We analyze a detailed large-scale dataset of a popular Facebook gifting application, iHeart, that contains more than 2 billion entries of user activities generated by 190 million users during a span of 64 weeks. We investigate (1) how users invite their friends to an OSN-based application, (2) how application adoption of an individual user can be predicted, (3) what factors drive the cascading process of application adoptions, and (4) what are the good predictors of the ultimate cascade sizes. We find that sending or receiving a large number of invitations does not necessarily help to recruit new users to iHeart. We also find that the average success ratio of inviters is the most important feature in predicting an adoption of an individual user, which indicates that the effectiveness of inviters has strong predictive power with respect to application adoption. Based on the lessons learned from our analyses, we build and evaluate learning-based models to predict whether a user will adopt iHeart. Our proposed model that utilizes additional activity information of individual users from other similar types of gifting applications can achieve high precision (83%) in predicting adoptions in the target application (i.e., iHeart). We next identify a set of distinctive features that are good predictors of the growth of the application adoptions in terms of final population size. We finally propose a prediction model to infer whether a cascade of application adoption will continue to grow in the future based on observing the initial adoption process. Results show that our proposed model can achieve high precision (over 80%) in predicting large cascades of application adoptions. We believe our work can give an important implication in resource allocation of OSN-based product stakeholders, for example, via targeted marketing.

The number of wireless-enabled devices owned by a user has had huge growth over the past few years. Over one third of adults in the United States currently own three wireless devices: a smartphone, laptop, and tablet. This article provides a study of the network usage behavior of today’s multidevice users. Using data collected from a large university campus, we provide a detailed multidevice user (MDU) measurement study of more than 30,000 users. The major objective of this work is to study how the presence of multiple wireless devices affects the network usage behavior of users. Specifically, we characterize the usage pattern of the different device types in terms of total and intermittent usage, how the usage of different devices overlap over time, and uncarried device usage statistics. We also study user preferences of accessing sensitive content and device-specific factors that govern the choice of WiFi encryption type. The study reveals several interesting findings about MDUs. We see how the use of tablets and laptops are interchangeable and how the overall multidevice usage is additive instead of being shared among the devices. We also observe how current DHCP configurations are oblivious to multiple devices, which results in inefficient utilization of available IP address space. All findings about multidevice usage patterns have the potential to be utilized by different entities, such as app developers, network providers, security researchers, and analytics and advertisement systems, to provide more intelligent and informed services to users who have at least two devices among a smartphone, tablet, and laptop.

Network inference (or tomography) problems, such as traffic matrix estimation or completion and link loss inference, have been studied rigorously in different networking applications. These problems are often posed as under-determined linear inverse (UDLI) problems and solved in a centralized manner, where all the measurements are collected at a central node, which then applies a variety of inference techniques to estimate the attributes of interest. This paper proposes a novel framework for decentralizing these large-scale under-determined network inference problems by intelligently partitioning it into smaller subproblems and solving them independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate. We apply this Multiple Description and Fusion Estimation (MDFE) framework to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how MDFE can speed up computation while maintaining (even improving) the estimation accuracy and how it enhances robustness against noise and failures. We also show that our MDFE framework is compatible with a variety of existing inference techniques used to solve the UDLI problems.

We revisit the problem of identifying link metrics from end- to-end path measurements in practical IP networks where shortest path routing is the norm. Previous solutions rely on explicit routing techniques (e.g., source routing or MPLS) to construct independent measurement paths for efficient link metric identification. However, most IP networks still adopt shortest path routing paradigm, while the explicit routing is not supported by most of the routers. Thus, this paper studies the link metric identification problem under shortest path routing constraints. To uniquely identify the link metrics, we need to place sufficient number of monitors into the network such that there exist $m$ (the number of links) linear independent shortest paths between the monitors. In this paper, we first formulate the problem as a mixed integer linear programming problem, and then to make the problem tractable in large networks, we propose a Monitor Placement and Measurement Path Selection (MP-MPS) algorithm that adheres to shortest path routing constraints. Extensive simulations on random and real networks show that the MP- MPS gets near-optimal solutions in small networks, and MP- MPS significantly outperforms a baseline solution in large networks.

Mobile advertisements have become the dominant source of revenue for mobile application developers, advertisers and brokers. Using novel sensing techniques and the advanced sensors of mobile devices, it has become feasible to determine a user's fine-grained context such as her location, activity, and interests. This information can be used by the advertisement (ad) brokers to provide more relevant ads to the user based on her context. However, this has led to serious privacy risks, since a user can be tracked by the broker or an adversary based on her context. In this paper, we present AnonAd, an ad delivery scheme that allows users to protect their privacy when receiving micro-targeted ads from the broker. AnonAd utilizes the encryption of the user's context based on a split-secret scheme that guarantees that the broker can decrypt the context only when there exists k other users in the same context. This way, a user's privacy is protected with k-anonymity during the context report. We show that the split-secret scheme integrates seamlessly with existing homomorphic encryption-based schemes that can provide differential privacy for ad click reports. We implement AnonAd on Android smartphones and evaluate it with real users as well as simulated users that follow real mobility traces. Our results show that AnonAd achieves a balance between user's privacy and relevancy of advertisements without the requirement of any additional proxy servers.

A key requirement for network management is the accurate and reliable monitoring of relevant network characteristics. In today's large-scale networks, this is a challenging task due to the hard constraints of network measurement resources. This paper proposes a new framework, SNIPER, which leverages the flexibility provided by Software-Defined Networking (SDN) to design the optimal observation or measurement matrix that can leads to the best achievable estimation accuracy using Matrix Completion (MC) techniques. To cope with the complexity of designing large-scale optimal observation matrices, we use the Evolutionary Optimization Algorithms (EOA) which directly target the ultimate estimation accuracy as the optimization objective function. We evaluate the performance of SNIPER using both synthetic and real network measurement traces from different network topologies and by considering two main applications including per-flow size and delay estimations. Our results show that SNIPER can be applied to a variety of network performance measurements under hard resource constraints. For example, by measuring 8.8\% of per-flow path delays in Harvard network, congested paths can be detected with probability 0.94. To demonstrate the feasibility of our framework, we also have implemented a prototype of SNIPER in Mininet.

This paper demystifies the adoption and cascading process of OSN-based applications that grow via user invitations. We analyze a detailed large-scale dataset of a popular Facebook gifting application, iHeart, that contains more than 2 billion entries of user activities generated by 190 million users during a span of 64 weeks. We investigate: (1) how users invite their friends to an OSN-based application, (2) what factors drive the cascading process of application adoptions, and (3) what are the good predictors of the ultimate cascade sizes. We find that sending or receiving a large number of invitations does not necessarily help to recruit new users to iHeart. We also identify a set of distinctive features that are good predictors of the growth of the application adoptions in terms of final population size. Finally, based on the insights learned from our analyses, we propose a prediction model to infer whether a cascade of application adoption will continue to grow in the future based on observing the initial adoption process. Results show our proposed model can achieve high precision (over 80%) in iHeart as well as in another OSN-based gifting application, Hugged.

There has been a huge growth in the number of wireless-enabled devices possessed by a user. Over two third of adults in United States currently own three devices - laptop, smartphone and tablet. In this paper, we provide a first look at the network usage behavior of today's multi-device users. Using the data collected from a large university campus, we provide a detailed measurement-based characterization study of over 30,000 users. Our objective is to understand how existence of multiple wireless devices affect the network usage behavior of users. Specifically, we study the usage pattern of devices, how the usage of difference devices overlap in time, user's preferences of accessing sensitive content and device-specific factors that govern their choice of WiFi encryption type. The study reveals numerous interesting findings such as how current DHCP configurations are oblivious to multiple devices which results in inefficient utilization of available IP address space.

Network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load-EqualIzed meaSUREment), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support both fixed and flexible monitor deployment scenarios. We formulate the latter flexible monitor deployment case as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75× smaller peak workload and 70× smaller variance in workloads) across all coordinated monitors in comparison to a naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks under the fixed monitor deployment scenario. We also show that under the flexible monitor deployment setting, our heuristic solutions can achieve almost the same load-balancing performance as the optimal solution while reducing the computation times by a factor up to 22.5× in Abilene and 800× in GEANT.

The rise of location-based services has enabled many opportunities for content service providers to optimize the content delivery based on user's location. Since sharing precise location remains a major privacy concern among the users, many location-based services rely on contextual location (e.g. residence, cafe etc.) as opposed to acquiring user's exact physical location. In this paper, we present PACL (Privacy-Aware Contextual Localizer), which can learn user's contextual location just by passively monitoring user's network traffic. PACL can discern a set of vital attributes (statistical and application-based) from user's network traffic, and predict user's contextual location with a very high accuracy. We design and evaluate PACL using real-world network traces of over 1700 users with over 100 gigabytes of total data. Our results show that PACL (built using decision tree) can predict user's contextual location with the accuracy of around 87%.

Fine-grained traffic flow measurement, which provides useful information for network management tasks and security analysis, can be challenging to obtain due to monitoring resource constraints. The alternate approach of inferring flow statistics from partial measurement data has to be robust against dynamic temporal/spatial fluctuations of network traffic. In this paper, we propose an intelligent Traffic (de)Aggregation and Measurement Paradigm (iSTAMP), which partitions TCAM entries of switches/routers into two parts to: 1) optimally aggregate part of incoming flows for aggregate measurements, and 2) de-aggregate and directly measure the most informative flows for per-flow measurements. iSTAMP then processes these aggregate and per-flow measurements to effectively estimate network flows using a variety of optimization techniques. With the advent of Software-Defined-Networking (SDN), such real-time rule (re)configuration can be achieved via OpenFlow or other similar SDN APIs. We first show how to design the optimal aggregation matrix for minimizing the flow-size estimation error. Moreover, we propose a method for designing an efficient-compressive flow aggregation matrix under hard resource constraints of limited TCAM sizes. In addition, we propose an intelligent Multi-Armed Bandit based algorithm to adaptively sample the most “rewarding” flows, whose accurate measurements have the highest impact on the overall flow measurement and estimation performance. We evaluate the performance of iSTAMP using real traffic traces from a variety of network environments and by considering two applications: traffic matrix estimation and heavy hitter detection. Also, we have implemented a prototype of iSTAMP and demonstrated its feasibility and effectiveness in Mininet environment.

Streaming network traffic measurement and analysis is critical for detecting and preventing any real-time anomalies in the network. The high speeds and complexity of today's networks, coupled with ever evolving threats, necessitate closing of the loop between measurements and their analysis in real time. The ensuing system demands high levels of programmability and processing where streaming measurements adapt to the changing network behavior in a goal-oriented manner. In this work, we exploit the features and requirements of the problem and develop an application-specific FPGA-based closed-loop measurement (CLM) system. We make novel use of fine-grained partial dynamic reconfiguration (PDR) as underlying reprogramming paradigm, performing low-latency just-in-time compiled logic changes in FPGA fabric corresponding to the dynamic measurement requirements. Our innovative dynamically reconfigurable socket offers 3× logic savings over conventional static solutions, while offering much reduced reconfiguration latencies over conventional PDR mechanisms. We integrate multiple sockets in a highly parallel CLM framework and demonstrate its effectiveness in identifying heavy flows in streaming network traffic. The results using an FPGA prototype offer 100 percent detection accuracy while sustaining increasing link speeds.

In a multi-tenant data center environment, the current paradigm for route control customization involves a labor-intensive ticketing process where tenants submit route control requests to the landlord. This results in tight coupling between tenants and the landlord, extensive human resource deployment, and long ticket resolution time. We propose Routing-as-a-Service (RaaS), a framework for tenant-directed route control in data centers. We show that RaaS-based implementation provides a route control platform where multiple tenants can perform route control independently with little administrative involvement, and the landlord can set the overall network policies. RaaS-based solutions can run on commercial off-the-shelf (COTS) hardware and leverage existing technologies, so it can be implemented in existing networks without major infrastructural overhaul. We present the design of RaaS, introduce its components, and evaluate a prototype based on RaaS.

Online network traffic measurements and analysis is critical for detecting and preventing any real-time anomalies in the network. We propose, implement, and evaluate an online, adaptive measurement platform, which utilizes real-time traffic analysis results to refine subsequent traffic measurements. Central to our solution is the concept of Multi-Resolution Tiling (MRT), a heuristic approach that performs sequential analysis of traffic data to zoom into traffic subregions of interest. However, MRT is sensitive to transient traffic spikes. In this paper, we propose three novel traffic streaming algorithms that overcome the limitations of MRT and can cater to varying degrees of computational and storage budgets, detection latency, and accuracy of query response. We evaluate our streaming algorithms on a highly parallel and programmable hardware as well as a traditional software-based platforms. The algorithms demonstrate significant accuracy improvement over MRT in detecting anomalies consisting of synthetic hard-to-track elephant flows and global icebergs. Our proposed algorithms maintain the worst-case complexities of the MRT while incurring only a moderate increase in average resource utilization.

We have previously introduced Multiple Description Fusion Estimation (MDFE) framework that partitions a large-scale Under-Determined Linear Inverse (UDLI) problem into smaller sub-problems that can be solved independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate [1]. In this paper, we extend MDFE framework to make it compatible with Compressive Sensing (CS) network inference, where the attributes of interests (i.e. unknowns) are fluctuating rapidly over time and/or space. For this purpose, we propose a new clustering based technique to intelligently divide a large-scale compressive sensing problem into smaller sub-problems where observations between sub-spaces contain redundancy. We apply this new framework, referred to as Compressive Sensing MDFE (CS-MDFE), to three classical inference problems in networking: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how CS-MDFE can improve the estimation accuracy and speed up computation time, and how it enhances robustness against noise and failures. We also show that this framework is compatible with different CS inference techniques.

Two forms of network inference (or tomography) problems have been studied rigorously: (a) traffic matrix estimation or completion based on link-level traffic measurements, and (b) link-level loss or delay inference based on end-to-end measurements. These problems are often posed as underdetermined linear inverse (UDLI) problems and solved in a centralized manner, where all the measurements are collected at a central node, which then applies a variety of inference techniques to estimate the attributes of interest. This paper proposes a novel framework for decentralizing these large-scale UDLI network inference problems by intelligently partitioning it into smaller sub-problems and solving them independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate. We apply this Multiple Description and Fusion Estimation (MDFE) framework to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how MDFE can speed up computation time while maintaining (even improving) the estimation accuracy and how it enhances robustness against noise and failures. We also show that our MDFE framework is compatible with a variety of existing inference techniques used to solve the UDLI problems.

While various models have been proposed for generating social/friendship network graphs, the dynamics of user interactions through online social network (OSN) based applications remain largely unexplored. We previously developed a growth model to capture static weekly snapshots of user activity graphs (UAGs) using data from popular Facebook gifting applications. This paper presents a new continuous graph evolution model aimed to capture microscopic user-level behaviors that govern the growth of the UAG and collectively define the overall graph structure. We demonstrate the utility of our model by applying it to forecast the number of active users over time as the application transitions from initial growth to peak/mature and decline/fatique phase. Using empirical evaluations, we show that our model can accurately reproduce the evolution trend of active user population for gifting applications, or other OSN applications that employ similar growth mechanisms. We also demonstrate that the predictions from our model can guide the generation of synthetic graphs that accurately represent empirical UAG snapshots sampled at different evolution stages.

The Domain Name System (DNS) provides a critical service for the Internet -- mapping of user-friendly domain names to their respective IP addresses. Yet, there is no standard set of metrics quantifying the Quality of Domain Name Service (QoDNS), let alone a thorough evaluation of it. This article attempts to fill this gap from the perspective of a DNS proxy/cache, which is the bridge between clients and authoritative servers. We present an analytical model of DNS proxy operations that offers insights into the design trade-offs of DNS infrastructure and the selection of critical DNS parameters. Due to the critical role DNS proxies play in QoDNS, they are the focus of attacks including cache poisoning attack. We extend the analytical model to study DNS cache poisoning attacks and their impact on QoDNS metrics. This analytical study prompts us to present Domain Name Cross-Referencing (DoX), a peer-to-peer systems for DNS proxies to cooperatively defend cache poisoning attacks. Based on QoDNS, we compare DoX with the cryptography-based DNS Security Extension (DNSSEC) to understand their relative merits.

Recent technological advances have resulted in a dramatic change in the market shares of cellular mobile devices. However, little is known about the impact of these changes on the landscape of cellular network traffic. Using anonymized traces from one million cellular subscribers, we conduct a comparative study of the usage characteristics of three different types of mobile devices: feature phones, air cards, and smart phones. Our study covers three aspects: traffic volume in terms of data, voice, and short messages and corresponding temporal fluctuations, applications breakdown in data access, and the presence of malicious traffic. Our study reveals some similarities as well as distinct differences among the three device types. These insights into the modern cellular network traffic could influence how cellular carriers manage and provision their networks.

We employ user activity data from three highly popular gifting applications on Facebook to study the evolution of user activity on applications through the most commonly-used growth mechanism, namely Application Requests. We find user activity graphs differ from friendship graphs in large part due to the inherent directionality of user activity, and node transience. Our results show that, unlike degree distributions in friendship graphs, activity graphs exhibit strong asymmetry in in- and out-degree distributions, and that out-degrees are not accurately described by currently known parametric distributions. As such, user activity graphs cannot be simulated through existing intent- and feature-driven algorithms that can model friendship graphs.

Network-wide traffic measurement is important for various network management tasks, ranging from traffic accounting, traffic engineering, and network troubleshooting to security. Existing techniques for traffic measurement tend to be sub-optimal due to poor choice of monitor deployment location or due to constantly evolving monitoring objectives and traffic characteristics. It is not feasible to dynamically reconfigure/redeploy monitoring infrastructure to satisfy such evolving measurement requirements. In this paper, we present a distributed measurement-aware traffic engineering protocol based on a game-theoretic re-routing policy that attempts to optimally utilize existing monitor locations for maximizing the traffic measurement gain while ensuring that the traffic load distribution across the network satisfies some traffic engineering constraint. We introduce a novel cost function on each link that reflects both the measurement gain and the traffic engineering (TE) constraint. Individual routers compete with each other (in a game) to minimize their own costs for the downstream paths, i.e., each router dynamically gathers its cost information for upstream routers and use it to locally decide how to adjust traffic split ratios for each destination to the next-hop routers among these multiple equal-cost paths. Our routing policy guarantees not only a provable Nash equilibrium, but also a quick convergence without significant oscillations to an equilibrium state in which the measurement gain of the network is close to the best case performance bounds We evaluate the protocol via simulations using real traces/topologies (Abilene, AS6461 and GEANT). The simulation results show fast convergence (as expected from the theoretical results), improved measurement gains (e.g., 12 % higher) and much lower TE-violations (e.g., up to 100X smaller) compared to static, centralized measurement-aware routing framework in dynamic traffic scenario.

Cloud infrastructure providers and data center operators spend a major portion of their operations budget on the electric bills. We present RED-BL (Relocate Energy Demand to Better Locations), a framework for determining an optimal mapping of workload to an existing set of data centers while considering the cost of workload relocation. Within each workload mapping interval, RED-BL solution exploits the geo diversity in electricity price markets. The temporal diversity in those markets is simultaneously exploited by considering a planning window comprising several mapping intervals. Using workload traces from live Internet applications and electricity prices from the US markets, RED-BL can reduce the electric bill by as much as 81% from the case when the workload is equally distributed. Compared to a single data center deployment, an average reduction of 27% in electric bill can be achieved when RED-BL uses 10 or more data centers, a common case for most operators. When compared to existing workload relocation solutions, RED-BL achieves a further reduction of 13.63%, on average. While modest, this reduction can save millions of dollars for the operators. The cost of this saving is an inexpensive computation at the start of each planning window.

Network-wide traffic measurement is important for various network management tasks, ranging from traffic accounting, traffic engineering, network troubleshooting to security. Previous research in this area has focused on either deriving better monitor placement strategies for fixed routing, or strategically routing traffic sub-populations over existing deployed monitors to maximize the measurement gain. However, neither of them alone suffices in real scenarios, since not only the number of deployed monitors is limited, but also the traffic characteristics and measurement objectives are constantly changing. This paper presents an MMPR (Measurement-aware Monitor Placement and Routing) framework that jointly optimizes monitor placement and dynamic routing strategy to achieve maximum measurement utility. The main challenge in solving MMPR is to decouple the relevant decision variables and adhere to the intra-domain traffic engineering constraints. We formulate it as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. Through experiments using real traces and topologies (Abilene , AS6461 , and GEANT ), we show that our heuristic solutions can achieve measurement gains that are quite close to the optimal solutions, while reducing the computation times by a factor of 23X in Abilene (small), 246X in AS6461 (medium), and 233X in GEANT (large), respectively.

Monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. Previous research in the area has focused on deriving a placement of monitors across the network toward the end of maximizing the monitoring utility of the network operator for a given traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. It is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. We address this problem by strategically routing traffic subpopulations over fixed monitors. We refer to this approach as MeasuRouting. The main challenge for MeasuRouting is to work within the constraints of existing intradomain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting quality-of-service (QoS) constraints, or both. A fundamental feature of intradomain routing, which makes MeasuRouting feasible, is that intradomain routing is often specified for aggregate flows. MeasuRouting can therefore differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. In this paper, we present a theoretical framework for MeasuRouting. Furthermore, as proofs of concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting.

Network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load-EqualIzed measurement), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support different deployment scenarios. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75X smaller peak workload and 70X smaller variance in workloads) across all coordinated monitors in comparison to naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks.

Streaming network traffic measurements and analysis is critical for detecting and preventing any real-time anomalies in the network. The high speeds and complexity of today's network make the traditional slow open-loop measurement schemes infeasible. We propose an alternate closed-loop measurement paradigm and demonstrate its practical realization. To the heart of our solution are three streaming algorithms that provide a tight integration between the measurement platform and the measurements. The algorithms cater to varying degrees of computational budgets, detection latency, and accuracy. We empirically evaluate our streaming solutions on a highly parallel and programmable measurement platform. The algorithms demonstrate a marked 100% accuracy increase from a recently proposed MRT algorithm in detecting DoS attacks made up of synthetic hard-to-track elephant flows. Our proposed algorithms maintain the worst case complexities of the MRT, while empirically demonstrating a moderate increase in average resource utilization.

Network measurement is a discipline that provides the techniques to collect data that are fundamental to many branches of computer science. While many capturing tools and comparisons have made available in the literature and elsewhere, the impact of these packet capturing tools on existing processes have not been thoroughly studied. While not a concern for collection methods in which dedicated servers are used, many usage scenarios of packet capturing now requires the packet capturing tool to run concurrently with operational processes. In this paper we perform experimental evaluations of the performance impact that packet capturing process have on webbased services; in particular, we observe the impact on web servers. We find that packet capturing processes indeed impact the performance of web servers, but on a multi- core system the impact varies depending on whether the packet capturing and web hosting processes are co-located or not. In addition, the architecture and behavior of the web server and process scheduling is coupled with the behavior of the packet capturing process, which in turn also affect the web server's performance.

In a multi-tenant data center environment, the current paradigm for route control customization involves a labor-intensive ticketing process, in which tenants submit route control requests to the landlord. This results in a tight coupling between tenants and landlord, extensive human resource deployment, and long ticket resolution time. We propose Routing-as-a-Service (RaaS), a framework for tenant-directed route control in data centers. We show that RaaS-based implementation provides a route control platform for multiple tenants to perform route control independently with little administrative involvement, and for the landlord to set the overall network policies. RaaS-based solutions can run on commercial off-the-shelf (COTS) hardware and leverage existing technologies, so it can be implemented in existing networks without major infrastructural overhaul. We present the design of RaaS, introduce its components, and evaluate a prototype based on RaaS.

Traffic density in wireless networks is time- and space-varying as users move from one area to another. For example, the majority of traffic stays in residential areas in the early morning and late evening; but moves to business or commercial areas in daytime. Therefore, it is challenging to efficiently locate base stations during network planning stage, due to the time-varying traffic distribution. Base stations vary from highly congested to seldom utilized depending on time. However, measurement studies show that the movement of the traffic density is highly predictable, and the traffic always travel along similar routes among different parts in a city or town during one day or over a week. Therefore, we introduce the traffic-tracing gateway (TTG), which acts as the base station that tracks the movement of the traffic. Given the traffic distribution of a period, we design an algorithm to determine the optimal trajectories of TTGs that can cover the maximum traffic. Our solution framework can optimally deploy TTGs in the congested areas to provide better coverage and relieve congestion. Our simulation studies based on realistic user mobility show that TTGs can result in significant improvement over fixed infrastructure based network across multiple metrics in multiple scenarios.

Excessive Green House Gas emission and high fuel consumption from vehicles has become not only an environmental but also an economic issue. This work demonstrates CarbonRecorder, a mobile-social application suite that is designed to enable individuals to track their daily vehicular carbon emission, and share them on social networks. It is intended to not only raise social awareness of vehicular carbon emission and encourage more efficient driving behavior, but also serve as a platform for data collection for research in vehicular traffic management, carbon emission, and user behavior analysis in social network based applications.

Because of unavoidable wireless packet losses and inapplicability of retransmission-based schemes due to the well-known negative acknowledgment implosion problem, providing high quality video multicast over wireless wide area networks (WWAN) remains difficult. Traditional joint source/channel coding (JSCC) schemes for video multicast target a chosen th-percentile WWAN user. Users with poorer reception than th-percentile user (poor users) suffer substantial channel losses, while users with better reception (rich users) have more channel coding than necessary, resulting in sub-optimal video quality. In this paper, we recast the WWAN JSCC problem in a new setting called cooperative peer-to-peer repair (CPR), where users have both WWAN and wireless local area network (WLAN) interfaces and use the latter to exchange received WWAN packets locally. Given CPR can mitigate some WWAN losses via cooperative peer exchanges, a CPR-aware JSCC scheme can now allocate more bits to source coding to minimize source quantization noise without suffering more packet losses, leading to smaller overall visual distortion. Through CPR, this quality improvement is in fact reaped by all peers in the collective, not just a targeted th-percentile user. To efficiently implement both WWAN forward error correction and WLAN CPR repairs, we propose to use network coding for this dual purpose to reduce decoding complexity and maximize packet recovery at the peers. We show that a CPR-aware JSCC scheme dramatically improves video quality: by up to 8.7 dB in peak signal-to-noise ratio for the entire peer group over JSCC scheme without CPR, and by up to 6.0 dB over a CPR-ignorant JSCC scheme with CPR.

A significant fraction of network events (such as topology or route changes) and the resulting performance degradation stem from premeditated network management and operational tasks. This paper introduces a general class of Graceful Network State Migration (GNSM) problems, where the goal is to discover the optimal sequence of operations that progressively transition the network from its initial to a desired final state while minimizing the overall performance disruption. We investigate two specific GNSM problems: 1) Link Weight Reassignment Scheduling (LWRS) studies the optimal ordering of link weight updates to migrate from an existing to a new link weight assignment; and 2) Link Maintenance Scheduling (LMS) looks at how to schedule link deactivations and subsequent reactivations for maintenance purposes. LWRS and LMS are both combinatorial optimization problems. We use dynamic programming to find the optimal solutions when the problem size is small, and leverage ant colony optimization to get near-optimal solutions for large problem sizes. Our simulation study reveals that judiciously ordering network operations can achieve significant performance gains. Our GNSM solution framework is generic and applies to similar problems with different operational contexts, underlying network protocols or mechanisms, and performance metrics.

Traffic measurements provide critical input for a wide range of network management applications, including traffic engineering, accounting, and security analysis. Existing measurement tools collect traffic statistics based on some predetermined, inflexible concept of “flows.” They do not have sufficient built-in intelligence to understand the application requirements or adapt to the traffic conditions. Consequently, they have limited scalability with respect to the number of flows and the heterogeneity of monitoring applications. We present ProgME, a Programmable MEasurement architecture based on a novel concept of flowset-an arbitrary set of flows defined according to application requirements and/or traffic conditions. Through a simple flowset composition language, ProgME can incorporate application requirements, adapt itself to circumvent the scalability challenges posed by the large number of flows, and achieve a better application-perceived accuracy. The modular design of ProgME enables it to exploit the surging popularity of multicore processors to cope with 7-Gb/s line rate. ProgME can analyze and adapt to traffic statistics in real time. Using sequential hypothesis test, ProgME can achieve fast and scalable heavy hitter identification.

The problem of Network Traffic Classification (NTC) has attracted significant amount of interest in the research community, offering a wide range of solutions at various levels. The core challenge is in addressing high amounts of traffic diversity found in today's networks. The problem becomes more challenging if a quick detection is required as in the case of identifying malicious network behavior or new applications like peer-to-peer traffic that have potential to quickly throttle the network bandwidth or cause significant damage. Recently, Traffic Dispersion Graphs (TDGs) have been introduced as a viable candidate for NTC. The TDGs work by forming a network wide communication graphs that embed characteristic patterns of underlying network applications. However, these patterns need to be quickly evaluated for mounting real-time response against them. This paper addresses these concerns and presents a novel solution for real-time analysis of Traffic Dispersion Metrics (TDMs) in the TDGs. We evaluate the dispersion metrics of interest and present a dedicated solution on an FPGA for their analysis. We also present analytical measures and empirically evaluate operating effectiveness of our design. The mapped design on Virtex-5 device can process 7.4 million packets/second for a TDG comprising of 10k flows at very high accuracies of over 96%.

By exploiting multiple network interfaces on one device, e.g., Wireless Wide Area Network (WWAN) and Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast/multicast packets can perform Cooperative Peer-to-peer Repair (CPR) by exchanging received WWAN packets with their local WLAN peers. This effectively improves the transmission success from a WWAN broadcast/multicast source to a CPR collective. In this paper, we propose a novel joint source/channel bit allocation scheme for WWAN scalable video multicast that leverages the CPR paradigm. One key observation is that given a peer can successfully receive a packet either from theWWAN channel directly, or via a CPR neighbor using ad-hoc WLAN connections, more bits can be redistributed from channel to source coding out of a fixed WWAN bit budget to further minimize individual node's expected visual distortion. In our proposal, groups of peers requiring different video resolutions are assigned to the same multicast group, and we perform one WWAN resource allocation and subsequent CPR over heterogeneous peers of different resolutions together. Our simulations show that our joint multicast group optimization can improve video quality by up to 2.84 dB, compared to a scheme where both WWAN resource allocation and WLAN CPR are separately performed for heterogeneous peers.

Detection and diagnosis of failures in wireless networks is of crucial importance. It is also a very challenging task, given the myriad of problems that plague present day wireless networks. A host of issues such as software bugs, hardware failures, and environmental factors, can cause performance degradations in wireless networks. As part of this study, we propose a new approach for diagnosing performance degradations in wireless networks, based on the concept of ``fault signatures''. Our goal is to construct signatures for known faults in wireless networks and utilize these to identify particular faults. Via preliminary experiments, we show how these signatures can be generated and how they can help us in diagnosing network faults and distinguishing them from legitimate network events. Unlike most previous approaches, our scheme allows us to identify the root cause of the fault by capturing the state of the network parameters during the occurrence of the fault.

Recent research has exploited the multi-homing property (one terminal with multiple network interfaces) of modern devices to improve communication performance in wireless networks. Cooperative Peer-to-peer Repair (CPR) is one example where given simultaneous connections to both a Wireless Wide Area Network (WWAN) and an ad-hoc Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast packets can exchange received WWAN packets with their ad-hoc WLAN peers for local recovery. In our previous work, we have shown that by using Network Coding (NC) to linearly combine received packets into new CPR packets for local exchanges, packet recovery can be improved. Moreover, by imposing Structure on Network Coding (SNC) when encoding a CPR packet, decoding of at least the important packets becomes possible in the event when insufficient number of CPR packets were received for full recovery. Given SNC is used during CPR, the key decision for each peer is to determine which SNC type to encode a repair packet at each WLAN transmission opportunity. The decision is further complicated by the observation that peers in general receive different numbers of CPR packets from neighbors due to varying amount of WLAN link contentions and interference experienced. In this paper, we propose a novel counter-based deterministic SNC type selection scheme. Using this approach, we show that a simple local optimization procedure, taking advantage of available neighbors' state information, can be easily implemented to further improved CPR performance. Simulation results show that our proposed scheme outperformed our previous randomized SNC type selection scheme by up to 1.87dB.

Wireless networking enabled vehicles can form vehicular ad hoc mesh networks (VMeshs). Using cooperative communication among VMeshs, a local transient information could be "retained" within a given geographic region for a certain period of time, without any infrastructure help. In this paper, we study this "storage capability" of VMeshs. We analyze the scenarios of highway traffic (both one-way and two-way highway free flow traffic) and vehicular traffic in a city environment. For highway traffic, we study different properties of the "VMesh storage", using a simulation tool that accurately models the freeway vehicular mobility. For city traffic, we first perform simulations based on real traffic trace of San Francisco Yellow Cabs. Then we compare the results with the scenario where a general Random Way Point (RWP) mobility model is used. Our results show that transmission range has high impact on the storage lifetime for one-way highway traffic, and the size of the region in which we want the information stored has high impact for two-way highway traffic. For city-wide traffic, the storage's lifetime generated using San Francisco Yellow Cab trace is shorter than that obtained using the RWP mobility model. This is due to the regular movement of the cabs as compared to the random vehicle movement in the RWP mobility model.

Monitoring transit traffic at one or more points in a network is of interest to network operators for reasons of traffic accounting, debugging or troubleshooting, forensics, and traffic engineering. Previous research in the area has focused on deriving a placement of monitors across the network towards the end of maximizing the monitoring utility of the network operator for a given traffic routing. However, both traffic characteristics and measurement objectives can dynamically change over time, rendering a previously optimal placement of monitors suboptimal. It is not feasible to dynamically redeploy/reconfigure measurement infrastructure to cater to such evolving measurement requirements. We address this problem by strategically routing traffic sub-populations over fixed monitors. We refer to this approach as MeasuRouting. The main challenge for MeasuRouting is to work within the constraints of existing intra-domain traffic engineering operations that are geared for efficiently utilizing bandwidth resources, or meeting Quality of Service (QoS) constraints, or both. A fundamental feature of intra-domain routing, that makes MeasuRouting feasible, is that intra-domain routing is often specified for aggregate flows. MeasuRouting, can therefore, differentially route components of an aggregate flow while ensuring that the aggregate placement is compliant to original traffic engineering objectives. In this paper we present a theoretical framework for MeasuRouting. Furthermore, as proofs-of-concept, we present synthetic and practical monitoring applications to showcase the utility enhancement achieved with MeasuRouting.

The IEEE 1609.4 standard has been proposed to provide multi-channel operations in wireless access for vehicular environments (WAVE), where all the channels are periodically synchronized into control and service intervals. The communication device in each vehicle will stay at the control channel for negotiation and contention during the control interval, and thereafter switch to one of the service channels for data transmission in the service interval. The inefficiency of WAVE system comes from the fact that half of the time intervals of the service channels remain idle since all the stations are performing message contention within the control channel. In this paper, the cognitive radio-enabled multi-channel access (CREM) protocol is proposed to increase the channel utilization of IEEE 1609.4 standard. Based on the concept of cognitive radio, the vehicular stations are categorized into primary stations with safety-related messages and secondary stations with non-safety information to be delivered. Prioritized channel access is designed in the proposed CREM scheme in order to increase the transmission opportunity of primary stations. Moreover, extended time intervals are granted for primary stations to ensure reliability for data transmission. The enhanced CREM (CREM-E) protocol is proposed to further opportunistically increase the channel utilization of secondary stations. Simulation results show that the proposed CREM-E scheme outperforms the existing IEEE 1609.4 protocol with enhanced channel utilization and smaller waiting time intervals.

In the above titled paper (ibid., vol. 11, no. 4, pp. 730-741, Jun. 09), simulation errors were discovered. This errata outlines a corrective derivation and presents updated simulation results.

The popularity of a new generation of smart peer-to-peer applications has resulted in several new challenges for accurately classifying network traffic. In this paper, we propose a novel 2-stage P2P traffic classifier, called self learning traffic classifier (SLTC), that can accurately identify P2P traffic in high speed networks. The first stage classifies P2P traffic from the rest of the network traffic, and the second stage automatically extracts application payload signatures to accurately identify the P2P application that generated the P2P flow. For the first stage, we propose a fast, light-weight algorithm called time correlation metric (TCM), that exploits the temporal correlation of flows to clearly separate peer-to-peer (P2P) traffic from the rest of the traffic. Using real network traces from tier-1 ISPs that are located in different continents, we show that the detection rate of TCM is consistently above 95 % while always keeping the false positives at 0%. For the second stage, we use the LASER signature extraction algorithm to accurately identify signatures of several known and unknown P2P protocols with very small false positive rate (< 1%). Using our prototype on tier-1 ISP traces, we demonstrate that SLTC automatically learns signatures for more than 95% of both known and unknown traffic within 3 minutes.

With over half a billion users, Online Social Networks (OSNs) are the major new applications on the Internet. Little information is available on the network impact of OSNs, although there is every expectation that the volume and diversity of traffic due to OSNs is set to explode. In this paper, we examine the specific role played by a key component of OSNs: the extremely popular and widespread set of third-party applications on some of the most popular OSNs. With over 81,000 third-party applications on Facebook alone, their impact is hard to predict and even harder to study.

Measurement of available bandwidth in a network has always been a topic of great interest. This knowledge can be applied to a wide variety of applications and can be instrumental in providing quality of service to end users. Several probe-based tools have been proposed to measure available bandwidth in wired networks. However, the performance of these tools in the realm of wireless networks has not been evaluated extensively. In recent years, there has also been some work on estimating bandwidth in wireless networks via passively monitoring the channel and determining the 'busy' and 'idle' periods. However, such techniques have primarily been evaluated via simulations only. In this work, we perform an extensive experimental comparison study of both passive and active bandwidth estimation tools for 802.11-based wireless mesh networks. We investigate the impact of interference, packet loss, and 802.11 rate-adaptation, on the performance of these tools. Our results indicate that for wireless networks, a passive technique provides much greater accuracy than the probe-based tools.

A significant fraction of network events (such as topology or route changes) and the resulting performance degradation stem from premeditated network management and operational tasks. This paper introduces a general class of graceful network operation (GNO) problems, where the goal is to discover the optimal sequence of operations that progressively transition the network from its initial to a desired final state while minimizing the overall performance disruption. We investigate two specific GNO problems: (a) link weight reassignment scheduling (LWRS) studies the optimal ordering of link weight updates to migrate from an existing to a new link weight assignment, and (b) link maintenance scheduling (LMS) looks at how to schedule link deactivations and subsequent reactivations for maintenance purposes. LWRS and LMS are both combinatorial optimization problems. We use dynamic programming to find the optimal solutions when the problem size is small, and leverage ant colony optimization to get near-optimal solutions for large problem sizes. Our simulation study reveals that judiciously ordering network operations can achieve significant performance gains. Our GNO solution framework is generic and applies to similar problems with different operational contexts, underlying network protocols or mechanisms, and performance metrics.

Security is becoming an increasingly important QoS parameter for which network providers should provision. We focus on monitoring and detecting one type of network event, which is important for a number of security applications such as DDoS attack mitigation and worm detection, called distributed global icebergs. While previous work has concentrated on measuring local heavy-hitters using “sketches” in the non-distributed streaming case or icebergs in the non-streaming distributed case, we focus on measuring icebergs from distributed streams. Since an iceberg may be “hidden” by being distributed across many different streams, we combine a sampling component with local sketches to catch such cases. We provide a taxonomy of the existing sketches and perform a thorough study of the strengths and weaknesses of each of them, as well as the interactions between the different components, using both real and synthetic Internet trace data. Our combination of sketching and sampling is simple yet efficient in detecting global icebergs.

Because of frequent wireless packet losses and inapplicability of retransmission-based schemes due to the wellknown NAK implosion problem, providing high quality video multicast over wireless wide area networks (WWAN) remains difficult. Traditional joint source/channel coding schemes for video multicast-optimal bit allocation among source coding and channel coding such as forward error correction (FEC) subject to a bitrate constraint-target a chosen nth-percentile WWAN user. Not only is FEC bitwise expensive, users with poorer reception than nth-percentile user suffer substantial channel losses, while users with better reception have more channel coding than necessary, meaning too few bits are devoted for source coding to reduce quantization noise and sub-optimal video quality. Instead, in this paper we perform joint source/channel coding of WWAN video multicast for an entire collective of multi-homed ad-hoc peers in the same multicast group and connected via wireless local area networks (WLAN). In a cooperative peer-to-peer repair (CPR) scenario, after each peer received a different subset of WWAN packets, the peer group repairs WWAN losses locally by packet-forwarding to each other via WLAN. From an end-to-end system view, CPR means that a packet can be transmitted from source to a peer either via WWAN directly, or via WLAN local repairs exploiting neighboring peers' WWAN links; the overall more general transmission condition means a clever joint source/channel coding scheme can now allocate more bits to source coding without suffering more packet losses, leading to higher video quality. To efficiently implement both WWAN FEC and WLAN CPR repairs, we propose to use network coding for this dual purpose to reduce decoding complexity at the peers. We show through simulations that using our proposed scheme dramatically improves video quality over existing optimization scheme where joint source/channel coding was performed, but WLAN CPR was not used, by up to 8.4 dB, and over scheme when WLAN CPR and WWAN joint source/channel coding were performed separately by up to 4.4 dB.

In a scenario where each peer of an ad-hoc wireless local area network (WLAN) receives one of many available video streams from a wireless wide area network (WWAN), we propose a network-coding-based cooperative repair framework for the ad-hoc peer group to improve broadcast video quality during channel losses. Specifically, we first impose network coding structures globally, and then select the appropriate video streams and network coding types within the structures locally, so that repair can be optimized for broadcast video in a rate-distortion manner. Innovative probability—the likelihood that a repair packet is useful in data recovery to a receiving peer—is analyzed in this setting for accurate optimization of the network codes. Our simulation results show that by using our framework, video quality can be improved by up to 19.71 dB over un-repaired video stream and by up to 5.39 dB over video stream using traditional unstructured network coding.

Accurate and real-time traffic measurement is becoming increasingly critical for large variety of applications including accounting, bandwidth provisioning and security analysis. Existing network measurement techniques, however, have major difficulty dealing with large number of flows in today’s high-speed networks and offer limited scalability with increasing link speeds. Consequently, the current state of the art solutions have to resort to conservative sampling of the traffic stream and/or accounting for only a few frequent flows that often fail to provide accurate estimates of traffic features. In this paper, we present a novel hardware-software codesigned solution that is programmable and adaptable to runtime situations offering high-throughputs that can easily

Multimedia Broadcast/Multicast Service (MBMS) allows a common broadcast channel to be shared by users interested in identical content. We explore the problem of enhancing MBMS resilience by repairing packets lost during broadcast. Since MBMS broadcast consumes expensive 3G resources, we leverage the ubiquity of multi-homed mobile devices i.e., devices having both cellular and IEEE 802.11 wireless interfaces. We thus accomplish out-of-band repair of MBMS packet losses through an ad-hoc, peer-to-peer 802.11-based network. A fundamental challenge in scheduling repair transmissions is handling interference between distributed nodes. We present DiCoR, a fully distributed protocol for CPR. Our protocol does not assume any a priori knowledge of the network topology or peer losses, and is resilient to dynamic network changes due to node mobility or the continuous joining and leaving of peers. Detailed simulation experiments, under realistic loss models and network conditions, demonstrate that DiCoR presents a viable solution for timely out-of-band loss repair of MBMS real-time broadcast.

Cooperative Peer-to-Peer Repair (CPR) has been proposed to recover from packet losses incurred during 3G broadcast. CPR leverages the increasing presence of multi-homed mobile devices having both 3G cellular and IEEE 802.11 wireless interfaces. Mobile devices can, therefore, draw upon IEEE 802.11 peering links to cooperatively achieve out-of-band repair of 3G broadcasting losses. This paper considers the problem of employing Network Coding (NC) to exploit the broadcast nature of the wireless medium towards enhancing the efficiency of CPR. We show that the minimum latency scheduling problem for NC based CPR (NC-CPR) is NP-Hard. We present heuristics for NC-CPR that assume a priori topology and packet loss information. Insights gained from our heuristics are leveraged to propose NC-DCPR, a fully distributed protocol for NC-CPR. We conduct extensive simulation experiments under realistic network conditions. Our results show that employing network coding significantly improves the efficiency of CPR.

Online social networking sites such as Facebook and MySpace have become increasingly popular, with close to 500 million users as of August 2008. The introduction of the Facebook Developer Platform and OpenSocial allows third-party developers to launch their own applications for the existing massive user base. The viral growth of these social applications can potentially influence how content is produced and consumed in the future Internet.

802.11-based multi-hop wireless mesh networks have become increasingly prevalent over the last few years. Recently, a lot of focus has been on deploying monitoring frameworks for enterprise and municipal multi-hop wireless networks. A lot of work has also been done on developing measurement-based schemes for resource management and fault management in these networks. The above goals require an efficient monitoring infrastructure to be deployed in the wireless network, which can provide the maximum amount of information regarding the network status, while utilizing the least possible amount of network resources. However, network monitoring introduces overheads, which can impact network performance, from the perspective of the end user. The impact of monitoring overheads on data traffic has been overlooked in most of the previous works. It remains unclear, as to how parameters such as number of monitoring agents, frequency of reporting monitoring data, and others, impact the performance of a wireless network. In this work, we first evaluate the impact of monitoring overheads on data traffic, and show that even small amounts of overheads can cause large degradation in network performance. We then explore several different techniques for reducing monitoring overheads, while maintaining the objective (resource management, fault management and others) that needs to be achieved. Via extensive simulations, we investigate whether a monitoring framework, which is constrained in terms of number of monitors or periodicity of monitoring, can achieve similar performance as a monitoring framework spanning the entire network. We show that different techniques lend themselves to different application scenarios, and evaluate the trade-offs involved in terms of monitoring overheads and quality of monitoring data.

Wi-Fi-based mesh networks have been considered as a viable option to provide wireless coverage for a vast area, such as community-wide or city-wide. However, interference due to multihop transmissions and potential isolated (disconnected) nodes are the major obstacles to achieve high performance. In this paper, we propose a heterogeneous wireless network architecture, consisting of Wi-Fi and WiMAX, to overcome these limitations. We first construct an optimization problem to analyze the benefits of heterogeneous networks. Then, we design a practical protocol to efficiently combine the resources of Wi-Fi and WiMAX networks. The evaluations show that our new scheme greatly improves the system performance in terms of throughput and fairness.

By providing coding ability at intermediate nodes, network coding has been shown to improve throughput in wireless broadcast/multicast networks. Considering a scenario where wireless ad-hoc peers cooperatively relay packets to each other to recover packets lost during MBMS broadcast, we show that by first imposing coding structures globally and then selecting the appropriate types within the structures locally, network coding can be optimized for video streaming in a rate-distortion manner. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71 dB over un-repaired video stream and by up to 8.34 dB over video stream using traditional unstructured network coding.

In this paper, we propose a BGP anomaly detection framework called BAlet that delivers both temporal and spatial localization of the potential anomalies. It requires only a simple count of BGP update messages collected over a certain period. We first investigate the self-similarity in BGP update traffic and present a quantitative validation. The strength of wavelet analysis in handling signals with scaling property and earlier success in applying it for network anomaly detection motivate us to apply the same technique on BGP routing traffic. Later by clustering the anomalies detected at different locations, BAlet is capable of identifying possible network-wide anomalous events. Our method does not rely on any information within the BGP messages, and serves as a complementary tool to reduce the candidate data set for further detailed root cause analysis. We evaluate BAlet on real BGP data sets that are known to contain anomalies. Results show that it is capable of detecting network-wide events such as message volume surges caused by slammer worm attack, and separating affected ASes from the rest.

Modern day wireless networks are increasingly supporting various civilian applications that require high bandwidth for successful operation. In such cases, it is important to ensure proper maintenance of links that contribute the most to achieving the required level of service. In this paper, we devise a method to analytically characterize the importance of each link in a multichannel, multi-radio, multi-rate wireless mesh network in satisfying quality-of-service (QoS) requirements of active flows. We propose link importance metrics that can guide network/traffic engineers in properly provisioning the network to handle failures of critical links that contribute significantly to the achievability of flow demands. We consider single-commodity flows and perform simulations to evaluate the quality of our metrics.

By providing coding ability at intermediate nodes, network coding has been shown to improve network throughput in broadcast/multicast wireless networks. In this paper, we show that by imposing coding structure, network coding can be further optimized specifically for video streaming in a rate-distortion manner, in a scenario where wireless adhoc peers cooperatively relay packets to each other to repair packet losses during MBMS broadcast. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71dB over un-repaired video stream and by up to 7.90dB over video stream using traditional unstructured network coding.

Firewalls are among the most pervasive network security mechanisms, deployed extensively from the borders of networks to end systems. The complexity of modern firewall policies has raised the computational requirements for firewall implementations, potentially limiting the throughput of networks. Administrators currently rely on ad hoc solutions to firewall optimization. To address this problem, a few automatic firewall optimization techniques have been proposed, but there has been no general approach to evaluate the optimality of these techniques. In this paper we present a general framework for rule-based firewall optimization. We give a precise formulation of firewall optimization as an integer programming problem and show that our framework produces optimal reordered rule sets that are semantically equivalent to the original rule set. Our framework considers the complex interactions among the rules in firewall configurations and relies on a novel partitioning of the packet space defined by the rules themselves. For validation, we employ this framework on real firewall rule sets for a quantitative evaluation of existing heuristic approaches. Our results indicate that the framework is general and faithfully captures performance benefits of firewall optimization heuristics.

With the availability of cheap and robust wireless devices there is demand for new applications in vehicular ad-hoc networks (VANET). The challenge in implementing applications is in understanding of the complex dynamics of highly mobile multi-hop ad hoc networks which is a characteristics of VANET. Studies have been reported that attempt to quantify transport protocol (TCP and UDP) performance in mobile ad-hoc network in general and VANet in particular. However, very little work has been done in looking at the effect of tuning transmission power and its effect on the performance of the transport layer protocols. Our work specifically looks at the result of tuning transmission power and its effect on UDP throughput in VANet. To facilitate this study we first developed a comprehensive integrated simulation tool which accurately simulates both vehicular mobility patterns and wireless network environment and the communication protocols; the former is based on a cellular automata model while the later is developed using JIST/SWANS network simulator. Results show that the major mitigating factor in VANETs multi-hop environment is the number of hops between the source and the destination. Increasing the transmission range results in decreasing the number of hops between source and destination effectively increasing throughput. However, increasing the transmission range beyond a certain point saturates the throughput due to increased interference. We also found that the effect of vehicle densities is only important at lower transmission ranges to provide the required connectivity.

We explore the use of partially overlapped channels in wireless mesh networks that consist of multiple 802.11-based access points. We propose novel channel allocation and link scheduling algorithms in the MAC layer to enhance network performance. Due to different traffic characteristics in multi-hop WMNs compared to those in one-hop 802.11 networks, we perform our optimization based on end-to-end flow requirement, instead of the sum of link capacity. In addition, we discuss other factors affecting the performance of POC, including topology, node density, and distribution.

This paper explores how to leverage IEEE802.11-based cooperative peer-to-peer repair (CPR) to enhance the reliability of wireless multimedia broadcasting. We first formulate the CPR problem and present an algorithm that assumes global state information to optimally schedule CPR transmissions. Based on insights gained from the optimal algorithm, we propose a fully distributed CPR (DCPR) protocol. Simulation results demonstrate that the DCPR protocol can effectively enhance the reliability of wireless broadcast services with a repair latency comparable to that of optimal scheduling.

The domain name system (DNS) provides a critical service for the Internet -mapping of user-friendly domain names to their respective IP addresses. Yet, there is no standard set of metrics quantifying the quality of domain name service or QoDNS, let alone a thorough evaluation of it. This paper attempts to fill this gap from the perspective of a DNS proxy/cache, which is the bridge between clients and authoritative servers. We present an analytical model of DNS proxy operations that offers insights into the design tradeoffs of DNS infrastructure and the selection of critical DNS parameters. After validating our model against simulation results, we extend it to study the impact of DNS cache poisoning attacks and evaluate various DNS proposals with respect to the QoDNS metrics. In particular, we compare the performance of two newly proposed DNS security solutions: one based on cryptography and one using collaborative overlays.

The increased deployment of wireless mesh networks (WMNs) should be complemented by a robust resource management scheme that can provide performance guarantees to mission-critical applications. Several admission control schemes have been presented for wireless LANs and wireless ad-hoc networks. However, wireless mesh networks, with static wireless back-bone and multi-hop communication, pose new design challenges. Evaluation of existing admission control schemes has been done primarily via simulations, which often do not have accurate models for capturing interference between adjacent wireless links and nodes. In this paper, we develop light-weight monitoring modules to measure current network/traffic conditions and estimate end-to-end path delay, which is then incorporated in our admission control decision. We utilize a novel layer-2 packet forwarding mechanism, based on the wireless distribution system (WDS) for WMNs. We evaluate our scheme via experiments conducted on a test-bed consisting of IEEE 802.11a-based nodes that form a wireless mesh. Results show that our proposed scheme can provide performance assurance without incurring too much control overhead.

Traffic measurements provide critical input for a wide range of network management applications, including traffic engineering, accounting, and security analysis. Existing measurement tools collect traffic statistics based on some pre-determined, inflexible concept of "flows". They do not have sufficient built-in intelligence to understand the application requirements or adapt to the traffic conditions. Consequently, they have limited scalability with respect to the number of flows and the heterogeneity of monitoring applications.

The mapping service provided by the Domain Name System (DNS) is fundamental not only to the health of the Internet but also to the protection and integrity of the data. Recently, the DNS infrastructure has suffered several malicious attacks including DNS cache poisoning, which causes the DNS to return false name-to-IP mappings and can be used as a foothold for more insidious attacks. This paper proposes DoX, a peer-to-peer based scheme, to detect and correct inaccurate DNS records caused by cache poisoning attacks. DoX also helps DNS servers to improve cache consistency by detecting and removing obsolete records. DoX does not require modifications to the current infrastructure and can be deployed quickly. It does not use cryptographic techniques and thus does not suffer from the key management and processing overhead issues of those techniques.

In a multi-source video streaming system, premature draining of low-power nodes can cause sudden failures of peer connections and degrade streaming performance. To solve this problem, we propose an energy-aware scheduling (EAS) scheme to better distribute the streaming load among different peers by jointly considering network conditions and node energy levels. We model the proposed scheme using a rate/energy-distortion optimization framework and heuristically solve it using the concept of asynchronous clocks. Simulation studies show that the proposed EAS scheme can achieve comparable streaming quality while consuming less energy.

Sampling techniques are widely used for traffic measurements at high link speed to conserve router resources. Traditionally, sampled traffic data is used for network management tasks such as traffic matrix estimations, but recently it has also been used in numerous anomaly detection algorithms, as security analysis becomes increasingly critical for network providers. While the impact of sampling on traffic engineering metrics such as flow size and mean rate is well studied, its impact on anomaly detection remains an open question. This paper presents a comprehensive study on whether existing sampling techniques distort traffic features critical for effective anomaly detection. We sampled packet traces captured from a Tier-1 IP-backbone using four popular methods: random packet sampling, random flow sampling, smart sampling, and sample-and-hold. The sampled data is then used as input to detect two common classes of anomalies: volume anomalies and port scans. Since it is infeasible to enumerate all existing solutions, we study three representative algorithms: a wavelet-based volume anomaly detection and two portscan detection algorithms based on hypotheses testing. Our results show that all the four sampling methods introduce fundamental bias that degrades the performance of the three detection schemes, however the degradation curves are very different. We also identify the traffic features critical for anomaly detection and analyze how they are affected by sampling. Our work demonstrates the need for better measurement techniques, since anomaly detection operates on a drastically different information region, which is often overlooked by existing traffic accounting methods that target heavy-hitters.

This paper proposes to leverage multi-source multi-path diversity to design a video streaming system for supporting concurrent video-on-demand (VoD) services over wireless mesh networks (WMNs). By integrating a wireless interference model into consideration, we have a more realistic network model to capture the characteristics of wireless networks. Based on that, we mathematically formulate the route selection problem for the proposed streaming system using rate/interference-distortion optimization framework, and rely on a genetic algorithm to solve it heuristically. Simulation results show that the proposed system has better performance than systems using single-source, single-path and systems that do not consider interference.

Security concerns are becoming increasingly critical in networked systems. Firewalls provide important defense for network security. However, misconfigurations in firewalls are very common and significantly weaken the desired security. This paper introduces FIREMAN, a static analysis toolkit for firewall modeling and analysis. By treating firewall configurations as specialized programs, FIREMAN applies static analysis techniques to check misconfigurations, such as policy violations, inconsistencies, and inefficiencies, in individual firewalls as well as among distributed firewalls. FIREMAN performs symbolic model checking of the firewall configurations for all possible IP packets and along all possible data paths. It is both sound and complete because of the finite state nature of firewall configurations. FIREMAN is implemented by modeling firewall rules using binary decision diagrams (BDDs), which have been used successfully in hardware verification and model checking. We have experimented with FIREMAN and used it to uncover several real misconfigurations in enterprise networks, some of which have been subsequently confirmed and corrected by the administrators of these networks.

Owing to the inter-domain aspects of BGP routing, it is difficult to correlate information across multiple domains in order to analyze the root cause of the routing outages. We present BGP Eye, a tool for visualization-aided root-cause analysis of BGP anomalies. In contrast to previous approaches, BGP Eye performs real-time analysis of BGP anomalies through hierarchical analysis. First, BGP updates are clustered to obtain BGP events that are more representative of an anomaly. These events are then correlated across all border routers to ascertain the extent of the anomaly. Furthermore, BGP Eye provides both the capability to analyze BGP anomalies from an Internet-Centric View through multiple vantage points as well as from a Home-Centric View of a particular Autonomous System. We present the capability for scalable and real-time root-cause analysis provided by BGP Eye through the analysis of two very different anomalies. First, we provide an Internet-Centric view from AS568 of the routing outages during the spread of the Slammer Worm on January 25th, 2003. Second, we provide a Home-Centric view from AS6458 of the routing outages caused by the inadvertent prefix hijacking by AS9121 on December 24th, 2004.

Packet sampling is commonly deployed in high-speed backbone routers to minimize resources used for network monitoring. It is known that packet sampling distorts traffic statistics and its impact has been extensively studied for traffic engineering metrics such as flow size and mean rate. However, it is unclear how packet sampling impacts anomaly detection, which has become increasingly critical to network providers. This paper is the first attempt to address this question by focusing on one common class of nonvolume-based anomalies, portscans , which are associated with worm/virus propagation. Existing portscan detection algorithms fall into two general approaches: target-specific and traffic profiling. We evaluated representative algorithms for each class, namely: 1) TRWSYN that performs stateful traffic analysis; 2) TAPS that tracks connection pattern of scanners; and 3) entropy-based traffic profiling. We applied these algorithms to detect portscans in both the original and sampled packet traces from a Tier-1 provider's backbone network. Our results demonstrate that sampling introduces fundamental bias that degrades the effectiveness of these detection algorithms and dramatically increases false positives. Through both experiments and analysis, we identify the traffic features critical for anomaly detection that are affected by sampling. Finally, using insight gained from this study, we show how portscan algorithms can be enhanced to be more robust to sampling.

A plethora of coding and streaming mechanisms have been proposed for real-time multimedia transmission over the Internet. However, most proposed mechanisms rely only on global (e.g. based on end-to-end measurements), delayed (at least by the round-trip-time), or statistical (often based on simplistic network models) information available about the network state. Based on recently-proposed state-of-the-art open-loop video coding schemes, we propose a new integrated streaming and routing framework for robust and efficient video transmission over networks exhibiting path failures. Our approach explicitly takes into account the network dynamics, path diversity, and the modeled video distortion at the receiver side to optimize the packet redundancy and scheduling. In the derived framework, multimedia streams can be adapted dynamically at the video server based on instantaneous routing-layer information or failure-modeling statistics. The performance of our integrated application and network-layer method is simulated against equivalent approaches that are not optimized based on routing-layer feedback and distortion modeling, and the obtained gains in video quality are quantified

This paper describes a novel sequential wavelength-time-space (sWTS) scheduling algorithm to solve the arbitration problem in an all-optical packet switch router and shows the simulation as well as the hardware implementation results. The simulation results with self-similar traffic input demonstrate that the sWTS arbitration algorithm effectively improves the packet blocking rate, forwarding latency and jitter as the number of wavelength channels per port and the number of recirculation buffer ports in the switch fabric increase. The proposed algorithm further facilitates a very fast and hardware-efficient mixed-tree output port arbiter design. The hardware implementation is evaluated in terms of area and delay for various switch sizes with both the Xilinx XCV1000E FPGA and a 0.25-micron commercial ASIC library.

By allowing end hosts to make routing decisions at the application level, different overlay networks may unintentionally interfere with each other. This paper describes how multiple similar or dissimilar overlay networks making independent routing decisions could experience race conditions, resulting in oscillations in both route selection and network load. We pinpoint the causes for synchronization in terms of partially overlapping routes and periodic path probing processes and derive an analytic formulation for the synchronization probability of two overlays. Our model indicates that the probability of synchronization is non-negligible across a wide range of parameter settings, thus implying that the ill-effects of synchronization should not be ignored. Using the analytical model, we find an upper bound on the duration of traffic oscillations. We validate our model through simulations that are designed to capture the transient routing behavior of both the IP- and overlay-layers. We use our model to study the effects of factors such as path diversity (measured in round trip times) and probing aggressiveness on these race conditions. Finally, we discuss the implications of our study on the design of overlay networks and the choice of their path probing parameters

With the emergence of voice over IP and other real-time business applications, there is a growing demand for an IP network with high service availability. Unfortunately, in today's Internet, transient failures occur frequently due to faulty interfaces, router crashes, etc., and current IP networks lack the resiliency needed to provide high availability. To enhance availability, we proposed failure inferencing based fast rerouting (FIFR) approach that exploits the existence of a forwarding table per line-card, for lookup efficiency in current routers, to provide fast rerouting similar to MPLS, while adhering to the destination-based forwarding paradigm. In our previous work, we have shown that the FIFR approach can deal with single link failures. In this paper, we extend the FIFR approach to ensure loop-free packet delivery in case of single router failures also, thus mitigating the impact of many scenarios of failures. We demonstrate that the proposed approach not only provides high service availability but also incurs minimal routing overhead.

This paper introduces a hybrid server/P2P streaming system called bittorrent-assisted streaming system (BASS) for large-scale video-on-demand (VoD) services. By distributing the load among P2P connections as well as maintaining active server connections, BASS can increase the system scalability while decreasing media playout wait times. To analyze the benefits of BASS, we examine torrent trace data collected in the first week of distribution for Fedora Core 3 and develop an empirical model of bittorrent client performance. Based on this, we run trace-based simulations to evaluate BASS and show that it is more scalable than current unicast solutions and can greatly decrease the average waiting time before playback

One of the main design issues for wireless sensor networks is the sensor placement problem. We formulate a constrained multivariable nonlinear programming problem to determine both the locations of the sensor nodes and data transmission pattern. Our two objectives are to maximize the network lifetime and to minimize the application-specific total cost, given a fixed number of sensor nodes in a region with a certain coverage requirement. We first study a linear network, and find optimal placement strategies numerically. Through numerical results, we show that the optimal node placement strategies provide significant benefit over a commonly used uniform placement scheme. Furthermore, we also present a performance bound as a benchmark. Lastly, we extend the results to a more sophisticated planar network, and use numerical results to evaluate the performance of the proposed strategies.

According to conventional wisdom, links connecting different autonomous systems (AS) are the performance bottlenecks in the core of the Internet. The paper presents an empirical evaluation of delays across inter-AS links using hop-limited active probes. The measurements cover a diverse set of Internet paths starting from locations within three large transit Internet service providers (ISPs). We find that most inter-AS links on the Internet paths covered by this study do not contribute significantly to end-to-end delays. The few exceptions are long-haul links with large propagation delays. Furthermore, the delay estimates are fairly stable across days, making it possible for ISPs to choose inter-domain paths or perform traffic engineering based on delay measurement feedback. Our observations also suggest that a very large component of the end-to-end delay for the measured paths usually occurs within a single AS.

The problem of aggregating large data files from distributed databases and address the corresponding challenges involved from a network architecture perspective is considered. We model this problem as one of identifying a time-path schedule (TPS) in a graph representation of the network. We prove that the TPS problem (TPSP) is NP-complete. We then propose a mixed integer linear programming (MILP)-based approach and three heuristics longest-file-first (LFF), disjoint-paths (DP), and most-distant-file-first (MDFF) - to solve TPSP.

In addition to network congestion, a link/node failure is another major cause of performance degradation for video streaming over the Internet. Such failures may be followed by a long routing instability period, during which packets can be black-holed due to invalid paths or caught in routing loops. This paper proposes a routing proxy approach to improve media streaming adaptation against both link/node failures and network congestion. In particular, we first argue that it is important to distinguish between network performance degradation due to network congestion versus link/node failures, and then model link/node failures using empirical models derived from measurements. We then show how by means of proper congestion control, such timely notifications from the network layer can be exploited at the streaming server to improve the performance of a rate-adaptive automatic retransmission request (ARQ) video streaming scheme. Simulation results show that a rate-adaptive streaming scheme using feedbacks from our proposed proxy can recover much faster from link/node failures than a scheme without such feedbacks.

This paper proposes a joint server/peer video streaming architecture for wireless networks, where a receiver can access a video server via an access point using the infrastructure mode and at the same lime communicate with its peers using the ad hoc mode of its IEEE 802.11 interface card. We introduce a joint infrastructure/peer-to-peer, receiver-driven streaming scheme, and formulate it as a combinatorial optimization problem. We decouple the problem into two steps: first selecting the sender (server or peer) by introducing asynchronous clocks, and then applying point-to-point rate-distortion optimization algorithm between a specific sender-receiver pair. Simulation results show that our joint approach has better performance than those systems with single server or with round-robin selection scheme.

Dealing with network failures effectively is a major operational challenge for Internet service providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network-wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing (FIR). The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we prove that when no more than one link failure notification is suppressed, FIR always finds a loop-free path to a destination if one such path exists. We also formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF.

We analyze IS-IS routing updates from sprint's IP network to characterize failures that affect IP connectivity. Failures are first classified based on probable causes such as maintenance activities, router-related and optical layer problems. Key temporal and spatial characteristics of each class are analyzed and, when appropriate, parameterized using well-known distributions. Our results indicate that 20% of all failures is due to planned maintenance activities. Of the unplanned failures, almost 30% are shared by multiple links and can be attributed to router-related and optical equipment-related problems, while 70% affect a single link at a time. Our classification of failures according to different causes reveals the nature and extent of failures in today's IP backbones. Furthermore, our characterization of the different classes can be used to develop a probabilistic failure model, which is important for various traffic engineering problems.

Traditional SLAs, defined by average delay or packet loss, often camouflage the instantaneous performance perceived by end-users. We define a set of metrics for service availability to quantify the performance of IP backbone networks and capture the impact of routing dynamics on packet forwarding. Given a network topology and its link weights, we propose a novel technique to compute the associated service availability by taking into account transient routing dynamics and operational conditions, such as BGP table size and traffic distributions. Even though there are numerous models for characterizing topologies, none of them provide insights on the expected performance perceived by end customers. Our simulations show that the amount of service disruption experienced by similar networks (i.e., with similar intrinsic properties such as average out-degree or network diameter) could be significantly different, making it imperative to use new metrics for characterizing networks. In the second part of the paper, we derive goodness factors based on service availability viewed from three perspectives: ingress node (from one node to many destinations), link (traffic traversing a link), and network-wide (across all source-destination pairs). We show how goodness factors can be used in various applications and describe our numerical results.

Recent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered the impact of inter-domain routing changes in BGP (Border Gateway Protocol) . BGP routing changes have the potential to introduce significant errors in estimated traffic matrices by causing traffic shifts between egress routers or PoPs within a single backbone network. We present a methodology to correlate BGP routing table changes with packet traces in order to analyze how BGP dynamics affect traffic fan-out within a large "tier-1" network. Despite an average of 133 BGP routing updates per minute, we find that BGP routing changes do not cause more than 0.03% of ingress traffic to shift between egress PoPs. This limited impact is mostly due to the relative stability of network prefixes that receive the majority of traffic -- 0.05% of BGP routing table changes affect intra-domain routes for prefixes that carry 80% of the traffic. Thus our work validates an important assumption underlying existing techniques for traffic matrix estimation in large IP networks.

We analyzed 70 voice traces collected from IP-telephony applications, multicast lectures, and multimedia conferencing sessions which involve multiple speakers and different dynamics of interaction beyond two-way conversations. Results show that application differences have significant impact on the traffic characteristics. The conventional exponential model, established for telephone conversations, fails to capture accurately the packet level activity observed in these traces, e.g., the heavy-tail distributions of the talk-spurt and silence periods. We classify the traces into four types based on their audio contents: audience, lecture, multi-party conferencing and conversation. Further analysis shows that Weibull is a better matching statistical model and achieves lower mean-square-error than the exponential model (by 1 to 2 orders of magnitude) in approximating the audio streams for all four cases.

Today's IP backbones are provisioned to provide excellent performance in terms of loss, delay and availability. However, performance degradation and service disruption are likely in the case of failure, such as fiber cuts, router crashes, etc. In this paper, we investigate the occurence of failures in Sprint's IP backbone and their potential impact on emerging services such as Voice-over-IP (VoIP). We first examine the frequency and duration of failure events derived from IS-IS routing updates collected from three different points in the Sprint IP backbone. We observe that link failures occur as part of everyday operation, and the majority of them are short-lived (less than 10 minutes). We also discuss various statistics such as the distribution of inter-failure time, distribution of link failure durations, etc. which are essential for constructing a realistic link failure model. Next, we present an analysis of routing and service reconvergence time during a controlled link failure scenario in our backbone. Our results indicate that disruption to packet forwarding after link failures depends not only on routing protocol dynamics, but also on the design of routers' architectures and control planes. Thus our results offer insights into two basic components for defining network-wide availability, which we consider a more appropriate metric for service-level agreements to support emerging applications.

Previous studies have shown that single-user systems employing n-element antenna arrays at both the transmitter and the receiver can achieve a capacity proportional to n, assuming independent Rayleigh fading between antenna pairs. We explore the capacity of dual-antenna-array systems under correlated fading via theoretical analysis and ray-tracing simulations. We derive and compare expressions for the asymptotic growth rate of capacity with n antennas for both independent and correlated fading cases; the latter is derived under some assumptions about the scaling of the fading correlation structure. In both cases, the theoretic capacity growth is linear in n but the growth rate is 10-20% smaller in the presence of correlated fading. We analyze our assumption of separable transmit/receive correlations via simulations based on a ray-tracing propagation model. Results show that empirical capacities converge to the limit capacity predicted from our asymptotic theory even at moderate n = 16. We present results for both the cases when the transmitter does and does not know the channel realization.

We demonstrate the capacity growth of multiple-element antenna arrays (MEAs) in a realistic propagation environment using WiSE, an experimental ray tracing tool. WiSE is used to construct the channel response for MEAs operating at 1.9 GHz for two situations: (a) (16-16)-MEAs located inside an office building and (b) (4, 4)-MEAs located in an outdoor fixed wireless loop. We define effective degrees of freedom (EDOFs) as parallel spatial modes of transmission for an MEA. We quantify the increase in both the number of EDOFs and capacity with transmit power, received SNR, and antenna spacing. More EDOFs are present when receiving MEAs are physically closer to the transmitting MEA, regardless of the scattering effect.

Wireless systems using multi-element antenna arrays simultaneously at the both transmitter and receiver promise a much higher capacity than conventional systems. Previous studies have shown that single-user systems employing n-element transmit and receive arrays can achieve a capacity proportional to n, assuming independent Rayleigh fading between pairs of antenna elements. We explore the capacity of dual-antenna-array systems via theoretical analysis and simulation experiments. We present expressions for the asymptotic growth rate of capacity with n for both independent and correlated fading cases; the latter is derived under some assumptions about the fading correlation structure. We show that the capacity growth is linear in n in both the independent and correlated cases, but the growth rate is smaller in the latter case. We compare the predictions of our asymptotic theory to the capacities of channels simulated using ray tracing, and find good agreement even for moderate n, i.e., 1/spl les/n/spl les/16. Our results address both the cases when the transmitter does and does not know the channel realization.

Previous work has shown that a handoff algorithm based on SIR alone (SIR based handoff) prohibits handoffs near nominal cell boundaries, causing cell dragging and unnecessarily high transmitter powers. We propose the minimum power handoff (MPH) algorithm in which mobiles constantly search for a combination of base and channel assignment that minimizes the uplink transmitted power. This algorithm is shown to reduce the average power level by 4dB compared to SIR based handoff. Results show that using received power as a handoff criterion reduces call dropping but increases the number of unnecessary handoffs significantly. To avoid a "ping pong" effect, a timer is introduced to delay the intercell handoff.