Recent studies reveal that vision-language models (VLMs) become more susceptible to harmful requests and jailbreak attacks after integrating the vision modality, exhibiting greater vulnerability than their text-only LLM backbones. To uncover the root cause of this phenomenon, we conduct an in-depth analysis and identify a key issue: multimodal inputs introduce an modality-induced activation shift toward a “safer” direction compared to their text-only counterparts, leading VLMs to systematically overestimate the safety of harmful inputs. We refer to this issue as safety perception distortion. To mitigate such distortion, we propose Activation Shift Disentanglement and Calibration (ShiftDC), a training-free method that decomposes and calibrates the modality-induced activation shift to reduce its impact on safety. By isolating and removing the safety-relevant component, ShiftDC restores the inherent safety alignment of the LLM backbone while preserving the vision-language capabilities of VLMs. Experiments demonstrate that ShiftDC significantly enhances safety alignment without impairing model utility.

Deep neural networks (DNNs) have achieved tremendous success in various applications including video action recognition, yet remain vulnerable to backdoor attacks (Trojans). The backdoor-compromised model will mis-classify to the target class chosen by the attacker when a test instance (from a non-target class) is embedded with a specific trigger, while maintaining high accuracy on attack-free instances. Although there are extensive studies on backdoor attacks against image data, the susceptibility of video-based systems under backdoor attacks remains largely unexplored. Current studies are direct extensions of approaches proposed for image data, e.g., the triggers are independently embedded within the frames, which tend to be detectable by existing defenses. In this paper, we introduce a simple yet effective backdoor attack against video data. Our proposed attack, adding perturbations in a transformed domain, plants an imperceptible, temporally distributed trigger across the video frames, and is shown to be resilient to existing defensive strategies. The effectiveness of the proposed attack is demonstrated by extensive experiments with various well-known models on two video recognition benchmarks, UCF101 and HMDB51, and a sign language recognition benchmark, Greek Sign Language (GSL) dataset. We delve into the impact of several influential factors on our proposed attack and identify an intriguing effect termed "collateral damage" through extensive studies.

Backdoor attacks are an important type of adversarial threat against deep neural network classifiers, wherein test samples from one or more source classes will be (mis)classified to the attacker’s target class when a backdoor pattern is embedded. In this paper, we focus on the post-training backdoor defense scenario commonly considered in the literature, where the defender aims to detect whether a trained classifier was backdoor-attacked without any access to the training set. Many post-training detectors are designed to detect attacks that use either one or a few specific backdoor embedding functions (e.g., patch-replacement or additive attacks). These detectors may fail when the backdoor embedding function used by the attacker (unknown to the defender) is different from the backdoor embedding function assumed by the defender. In contrast, we propose a post-training defense that detects backdoor attacks with arbitrary types of backdoor embeddings, without making any assumptions about the backdoor embedding type. Our detector leverages the influence of the backdoor attack, independent of the backdoor embedding mechanism, on the landscape of the classifier’s outputs prior to the softmax layer. For each class, a maximum margin statistic is estimated. Detection inference is then performed by applying an unsupervised anomaly detector to these statistics. Thus, our detector does not need any legitimate clean samples, and can efficiently detect backdoor attacks with arbitrary numbers of source classes. These advantages over several state-of-the-art methods are demonstrated on four datasets, for three different types of backdoor patterns, and for a variety of attack configurations. Finally, we propose a novel, general approach for backdoor mitigation once a detection is made. The mitigation approach was the runner-up at the first IEEE Trojan Removal Competition. The code is online available.

Data Poisoning (DP) is an effective attack that causes trained classifiers to misclassify their inputs. DP attacks significantly degrade a classifier's accuracy by covertly injecting attack samples into the training set. Broadly applicable to different classifier structures, without strong assumptions about the attacker, anunsupervisedBayesian Information Criterion (BIC)-based mixture model defense against “error generic” DP attacks is herein proposed that: 1) addresses the most challengingembeddedDP scenario wherein, if DP is present, the poisoned samples are ana prioriunknown subset of the training set, and with no clean validation set available; 2) applies a mixture model both to well-fit potentially multi-modal class distributions and to capture poisoned samples within a small subset of the mixture components; 3) jointly identifies poisoned components and samples by minimizing the BIC cost defined over the whole training set, with the identified poisoned data removed prior to classifier training. Our experimental results, for various classifier structures and benchmark datasets, demonstrate the effectiveness of our defense under strong DP attacks, as well as its superiority over other DP defenses.

A backdoor or Trojan attack is an important type of data poisoning attack against deep neural network (DNN) classifiers, wherein the training dataset is poisoned with a small number of samples that each possess the backdoor pattern (usually a pattern that is either imperceptible or innocuous) and which are mislabeled to the attacker’s target class. When trained on a backdoor-poisoned dataset, a DNN behaves normally on most benign test samples but makes incorrect predictions to the target class when the test sample has the backdoor pattern incorporated (i.e., contains a backdoor trigger). Here we focus on image classification tasks and show that supervised training may build stronger association between the backdoor pattern and the associated target class than that between normal features and the true class of origin. By contrast, self-supervised representation learning ignores the labels of samples and learns a feature embedding based on images’ semantic content. Using a feature embedding found by self-supervised representation learning, a data cleansing method, which combines sample filtering and relabeling, is developed. Experiments on CIFAR-10 benchmark datasets show that our method achieves state-of-the-art performance in mitigating backdoor attacks.

Deep neural networks (DNNs) are increasingly popular owing to their ability to solve complex problems such as image recognition, autonomous driving, and natural language processing. Their growing complexity coupled with the use of larger volumes of training data (to achieve acceptable accuracy) has warranted the use of GPUs and other accelerators. Such accelerators are typically expensive, with users having to pay a high upfront cost to acquire them. For infrequent use, users can, instead, leverage the public cloud to mitigate the high acquisition cost. However, with the wide diversity of hardware instances (particularly GPU instances) available in public cloud, it becomes challenging for a user to make an appropriate choice from a cost/performance standpoint. In this work, we try to address this problem by (i) introducing a comprehensive distributed deep learning (DDL) profiler Stash, which determines the various execution stalls that DDL suffers from, and (ii) using Stash to extensively characterize various public cloud GPU instances by running popular DNN models on them. Specifically, it estimates two types of communication stalls, namely, interconnect and network stalls, that play a dominant role in DDL execution time. Stash is implemented on top of prior work, DS-analyzer, that computes only the CPU and disk stalls. Using our detailed stall characterization, we list the advantages and shortcomings of public cloud GPU instances for users to help them make an informed decision(s). Our characterization results indicate that the more expensive GPU instances may not be the most performant for all DNN models and that AWS can sometimes sub-optimally allocate hardware interconnect resources. Specifically, the intra-machine interconnect can introduce communication overheads of up to 90% of DNN training time and the network-connected instances can suffer from up to 5× slowdown compared to training on a single instance. Furthermore, (iii) we also model the impact of DNN macroscopic features such as the number of layers and the number of gradients on communication stalls, and finally, (iv) we briefly discuss a cost comparison with existing work.

With the rapid growth of users adopting public clouds to run their applications, the types of resources procured from the different public cloud resource offerings are critical in simultaneously achieving satisfactory performance and reducing deployment costs. Typically, no one resource type can meet all application requirements, and thus combining different resource offerings is known to considerably reduce the performance-cost problem. However, it is non-trivial to use blended resources, due to the manual overhead of designing and implementing such blended approaches. Specifically, it necessitates rewriting the application code to suit a given resource and scaling it on demand. In order to overcome this manual hurdle, we take the first step by proposing Splice, an automated framework for cost-and performance-aware blending of IaaS and FaaS services. The three major goals of Splice are: (1) while cost-saving opportunities exist from blending resources, we aim to largely automate the blending process for public cloud services through a compiler-driven approach; (2) more specifically, we focus on automated blending of VMs and serverless functions; and (3) for serverless applications which contain multiple chained functions, we unearth the potential choices in determining a portion of the services to be blended cost-efficiently. We implement Splice on Amazon Web Services (AWS) using an Abstract Syntax Tree (AST), and extensively evaluate its effectiveness using several ap-plications with real-world traces. Our experiments demonstrate that, through automated blending, Splice is able to reduce SLO violations by 31 % compared to VM - based resource procurement schemes, while simultaneously minimizing costs by up to 32 %.

Backdoor (Trojan) attacks are emerging threats against deep neural networks (DNN). A DNN being attacked will predict to an attacker-desired target class whenever a test sample from any source class is embedded with a backdoor pattern, while correctly classifying clean (attack-free) test samples. Existing backdoor defenses have shown success in detecting whether a DNN is attacked and in reverse-engineering the backdoor pattern in a "post-training" scenario: the defender has access to the DNN to be inspected and a small, clean dataset collected independently, but has no access to the (possibly poisoned) training set of the DNN. However, these defenses neither catch culprits in the act of triggering the backdoor mapping, nor mitigate the backdoor attack at test-time. In this paper, we propose an "in-flight" unsupervised defense against backdoor attacks on image classification that 1) detects use of a backdoor trigger at test-time; and 2) infers the class of origin (source class) for a detected trigger example. The effectiveness of our defense is demonstrated experimentally for a wide variety of DNN architectures, datasets, and backdoor attack configurations.

Backdoor attacks (BA) are an emerging threat to deep neural network classifiers. A classifier being attacked will predict to the attacker’s target class when a test sample from a source class is embedded with the backdoor pattern (BP). Recently, the first BA against point cloud (PC) classifiers was proposed, creating new threats to many important applications including autonomous driving. Such PC BAs are not detectable by existing BA defenses due to their special BP embedding mechanism. In this paper, we propose a reverse-engineering defense that infers whether a PC classifier is backdoor attacked, without access to its training set or to any clean classifiers for reference. The effectiveness of our defense is demonstrated on the benchmark ModeNet40 dataset for PCs.

Using a flash-based layer to serve the caching and buffering needs of multiple workloads has become a common practice. In such settings, resource demands will inevitably exceed available capacity sometimes. "Fair" resource allocation may offer a systematic way of partitioning resources across competing workloads during such periods of scarcity. Existing works only offer fair allocation strategies for a single resource (capacity or bandwidth) within a flash device in isolation. However, since there exist multiple critical resources that need to be partitioned within a flash device and they are correlated to each other, fair allocation of a single resource may result in a waste of other resource(s) or performance degradation of workload(s). To this end, we make a case for multi-resource fair allocation solutions for flash-based caches that consolidate multiple workloads. Furthermore, we argue that device lifetime, which depends on the behavior of running workloads, should also be considered as a first-class resource on par with capacity and bandwidth. Specifically, we build upon existing ideas related to dominant resource fairness (DRF) to devise flash-specific multi-resource fair algorithms: (i) nDRF, that jointly allocates capacity and bandwidth taking their non-linear relationship into account; (ii) ℓDRF, that explicitly considers lifetime as well in its allocation; and (iii) several variants of these. Our experimental evaluation offers important findings: (i) both nDRF and ℓDRF result in superior performance fairness compared to the state-of-the-art techniques that partition capacity in isolation; (ii) ℓDRF additionally offers improved device "wear" behavior; and (iii) our algorithms combined with reasonable demand prediction work very well in online settings with workload dynamism and uncertainty.

With wide deployment of deep neural network (DNN) classifiers, there is great potential for harm from adversarial learning attacks. Recently, a special type of data poisoning (DP) attack, known as a backdoor (or Trojan), was proposed. These attacks do not seek to degrade classification accuracy, but rather to have the classifier learn to classify to a target class$t^{\ast }$whenever the backdoor pattern is present in a test example originally from a source class$s^{\ast }$. Launching backdoor attacks does not require knowledge of the classifier or its training process—only the ability to poison the training set with exemplars containing a backdoor pattern (labeled with the target class). Defenses against backdoors can be deployed before/during training, post-training, or at test time. Here, we address post-training detection in DNN image classifiers, seldom considered in existing works, whereinthe defender does not have access to the poisoned training set, but only to the trained classifier itself, as well as to clean (unpoisoned) examples from the classification domain. This scenario is of great interest because e.g., a classifier may be the basis of a phone app that will be shared with many users. Detection may thus reveal a widespread attack. We propose a purely unsupervised anomaly detection (AD) defense against imperceptible backdoor attacks that: 1) detects whether the trained DNN has been backdoor-attacked; 2) infers the source and target classes in a detected attack; 3) estimates the backdoor pattern itself. Our AD approach involves learning (via suitable cost function minimization) the minimum size/norm perturbation (putative backdoor) required to induce the classifier to misclassify (most) examples from class$s$to class$t$, for all$(s,t)$pairs. Our hypothesis is that nonattacked pairs require large perturbations, while the attacked pair$(s^{\ast }, t^{\ast })$requires much smaller ones. This is convincingly borne out experimentally. We identify a variety of plausible cost functions and devise a novel, robust hypothesis testing approach to perform detection inference. We test our approach, in comparison with the state-of-the-art methods, for several backdoor patterns, attack settings and mechanisms, and data sets and demonstrate its favorability. Our defense essentially requires setting a single hyperparameter (the detection threshold), which can e.g., be chosen to fix the system’s false positive rate.

Distributed data processing frameworks such as Hadoop, Tez, Spark, and Flink are exclusively used by public cloud tenants for executing large scale data analytics applications in various domains including but not limited to content management, financial sector, healthcare etc. These frameworks slice a job into a number of smaller tasks, which are then executed by a job scheduler on a multi-node compute cluster. While making scheduling decisions, the State-of-art schedulers employed in these frameworks assume hardware resources such as CPU, disk I/O and network I/O to offer a fixed service rate. However, in a public cloud environment, many of these resources are associated with burstable service rates. More specifically, the resources offer a guaranteed baseline service rate with an option to burst above their baseline rate by expending accumulated burst credits. Being unaware about this underlying hardware burstability, schedulers tend to make sub-optimal task placement decisions, thereby adversely affecting the job completion times, leading to higher deployment costs.In this paper, we propose CASH, a burst credit aware scheduler, which is cognizant about the burst credits associated with the individual hardware resources in the public cloud cluster. Through coarse grained task annotations depicting the burst credit demand of individual tasks and dynamically monitoring the credits for the underlying resources, CASH performs optimal task placement decisions. We prototype CASH on YARN, Hadoop, and Tez, and extensively evaluate it using both batch and streaming workloads. Our experimental results with CASH show CPU-credit based instances, like AWS T3, are a viable cost effective alternative when compared to self-managed offerings like Amazon EMR, for running large scale batch workloads. Furthermore, we demonstrate that CASH can accelerate streaming SQL queries on a large Hive database by up to 39.4% , leading to public cloud cost savings by up to 22%.

Microservices architecture have been widely adopted in designing distributed cloud applications where the application is decoupled into multiple small components (i.e. "microservices"). One of the challenges in deploying microservices is finding the optimal amount of resources (i.e. size) and the number of instances (i.e. replicas) for each microservice in order to maintain a good performance as well as prevent resource wastage and under-utilization which is not cost-effective. This paper presents SHOWAR, a framework that configures the resources by determining the number of replicas (horizontal scaling) and the amount of CPU and Memory for each microservice (vertical scaling). For vertical scaling, SHOWAR uses empirical variance in the historical resource usage to find the optimal size and mitigate resource wastage. For horizontal scaling, SHOWAR uses basic ideas from control theory along with kernel level performance metrics. Additionally, once the size for each microservice is found, SHOWAR bridges the gap between optimal resource allocation and scheduling by generating affinity rules (i.e. hints) for the scheduler to further improve the performance. Our experiments, using a variety of microservice applications and real-world workloads, show that, compared to the state-of-the-art autoscaling and scheduling systems, SHOWAR on average improves the resource allocation by up to 22% while improving the 99th percentile end-to-end user request latency by 20%.

Serverless computing is a rapidly growing paradigm in the cloud industry that envisions functions as the computational building blocks of an application. Instead of forcing the application developer to provision cloud resources for their application, the cloud provider provisions the required resources for each function "under the hood." In this work, we envision virtual serverless providers (VSPs) to aggregate serverless offerings. In doing so, VSPs allow developers (and businesses) to get rid of vendor lock-in problems and exploit pricing and performance variation across providers by adaptively utilizing the best provider at each time, forcing the providers to compete to offer cheaper and superior services. We discuss the merits of a VSP and show that serverless systems are well-suited to cross-provider aggregation, compared to virtual machines. We propose a VSP system architecture and implement an initial version. Using experimental evaluations, our preliminary results show that a VSP can improve maximum sustained throughput by 1.2x to 4.2x, reduces SLO violations by 98.8%, and improves the total invocations' costs by 54%.

Backdoor attacks (BAs) are an emerging form of adversarial attack typically against deep neural network image classifiers. The attacker aims to have the classifier learn to classify to a target class when test images from one or more source classes contain a backdoor pattern, while maintaining high accuracy on all clean test images. Reverse-Engineering-based Defenses (REDs) against BAs do not require access to the training set but only to an independent clean dataset. Unfortunately, most existing REDs rely on an unrealistic assumption that all classes except the target class are source classes of the attack. REDs that do not rely on this assumption often require a large set of clean images and heavy computation. In this paper, we propose a Lagrangian-based RED (L-RED) that does not require knowledge of the number of source classes (or whether an attack is present). Our defense requires very few clean images to effectively detect BAs and is computationally efficient. Notably, we detect 56 out of 60 BAs using only two clean images per class in our experiments on CIFAR-10.

Vulnerability of 3D point cloud (PC) classifiers has become a grave concern due to the popularity of 3D sensors in safety-critical applications. Existing adversarial attacks against 3D PC classifiers are all test-time evasion (TTE) attacks that aim to induce test-time misclassifications using knowledge of the classifier. But since the victim classifier is usually not accessible to the attacker, the threat is largely diminished in practice, as PC TTEs typically have poor transferability. Here, we propose the first backdoor attack (BA) against PC classifiers. Originally proposed for images, BAs poison the victim classifier’s training set so that the classifier learns to decide to the attacker’s target class whenever the attacker’s backdoor pattern is present in a given input sample. Significantly, BAs do not require knowledge of the victim classifier. Different from image BAs, we propose to insert a cluster of points into a PC as a robust backdoor pattern customized for 3D PCs. Such clusters are also consistent with a physical attack (i.e., with a captured object in a scene). We optimize the cluster’s location using an independently trained surrogate classifier and choose the cluster’s local geometry to evade possible PC preprocessing and PC anomaly detectors (ADs). Experimentally, our BA achieves a uniformly high success rate (≥ 87%) and shows evasiveness against state-of-the-art PC ADs. Code is available at https://github.com/zhenxianglance/PCBA.

Backdoor data poisoning attacks add mislabeled examples to the training set, with an embedded backdoor pattern, so that the classifier learns to classify to a target class whenever the backdoor pattern is present in a test sample. Here, we address posttraining detection of scene-plausible perceptible backdoors, a type of backdoor attack that can be relatively easily fashioned, particularly against DNN image classifiers. A post-training defender does not have access to the potentially poisoned training set, only to the trained classifier, as well as some unpoisoned examples that need not be training samples. Without the poisoned training set, the only information about a backdoor pattern is encoded in the DNN's trained weights. This detection scenario is of great import considering legacy and proprietary systems, cell phone apps, as well as training outsourcing, where the user of the classifier will not have access to the entire training set. We identify two important properties of scene-plausible perceptible backdoor patterns, spatial invariance and robustness, based on which we propose a novel detector using the maximum achievable misclassification fraction (MAMF) statistic. We detect whether the trained DNN has been backdoor-attacked and infer the source and target classes. Our detector outperforms existing detectors and, coupled with an imperceptible backdoor detector, helps achieve posttraining detection of most evasive backdoors of interest.

Recently, a special type of data poisoning (DP) attack against deep neural network (DNN) classifiers, known as a backdoor, was proposed. These attacks do not seek to degrade classification accuracy, but rather to have the classifier learn to classify to a target class whenever the backdoor pattern is present in a test example. Here, we address the challenging post-training detection of backdoor attacks in DNN image classifiers, wherein the defender does not have access to the poisoned training set, but only to the trained classifier itself, as well as to clean (unpoisoned) examples from the classification domain. We propose a defense against imperceptible backdoor attacks based on perturbation optimization and novel, robust detection inference. Our method detects whether the trained DNN has been backdoor-attacked and infers the source and target classes involved in an attack. It outperforms alternative defenses for several backdoor patterns, data sets, and attack settings.

Due to their lower startup latencies and finer-grain pricing than virtual machines (VMs), Amazon Lambdas and other cloud functions (CFs) have been identified as ideal candidates for handling unexpected spikes in simple, stateless workloads. However, it is not immediately clear if CFs would be similarly effective in autoscaling complex workloads involving significant state transfer across distributed application components. We have found that, through careful design, currently available CFs can indeed be useful even for complex workloads. To demonstrate this, we design and implement SplitServe, an enhancement of Apache Spark. If not enough executors on existing VMs are available for a newly arriving latency-sensitive job, SplitServe is able to use CFs to quickly bridge this shortfall in VMs, so avoiding the startup latencies of newly requested VMs. If desirable in terms of performance or cost, when newly requested VMs, or executors on existing VMs, do become available, SplitServe is able to move ongoing work from CFs to them. Our experimental evaluation of SplitServe using four different workloads (either on a mixture of VM-based executors and CFs or just CFs) shows that it improves execution time by up to (a) 55% for workloads with small to modest amount of shuffling, and (b) 31% in workloads with large amounts of shuffling, when compared to only VM-based autoscaling.

Computing systems have been facing severe technology challenges in recent years with regard to power consumption, circuit reliability, and high performance. For many years, the issues of power consumption and performance have been addressed with the use of technology scaling.However, as Dennard’s scaling tends toward an end, it has become difficult to further improve the performance under the same power constraints. In addition to power, reliability also becomes a critical issue when the feature size of the complementary metal-oxide–semiconductor (CMOS) technology is reduced below 7 nm. Thus, ensuring the complete accuracy of the signal has become increasingly challenging in recent years.

With wide deployment of machine learning (ML)-based systems for a variety of applications including medical, military, automotive, genomic, multimedia, and social networking, there is great potential for damage from adversarial learning (AL) attacks. In this article, we provide a contemporary survey of AL, focused particularly on defenses against attacks on deep neural network classifiers. After introducing relevant terminology and the goals and range of possible knowledge of both attackers and defenders, we survey recent work on test-time evasion (TTE), data poisoning (DP), backdoor DP, and reverse engineering (RE) attacks and particularly defenses against the same. In so doing, we distinguish robust classification from anomaly detection (AD), unsupervised from supervised, and statistical hypothesis-based defenses from ones that do not have an explicit null (no attack) hypothesis. We also consider several scenarios for detecting backdoors. We provide a technical assessment for reviewed works, including identifying any issues/limitations, required hyperparameters, needed computational complexity, as well as the performance measures evaluated and the obtained quality. We then delve deeper, providing novel insights that challenge conventional AL wisdom and that target unresolved issues, including: robust classification versus AD as a defense strategy; the belief that attack success increases with attack strength, which ignores susceptibility to AD; small perturbations for TTE attacks: a fallacy or a requirement; validity of the universal assumption that a TTE attacker knows the ground-truth class for the example to be attacked; black, gray, or white-box attacks as the standard for defense evaluation; and susceptibility of query-based RE to an AD defense. We also discuss attacks on the privacy of training data. We then present benchmark comparisons of several defenses against TTE, RE, and backdoor DP attacks on images. The article concludes with a discussion of continuing research directions, including the supreme challenge of detecting attacks whose goal is not to alter classification decisions, but rather simply to embed, without detection, “fake news” or other false content.

We consider a system in which there exists two ISPs, one “big” Content Provider (CP), and a continuum of End-Users (EUs). One of the ISPs is neutral and the other is non-neutral. We consider that the CP can differentiate between ISPs by controlling the quality of the content she is offering on each one. We also consider that EUs have different levels of innate preferences for ISPs. We formulate a sequential game, and explicitly characterize all the possible Sub-game Perfect Nash Equilibria (SPNE) of the game. We prove that if an SPNE exists, it would be one of the five possible strategies each of which we explicitly characterize. We prove that when EUs have sufficiently low innate preferences for ISPs, a unique SPNE exists in which the neutral ISP would be driven out of the market. We also prove that when these preferences are sufficiently high, there exists a unique SPNE with a non-neutral outcome in which both ISPs are active. Numerical results reveal that the neutral ISP receives a lower payoff and the non-neutral ISP receives a higher payoff (most of the time) in a non-neutral scenario. However, we identify scenarios in which the non-neutral ISP loses payoff by adopting non-neutrality. We also show that a non-neutral regime yields a higher welfare for EUs in comparison to a neutral one if the market power of the non-neutral ISP is small, the sensitivity of EUs (respectively, the CP) to the quality is low (respectively, high), or a combinations of these factors.

We are witnessing the emergence of elastic web services which are hosted in public cloud infrastructures. For reasons of cost-effectiveness, it is crucial for the elasticity of these web services to match the dynamically-evolving user demand. Traditional approaches employ clusters of virtual machines (VMs) to dynamically scale resources based on application demand. However, they still face challenges such as higher cost due to over-provisioning or incur service level objective (SLO) violations due to under-provisioning. Motivated by this observation, we propose Spock, a new scalable and elastic control system that exploits both VMs and serverless functions to reduce cost and ensure SLO for elastic web services. We show that under two different scaling policies, Spock reduces SLO violations of queries by up to 74% when compared to VM-based resource procurement schemes. Further, Spock yields significant cost savings, by up to 33% compared to traditional approaches which use only VMs.

Amazon Web Services (AWS) Lambdas and other "cloud functions" (CFs) offer much lower startup latencies than virtual machines (VMs) (tens/hundreds of milliseconds vs. a few/several minutes) with lower minimum cost. This makes it appealing to use them for handling unexpected spikes in simple, stateless workloads [2, 3, 5]. If the spike persists, additional VMs may be launched and CFs can be decommissioned when the VMs are ready (VMs are cheaper per unit resource procured than CFs). However, it is not immediately clear if using CFs for complex workloads - those involving significant state exchange among components - is similarly effective. Current CFs have several restrictions that may limit their efficacy: (i) relatively limited resource capacity, especially main memory (e.g., an AWS Lambda may only have up to 3GB memory), (ii) limited lifetime (e.g., Lambdas are terminated after 15 minutes), and (iii) limited support for sharing of intermediate state (e.g., Lambdas must employ an external storage system such as AWS S3). Contrary to conventional wisdom, we show that it is possible to exploit the faster startup times of CFs to improve cost and performance of autoscaling even for complex workloads.

This paper addresses detection of a reverse engineering (RE) attack targeting a deep neural network (DNN) image classifier; by querying, RE's aim is to discover the classifier's decision rule. RE can enable test-time evasion attacks, which require knowledge of the classifier. Recently, we proposed a quite effective approach (ADA) to detect test-time evasion attacks. In this paper, we extend ADA to detect RE attacks (ADA-RE). We demonstrate our method is successful in detecting "stealthy" RE attacks before they learn enough to launch effective test-time evasion attacks.

A significant threat to the recent, wide deployment of machine learning-based systems, including deep neural networks (DNNs), is adversarial learning attacks. The main focus here is on evasion attacks against DNN-based classifiers at test time. While much work has focused on devising attacks that make small perturbations to a test pattern (e.g., an image) that induce a change in the classifier's decision, until recently there has been a relative paucity of work defending against such attacks. Some works robustify the classifier to make correct decisions on perturbed patterns. This is an important objective for some applications and for natural adversary scenarios. However, we analyze the possible digital evasion attack mechanisms and show that in some important cases, when the pattern (image) has been attacked, correctly classifying it has no utility---when the image to be attacked is (even arbitrarily) selected from the attacker's cache and when the sole recipient of the classifier's decision is the attacker. Moreover, in some application domains and scenarios, it is highly actionable to detect the attack irrespective of correctly classifying in the face of it (with classification still performed if no attack is detected). We hypothesize that adversarial perturbations are machine detectable even if they are small. We propose a purely unsupervised anomaly detector (AD) that, unlike previous works, (1) models the joint density of a deep layer using highly suitable null hypothesis density models (matched in particular to the nonnegative support for rectified linear unit (ReLU) layers); (2) exploits multiple DNN layers; and (3) leverages a source and destination class concept, source class uncertainty, the class confusion matrix, and DNN weight information in constructing a novel decision statistic grounded in the Kullback-Leibler divergence. Tested on MNIST and CIFAR image databases under three prominent attack strategies, our approach outperforms previous detection methods, achieving strong receiver operating characteristic area under the curve detection accuracy on two attacks and better accuracy than recently reported for a variety of methods on the strongest (CW) attack. We also evaluate a fully white box attack on our system and demonstrate that our method can be leveraged to strong effect in detecting reverse engineering attacks. Finally, we evaluate other important performance measures such as classification accuracy versus true detection rate and multiple measures versus attack strength.

In this paper, we study cost-efficient and fair allocation of multiple types of resources in an environment of heterogeneous and self-organizing servers. To address this problem, we formulate an optimization problem which aims at minimizing the operational costs for all servers, while providing fairness across different users. We propose a fully distributed implementation to solve this problem. The proposed mechanism is shown to achieve envy-freeness among different users. Furthermore, we show how it captures the trade-off between cost-efficiency and fairness. We employ numerical experiments to show the effectiveness of our proposed mechanism in reducing operational costs for a geo-distributed data-center.

We first consider the static problem of allocating resources to (i.e., scheduling) multiple distributed application frameworks, possibly with different priorities and server preferences, in a private cloud with heterogeneous servers. Several fair scheduling mechanisms have been proposed for this purpose. We extend prior results on max-min fair (MMF) and proportional fair (PF) scheduling to this constrained multiresource and multiserver case for generic fair scheduling criteria. The task efficiencies (a metric related to proportional fairness) of max-min fair allocations found by progressive filling are compared by illustrative examples. In the second part of this paper, we consider the online problem (with framework churn) by implementing variants of these schedulers in Apache Mesos using progressive filling to dynamically approximate max-min fair allocations. We evaluate the implemented schedulers in terms of overall execution time of realistic distributed Spark workloads. Our experiments show that resource efficiency is improved and execution times are reduced when the scheduler is "server specific" or when it leverages characterized required resources of the workloads (when known).

In this article, we explore the efficacy of dynamic effective capacity modulation (i.e., using virtualization techniques to offer lower resource capacity than that advertised by the cloud provider) as a control knob for a cloud provider’s profit maximization complementing the more well-studied approach of dynamic pricing. In particular, our focus is on emerging cloud ecosystems wherein we expect tenants to modify their demands strategically in response to such modulation in effective capacity and prices. Toward this, we consider a simple model of a cloud provider that offers a single type of virtual machine to its tenants and devise a leader/follower game-based cloud control framework to capture the interactions between the provider and its tenants. We assume both parties employ myopic control and short-term predictions to reflect their operation under the high dynamism and poor predictability in such environments. Our evaluation using a combination of real data center traces and real-world benchmarks hosted on a prototype OpenStack-based cloud shows 10% to 30% profit improvement for a cloud provider compared with baselines that use static pricing and/or static effective capacity.

Efficient and fair allocation of multiple types of resources is a crucial objective in a cloud/distributed computing cluster. Users may have diverse resource needs. Furthermore, diversity in server properties/capabilities may mean that only a subset of servers may be usable by a given user. In platforms with such heterogeneity, we identify important limitations in existing multi-resource fair allocation mechanisms, notably Dominant Resource Fairness and its follow-up work. To overcome such limitations, we propose a new server-based approach; each server allocates resources by maximizing a per-server utility function. We propose a specific class of utility functions which, when appropriately parameterized, adjusts the trade-off between efficiency and fairness, and captures a variety of fairness measures (such as our recently proposed Per-Server Dominant Share Fairness ). We establish conditions for the proposed mechanism to satisfy certain properties that are generally deemed desirable, e.g., envy-freeness, sharing incentive, bottleneck fairness, and Pareto optimality. To implement our resource allocation mechanism, we develop an iterative algorithm which is shown to be globally convergent. Subsequently, we show how the proposed mechanism could be implemented in a distributed fashion. Finally, we carry out extensive trace-driven simulations to show the enhanced performance of our proposed mechanism over the existing ones.

We consider a single, unaffiliated streaming content provider (CP) and another that is vertically integrated (affiliated) with a cellular wireless ISP. We formulate a non-cooperative game between these two CPs involving, e.g., linear demand-response to price by the end-users with long-duration sessions (e.g., streaming video), and a model as amplified noise of additional network delay jitter and reduced responsiveness to changing channel conditions by the unaffiliated CP. The effect of effective additional side-payments from the unaffiliated CP to the ISP, as may be set by a government regulator, is studied at Stackelberg equilibrium both analytically and numerically.

In order to keep the costs of operating in-memory storage on the public cloud low, we devise novel ideas and enabling modeling and optimization techniques for combining conventional Amazon EC2 instances with the cheaper spot and burstable instances. Whereas a naturally appealing way of using failure-prone spot instances is to selectively store unpopular ("cold") content, we show that a form of "hot-cold mixing" across regular and spot instances might be more cost-effective. To overcome performance degradation resulting from spot instance revocations, we employ a highly available passive backup using the recently emergent burstable instances. We show how the idiosyncratic resource allocations of burstable instances make them ideal candidates for such a backup. We implement all our ideas in an EC2-based memcached prototype. Using simulations and live experiments on our prototype, we show that (i) our hot-cold mixing, informed by our modeling of spot prices, helps improve cost savings by 50-80% compared to only using regular instances, and (ii) our burstable-based backup helps reduce performance degradation during spot revocation, e.g., the 95% latency during failure recovery improves by 25% compared to a backup based on regular instances.

In a variety of Network-based Intrusion Detection System (NIDS) applications, one desires to detect groups of unknown attack (e.g., botnet) packet-flows, with a group potentially manifesting its a typicality (relative to a known reference “normal”/null model) on a low-dimensional subset of the full measured set of features used by the IDS. What makes this anomaly detection problem quite challenging is that it is a priori unknown which (possibly sparse) subset of features jointly characterizes a particular application, especially one that has not been seen before, which thus represents an unknown behavioral class (zero-day threat). Moreover, nowadays botnets have become evasive, evolving their behavior to avoid signature-based IDSes. In this work, we apply a novel active learning (AL) framework for botnet detection, facilitating detection of unknown botnets (assuming no ground truth examples of same). We propose a new anomaly-based feature set that captures the informative features and exploits the sequence of packet directions in a given flow. Experiments on real world network traffic data, including several common Zeus botnet instances, demonstrate the advantage of our proposed features and AL system.

Users of cloud computing platforms pose different types of demands for multiple resources on servers (physical or virtual machines). Besides differences in their resource capacities, servers may be additionally heterogeneous in their ability to service users - certain users' tasks may only be serviced by a subset of the servers. We identify important shortcomings in existing multi-resource fair allocation mechanisms - Dominant Resource Fairness (DRF) and its follow up work - when used in such environments. We develop a new fair allocation mechanism called Per-Server Dominant-Share Fairness (PS-DSF) which we show offers all desirable sharing properties that DRF is able to offer in the case of a single “resource pool” (i.e., if the resources of all servers were pooled together into one hypothetical server). We evaluate the performance of PS-DSF through simulations. Our evaluation shows the enhanced efficiency of PS-DSF compared to the existing allocation mechanisms. We argue how our proposed allocation mechanism is applicable in cloud computing networks and especially large scale data-centers.

A significant fraction of the operational expenditures incurred by cloud service providers relates to their networking (Internet access) and electricity consumption. Both depend on the peak-demand over the billing interval. In the future, cloud services providers may in turn recoup these costs from their long-term customers through peak-based pricing. We explore two different methods for the cloud provider to recoup this charge: (i) equal allocation and (ii) proportional to usage allocation. Furthermore, we consider multiple strategic tenants whose active demand response to cloud price settings jointly depends on job responsiveness (modeled as queueing delay of admitted jobs) and lost/shed workload (due to excessive delay). Under certain conditions, we prove existence and uniqueness of Nash equilibria for regimes (i) and (ii). Due to nonconvexity in the utility (or cost) functions, existence statements require leveraging potentiality arguments while uniqueness statements rely on imposing further convexityrequirements. The resulting Nash equilibrium is parametrized by the price per unit demand, which may be strategically set by the cloud to maximize its revenue subject to tenants reaching a Nash equilibrium. We model the resulting interactions as a Stackelberg game between the cloud and a set of tenants. A relatively general existence statement is provided for the Stackelberg equilibrium under regime (i). For a special case of regime (ii), the unique Stackelberg equilibrium is characterized. Finally, we provide a numerical study for such a framework using real-world peak-based prices from an electric utility and demands given by Google workload traces".

A datacenter's power consumption is a major contributor to its operational expenditures (op-ex) and one-time capital expenditures (cap-ex). The recurring electricity cost is often in large determined by datacenter peak-demand under peak-based pricing which is employed by major electric utility providers. There is a growing interest in reducing a datacenter's electricity costs by using throttling techniques and/or energy storage devices (batteries) which are readily available at most datacenters as a backup energy source. A datacenter's power-demand uncertainty makes this a challenging problem, which is largely neglected in existing work, by assuming perfect predictability of power demand. We model this inherent uncertainty as a Markov chain and also evaluate the risk of over/under charging batteries as a result of the randomness in power demand. We design an online optimization framework for peak shaving which considers Conditional Value at Risk and allows for navigating cost-risk trade-offs of datacenters based on their energy infrastructure and workload characteristics. We show that this framework offers significantly higher (up to 2X) cost-savings with small risks of over/under charging batteries, compared to existing stochastic optimization techniques. This framework leverages Markov Decision Processes to perform online dynamic peak shaving, considering battery degradation costs under peak-based pricing.

We investigate semisupervised learning (SL) and pool-based active learning (AL) of a classifier for domains with label-scarce (LS) and unknown categories, i.e., defined categories for which there are initially no labeled examples. This scenario manifests, e.g., when a category is rare, or expensive to label. There are several learning issues when there are unknown categories: 1) it is a priori unknown which subset of (possibly many) measured features are needed to discriminate unknown from common classes and 2) label scarcity suggests that overtraining is a concern. Our classifier exploits the inductive bias that an unknown class consists of the subset of the unlabeled pool's samples that are atypical (relative to the common classes) with respect to certain key (albeit a priori unknown) features and feature interactions. Accordingly, we treat negative log- p -values on raw features as nonnegatively weighted derived feature inputs to our class posterior, with zero weights identifying irrelevant features. Through a hierarchical class posterior, our model accommodates multiple common classes, multiple LS classes, and unknown classes. For learning, we propose a novel semisupervised objective customized for the LS/unknown category scenarios. While several works minimize class decision uncertainty on unlabeled samples, we instead preserve this uncertainty [maximum entropy (maxEnt)] to avoid overtraining. Our experiments on a variety of UCI Machine learning (ML) domains show: 1) the use of p -value features coupled with weight constraints leads to sparse solutions and gives significant improvement over the use of raw features and 2) for LS SL and AL, unlabeled samples are helpful, and should be used to preserve decision uncertainty (maxEnt), rather than to minimize it, especially during the early stages of AL. Our AL system, leveraging a novel sample-selection scheme, discovers unknown classes and discriminates LS classes from common ones, with sparing use of oracle labeling.

Network function virtualization along with network service chaining and forwarding graphs envision a reduction in the respective cost that end users, service providers, and network operators are experiencing, while providing complete and high quality services. The allocation of these service chains in a pool of available cloud or data center resources is a challenging problem that can affect the overall performance of the offered network services. Furthermore, a number of challenges associated with the hardware capabilities and the available resources of the cloud infrastructure, along with possible collocation constraints between the components of the service chain, can exponentially increase the complexity of resource allocation. This paper examines how to improve the overall allocation performance of deploying service chains in a cloud environment satisfying server affinity, collocation, and latency constraints. The proposed method is inspired by a partitioning game, where the various components of a service chain are split in a set of partitions executed as virtual machines/containers in appropriate servers. We mathematically prove that a Nash equilibrium exists for our partitioning game corresponding to an optimal solution. By implementing the partitioning game as an iterative refinement process, we also experimentally validate that the proposed algorithm converges to the optimal solution.

Sharing photos through Online Social Networks is an increasingly popular fashion. However, it poses a seriousthreat to end users as private information in the photos maybe inappropriately shared with others without their consent. This paper proposes a design and implementation of a system using a dynamic privacy preserving partial image sharing technique (namely PUPPIES), which allows data owners to stipulate specific private regions (e.g., face, SSN number) in an image and correspondingly set different privacy policies for each user. As a generic technique and system, PUPPIES targets at threats about over-privileged and unauthorized sharing of photos at photo service provider (e.g., Flicker, Facebook, etc) side. To this end, PUPPIES leverages the image perturbation technique to "encrypt" the sensitive areas in the original images, and therefore it can naturally support popular image transformations (such as cropping, rotation) and is well compatible with most image processing libraries. The extensive experiments on 19,000 images demonstrate that PUPPIES is very effective for privacy protection and incurs only a small computational overhead. In addition, PUPPIES offers high flexibility for different privacy settings, and is very robust to different types of privacy attacks.

We describe a scheduler for multiple servers shared among different packet-flows, where each packet-flow may be served by only a subset of available (preferred) servers. The scheduler allocates tokens to flows in a round-by-round manner, where token allocation to flows at the beginning of each round is weighted max-min fair. We present a packet scheduling scheme where when a server becomes free, it is allocated to serve the HOL packet of an eligible flow with the maximum remaining tokens. The scheduling algorithm is applicable even when the capacity of servers are not known a priori and may vary over duration of a round. Numerical examples are given to illustrate that the scheduler itself is weighted max-min fair.

Network Function Virtualization along with Network Service Chaining envision a reduction in the respective cost that end users, service providers, and network operators are experiencing, while providing complete and high quality services. However, the vast range of available services and the service on-demand model, creates dynamic traffic conditions that necessitates a flexible and automatic network platform to redirect traffic according to network conditions. In this paper, we study the problem of deploying service chains, consisting of a number of virtualized network functions (VNFs), in a SDN enabled data center network, where a random number of users are associated with each service chain. To this end, appropriate resource management algorithms are introduced for the placement of VNFs satisfying server affinity and latency constraints. The interconnection of the VNFs is facilitated by an SDN controller, which periodically recalculates the routing paths to adjust to the dynamic traffic conditions.

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity, e.g., reflecting their degree of altruism, and heterogenous class-based likelihoods of query resolution at nodes which may reflect query loads and the manner in which files/resources are distributed across the network. The approach is shown to be stabilize the query load subject to a grade of service constraint, i.e., a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. An explicit characterization of the capacity region for such systems is given and numerically compared to that associated with random walk based searches. Simulation results further show the performance benefits, in terms of mean delay, of the proposed approach. Additional aspects associated with reducing complexity, estimating parameters, and adaptation to class-based query resolution probabilities and traffic loads are studied.

Sharing photos through Online Social Networks becomes an increasingly popular fashion. However, users' privacy may be at stake when sensitive photos are shared improperly. This paper presents a dynamic privacy protection technique (named PuPPIeS) for image data where the data owner stipulates small private regions for sensitive objects (faces, SSN numbers, etc.) of a photo/image and sets different sharing policies for these partial regions with respect to different individuals. PuPPIeS is based on optimized reversible matrix perturbation of compressed image data. Hence it can naturally support frequently used image transformations. Our experiments show that our solution is effective for privacy protection and incurs only a small overhead for partial image sharing.

The costs incurred by cloud providers towards operating their data centers are often determined in large part by their peak demands. The pricing schemes currently used by cloud providers to recoup these costs from their tenants, however, do not distinguish tenants based on their contributions to the cloud's overall peak demand. Using the concrete example of peak-based pricing as employed by many electric utility companies, we show that this "gap" may lead to unfair attribution of costs to the tenants. Simple enhancements of existing cloud pricing (e.g., analogous to the coincident peak pricing (CPP) used by some electric utilities) do not adequately address these shortcomings and suffer from short-term unfairness and undesirable oscillatory price vs. demand relationship offered to tenants. To overcome these shortcomings, we define an alternative pricing scheme to more fairly distribute a cloud's costs among its tenants. Our approach to fair attribution of cloud's costs is inspired by the concept of Shapley values used to fairly divide revenue among participants of a financial coalition. We demonstrate the efficacy of our scheme under price-sensitive tenant demand response using a combination of (i) extensive empirical evaluation with recent workloads from commercial data centers operated by IBM, and (ii) analytical modeling through non-cooperative game theory for a special case of tenant demand model.

Crowdsourcing allows instant recruitment of workers on the web to annotate image, webpage, or document databases. However, worker unreliability prevents taking a worker's responses at “face value”. Thus, responses from multiple workers are typically aggregated to more reliably infer ground-truth answers. We study two approaches for crowd aggregation on multicategory answer spaces: stochastic modeling-based and deterministic objective function-based. Our stochastic model for answer generation plausibly captures the interplay between worker skills, intentions, and task difficulties and captures a broad range of worker types. Our deterministic objective-based approach aims to maximize the average aggregate confidence of weighted plurality crowd decision making. In both approaches, we explicitly model the skill and intention of individual workers, which is exploited for improved crowd aggregation. Our methods are applicable in both unsupervised and semi-supervised settings, and also when the batch of tasks is heterogeneous, i.e., from multiple domains, with task-dependent answer spaces. As observed experimentally, the proposed methods can defeat “tyranny of the masses”, i.e., they are especially advantageous when there is an (a priori unknown) minority of skilled workers amongst a large crowd of unskilled (and malicious) workers.

This paper considers a hybrid peer-to-peer (p2p) system, a dynamic distributed caching system with an authoritative server dispensing contents only if the contents fail to be found by searching an unstructured p2p system. We study the case when some peers may not be fully cooperative in the search process and examine the impact of various noncooperative behaviors in the aspect of scalability, more specifically average server load and average peer load as the peer population size increases. We categorize selfish peers into three classes: impatient peers that directly query the server without searching the p2p system, non-forwarders that refuse to forward query requests, and non-resolvers that refuse to share contents. It is shown that in the hybrid p2p system, impatient and/or non-forwarding behaviors prevent the system from scaling well because of the high server load, while the system scales well under the non-resolving selfish peers. Our study implies that the hybrid p2p system does not mandate an incentive mechanism for content sharing, which is in stark contrast to unstructured p2p systems, where incentivizing peers to share contents is known to be a key factor for the system's scalability.

In this paper, we study the problem of differential pricing and QoS assignment by a broadband data provider. In our model, the broadband data provider decides on the power allocated to an end-user not only based on parameters of the transmission medium, but also based on the price the user is willing to pay. In addition, end-users bid the price that they are willing to pay to the Base Station (BS) based on their channel condition, the throughput they require, and their belief about other users' parameters. We will characterize the optimum power allocation by the BS which turns out to be a modification of the solution to the well-known water-filling problem. We also characterize the optimum bidding strategy of end-users using the belief of each user about the cell condition.

We study the problem of optimizing data center electric utility bill under uncertainty in workloads and real-world pricing schemes. Our focus is on using control knobs that modulate the power consumption of IT equipment. To overcome the difficulty of casting/updating such control problems and the computational intractability they suffer from in general, we propose and evaluate a hierarchical optimization framework wherein an upper layer uses (i) temporal aggregation to restrict the number of decision instants during a billing cycle to computationally feasible values, and (ii) spatial (i.e., control knob) aggregation whereby it models the large and diverse set of power control knobs with two abstract knobs labeled demand dropping and demand delaying. These abstract knobs operate upon a fluid power demand. The key insight underlying our modeling is that the power modulation effects of most IT control knobs can be succinctly captured as dropping and/or delaying a portion of the power demand. These decisions are passed onto a lower layer that leverages existing research to translate them into decisions for real IT knobs. We develop a suite of algorithms for our upper layer that deal with different forms of input uncertainty. An experimental evaluation of the proposed approach offers promising results: e.g., it offers net cost savings of about 25% and 18% to a streaming media server and a MapReduce-based batch workload, respectively.

We consider private commons for secondary sharing of licensed spectrum bands with no access coordination provided by the primary license holder. In such environments, heterogeneity in demand patterns of the secondary users can lead to constant changes in the interference levels, and thus can be a source of volatility to the utilities of the users. In this paper, we consider secondary users to be service providers that provide downlink services. We formulate the spectrum sharing problem as a non-cooperative iterated game of power control where service providers change their power levels to fix their long-term average rates at utility-maximizing values. First, we show that in any iterated 2x 2 game, the structure of the single-stage game dictates the degree of control that a service provider can exert on the long-term outcome of the game. Then we show that if service providers use binary actions either to access or not to access the channel at any round of the game, then the long-term rate can be fixed regardless of the strategy of the opponent. We identify these rates and show that they can be achieved using mixed Markovian strategies which will be also identified.

A new method for semisupervised learning from pairwise sample (must- and cannot-link) constraints is introduced. It addresses an important limitation of many existing methods, whose solutions do not achieve effective propagation of the constraint information to unconstrained samples. We overcome this limitation by constraining the solution to comport with a smooth (soft) class partition of the feature space, which necessarily entails constraint propagation and generalization to unconstrained samples. This is achieved via a parameterized mean-field approximation to the posterior distribution over component assignments, with the parameterization chosen to match the representation power of the chosen (generative) mixture density family. Unlike many existing methods, our method flexibly models classes using a variable number of components, which allows it to learn complex class boundaries. Also, unlike most of the methods, ours estimates the number of latent classes present in the data. Experiments on synthetic data and data sets from the UC Irvine machine learning repository show that, overall, our method achieves significant improvements in classification performance compared with the existing methods.

This paper considers a hybrid peer-to-peer (p2p) system, a dynamic distributed caching system with an authoritative server dispensing contents only if the contents fail to be found by searching an unstructured peer-to-peer (p2p) system. We study the case when some peers may not be fully cooperative in the search process and examine the impact of various noncooperative behaviors on the querying load on the server as the peer population size increases. We categorize selfish peers into three classes: impatient peers that directly query the server without searching the p2p system, non-forwarders that refuse to forward query requests, and non-resolvers that refuse to share contents. It is shown that in the hybrid p2p system, impatient and/or nonforwarding behaviors prevent the system from scaling well because of the high server load, while the system scales well under the non-resolving selfish peers. Our study implies that the hybrid p2p system does not mandate an incentive mechanism for content sharing, which is in stark contrast to unstructured p2p systems, where incentivizing peers to share contents is known to be a key factor for the system's scalability.

Recently, economic models have been proposed to study adoption dynamics of entrant and incumbent technologies motivated by the need for new network architectures to complement the current Internet. We propose new models of adoption dynamics of entrant and incumbent technologies among bounded rational users who choose a satisfying strategy rather than an optimal strategy based on aspiration-based learning. Two models of adoption dynamics are proposed according to the characteristics of aspiration level. The impacts of switching cost, the benefit from entrant and incumbent technologies, and the initial aspiration level on the adoption dynamics are investigated.

This paper is concerned with the issue of side payments between content providers (CPs) and Internet service (access bandwidth) providers (ISPs) in an Internet that is potentially not neutral. We herein generalize past results modeling the ISP and CP interaction as a noncooperative game in two directions. We consider different demand response models (price sensitivities) for different provider types in order to explore when side payments are profitable to the ISP. Also, we consider convex (non-linear) demand response to model demand triggered by traffic which is sensitive to access bandwidth congestion, particularly delay-sensitive interactive real-time applications.

We consider unsupervised crowdsourcing performance based on the model wherein the responses of end-users are essentially rated according to how their responses correlate with the majority of other responses to the same subtasks/questions. In one setting, we consider an independent sequence of identically distributed crowdsourcing assignments (meta-tasks), while in the other we consider a single assignment with a large number of component subtasks. Both problems yield intuitive results in which the overall reliability of the crowd is a factor.

We model the aggregate overnight demand for electricity by a large community of (possibly hybrid) plug-in electric vehicles (PEVs) each of whose power demand follows a prescribed profile and is interruptible. The community is served by a regional electrical utility which is assumed to purchase electricity from a state/national distribution grid according to a flat-rate Φ per kilowatt-unit-time up to a threshold L, and thereafter overage (demand >; L) charges π >; Φ are leveed per kilowatt-unit-time. Rather than a spot-price system for household consumers (which would necessarily need to be operated by automated means overnight when most consumers sleep), the “grid” (regional utility) is “smart” in that it monitors its total load and, when overages threaten, can reduce load by signaling certain consumers to interrupt charging and defer their charging load by one unit of time. In this paper, we model the uninterrupted load by a Gaussian process which we justify by means of a functional central limit theorem (FCLT). This limiting Gaussian process is the arrival process of a discrete-time queue which is used to model the (partially) interrupted and deferred load over a finite time-horizon. We can then compute the mean amount of overage at the end of this time horizon (say at 6 AM when charging is to be completed ahead of the morning commute).

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a dynamic query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity and heterogenous class-based likelihoods of query resolution at nodes, reflecting the query loads and manner in which files/resources are distributed across the network. Finite processing capacity at nodes, e.g., reflecting their degree of altruism, can indeed limit the stabilizable load into the system. Our approach is shown to be throughput optimal subject to a grade of service constraint, i.e., it stabilizes the query load subject to a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. Numerical and simulation results show significant improvement in capacity region and performance benefits, in terms of mean delay, over random walk based searches. Additional aspects associated with reducing complexity, learning, and adaptation to class-based query resolution probabilities and traffic loads are studied.

We consider a game theoretic model incorporating channel state information into slotted ALOHA in a fading environment. Each user sets a threshold for her channel gain and sends a packet only when the channel gain is higher than the threshold at a given slot. This threshold is decided to maximize the net benefit of a user, utility minus power consumption. The asymptotic behaviors of the total throughput at a symmetric Nash equilibrium point are studied for fading and non-fading environments in a homogeneous system. It is shown that the total throughput in a fading environment increases as the number of users increases, while the total throughput in the simple classical slotted ALOHA decreases when users are sensitive enough to power consumption. Convergence to the symmetric Nash equilibrium is also studied.

We introduce new inductive, generative semisupervised mixtures with more finely grained class label generation mechanisms than in previous work. Our models combine advantages of semisupervised mixtures, which achieve label extrapolation over a component, and nearest-neighbor (NN)/nearest-prototype (NP) classification, which achieve accurate classification in the vicinity of labeled samples or prototypes. For our NN-based method, we propose a novel two-stage stochastic data generation, with all samples first generated using a standard finite mixture and then all class labels generated, conditioned on the samples and their components of origin. This mechanism entails an underlying Markov random field, specific to each mixture component or cluster. We invoke the pseudo-likelihood formulation, which forms the basis for an approximate generalized expectation-maximization model learning algorithm. Our NP-based model overcomes a problem with the NN-based model that manifests at very low labeled fractions. Both models are advantageous when within-component class proportions are not constant over the feature space region “owned by” a component. The practicality of this scenario is borne out by experiments on UC Irvine data sets, which demonstrate significant gains in classification accuracy over previous semisupervised mixtures and also overall gains, over KNN classification. Moreover, for very small labeled fractions, our methods overall outperform supervised linear and nonlinear kernel support vector machines.

Despite its existing incentives for leecher cooperation, BitTorrent file sharing fundamentally relies on the presence of seeder peers. Seeder peers essentially operate outside the BitTorrent incentives, with two caveats: slow downlinks lead to increased numbers of "temporary" seeders (who left their console, but will terminate their seeder role when they return), and the copyright liability boon that file segmentation offers for permanent seeders. Using a simple epidemic model for a two segment BitTorrent swarm, we focus on the BitTorrent rule to disseminate the (locally) rarest segments first. With our model, we show that the rarest-segment first rule minimizes transition time to seeder (complete file acquisition) and equalizes the segment populations in steady-state. We discuss how alternative dissemination rules may beneficially increase file acquisition times causing leechers to remain in the system longer (particularly as temporary seeders). The result is that leechers are further enticed to cooperate. This eliminates the threat of extinction of rare segments which is prevented by the needed presence of permanent seeders. Our model allows us to study the corresponding trade-offs between performance improvement, load on permanent seeders, and content availability, which we leave for future work.

Decentralized reputation systems help to enforce discipline and fairness in large unstructured and ad-hoc systems by rewarding good behavior and penalizing dishonest or greedy behavior. They are essential in large networks of independent nodes where centralized monitoring of node behavior is difficult due to the sheer size of the network. Sybil nodes pose a threat to the reputation systems by false referrals through sybil identities. We propose a scalable and distributed algorithm to identify attack edges and quarantine sybil clusters. This algorithm works well with dynamic trust graphs as nodes do not need to store any pre-computed data.

Flow classification by application type is motivated by on-line anomaly detection, off-line network planning, and on-line enforcement of terms-of-use policies by public ISPs or by administrators of private-enterprise networks. Both signature matching and a variety of feature-based pattern recognition methods have been applied to address this problem. In this paper, we propose a TCP flow classifier that employs neither packet header information that is protocol-specific (including port numbers) nor packet-payload information. Techniques based on the former are readily evadable, while detailed yet scalable inspection of packet payloads is difficult to achieve, may violate privacy laws, and is defeated by data encryption. Our classifier is tested on two contemporary publicly available datasets recorded in similar networking contexts. We consider the often encountered scenario where ground-truth labels, necessary for supervised classifier training, are unavailable for a domain where flow classification needs to be applied. In this case, one must "port over" a classifier trained on one domain to make decisions on another. We address issues in reconciling differences in class definitions between the two domains. We also demonstrate by our results that domain differences in the class-conditional feature distributions, which will exist in practice, can lead to substantial losses in classification accuracy on the new domain. Finally, we also propose and evaluate a hypothesis testing approach to detect port spoofing by exploiting confusion matrix statistics.

We have recently introduced new generative semi supervised mixtures with more fine-grained class label generation mechanisms than previous methods. Our models combine advantages of semi supervised mixtures, which achieve label extrapolation over a component, and nearest-neighbor (NN)/nearest-prototype (NP) classification, which achieves accurate classification in the vicinity of labeled samples. Our models are advantageous when within-component class proportions are not constant over the feature space region "owned by'' a component. In this paper, we develop an active learning extension of our fine-grained labeling methods. We propose two new uncertainty sampling methods in comparison with traditional entropy-based uncertainty sampling. Our experiments on a number of UC Irvine data sets show that the proposed active learning methods improve classification accuracy more than standard entropy-based active learning. The proposed methods are particularly advantageous when the labeled percentage is small. We also extend our semi supervised method to allow variable weighting on labeled and unlabeled data likelihood terms. This approach is shown to outperform previous weighting schemes.

In this note, we first give an overview of the economic and traffic conditions of residential broadband Internet access in the United states, with a focus on Comcast's multiple-priority approach to congestion control for its cable modem termination system (CMTS). We compare the Comcast framework to alternative proposals, including those based on usage based pricing and quotas. The security overhead and potential network security benefits of usage priced systems are also explored.

Abstract We propose PWC, a proactive worm containment solution for enterprises. PWC can stop—instead of just slow down—an infected host from releasing worm scans as early as after merely four scans. Motivated by the observation that a worm uses a sustained outgoing packet rate, PWC gains infection awareness seconds before a signature or filter can be generated. To overcome denial‐of‐service possibly caused by such characteristic indicators of infection, PWC/,develops two new white detection (detecting who are uninfected) techniques: (a) the vulnerability time window lemma, and (b) the relaxation analysis. PWC does not rely on contents‐based signatures thus it can defend against polymorphic worms timely in containment. PWC is also resilient to containment evading. PWC is not sensitive to worm scan rate, and not protocol specific. Due to white detection, PWC causes minimal denial‐of‐service. Evaluation based on real traces and worm simulations demonstrates that PWC significantly outperforms Virus Throttle in terms of number of released worm scans, number of hosts infected by local scans, and denial‐of‐service effects. Copyright © 2009 John Wiley & Sons, Ltd.

Feature selection for classification in high-dimensional spaces can improve generalization, reduce classifier complexity, and identify important, discriminating feature "markers." For support vector machine (SVM) classification, a widely used technique is recursive feature elimination (RFE). We demonstrate that RFE is not consistent with margin maximization, central to the SVM learning approach. We thus propose explicit margin-based feature elimination (MFE) for SVMs and demonstrate both improved margin and improved generalization, compared with RFE. Moreover, for the case of a nonlinear kernel, we show that RFE assumes that the squared weight vector 2-norm is strictly decreasing as features are eliminated. We demonstrate this is not true for the Gaussian kernel and, consequently, RFE may give poor results in this case. MFE for nonlinear kernels gives better margin and generalization. We also present an extension which achieves further margin gains, by optimizing only two degrees of freedom--the hyperplane's intercept and its squared 2-norm--with the weight vector orientation fixed. We finally introduce an extension that allows margin slackness. We compare against several alternatives, including RFE and a linear programming method that embeds feature selection within the classifier design. On high-dimensional gene microarray data sets, University of California at Irvine (UCI) repository data sets, and Alzheimer's disease brain image data, MFE methods give promising results.

Timely deletion of a large number of stale sessions monitored by Internet routers, particularly in the presence of SYN floods, is critical to prevent flow table explosion. We investigate two frameworks for purging of stale sessions: "opportunistic" purging that employs a free-list of pointers to memory and "deterministic purging" involving logical swapping of a 1-bit flow enable and touch-bit vectors without requiring a free list. We compare the performance of our algorithms with a state-of-the-art algorithm, namely finger-compressed filter (FCF). Our analysis using Internet traces shows that the deterministic purging, with no purging overhead, is ideal in that it reduces false positive and negative rates as compared to FCF by 52.5% and 59.2%, when the table size is twice the average number of active flows.

In this research, we propose a robust Sybil attack detection framework for MANETs based on cooperative monitoring of network activities. We do not require designated and honest monitors to perform the Sybil attack detection. Each mobile node in the network observes packets passing through it and periodically exchanges its observations in order to determine the presence of an attack. Malicious nodes fabricating false observations will be detected and rendered ineffective. Our framework requires no centralized authority and, thus, is scalable in expanding network size. Privacy of each mobile node is also a consideration of our framework. Our preliminary experimental results yield above 80% accuracy (true positives) and about 10% error rate (false positives).

In the context of a collaborating surveillance system for active TCP sessions handled by a networking device, we consider two problems. The first is the problem of protecting a flow table from overflow and the second is developing an efficient algorithm for estimating the number of active flows coupled with the identification of "heavy-hitter" TCP sessions. Our proposed techniques are sensitive to limited hardware and software resources allocated for this purpose in the linecards in addition to the very high data rates that modern line cards handle; specifically we are interested in cooperatively maintaining a per-flow state with a low cost, which has resiliency on dynamic traffic mix. We investigate a traditional timeout processing mechanism to manage the flow table for per-flow monitoring, called Timeout-Based Purging (TBP), our proposed Clock-like Flow Replacement (CFR) algorithms using a replacement policy, called "clock", and a hybrid approach combining these two. Experiments with Internet traces show that our CFR schemes can significantly reduce both false positive and false negative rates regardless of whether the flow table is fully occupied or sufficiently empty, even under SYN flooding. Our hybrid scheme estimates the number of active flows accurately, and confines the heavy-hitters without storing packet counters.

A worm-infected host scanning globally may not cause any new infection in its underlying local network before it is detected and quarantined by a worm detector using methods such as failed scan detection. But for a stealthier worm limiting its scan inside an enterprise network, the chance of a successful local outbreak increases substantively due to the more limited scan space. Though a number of worm scanner detection methods exist including failed scan detection, honeypot, and dark port detection, a coordinated and cost-conscious defense against a local outbreak entails an accurate estimate of worm virulence level. In this regard, we develop a maximum likelihood estimation algorithm to progressively estimate the size of susceptible host population in the network so an appropriate containment threshold can be set to effectively stop the worm propagation while causing minimum service disruption to normal network users.

Many ensemble classification systems apply supervised learning to design a function for combining classifier decisions, which requires common labeled training samples across the classifier ensemble. Without such data, fixed rules (voting, Bayes rule) are usually applied. [1] alternatively proposed a transductive constraint-based learning strategy to learn how to fuse decisions even without labeled examples. There, decisions on test samples were chosen to satisfy constraints measured by each local classifier. There are two main limitations of that work. First, feasibility of the constraints was not guaranteed. Second, heuristic learning was applied. Here we overcome both problems via a transductive extension of maximum entropy/improved iterative scaling for aggregation in distributed classification. This method is shown to achieve improved decision accuracy over the earlier transductive approach on a number of UC Irvine data sets.

Although the problem of spam detection in email is well understood and has been extensively researched, a significant portion of emails today are spam. A most widely used method to detect spam involves content filtering, where the spam detector scans the received email for keywords. However, the same approach cannot be applied to detect Voice over IP (VoIP) spam, since a call has to be categorized as a legitimate or a spam (each to a degree with a certain reliability) before the connection is established. Also, spammers over IP can potentially generate orders of magnitude more spam volume, at far less cost, and with greater anonymity than telemarketers using the Public Switch Telephone Network (PSTN). The spam problem in VoIP is further compounded by the absence of a do-not-call-list, which has been the main reason for the reduction of spam calls in PSTN. Thus, the spam issue for VoIP is as important as those pertaining to quality-of-service (QoS) of the voice traffic itself. To this end, we propose two different anti-spam frameworks for large scale VoIP systems. The first one is a centralized SIP-based spam detection framework that relies on SIP messages during the call establishment phase to identify spam calls, and the second one is a distributed referral social network model, where a user is assigned a reputation score by its neighbors. Based on the reputation, a callee can decide either to accept or decline a call. Our simulation results indicate that the referral model can provide better anti-spam capabilities by isolating a spammer faster than the SIP based approach, and can also correctly identify spam calls over 98% of time.

Despite the many routing protocols to choose from in the existing wireless network literature, routing has remained a challenging problem in the actual deployment of wireless mesh and ad hoc networks. To address some of the issues involved with routing in wireless mesh networks, in this paper we attempt to make routing more sensitive to the dynamics of the network such as interference, traffic load and congestion. We introduce a link/load-sensitive metric using linkspsila idle time and average Signal to Interference Noise Ratio (SINR), as perceived by receiving nodes into link/path selection. We use this quantity as a secondary link metric to prevent instability that might happen due to frequent SINR variations. We therefore attempt to introduce better load balancing critical to mesh networks as the nodes closer to the base stations tend to be the natural bottlenecks of the network. We perform a simulation study to assess the performance enhancement due to this technique under different load conditions. We use ETX as primary link metric and observe throughput enhancement when a secondary SINR-based metric is incorporated in the link metric.

Abstract Wireless access points (APs) act as bridges between wired and wireless networks. Since the actually available bandwidth in wireless networks is much smaller than the bandwidth in wired networks, there is a disparity in channel capacity which makes the access point a significant network congestion point in the downstream direction. A current architectural trend in wireless local area networks (WLAN) is to move functionality from APs to a centralized gateway in order to reduce cost and improve features. In this paper, we study the use of RED, a well known active queue management (AQM) scheme, and explicit congestion notification (ECN) to handle bandwidth disparity between the wired and the wireless interface of an access point. Then, we propose the Proxy‐RED scheme, as a solution for reducing the AQM overhead from the access point. Simulations‐based performance analysis indicates that the proposed Proxy‐RED scheme improves the overall performance of a network. In particular, the Proxy‐RED scheme significantly reduces packet loss rate and improves goodput for a small buffer, and minimizes delay for a large buffer size. Copyright © 2006 John Wiley & Sons, Ltd.

A Mobile Ad-Hoc Network (MANET) is considered with nodes that may act selfishly or maliciously by simply dropping data packets rather than forwarding them. We study a distributed route assessment (reputation) system for a MANET context in which nodes attribute a route’s performance to their nearest neighbors on the route. Also, attribution to all relaying nodes is studied for the case where path vectors are available, and blame for dropped packets is assigned to each node on the path. For the situation where there is sufficient mobility (“mixing”) within the domain, we show that these reputations converge to reveal the true relative dropping rates of the individual nodes. These results may be applicable to a more general category of peer-to-peer networks with sufficient route diversity.

We propose a new model for file-sharing peer-to-peer (P2P) networks that mimics the incentives provided by the popular BitTorrent system. In it, larger files are split into chunks and a peer can download or swap only one chunk at a time. We propose a Markov chain model in continuous time that resembles a stochastic epidemic/coagulation model. We prove that the Markov chain is approximated by a differential equation which, by itself, can give some rough information about the performance of the system. Finally, using this model, we explore the performance of BitTorrent-like incentives for an open system with peer departures and arrivals and a single file (torrent) with two chunks.

In this paper, we propose a distributed power control algorithm for multihop ad hoc CDMA networks. The algorithm attempts to maximize the QoS of each user as well as a global network utility, given a set of routes and link schedules. By defining the local objective of each node as a summation of its own utility and that of the "bottleneck" nodes in its vicinity, users are considered partially cooperative. Since the overall QoS of a single flow is determined by the minimum received QoS among all of its subflows, the global network utility is defined only based on these bottleneck QoS's for each user.

In this paper, we study non-cooperative user behavior in random-access wireless networks in which users have freedom to choose their back-off contention window size according to network's congestion status. We formulate a non- cooperative game and show the existence and uniqueness of its equilibrium point. We also propose an iterative method leading to the equilibrium point of the game. A discussion of alternative game formulations in the same problem context is also given.

Bit Torrent is a popular peer-to-peer file-sharing network that employs transaction-level incentives, i.e., typically two files are swapped for each transaction between peers. Also, larger files are segmented into "chunks" that are the subject of individual transactions. In this paper, we give a simple deterministic stratified epidemiological models of the dissemination of a single popular file in peer-to-peer file-sharing networks that employ BitTorrent-like incentives. We then use this simple model to evaluate the effect of these incentives by comparison with a system does not segment files and always involves only a single file transfer per transaction, i.e., involves a client-peer and server- peer.

Surveillance data generated by the nodes of a wireless ad-hoc (multihop) sensor network is aggregated at local sinks and forwarded to a central node. The number of sensor nodes that the sinks can support determines a "capacity" of the network. The number of surveillance data flows (each emanating from a sensor node) that a node can relay is limited by a variety of factors such as channel conditions (including interference, attenuation, fading and ambient noise) and internal hardware and energy resources of the node. Assuming that the one-hop neighbors of a sink form the most significant communication relaying bottleneck, we analytically determine the fraction of sensor nodes that are unable to connect to their sink, i.e., the outage probability. This expression is numerically evaluated and its accuracy is assessed and reported in a preliminary simulation study.

In multihop ad hoc CDMA networks, uplink-downlink schedules are needed to forward packet flows throughout the network without conflict. Also, a routing algorithm and a power control mechanism are required to route the flows while satisfying the QoS needs of the users. To maximize bandwidth utilization efficiency, scheduling tables of minimum length are desired. We suggest an incremental contention-based algorithm as a heuristic distributed solution to the NP-hard uplink-downlink scheduling problem. Also, we propose a routing strategy that considers these schedules, i.e., integrated routing and scheduling.

The increasing availability of network testbeds and the benefits of visualization-based security study call for the emergence of supporting tools for network security research. In this article we present ESVT, an integrated experiment specification and visualization toolkit that supports network experimenters to conduct interactive experiments on network testbeds such as DETER and Emulab. The ESVT package includes a topology builder including experiment specification, a TCL script generator, and various visualization tools. The unique feature of ESVT visualization is the combination of topology-based network animation for global awareness and detailed data analysis support through a complete set of data conversion, data selection, and graphical analytical tools.

This paper considers the problem of finding a tamper-resistant and charge-sensitive end-to-end window flow-control mechanism for greedy users. Using a mathematical model of resource distribution, we propose a distributed window flow-control mechanism leading to a flow-rate vector which achieves maximum total utility. Desirable features of the proposed window control algorithm and properties of the equilibrium points are explored. We also prove the convergence of the proposed window control algorithm.

Mining traffic to identify the dominant flows sent over a given link, over a specified time interval, is a valuable capability with applications to traffic auditing, simulation, visualization, as well as anomaly detection. Recently, Estan advanced a comprehensive data mining structure tailored for networking data-a parsimonious, multidimensional flow hierarchy, along with an algorithm for its construction. While they primarily targeted offline auditing, use in interactive traffic visualization and anomaly/attack detection will require real-time data mining. We suggest several improvements to Estan's algorithm that substantially reduce the computational complexity of multidimensional flow mining. We also propose computational and memory-efficient approaches for unidimensional clustering of the IP address spaces. For baseline implementations, evaluated on the New Zealand (NZIX) trace data, our method reduced CPU execution times of the Estan method by a factor of more than eight. We also develop a methodology for anomaly/attack detection based on flow mining, demonstrating the usefulness of this approach on traces from the Slammer and Code Red worms and the MIT Lincoln Laboratories DDoS data

We describe a hierarchical traffic shaper-scheduler, hierarchical SDRR (HSDRR), for flows of variable-length packets that is low-complexity (scales with the number of queues). That is, HSDRR can be used channelize the output link of a router to satisfy service-level agreements (token bucket constraints) struck at network-to-network boundaries. HSDRR is a hybrid round-robin/time-stamp scheduler (S. Ramabhadran and J. Pasquale, 2003) that employs shaped deficit round-robin (SDRR) (S. Jiwasurat and G. Kesidis, 2004) scheduling in the first stage and shaped virtual clock (SVC) (D. Stiliadis and A. Varma, 1997) in the second and final stage.

In this paper, we study end-user dynamics of communication networks employing usage-based pricing. We propose a generic network access mechanism in which users modify their access control parameter based on the quality of service they receive in order to maximize their net benefit. For the examples of users sharing access to a bandwidth resource via a single trunk with Erlang loss dynamics and for a differentiated services (diffserv) network, we study the equilibrium/fixed points and give analytical results on convergence assuming the network prices are fixed.

Wireless ad-hoc sensor networks are being developed to carry out tasks such as target detection and tracking, environment monitoring, and data collection across the area of deployment. We explore the problem of using sensor networks to detect and track continuous objects, such as wild fire and bio-chemical material. The continuous objects are different from traditional one or many individual targets in that they are continuously distributed across a region and usually occupy a large area. These continuous objects tend to diffuse, increase in size, change in shape, or even split into multiple relatively smaller continuous objects. The fusion and dissemination of local boundary information becomes a very challenging problem. In the paper, we propose a dynamic cluster-based structure to track the movement of boundaries and facilitate the fusion and dissemination of boundary information in a sensor network.

We consider a mobile ad hoc sensor network. The mobility of the sensor nodes is designed with the cost of communication and mobility in mind along with consideration of the possible scanning tasks of the nodes. Our mobility algorithm is developed in the context of a distributed system where, for any single mobile node, only local information about associated energy costs is known. We use a distributed simulated annealing framework to govern the motion of the nodes and prove that, in a limiting sense, a global objective function comprising mobility and communication energy costs are minimized. This paper concludes with a simulation study focusing on mobile sensors with dual roles of scanning and relaying higher priority tracking traffic from tracking nodes.

In this paper, we use a control theoretic approach to develop a generic framework for analyzing various active queue management (AQM) schemes as proportional-integral-derivative (PID) controllers. Based on this PID model, we propose an adaptive control mechanism to improve the system stability and performance under changing network conditions. We then present a generic implementation of the PID controller by introducing a derivative control into a PI controller. In addition, we propose an improved adaptive virtual queue (AVQ) scheme with explicit queue length control. A simulation study under a wide range of traffic conditions suggests that the proposed algorithms outperform the existing AQM schemes in achieving better system performance and stability.

Ad hoc networks are gaining presence with the proliferation of cheap wireless devices and the need to keep them connected. Individual applications and larger missions, such as those of tactical sensor networks, require secure data transmission among wireless devices. Security remains a major challenge for such networks. Current protocols employ encryption and authentication techniques for secure message exchange, but given the limitations and innately insecure nature of ad-hoc networks, such mechanisms may not suffice. A security breach can, for example, be a network-level denial-of-service (DoS) attack, passive eavesdropping, or physical layer jamming to degrade communication channels. In a multihop network, an intruder node can degrade communication quality by simply dropping packets that are meant to be relayed (forwarded). The network could then misinterpret the cause of packet loss as congestion instead of malicious activity. In this paper, we suggest that traffic transmission patterns be selected to facilitate verification by a receiver. Such traffic patterns are used in concert with suboptimal MAC that preserves the statistical regularity from hop to hop. This general technique for intrusion detection is therefore suitable for networks that are not bandwidth limited but have strict security requirements, e.g., certain kinds of tactical sensor networks.

A generic mechanism for end-user transmission rate control into a differentiated services Internet is formulated and basic results of corresponding Nash equilibria are proved. We consider specific examples of the mechanism including additive increase and multiplicative decrease inspired by present day TCP congestion control. For the example of users sharing access to a bandwidth resource via resizable provisioned label-switched paths (MPLS), we study the equilibria and the performance of the generic mechanism and give analytical results on convergence to equilibria. The fairness of the resulting equilibria when user demands exceed available network resources is also studied.

We present a virtual queue-based active queue management (AQM) scheme, called stabilized virtual buffer (SVB). The SVB scheme uses the packet arrival rate and queue length information to drop/mark packets probabilistically in a congested Internet router. System goodput, packet loss rate, average queue length, and stability of the queue are used to compare the proposed SVB scheme with prior AQM schemes (RED - random early detection; REM - random exponential marking; AVQ - adaptive virtual queue). Simulation results indicate that the SVB algorithm can provide better goodput and lower loss rate than the other three AQMs. The most striking feature of the proposed scheme is its robustness to workload fluctuations in maintaining a stable queue for different workload mixes (short and long flows) and parameter settings.

The Differentiated Service (DiffServ) architecture does not specify any priority scheme between assured forwarding (AF) out-profile packets and best-effort (BE) packets. Therefore, a misbehaving AF flow can penalize many BE flows unless a fair bandwidth sharing mechanism is employed in the routers. In this paper, we propose two different techniques for solving the inter- and intra-class fairness problems at the core and edge routers, respectively. For the core routers, we propose a fair weighted round robin (FWRR) scheduler that protects BE packets from monopolizing AF out-profile packets by dynamically adjusting the service weights and buffer spaces according to the traffic changes. For the edge routers, we propose a scheme, called fair dropper (FD), that provides intra-class fairness by penalizing the greedy flows. Simulation results indicate that both these techniques are quite effective in providing inter- and intra-class fairness, while maintaining a low packet loss rate.

Bluetooth is a new short-range radio technology to form a small wireless system. In most of the current Bluetooth products, the master polls the slaves in a round robin manner and it may waste a significant amount of power. We propose an adaptive power conserving scheme to address this problem. The proposed solution schedules each flow based on its predictive rate and achieves power optimization based on a low-power mode existing in Bluetooth standard. Unlike other research work related to low-power, we also consider QoS of each flow. Theoretical analyses verify that our scheme can achieve throughput guarantees, delay guarantees, and fairness guarantees. Simulation results demonstrate that our scheme can save a significant amount of power compared to the round robin scheme and it shows that there exists a tradeoff between power and delay under various traffic models.

We consider a variable bit-rate connection with a deterministically shaped random traffic process, as specified by communications networking standards. Regarding randomness, we assume no restricted model other than the natural requirement that the process be stationary and ergodic. Given only the shape parameters, we consider the open problem of determining the maximum service bandwidth required to achieve a given bound on the probability that the packet-transfer delay exceeds a certain threshold. The shape parameters together with a probabilistic bound on the packet-transfer delay define a variable bit-rate "channel"; an equivalent problem is to determine the "capacity" of this channel. To this end, we consider a queue with a constant service rate and a shaped arrival process and obtain tight bounds on queue occupancy and queueing delay. In particular, we describe that traffic pattern (among all stationary-ergodic and deterministically constrained arrival processes) which achieves the probabilistic bound.

There is considerable interest in the provision of guaranteed-rate services for IP and ATM networks. Simultaneously, bandwidth demands make input-buffered architectures attractive, and in some cases, necessary. We consider the problem of how to support guaranteed-rate services in a single-stage, input-buffered switch suitable for a LAN switch, an ATM switch or an IP router. Such a switch must be feasible at high transmission speeds, offering both guaranteed-rate performance for CBR channels (e.g. for real-time connections) and best-effort services for traditional data traffic. We consider a switch scheduling mechanism that employs idling hierarchical round-robin (HRR) scheduling and fabric arbitration at the connection-level for guaranteed-rate service using the Slepian-Duguid algorithm. The switch uses cell level arbitration for best-effort service. This overall switch scheduling mechanism is a variation of DEC's AN2 design.

In this paper, we give an overview of the basic design principles and trade-offs of output-buffer ATM switching. Output-buffer switches give optimal performance in terms of offering bandwidth guarantees to individual flows. Bandwidth scheduling and memory bandwidth requirements are also described.

We consider the asymptotic behavior of the queue length distribution in segregated buffers sharing a deterministic server via a class of generalized processor sharing (GPS) policies. Such policies have been proposed as a means to guarantee individual quality of service constraints to heterogeneous streams in integrated services digital networks. These results exhibit the manner in which spare capacity is shared by statistically multiplexed traffic streams. The framework corresponds to a natural relaxation of a single GPS node subject to (/spl sigma/, /spl rho/)-constrained flows where, instead of studying the worst case behavior, we consider statistical bounds on the performance of individual traffic streams.

The paper is concerned with the design of a class of bandwidth scheduling policies that are suitable for public, wide-area asynchronous transfer mode (ATM) networks. The authors specify design goals for such strategies including ease of implementation and the ability to guarantee minimum bandwidths to individual buffers. Packetized generalized processor sharing is briefly discussed and a minimum bandwidth result for self-clocked fair queueing is given. The authors revisit an approach originally proposed by Zhang (1991) and prove that it is appropriate for ATM. Some novel, related approaches are described and analyzed.

This paper is principally concerned with resource allocation for connections tolerating statistical quality of service (QoS) guarantees in a public wide-area ATM network. Our aim is to sketch a framework, based on effective bandwidths, for call admission schemes that are sensitive to individual QoS requirements and account for statistical multiplexing. Results approximating the effective bandwidth required by heterogeneous streams sharing buffered links, including results for the packetized generalized processor sharing service discipline, are described. Extensions to networks follow via the concept of decoupling bandwidths, motivated by a study of the input-output properties of queues. Based on these results we claim that networks with sufficient routing diversity will inherently satisfy nodal decoupling. We then discuss on-line methods for estimating the effective bandwidth of connection. Using this type of traffic monitoring we propose an approach to usage parameter control (i.e., policing) for effective bandwidth descriptors. Finally, we suggest how on-line monitoring might be combined with admission control to exploit unknown statistical multiplexing gains and thus increase utilization.>

Addresses the issue of call acceptance and routing in ATM networks. The goal is to design an algorithm that guarantees bounds on the fraction of cells lost by a call. The method proposed for call acceptance and routing does not require models describing the traffic. Each switch estimates the additional fraction of cells that would be lost if new calls were routed through the switch. The routing algorithm uses these estimates. The estimates are obtained by monitoring the switch operations and extrapolating to the situation where more calls are routed through the switch. The extrapolation is justified by a scaling property. To reduce the variance of the estimates, the switches calculate the cell loss that would occur with virtual buffers. A way to choose the sizes of the virtual buffers in order to minimize the variance is discussed. Thus, the switches constantly estimate their spare capacity. Simulations were performed using Markov fluid sources to test the validity of the approach.>

We describe E. Wong's stochastic neural network (1989) and show that it can be used, in principle, to perform analog optimization. The optimization dynamics are analogous to those of simulated annealing. To show this, we use the theory developed in Holley and Stroock (1988) for the continuous-time simulated annealing process.

The relative entropy between two Markov transition rate matrices is derived from sample path considerations. This relative entropy is interpreted as a level-2.5 large-deviations action functional. That is, the level-two large-deviations action functional for empirical distributions of continuous-time Markov chains can be derived from the relative entropy using the contraction mapping principle.>

The authors show the existence of effective bandwidths for multiclass Markov fluids and other types of sources that are used to model ATM traffic. More precisely, it is shown that when such sources share a buffer with deterministic service rate, a constraint on the tail of the buffer occupancy distribution is a linear constraint on the number of sources. That is, for a small loss probability one can assume that each source transmits at a fixed rate called its effective bandwidth. When traffic parameters are known, effective bandwidths can be calculated and may be used to obtain a circuit-switched style call acceptance and routing algorithm for ATM networks. The important feature of the effective bandwidth of a source is that it is a characteristic of that source and the acceptable loss probability only. Thus, the effective bandwidth of a source does not depend on the number of sources sharing the buffer or the model parameters of other types of sources sharing the buffer.>