The recent surge in popularity of cloud-native applications using microservice architectures has led to a focus on accurate end-to-end latency prediction for proactive resource allocation. Existing models leverage Graph Transformers to Microservice Call Graphs or the Program Evaluation and Review Technique (PERT) graphs to capture complex temporal dependencies between microservices. However, these models incur a high computational cost during both training and inference phases. This paper introduces FastPERT, an efficient model for predicting end-to-end latency in microservice applications. FastPERT dissects an execution trace into several microservices tasks, using observations from prior execution traces of the application, akin to the PERT approach. Subsequently, a prediction model is constructed to estimate the completion time for each individual task. This information, coupled with the computational and structural inductive bias of the PERT graph, facilitates the efficient computation of the end-to-end latency of an execution trace. As a result, FastPERT can efficiently capture the complex temporal causality of different microservice tasks without relying on Graph Neural Networks, leading to more accurate and robust latency predictions across a variety of applications. An evaluation based on datasets generated from large-scale Alibaba microservice traces reveals that FastPERT significantly improves training and inference efficiency without compromising performance, demonstrating its potential as a superior solution for real-time end-to-end latency prediction in cloud-native microservice applications.

Graph Neural Networks (GNNs) are widely used as the engine for various graph-related tasks, with their effectiveness in analyzing graph-structured data. However, training robust GNNs often demands abundant labeled data, which is a critical bottleneck in real-world applications. This limitation severely impedes progress in Graph Anomaly Detection (GAD), where anomalies are inherently rare, costly to label, and may actively camouflage to evade detection. To address these problems, we propose Context Refactoring Contrast (CRoC), a simple yet effective framework that trains GNNs for GAD by jointly leveraging limited labeled and abundant unlabeled data. Unlike previous works, CRoC exploits the class imbalance inherent in GAD to refactor the context of each node, which builds augmented graphs by recomposing the attributes of nodes while preserving their interaction patterns. Furthermore, CRoC encodes heterogeneous relations separately and integrates them into the message-passing process, inducing the model to capture complex interaction semantics. These operations preserve node semantics while encouraging robustness against adverse camouflage, enabling GNNs to uncover intricate anomalous cases. In the training stage, CRoC is further integrated with the contrastive learning paradigm. This allows GNNs to effectively harness unlabeled data during joint training, producing richer, more discriminative node embeddings. CRoC is evaluated on seven real-world GAD datasets with different sizes. Extensive experiments demonstrate that CRoC achieves up to 14% AUC improvement over baseline GNNs and outperforms state-of-the-art GAD methods under limited-label settings.

The GPU device heterogeneity in accelerating deep learning training workloads poses significant challenges for job scheduling in datacenters.Existing heterogeneity-aware job schedulers, however, cannot effectively reduce the overall job completion time (JCT) or provide fairness guarantees due to their coarse-grained resource allocation and poor integration of conflicting objectives.This paper presents FFT, a novel scheduling system designed for Fast and Fair deep learning Training in heterogeneous GPU clusters.FFT incorporates two key designs.First, it incorporates a resource allocation scheme in each round to enable fine-grained control over resource utilization.Second, it seamlessly integrates a fairness compensation mechanism that dynamically evaluates fairness in real-time.Building upon these designs, FFT formulates a cost minimization problem to determine the optimal schedule, striking a delicate balance between efficiency and fairness.Extensive experiments conducted in physical clusters as well as large-scale testbed demonstrate that FFT can significantly accelerate the overall JCT by up to 5.2× while improving job finishtime-fairness by more than 2.2× compared to state-of-the-art heterogeneity-aware solutions.

The problem of multi-armed bandit (MAB) with fairness constraints has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed number of pull rounds, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing various online selection solutions for MAB, however, when incorporating such fairness constraints, they fail to achieve a sublinear regret bound. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we design a new selection algorithm that solves MAB problems from an online convex optimization perspective. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound of O( √ T ln T) with high probability guarantees in T selection rounds. We also extend our framework to include more general knapsack constraints. Finally, we assess the performance of our algorithm through extensive simulations and real dataset applications, demonstrating its significant advantages over baseline schemes.

Web attacks, a primary vector for system breaches, pose a significant challenge within the cybersecurity landscape. The growing intensity of web attack attempts has led to "alert fatigue" where enterprises are inundated by excessive alerts. Although extensive research is being conducted on automated methods for detecting web attacks, it remains an open problem to identify whether the attacks are successful. Towards this end, we present SWIDE (Successful Web Injection Detection Engine), an engine to pinpoint successful web injection attacks (e.g., PHP command injection, SQL injection). This enables enterprises to focus exclusively on those crucial threats. Our methodology builds on two insights: Firstly, while attackers tend to apply payload obfuscation techniques to evade detection, all successful web injection attacks must comply with the programming language syntax to be executable; Secondly, these attacks inevitably produce observable effects, such as returning execution result or creating backdoors for future access by the attacker. Consequently, we leverage advanced syntactic and semantic analysis to 1) detect malicious syntax features in obfuscated payloads and 2) perform semantic analysis of the payload to recover the intention of the attack. With a two-stage design, namely, attack identification and confirmation mechanisms, SWIDE can accurately identify successful attacks, even amidst intricate obfuscations. Unlike proof-of-concept studies, SWIDE has been deployed and validated in real-world environments through collaborations with a cybersecurity firm. Serving 5,045 enterprise users, our system identifies that roughly 15% of enterprises have suffered from successful attacks on a weekly basis - an alarmingly high rate. Moreover, we perform a detailed analysis of six months' data and discover 60 zero-day vulnerabilities exploited in the wild, including 12 high-risk ones acknowledged by relevant authorities. These findings underscore the practical effectiveness of SWIDE.

Ensuring the highest training throughput to maximize resource efficiency, while maintaining fairness among users, is critical for deep learning (DL) training in heterogeneous GPU clusters. However, current DL schedulers provide only limited fairness properties and suboptimal training throughput, impeding tenants from effectively leveraging heterogeneous resources. The underlying design challenge stems from inherent conflicts between efficiency and fairness properties.

Graph Neural Networks (GNNs) is a family of promising tools for graph semi-supervised learning. However, in training, most existing GNNs rely heavily on a large amount of labeled data, which is rare in real-world scenarios. Unlabeled data with useful information are usually under-exploited, which limits the representation power of GNNs. To handle these problems, we propose Virtual Overbridge Linking (Violin), a generic framework to enhance the learning capacity of common GNNs. By learning to add virtual overbridges between two nodes that are estimated to be semantic-consistent, labeled and unlabeled data can be correlated. Supervised information can be well utilized in training while simultaneously inducing the model to learn from unlabeled data. Discriminative relation patterns extracted from unlabeled nodes can also be shared with other nodes even if they are remote from each other. Motivated by recent advances in data augmentations, we additionally integrate Violin with the consistency regularized training. Such a scheme yields node representations with better robustness, which significantly enhances a GNN. Violin can be readily extended to a wide range of GNNs without introducing additional learnable parameters. Extensive experiments on six datasets demonstrate that our method is effective and robust under low-label rate scenarios, where Violin can boost some GNNs' performance by over 10% on node classifications.

Cloud-native applications using microservice architectures are rapidly replacing traditional monolithic applications. To meet end-to-end QoS guarantees and enhance user experience, each component microservice must be provisioned with sufficient resources to handle incoming API calls. Accurately predicting the latency of microservices-based applications is critical for optimizing resource allocation, which turns out to be extremely challenging due to the complex dependencies between microservices and the inherent stochasticity. To tackle this problem, various predictors have been designed based on the Microservice Call Graph. However, Microservice Call Graphs do not take into account the API-specific information, cannot capture important temporal dependencies, and cannot scale to large-scale applications.

Recognizing the diversity of Big Data analytic jobs, cloud providers offer a wide range of VM instance types or even clusters to cater for different use cases. The choice of cloud configurations can have a significant impact on the response time and running cost of batch-processing applications, which may need to be re-run regularly with cloud-scale resources. However, identifying the best cloud configuration with a low search cost is quite challenging due to i) the large and high-dimensional configuration space, ii) the time-varying cloud service cost (e.g., AWS Spot instances), and iii) job response time variation even given the same configuration. To tackle these challenges, we design and implementAccordia, a system that enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications. By leveraging recent algorithmic advances in Gaussian Process UCB techniques,Accordiacan unearth the cost-optimal configuration with a deadline constraint (i.e., maximum tolerated running time) under the time-varying cloud service cost. More importantly,Accordiamanages to achieve a theoretical performance guarantee,sub-linearly increasing dynamic regretof the job completion cost. Using extensive trace-driven simulations and empirical measurements of our Kubernetes-based implementation, we demonstrate thatAccordiacan identify a near-cost-optimal configuration (i.e., within 10% of the optimum) after fewer than 20 runs from over 7000 candidate choices, which translates to a 2X-speedup and up to 17.9% cost-savings, when comparing to the state-of-the-art approach,CherryPick.

Graph Neural Networks (GNNs) have recently become a popular framework for semi-supervised learning on graph-structured data. However, typical GNN models heavily rely on labeled data in the learning process, while ignoring or paying little attention to the data that are unlabeled but available. To make full use of available data, we propose a generic framework, Contrastive Context Sharing (CoCoS), to enhance the learning capacity of GNNs for semi-supervised tasks. By sharing the contextual information among nodes estimated to be in the same class, different nodes can be correlated even if they are unlabeled and remote from each other in the graph. Models can therefore learn different combinations of contextual patterns, which improves the robustness of node representations. Additionally, motivated by recent advances in self-supervised learning, we augment the context sharing strategy by integrating with contrastive learning, which naturally correlates intra-class and inter-class data. Such operations utilize all available data for training and effectively improve a model's learning capacity. CoCoS can be easily extended to a wide range of GNN-based models with little computational overheads. Extensive experiments show that CoCoS considerably enhances typical GNN models, especially when labeled data are sparse in a graph, and achieves state-of-the-art or competitive results in real-world public datasets. The code of CoCoS is available online.

Graph Neural Networks (GNNs) are the current state-of-the-art models in learning node representations for many predictive tasks on graphs. Typically, GNNs reuses the same set of model parameters across all nodes in the graph to improve the training efficiency and exploit the translationally-invariant properties in many datasets. However, the parameter sharing scheme prevents GNNs from distinguishing two nodes having the same local structure and that the translation invariance property may not exhibit in real-world graphs. In this paper, we present Graph Adaptive Mixtures (GraphAdaMix), a novel approach for learning node representations in a graph by introducing multiple independent GNN models and a trainable mixture distribution for each node. GraphAdaMix can adapt to tasks with different settings. Specifically, for semi-supervised tasks, we optimize GraphAdaMix using the Expectation-Maximization (EM) algorithm, while in unsupervised settings, GraphAdaMix is trained following the paradigm of contrastive learning. We evaluate GraphAdaMix on ten benchmark datasets with extensive experiments. GraphAdaMix is demonstrated to consistently boost state-of-the-art GNN variants in semi-supervised and unsupervised node classification tasks. The code of GraphAdaMix is available online.

Recognizing the explosion of large-scale real-time analytics needs, a plethora of stream processing systems, such as Apache Storm and Flink, have been developed to support such applications. Under these systems, a stream processing application is realized as a directed acyclic graph (DAG) of operators, where the resource configuration of each operator has a significant impact on its overall throughput and latency performance. However, there is a lack of dynamic resource allocation schemes, which are theoretically sound and practically implementable, especially under the drastically changing offered load. To address this challenge, we present Dragster1, an online-optimization-based dynamic resource allocation scheme for elastic stream processing. By combining the online optimization framework with upper confidence bound (UCB) techniques, Dragster can guarantee, in expectation, a sub-linear increase in the throughput regret w.r.t. time. To demonstrate the efficacy, we implement Dragster to improve the throughput of Flink applications over Kubernetes. Compared to the state-of-the-art algorithm Dhalion, Dragster can achieve a 1.8X-2.2X speed-up in converging to the optimal configuration. It can contribute to 20.0%-25.8% gain in tuple-processing goodput and 14.6%-15.6% cost-savings.

To mitigate the straggler effect, today’s systems and computing frameworks have adopted redundancy to launch extra copies for stragglers. Two limitations of the existing straggler-mitigation techniques, however, are that resource demand of tasks is only considered in the context of slots and, moreover, redundancy is seldom coordinated with job scheduling. To tackle these issues, in this paper, we present DollyMP, a job scheduler that addresses multi-resource scheduling with task cloning in heterogeneous clusters. DollyMP carefully combines SRPT (Shortest Remaining Processing Time) and SVF (Smallest Volume First) via knapsack optimization to schedule tasks with multi-resource demands and, in the meanwhile, dynamically launches task clones to yield a small job completion time. DollyMP is built on a strong mathematical foundation to guarantee near-optimal performance. The deployment of our Hadoop YARN prototype on a 30-node cluster demonstrates that DollyMP can reduce job response time by 50% under different cluster loads.

Jobs in modern computing clusters have highly diverse processing duration and heterogeneous resource requirements. In this paper, we consider the problem of job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the different resource demands of the jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the recently-proposed notion of fractional job flowtime as a surrogate objective for minimization. For the general online job arrival case with multi-dimensional resource requirements, we apply Online Convex Optimization (OCO) techniques to design the corresponding scheduling algorithm with performance guarantees. In the single-dimensional resource setting, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function with the corresponding switching costs.

Recognizing the diversity of big data analytic jobs, cloud providers offer a wide range of virtual machine (VM) instances or even clusters to cater for different use cases. The choice of cloud configurations can have a significant impact on the response time and running cost of data-intensive, production batch-jobs, which need to be re-run regularly using cloud-scale resources. However, identifying the best cloud configuration with a low search cost is quite challenging due to i) the large and high-dimensional configuration-parameters space, ii) the time-varying price of some instance types (e.g. spot-price ones), iii) job execution-time variation even given the same configuration, and iv) gradual drifts / unexpected changes of the characteristics of a recurring job. To tackle these challenges, we have designed and implemented Accordia, a system that enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications. By leveraging recent algorithmic advances in Gaussian Process UCB (Upper Confidence Bound) techniques, the design of Accordia can handle time-varying instance pricing while providing a performance guarantee of sub-linearly increasing regret when comparing with the static, offline optimal solution. Using extensive trace-driven simulations and empirical measurements of our Kubernetes-based implementation, we demonstrate that Accordia can dynamically learn a near-cost-optimal cloud configuration (i.e. within 10% of the optimum) after fewer than 20 runs from over 7000 candidate choices within a 5-dimension search space, which translates to a 2X-speedup and 17.9% cost-savings, when comparing to CherryPick.

The problem of multi-armed bandit (MAB) with fairness constraint has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed round of pulls, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing efficient online selection solutions, however, they fail to achieve a sublinear regret bound when incorporating such fairness constraints. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we adopt a new approach that combines online convex optimization with bandit methods to design selection algorithms. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound with probability guarantees. Finally, we evaluate the performance of our algorithm via extensive simulations and demonstrate that it outperforms the baselines substantially.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today's large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job's lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

Mobile applications today increasingly integrate Single Sign-On (SSO) into their account management mechanisms. Unfortunately, the involved multi-party protocol, i.e., OAuth 2.0, was originally designed to serve websites for authorization purpose. Due to the complexity of the adapted protocol, a large number of insecure SSO implementations still exist in the wild. Although the security testing for real-world SSO deployments has attracted considerable attention in recent years, existing work either focuses on websites or relies on the manual discovery of specific and previously-known vulnerabilities. In the paper, we design and implement MoSSOT (Mobile SSO Tester), an automated blackbox security testing tool for Android applications utilizing the SSO services from three mainstream service providers. The tool detects the vulnerabilities within the practical SSO implementations by fuzzing related network messages. We used MoSSOT to examine over 500 first-tier third-party Android applications from US and Chinese app markets. According to the test result, around 72% of the tested applications incorrectly implement SSO and are thus vulnerable. Besides, our test identifies an unknown vulnerability as well as a new variant, in addition to four known ones. The vulnerabilities enable the attacker to illegally log into the mobile applications as the victims or gain access to the protected resources. MoSSOT has been released as an open-source project.

Recognizing the diversity of big data analytic jobs, cloud providers offer a wide range of virtual machine (VM) instances for different use cases. The choice of cloud instance configurations can have significant impact on the response time and running cost of data-intensive, recurring jobs for production. A poor choice of cloud instance-type/configuration can substantially degrade the response time by 5x, or increase the cost by 10x. Identifying the best cloud configuration under low search budget is a challenging problem due to i) the large and high-dimensional configuration-parameters space, ii) the dynamically varying price of some instance types, iii) job response time variation even given the same configuration, and iv) gradual drifts/ unexpected changes of the characteristics of the recurring jobs. To tackle this problem, we have designed and implemented Accordia, a system which enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications.

Jobs in modern computing clusters have highly diverse processing durations and heterogeneous resource requirements. In this paper, we consider the problem of online job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the diversity of resource demands for different jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the notion of fractional job flowtime as a surrogate objective for minimization. We apply Online Convex optimization (OCO) techniques to design the corresponding online scheduling algorithm. More importantly, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function of our online convex optimization formulation with the corresponding switching costs.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics [1], [2]. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performed machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is$(1+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive. We also show that our proposed Fair+R and LAPS+R($\beta$) Algorithms for a multitasking cluster are$(4+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive and ($2 + 2\beta + 2\epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes.

The use of color in QR codes brings extra data capacity, but also inflicts tremendous challenges on the decoding process due to chromatic distortion-cross-channel color interference and illumination variation. Particularly, we further discover a new type of chromatic distortion in high-density color QR codes-cross-module color interference-caused by the high density which also makes the geometric distortion correction more challenging. To address these problems, we propose two approaches, LSVM-CMI and QDA-CMI, which jointly model these different types of chromatic distortion. Extended from SVM and QDA, respectively, both LSVM-CMI and QDA-CMI optimize over a particular objective function and learn a color classifier. Furthermore, a robust geometric transformation method and several pipeline refinements are proposed to boost the decoding performance for mobile applications. We put forth and implement a framework for high-capacity color QR codes equipped with our methods, called HiQ. To evaluate the performance of HiQ, we collect a challenging large-scale color QR code dataset, CUHK-CQRC, which consists of 5390 high-density color QR code samples. The comparison with the baseline method [2] on CUHK-CQRC shows that HiQ at least outperforms [2] by 188% in decoding success rate and 60% in bit error rate. Our implementation of HiQ in iOS and Android also demonstrates the effectiveness of our framework in real-world applications.

Over the past few years, many major wireless providers restricted their unlimited data plans and replaced them with limited-size fixed-price data packages. While this could be perceived as a disadvantage for customers, it helps the cellular wireless providers to reduce the traffic intensity at their base stations and this leads to a better service quality and higher rates for concurrently connected users. Hence, there is a tradeoff between the data volume and the data rates attributed to the users. To avoid the adverse effect of service inaccessibility, the cellular providers should carefully set the size and pricing of their data packages. Toward this end, the providers need a model that, together with proper market information, would allow to set the best prices for volume-based data and estimate the acceptable quantity of subscribers and their average data rate. In this paper, we propose such a model that quantifies the relationship between pricing and various market/system parameters such as data volume size, user budget, data rate, and service blocking probability. In particular, we formulate a set of revenue optimization problems for different spectrum assignment criteria like shared-carrier and dynamic sub-carrier allocation. Finally, several realistic scenarios are investigated in which the optimal network parameters are computed.

The completion times of jobs in a computing cluster may be influenced by a variety of factors including job size and machine processing variability. In this paper, we explore online resource allocation policies which combine size-dependent scheduling with redundant execution and opportunistic checkpointing to minimize the overall job flowtime. We introduce a simplified model for the job service capacity of a computing cluster while leveraging redundant execution/checkpointing. In this setting, we propose two resource allocation algorithms, SRPT+R and LAPS+R(β) subject to checkpointing overhead not exceeding the number of jobs which are processed. We provide new theoretical performance bounds for these algorithms: SRPT+R is shown to be O(1/∊) competitive under (1 + ∊)-speed resource augmentation, while LAPS+R(β) is shown to be O(1/β∊) competitive under (2+ 2β + 2∊)-speed resource augmentation.

We investigate a cooperation scenario in which a cellular service provider (CSP) agrees to offer free Internet access to a certain number of applications offered by a governmental entity, referred to as a non-profit service provider (NSP). NSP also provides a WiFi Internet network via which its applications can be accessed free of charge but the network budget for the network expansion and making the access available to all potential users is limited. To overcome this issue, NSP aims to provide a part of its applications also available through a commercial cellular network. Thus, the main problem of NSP is finding the optimal portion of its budget that should be transferred to CSP as a side-payment for its service. To address this problem we propose a game that is modeling a multi-period contract between CSP and NSP. Since the coverage of NSP's free network affects the price of the CSP service, we solve a three stage Stackelberg game in which each network entity finds its best response. The outcome of our game is the optimally assigned NSP budget for the free cellular data access, the size of free cellular data volume, and the optimal service price of CSP in each period. We provide numerical examples in which we show the effect of the NSP budget and the number of subscribers on the optimal values.

A big parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable or congested machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow when extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for parallel processing clusters from an optimization perspective under different loading conditions. For the lightly loaded case, we analyze and propose one cloning scheme, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the overall system utility. We also derive the workload threshold under which SCA should be used for speculative execution. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme to mitigate stragglers. Our simulation results show SCA reduces the total job flowtime, i.e., the job delay/ response time by nearly$6$percent comparing to the speculative execution strategy of Microsoft Mantri. In addition, we show that the ESE Algorithm outperforms the Mantri baseline scheme by$71$percent in terms of the job flowtime while consuming the same amount of computation resource.

Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an$O(1)$-competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based$\beta$-fraction Sharing plus Cloning algorithm (SREW+C($\beta$)) for the online case. We also show that SREW+C($\beta$) is$(1+ 2\beta + \epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C($\beta$) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass.

Motivated by the prevalence of OAuth-related vulnerabilities in the wild, large-scale security testing of real-world OAuth 2.0 implementations have received increasing attention lately [31,37,42]. However, these existing works either rely on manual discovery of new vulnerabilities in OAuth 2.0 implementations or perform automated testing for specific, previously-known vulnerabilities across a large number of OAuth implementations. In this work, we propose an adaptive model-based testing framework to perform automated, large-scale security assessments for OAuth 2.0 implementations in practice. Key advantages of our approach include (1) its ability to identify existing vulnerabilities and discover new ones in an automated manner; (2) improved testing coverage as all possible execution paths within the scope of the model will be checked and (3) its ability to cater for the implementation differences of practical OAuth systems/ applications, which enables the analyst to offload the manual efforts for large-scale testing of OAuth implementations. We have designed and implemented OAuthTester to realize our proposed framework. Using OAuthTester, we examine the implementations of 4 major Identity Providers as well as 500 top-ranked US and Chinese websites which use the OAuth-based Single-Sign-On service provided by the formers. Our empirical findings demonstrate the efficacy of adaptive model-based testing on OAuth 2.0 deployments at scale. More importantly, OAuthTester not only manages to rediscover various existing vulnerabilities but also identify several previously unknown security flaws and new exploits for a large number of eal-world applications implementing OAuth 2.0.

The seminal works by Karger [13], [14] have shown that one can use Uniform Random Edge (URE) sampling to generate a graph skeleton which accurately approximates all cut-values in the original graph with high probability under some specific assumptions. As such, the random subgraphs resulted from URE sampling can often be used as substitutes for the original graphs in cut/flow-related graph-optimization problems [14]. In this paper, we extend the results of Karger to show that, besides the value (weight) of the cut-set, the weights of four additional types of edge-set, namely, Volume, Association, Complement Volume and Complement Association, are all well-preserved under URE sampling. More importantly, we show that these well-preserved edge-set metrics have dominant impact on the outcome of common graph-mining tasks including PageRank computation and Community Detection. As a result, URE sampling can be used to accelerate the corresponding graph-mining algorithms with small approximation errors. Via extensive experiments with large-scale graphs in practice, we demonstrate that URE sampling can achieve over 90% accuracy for PageRank computation and Modularity-based Community Detection by sampling only 20% edges of the original graph.

Color brings extra data capacity for QR codes, but it also brings tremendous challenges to the decoding because of color interference and illumination variation, especially for high-density QR codes. In this paper, we put forth a framework for high-capacity QR codes, HiQ, which optimizes the decoding algorithm for high-density QR codes to achieve robust and fast decoding on mobile devices, and adopts a learning-based approach for color recovery. Moreover, we propose a robust geometric transformation algorithm to correct the geometric distortion. We also provide a challenging color QR code dataset, CUHK-CQRC, which consists of 5390 high-density color QR code samples captured by different smartphones under different lighting conditions. Experimental results show that HiQ outperforms the baseline [1] by 286% in decoding success rate and 60% in bit error rate.

With the explosion of graph scale of social networks, it becomes increasingly impractical to study the original large graph directly. Being able to derive a representative sample of the original graph, graph sampling provides an efficient solution for social network analysis. We expect this sample could preserve some important graph properties and represent the original graph well. If one algorithm relies on the preserved properties, we can expect that it gives similar output on the original graph and the sampled graph. This leads to a systematic way to accelerate a class of graph algorithms. Our work is based on the idea of stratified sampling [14], a widely used technique in statistics. We propose a heuristic approach to achieve efficient graph sampling based on community structure of social networks. With the aid of ground-truth of communities available in social networks, we find out that sampling from communities preserves community- related graph properties very well. The experimental results show that our framework improves the performance of traditional graph sampling algorithms and therefore, is an effective method of graph sampling.

All printed documents/credentials are potentially subject to counterfeiting and forgery. Conventional counterfeiting solutions such as watermarking or printing using special-quality paper are not cost-effective. Certification via authorized chops/stamps is low-cost but only provides a false sense of security/ authenticity. To tackle this problem, we propose AuthPaper: a cost-effective, secure solution for authenticating paper-based documents/credentials using off-the-shelf handheld devices such as smartphones and tablets. The key idea is to extend existing 2D barcodes, e.g. the QR code, to carry a large amount of self-describing, and most importantly, authenticated data of all types containing text, image and other binary ones. By embedding the Authenticated 2D barcode as an integral part of a paper-based document, the authenticity of the document can be readily verified by comparing its content with the corresponding digitally-signed content contained in the Authenticated 2D barcode. No online network-access or real-time communication with the document issuer is required during the document verification process. We have built a prototype using Android smartphones to prove that the proposed system is feasible. As shown by measurements, our prototype can accurately create and decode 2D barcodes carrying different sets of document data including images while the increases in processing time and memory usage are negligible.

Job scheduling for a MapReduce cluster has been an active research topic in recent years. However, measurement traces from real-world production environment show that the duration of tasks within a job vary widely. The overall elapsed time of a job, i.e. The so-called flow time, is often dictated by one or few slowly-running tasks within a job, generally referred as the "stragglers". The cause of stragglers include tasks running on partially/intermittently failing machines or the existence of some localized resource bottleneck(s) within a MapReduce cluster. To tackle this online job scheduling challenge, we adopt the task cloning approach and design the corresponding scheduling algorithms which aim at minimizing the weighted sum of job flow times in a MapReduce cluster based on the Shortest Remaining Processing Time scheduler (SRPT). To be more specific, we first design a 2-competitive offline algorithm when the variance of task-duration is negligible. We then extend this offline algorithm to yield the so-called SRPTMS+C algorithm for the online case and show that SRPTMS+C is (1+∊) -- speed o(1/∊2) -- competitive in reducing the weighted sum of job flow times within a cluster. Both of the algorithms explicitly consider the precedence constraints between the two phases within the MapReduce framework. We also demonstrate via trace-driven simulations that SRPTMS+C can significantly reduce the weighted/unweighted sum of job flow times by cutting down the elapsed time of small jobs substantially. In particular, SRPTMS+C beats the Microsoft Mantri scheme by nearly 25% according to this metric.

Social Networking Service has become an essential part of our life today. However, many privacy concerns have recently been raised due to the centralized nature of such services. Decentralized Social Network (DSN) is believed to be a viable solution for these problems. In this paper, we design a protocol to coordinate the pulling operation of DSN nodes. The protocol is the result of forward engineering via utility maximization that takes communication layer congestion level as well as social network layer centrality into consideration. We solve the pulling rate control problem using the primal-dual approach and prove that the protocol can converge quickly when executed in a decentralized manner. Furthermore, we develop a novel “drumbeats” algorithm to estimate node centrality purely based on passively-observed information. Simulation results show that our protocol reduces the average message propagation delay by 15% when comparing to the baselined Fixed Equal Gap Pull protocol. In addition, the estimated node centrality matches well with the ground-truth derived from the actual topology of the social network.

A parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow or simply because extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for a parallel processing cluster under different loading conditions. For the lightly loaded case, we analyze and propose two optimization-based schemes, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the job utility. We also derive the workload threshold under which SCA should be used for speculative execution. Our simulation results show SCA can reduce the total job flowtime by nearly 22% comparing to the speculative execution strategy of Microsoft Mantri. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme. We show that the ESE algorithm can beat the Mantri baseline scheme by 35% in terms of job flowtime while consuming the same amount of resource.

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/ reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels.

Parallel processing plays an important role for large-scale data analytics. It breaks a job into many small tasks which run parallel on multiple machines such as MapReduce framework. One fundamental challenge faced to such parallel processing is the straggling tasks as they can delay the completion of a job seriously. In this paper, we focus on the speculative execution issue which is used to deal with the straggling problem in the literature. We present a theoretical framework for the optimization of a single job which differs a lot from the previous heuristics-based work. More precisely, we propose two schemes when the number of parallel tasks the job consists of is smaller than cluster size. In the first scheme, no monitoring is needed and we can provide the job deadline guarantee with a high probability while achieve the optimal resource consumption level. The second scheme needs to monitor the task progress and makes the optimal number of duplicates when the straggling problem happens. On the other hand, when the number of tasks in a job is larger than the cluster size, we propose an Enhanced Speculative Execution (ESE) algorithm to make the optimal decision whenever a machine is available for a new scheduling. The simulation results show the ESE algorithm can reduce the job flow time by 50% while consume fewer resources comparing to the strategy without backup.

Decentralized Social Network (DSN) has attracted a lot of research and development interest in recent years. It is believed to be the solution to many problems of centralized services. Due to the data limitation imposed by common decentralized architectures, centralized algorithms that support social networking functions need to be re-designed. In this work, we tackle the problem of community detection for a given user under the constraint of limited local topology information. This naturally yields a classification formulation for community detection. As an initial study, we focus on a specific type of classifiers — classification by thresholding against a proximity measure between nodes. We investigated four proximity measures: Common Neighbours (CN), Adamic/Adar score (AA), Page Rank (PR), Personalized PageRank (PPR). Using data collected from a large-scale Online Social Network (OSN) in practice, we show that PPR can outperform the others with a few pre-known labels (37.5% to 64.97% relative improvement in terms of Area Under the ROC Curve). We further carry out extensive numerical evaluation of PPR, showing that more pre-known labels can linearly increase the capability of the single-feature classifier based on PPR. Users can thus seek for a trade-off between labeling cost and classification accuracy.

Online Social Networks (OSNs) heavily rely on community detection algorithms to support many of their core services. Common functions such as friend recommendation, and timeline personalization all require the fast discovery of communities over some massive graph(s). For such applications, scalability, flexibility and speed are much more important than marginal improvement in the theoretical quality of the results. While the community detection problem has been studied intensively in the past, existing work tends to emphasize on theoretical optimality than the aforementioned practical needs. In this paper, we present a 2-stage framework called Proximity-Based Cut and Merge (PBCM), for scalable and robust community detection. In the first stage, edges between low proximity nodes are eliminated in one pass. In the second stage, high proximity nodes are merged iteratively to produce results conforming to the intuitive notion of community. We explore the design space via extensive numerical evaluation to instantiate an effective community detection algorithm under the framework, and compare the performance of PBCM-based designs against state-of-the-art baselines. Our results show that the proposed PBCM framework is effective, scalable and robust. We also demonstrate the flexibility of PBCM by extending it to handle both overlapping and non-overlapping communities.

All printed documents and credentials are potentially subject to counterfeiting and forgery. Conventional counterfeiting solutions such as watermarking or printing with special-quality paper are not cost-effective. Certification via authorized chops/ stamps is low-cost but only provides a false sense of security/ authenticity. While embedding a serial number in the document for online verification is low-cost and secure, it is not applicable without Internet connection. We demonstrate AuthPaper (Authenticated Paper) to solve these problems by: 1) Digitally sign on the document to be protected; 2) Put the original content, digital signature and optionally the signer's certificate in a self-describing encapsulation; 3) Generate a 2D barcode (e.g. QR code) to carry the encapsulation and embed it as an integral part of the paper document. Note that the information carried in Authenticated QR Code is 40 to 50 times more than a typical one (≈50 Bytes). The biggest technical challenge is to scan and decode such densely packed codes in a robust manner. We have developed an Android application to address the challenge. In short, AuthPaper provides a secure, low-cost and offline method for document authentication.

Several new RFID counting algorithms have recently been proposed based on the probabilistic counting schemes introduced by Kodialam et al. These existing algorithms took into account the unreliability of the communication channels between the RFID reader and the tags, and are capable of providing accurate tag-count estimates. However, all algorithms were designed and evaluated based on a simplistic packet loss model. It assumes that the loss probability of a packet between the reader and the tag-set follows an independent, identical distribution. As presented by some empirical measurements, movements of personnel or equipments in a building can generate Doppler effect, which introduces time correlations to the fading signal. Thus, the realistic packet loss of the wireless channels is temporally correlated due to the frequent change of the nearby environment. Depending on specific implementations of each algorithm, temporally correlated packet loss might have significant impact on the tag-set cardinality estimation. In this paper, we evaluate the performance of the aforementioned RFID counting algorithms under a more sophisticated time-correlated channel fading model. In particular, we focus on investigating how temporal correlations would influence the accuracy of these existing algorithms. Based on the experimental statistics that characterized the indoor channels, we refine the channel model to describe the time-correlation. Comparisons of the performance of the counting schemes under the simplistic uncorrelated packet loss channel model and the refined correlated channel model are conducted. We also propose extensions for these RFID counting schemes to mitigate the estimation inaccuracy generated by the correlated packet loss.

Decentralized Social Network (DSN) has attracted a lot of research and development interest in recent years. It is believed to be the solution to many problems of centralized services. Due to the data limitation imposed by common decentralized architectures, centralized algorithms that support social networking functions need to be re-designed. In this work, we tackle the problem of community detection for a given user under the constraint of limited local topology information. This naturally yields a classification formulation for community detection. As an initial study, we focus on a specific type of classifiers - classification by thresholding against a proximity measure between nodes. We investigated four proximity measures: Common Neighbours (CN), Adamic/Adar score (AA), Page Rank (PR), Personalized PageRank (PPR). Using data collected from a large-scale Social Networking Service (SNS) in practice, we show that PPR can outperform the others with a few pre-known labels (37.5% to 64.97% relative improvement in terms of Area Under the ROC Curve). We further carry out extensive numerical evaluation of PPR, showing that more pre-known labels can linearly increase the capability of the single-feature classifier based on PPR. Users can thus seek for a trade-off between labeling cost and classification accuracy.

The MapReduce paradigm is now the de facto standard for large-scale data analytics. In this paper we address the resource management issues in MapReduce Cluster. Speculative execution (task backup) plays an important role in resource management. We propose two different strategies and build two models to formulate the backup issue as an optimization problem when the cluster is lightly loaded. Moreover, we present an Enhanced Speculative Execution (ESE) algorithm when the cluster is heavily loaded and adopt the approximate analysis to get an optimal value for the parameter in the algorithm. The simulation results show that the algorithm can reduce the job completion time by 50% while consuming much less resource compared to the naive method without backup.

Feedback Retransmission Approximation for Slotted ALOHA (FRASA) is proposed to study the stability region of finite-user slotted ALOHA under the collision channel. With FRASA, the stability region is derived in closed form for any number of users in the system. The result derived from FRASA is shown to be identical to the analytical result of finite-user slotted ALOHA when there are two users. It is shown that the stability region obtained from FRASA is a good approximation to the stability region of finite-user slotted ALOHA. The convex hull bound, which is convex, piecewise linear and outer bounds the stability region of FRASA, is provided.$p$-convexity, an essential property that the stability region of FRASA should have to ensure the convex hull bound is close to the boundary, is characterized. From these, it is derived that the stability region of FRASA can never be convex when there are more than two users. A separate convex and piecewise linear inner bound on the stability region of FRASA, the supporting hyperplane bound, is also given.

We study the downlink scheduling performance of an IEEE 802.11-based roadside Access Point(AP) serving a number of moving vehicles. For determining the scheduling order, throughput and Fairness are two important considerations. If system throughput Maximization is the sole consideration, some vehicles can always get resource from the AP whereas some are starved. On the other hand, if fairness is the sole consideration, resource should be allocated among all the contending vehicles regardless of individual vehicle's channel conditions and the system utilization should not be affected greatly. In this paper, we propose a novel scheduling algorithm called VEhicular Context-Aware Downstream Scheduling (VECADS). By exploiting the real-time vehicular context including the position, speed and cumulative data received by each vehicle, the scheduler can get up-to-date information to determine an appropriate scheduling order. The design objective of VECADS is to strike a better balance between system throughput and fairness among heterogeneous drive-thru vehicles. The performance of VECADS is evaluated via extensive ns2 simulations using real-world vehicular traffic traces. We show that VECADS outperforms MV-MAX, the state-of-the-art scheduling scheme for Drive-thru networks, in terms of system throughput, by 7 % while eliminating the bandwidth starvation problem of ``weak" vehicles under MV-MAX for a Jain's Index of 0.895 vs. 0.727.

In order to spread malware more effectively, hackers have started to target popular social networking services (SNS) due to the inherent trust-relationship between the SNS users and the interactive nature of the services. A common attacking approach is for a malware to automatically login using stolen SNS user credentials and then deliver malicious weblinks (Uniform Resource Locators (URLs)) to the people on the contact/friend-list of the stolen user account by embedding them in some short messages. The victim then gets infected by clicking on the links thought to be delivered by their friends. However, for this approach to be effective, the malware has to mimic human-like behavior which can be quite challenging for anything beyond one or two-liner conversations. In this paper, we introduce Hitchbot, which uses a stealthier way to deliver malicious URLs by hitch-hiking on legitimate conversations among SNS users. In particular, when a SNS user sends a web-link/URL to his/her friends, Hitchbot will quietly replace it with a similar-looking, but malicious one by intercepting the link at one of the several possible points along the interactive input/output chain of the system. Since the malicious link is delivered within some proper conversation context between the legitimate users, this makes it much more difficult for the victim (as well as the innocent spreader) to realize the attack and thus can increase the conversion rate while reducing the rate of being detected substantially. The social hitch-hiking approach also enables Hitchbot to bypass most existing defense schemes which mainly rely on anomaly detection for user- behavior or application/network traffic pattern. As a proof of concept, we have implemented Hitchbot as a client-based module to hitch-hike on common social networking services including the Yahoo and Microsoft Messaging clients and other web-browser-based social networking services such as Facebook and Myspace. To quantify the effectiveness of Hitchbot, we have conducted experiments to measure the behavior of users in exchanging, handling and operating on URLs. Possible defense schemes for detecting social hitch-hiking attacks are also discussed.

A low-latency, accurate RFID counting scheme can be used as a fundamental building block to support more elaborated RFID query operations. RFID counting algorithms of such nature have been proposed recently by Kodialam et. al.. One distinct feature of these schemes is that they do not require the reader to explicitly identify individual tags and thus can help to preserve privacy of the RFID users. However, these schemes all assume a perfect communication channel between the reader and the tags which is not achievable in practice. Recent empirical measurement studies have found that the radio communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and non-deterministic due to ever-changing channel conditions. Worse still, given the stringent cost constraint, it is unlikely that standard channel estimation procedures can be applied for individual tags. In this paper, we propose two new algorithms which can provide good estimates of the size of an RFID tag-set over unreliable, lossy wireless channels while assuming minimal or no prior knowledge of channel parameters. These algorithms are scalable over a wide range of tag-set size using a small, fixed protocol frame-size, which is critical for low-cost RFID tags with typically sub-par synchronization or timing control. They are also adaptive in the sense that, they self-tune the algorithm parameters according to the tag-set size and channel characteristics. This set of features makes them applicable in a wide variety of situations where the reader is unaware of or has very limited knowledge of the channel conditions. We also demonstrate the efficacy of the proposed schemes via extensive simulation studies.

Drive-thru Internet systems are multiple-access wireless networks in which users in moving vehicles can connect to a roadside access point (AP) to obtain Internet connectivity for some period of time as the vehicles pass through the AP's coverage range. In order to evaluate the type of communication services and the quality-of-service that these systems can provide, in this paper, we investigate the data communication performance of a vehicle in Drive-thru Internet systems. In particular, we derive analytical models with tractable solutions to characterize the average and the distribution of the number of bytes downloaded by a vehicle by the end of its sojourn through an AP's coverage range, in the presence of other vehicles contending for the same AP's resources. Our models are able to quantify the impact of road traffic density, vehicle speed, service penetration rate, AP's transmission range and the corresponding bit rate, on the amount of data downloaded by an individual vehicle. In terms of analysis technique, we map the study of our vehicular data downloading process into the transient analysis of a series of Markov reward processes. Our use of Markov reward model is novel in the sense that we only select from the corresponding Markov chain, a subset of relevant sample paths that matches the required behavior of our vehicular flow model. We also validate our proposed analytical models through extensive simulations, driven by empirical vehicular traffic traces. We believe our work offers a unique analytical framework based on which the interplay between vehicular traffic parameters and a vehicle's data communication performance in a Drive-thru Internet system can be studied and optimized in a systematic, quantitative manner.

Dynamic Spectrum Access (DSA) networks can achieve higher spectrum efficiency by exploring the unused spectrum in licensed band. Most of the existing work focuses on maximizing the spectrum utilization while ignoring the immediate influence from the primary (licensed) users to the DSA traffic flows generated by secondary (often unlicensed) users. In this paper, we focus on providing reliability (in terms of a probabilistic life-time guarantee) to the DSA flows. We first propose 3 protection schemes, which provide different levels of pre-planned reliability to an end-to-end DSA flow. We will quantify the lifetime distributions of an end-to- end path in a DSA network under the aforementioned protection schemes. Based on our analysis of the end-to-end path lifetime distribution, various route selection algorithms are proposed to find paths with long lifetime under the corresponding protection scheme. Through simulations, we quantify the tradeoffs between required network capacity and uninterrupted call duration of DSA flows under different route selection algorithms.

Web access logs contain information which can be converted to represent the access history of individual users. A large number of essential attributes can be extracted from the access history. For example, the access counts of each webpage, the occurrence of different webpage access sequences and the time spent between consecutive accesses. Each of the above attributes represents a dimension in the feature space, and all the attributes together form a very high dimension space. Diffusion Wavelets can efficiently project the high dimensional data onto a low-dimensional space according to the correlations between various attributes, so that common anomaly detection algorithms can be applied. In this paper, we propose a system which leverages this technique to differentiate web-access requests generated by Denial of Service (DoS) attacks from legitimate ones. We demonstrate the effectiveness of the proposed system via simulation studies using real-world web access logs. For a simulated HTTP flooding attack which creates a 1000% overload at the web-server, the proposed scheme can reduce the ratio of the attack-to-legitimate requests admitted by the server from 200:1 to 30:1 so that more than 55% of the legitimate requests can still receive proper services under such a severe DoS attack.

Recently, Kodialam et al. [1], [2] have proposed a number of probabilistic counting algorithms with statistical guarantees for RFID. Those algorithms do not require explicit tag identification, and can provide good estimates of tag-set cardinality with low latency. However, these algorithms all assume unrealistically that the communication channel between the reader and the tags is perfect. Direct application of these algorithms in practice can lead to severe under-counting. In [7], we made the first attempt to modify the algorithm in [2] to account for the effects caused by unreliable communications with the tags. However, the scheme proposed in [7] requires the knowledge of the first two moments of the successful responding probability distribution of the tag-set of interest. In other words, a priori (indirect) channel calibration/ profiling is needed. In this paper, we introduce a probabilistic tag counting scheme which does not require prior knowledge of the communication channel between the tags and the reader and yet can provide a good estimate of the cardinality of the tag-set of interest while taking the imperfect, unknown radio channel conditions into account. Our proposed scheme is based on a novel interpretation of the "Capture-Recapture" techniques developed by the ecology/biostatistics community which can adapt automatically to different channel conditions. Our simulation results demonstrate the accuracy of the proposed scheme and its reduced latency when compared to other rudimentary approach relying on simple repeated probing by the reader.

A fast RFID counting algorithm with performance guarantee can be used as a fundamental building block for other more sophisticated RFID query protocols and operations. Recently, Kodialam et. al. propose various low-latency RFID counting schemes with accuracy guarantees based on a probabilistic counting approach which does not require explicit identification of individual tags. However, the proposed schemes all assume a perfect communication channel between the reader and the tags which is unlikely to be true in practice. On the contrary, as demonstrated by recent empirical measurement studies, the radio communications between an RFID reader and a set of seemingly "in-range" tags are rather non-deterministic and can even be unreliable at times due to varying radio conditions. In this paper, we extend the algorithms in by taking into account the effects of radio channel unreliability. By modeling the spatial distribution of tags and the corresponding channel fading effects, we analyze the new requirements on the algorithm parameters used in (e.g. number of reader polling cycles, frame-size and persistent probability) in order to achieve a desired level of estimation accuracy. Another key observation is that, unlike the perfect channel case where one can indefinitely reduce the estimation error by increasing the number of reader polling cycles, with an unreliable radio channel, there is a lower-bound on the estimation error due to the inherent variation in the spatial distribution of the tags and the radio channel conditions. Towards this end, we have derived an expression for this lower-bound. We also demonstrate the efficacy of our analytical results and their corresponding guarantees in estimation accuracy via an simulation study.

Opportunistic routing significantly improves the average progress per transmission over unicast routing by leveraging the opportunistic receptions of multiple potential forwarders in wireless mesh networks. Prior studies mainly focus on networks with omni-directional antenna only. Our previous work suggests that not every node contributes equally in a transmission. By concentrating the beam energy at a particular direction, directional antennas may further improve the performance of opportunistic routing in multi-hop wireless networks. In this paper, we derive an analytical model which allows the incorporation of various node distribution models, radio channel models and antenna models to evaluate the average progress per transmission. It is found that a directional antenna with high directivity does not always improve the performance of opportunistic routing and an optimal beamwidth exists for each particular network. When compared to the case of omni-directional antenna, a directional antenna with optimal beamwidth and direction settings can achieve 30 to 50% performance gain, in terms of average progress per transmission, under typical network configurations. Moreover, such performance gain can be as high as 100% for radio propagation environments where the packet reception probabilities fall off slowly with distance.

Given a large set of RFID tags, we are interested in determining the categories of tags that are present in the shortest time possible. Since there can be more than one tag present in a particular category, pure randomized strategies that rely on resolving individual tags are very inefficient. Instead, we rely on a pseudo-random strategy that utilizes a uniform hash function to accurately identify all t categories present among a given set of ψ tags with high probability. We propose two algorithms: (a) a single frame algorithm that determines the optimal frame size, and (b) a probabilistic version where the frame size is fixed, and we select the probability to minimize the number of frames needed for identification. Both of these algorithms run in time linear to the number of categories present, t. We show that our approach significantly outperforms existing algorithms for category identification. The performance of our algorithms is within a constant factor of the lower bound.

The delay performance of delay tolerant networks (DTN) can be improved by adding or replacing mobile nodes with higher mobility or transmit power. In this paper, we examine the design trade-offs in heterogeneous DTNs with two types of mobile relay nodes: normal and super. First we present the range of parameters in the Random Direction (RD) mobility model in which we have validated the Markovian assumption on the node inter-encounter intervals. Next, we describe the two-dimensional continuous time Markov chain (CTMC) model with absorption state, used for evaluating the performance of the heterogeneous DTNs. We demonstrate that the performance improvement of adding super nodes is not linear. For example, replacing 10% of the normal nodes with super nodes ones can achieve 40% of the delay reduction versus replacing all of them. Finally, Fluid Flow Approximation (FFA) and Moment Closure Methods for solving the CTMC with various error rates (about 10%) were developed to allow faster analysis of networks with large number of nodes.

As we continue to see the increasing global-scale deployment of Internet Protocol version 6 (IPv6) networks, it is equally important to evaluate the performance of these IPv6 networks. In this paper, we present comprehensive empirical measurements of the IPv6 network performance from an end- user's perspective. In particular, by sending probing traffic from our dual-stack IPv6/IPv4 testbed to over 2,000 dual-stack hosts worldwide, we quantify the performance differences of using IPv6 vs. IPv4, in terms of various network metrics like network connectivity, hop count, RTT, throughput, operating systems dependencies as well as the address configuration latency. We also investigate the performance impact of using IPv6 tunneling brokers instead of native IPv6 services. Whenever possible, we also compare our measurement results with previously published ones to reflect on the progress of IPv6 deployment/performance improvements in the past few years. In general, our results indicate that in these past few years, the IPv6 backbone has improved considerably to provide more than 95% network connectivity to various IPv6 sites. The end-user-perceived performance offered by some IPv6 tunnel brokers are also comparable to that of native IPv6 services.

Cognitive radio (CR) technology can achieve higher spectrum efficiency by exploring the unused spectrum in licensed band. Most of the existing work focuses on maximizing the spectrum utilization but ignores the immediate influence from primary users to network throughput. In this paper, we investigate the importance of planned link restoration in cognitive radio networks. We formulate the link restoration problem as an integer programming problem. By considering both channel assignment and interference between links, the link through-put can be guaranteed even when primary users appear, and therefore can provide the needed reliability for real-time wireless applications. We consider a link failure model which captures the induced link failures from multiple primary users operating on one frequency channel. Under this failure model, our algorithm explores the sharing of backup capacity. We compare our algorithm to two baseline restoration schemes. Our algorithm performs very well in terms of capacity usage and throughput reliability. By reserving 24.8% of network capacity, our algorithm meets the guarantee requirement in all simulation cases, while "no restoration" just meets the guarantee requirement in 50.8% of all simulation cases.

Recently, the idea of opportunistic routing has been widely explored to improve the performance of multi-hop wireless mesh networks. Most of the previous studies use simulations or empirical measurements to evaluate the performance gain of opportunistic routing and therefore are limited to relatively few types of scenarios. In this paper, we take an analytical approach to study the potential gain of opportunistic routing in multi- hop wireless networks. Unlike other analytical studies which use a deterministic channel model, our approach captures the key characteristics of opportunistic routing, i.e. its ability to take advantage of the numerous, yet unreliable wireless links in the network in a probabilistic manner and study the effectiveness of opportunistic routing under diverse radio propagation environment using lognormal shadowing and Rayleigh fading models. Our results show that, under typical network configurations and neglect overhead, the average progress per transmission of opportunistic routing in lognormal shadowing (Rayleigh fading) environment is about 3 (1.5) times higher than that of traditional unicast routing. Finally, we also demonstrate the potential benefits of using different forwarding regions and directional antennas in opportunistic routing.

This paper presents the findings of an extensive measurement study on multiple commercial 3G networks. We have investigated the performance of those 3G networks in terms of their data throughput, latency, video and voice calls handling capacities, and their ability to provide service guarantees to different traffic classes under saturated and lightly-loaded network conditions. Our findings point to the diverse nature of the network resources allocation mechanisms and the call admission control policies adopted by different operators. It is also found that the 3G network operators seem to have extensively customized their network configurations in a cell-by-cell manner according to the individual site's local demographics, projected traffic demand and the target coverage area of the cell. As such, the cell capacity varies widely not only across different operators but also across different measurement sites of the same operator. The results also show that it is practically impossible to predict the actual capacity of a cell based on known theoretical models and standard parameters, even when supplemented by key field measurements such as the received signal-to-noise ratio (Ec/N0)

In this paper, we propose DATALITE, a Distributed Architecture for Traffic Analysis via LIght-weight Traffic digEst, which introduces a set of new distributed algorithms and protocols to support general Traffic Measurement and Analysis (TMA) functions for large-scale, 10Gbps+ packet-switched networks. We formulate the network-wide traffic measurement/ analysis problem as a series of set-cardinality-determination (SCD) problems. By leveraging recent advances in probabilistic distinct sample counting techniques, the set-cardinalities, and thus, the network-wide traffic measurements of interest can be computed in a distributed manner via the exchange of extremely light-weight traffic digests (TD’s) amongst the network nodes. A TD for N packets only requires O(loglog N) bits of memory storage.

In evaluating the performance of a wireless network, the interference between wireless links plays a key role. In previous works, interference was assumed to be a binary phenomenon, i.e., either the links mutually interfere with each other, or they do not interfere. However, there were experimental results contradicting this binary assumption. We term this aspartialinterference. In this paper, we present an analytical framework to characterize partial interference in a single-channel wireless network under unsaturated traffic conditions, and use 802.11b with basic access scheme and differential binary phase shift keying as an illustration. An analogy is drawn between partial interference and code division multiple access to demonstrate their similarities. The gain in capacity across unit cut by exploiting partial interference can be as high as 67% under scheduling in a modified Manhattan network.

Real-time traffic has stringent delay requirement. However, bandwidth limited and error-prone wireless networks often show significant delay jitter. Traditional packet discarding schemes designed for high speed wired networks, such as random early detection (RED), are inadequate for wireless networks with high latency and delay variability. This paper describes an analytical framework for designing lifetime packet discard policies and proposes the channel state aware packet discard on expiration likelihood (CAPEL) algorithm, which only admits packets with expiration likelihood below a predefined requirement. Its effectiveness for improving goodput is quantified under a time varying channel modeled by the Markov-modulated Poisson process (MMPP). In addition, we use Gamma distribution to approximate the conditional system time distribution under the MMPP channel. It is verified to be accurate by simulation.

We propose FRASA, Feedback Retransmission Approximation for Slotted ALOHA, to study the stability region of finite-user slotted ALOHA under collision channel. With FRASA, we derive in closed form the boundary of the stability region for any number of users in the system, which is shown to be accurate via simulations. We use convex hulls and supporting hyperplanes to construct convex and piece-wise linear outer and inner bounds on the stability region of FRASA respectively to facilitate network optimization. We hope the analytical findings with FRASA can provide more insights on the characterization of the capacity region of other types of wireless random access networks, and enable traffic engineering with linear constraints in the design of wireless mesh networks.

The increasing use of RFID tags in many applications have brought forth valid concerns of privacy and anonymity among users. One of the primary concerns with RFID tags is their ability to track an individually tagged entity. While this capability is currently thought to be necessary for supporting some features of RFID systems, such practice can lead to potential privacy violations. In this paper, we propose a privacy-preserving scheme that enables anonymous estimation of the cardinality of a dynamic set of RFID tags, while allowing the set membership to vary in both the spatial and temporal domains. In addition, the proposed scheme can identify the dynamics of the changes in the tag set population. The main idea of the scheme is to avoid explicit identification of tags. We demonstrate that the proposed scheme is highly adaptive and can accurately estimate tag populations across many orders of magnitude, ranging from a few tens to millions of tags. The associated probing latency is also substantially lower (les 10%) than that of the schemes which require explicit tag identification. We also show that our proposed scheme performs well even in highly dynamic environments, where the tag set keeps changing rapidly.

This paper presents the findings of an extensive measurement study on multiple commercial 3G UMTS networks. We have investigated the performances of those 3G networks in terms of their data throughput, latency, video and voice calls handling capacities, and their ability to provide service guarantees to different traffic classes under various loading conditions. Our findings indicate the diverse nature of network resources allocation and call admission control policies employed by different operators. It is also found that the 3G network operators seem to have extensively customized their network configurations in a cell-by-cell manner according to the individual site's local demographics, projected traffic demand and the target coverage area of the cell. As such, the cell capacity varies widely not only across different operators but also across different measurement sites of the same operator. Even for the same site, the capacity can easily change by more than 10% across multiple measurements taken at different time of the day. The results also show that it is practically impossible to predict the actual capacity of a cell based on known theoretical models and standard parameters, even when supplemented by key field measurements such as the received signal-to-noise ratio (Ec/N0).

We study the stability of finite-user infinite-buffer slotted ALOHA with partial interference. For the case of two users, there is a gradual, transition from the collision channel to the orthogonal channel when the link separation increases. The stability region can be either convex or nonconvex, depending on the link separation and the transmission probability vector. A partial characterization on the boundary of the stability region in closed form for the case of general number of users is also given. We hope this work can provide insight in designing traffic engineering algorithms in wireless mesh networks with practical random access protocols like 802.11.

Disruption tolerant network (DTN) refers to the type of sparse mobile ad hoc network where the nodes are connected intermittently. A common strategy to cope with intermittent network connectivity is to use multiple-copy routing for message delivery. However, the resultant replicates of messages incur significant burden on the bandwidth and storage requirements of each node. In this paper, we investigate the effect of excessive message-replications in multiple-copy routing in DTNs under communication bandwidth and buffer constraints. By modeling the message delivery process as a Markov chain, we first analytically derive the delivery latency as a function of message-replication limit for the single-message-delivery case. The performance of the multiple-message-multiple-flow case is then evaluated via extensive simulations. For the latter, we observe that there is an optimal value for the message-replication limit of each message beyond which network performance will degrade. Finally, we propose an alternative forwarding and message-dropping strategy to address the problem of unfairness found in the basic FIFO-with-blocking strategy. Our results show that the average message delivery delay can be reduced by as much as 25% with the proposed scheme.

This paper proposes an energy-efficient and receiver-driven, TDMA-based MAC protocol (RMAC) for wireless sensor networks. By placing the ownership of the timeslots in the hands of the receiver nodes and letting the receiver nodes assign the timeslots to their neighboring sender nodes, RMAC not only eliminates the need for the sender nodes to explicitly wake-up a receiver node for data transmission, but also eliminates any collision or contention overhead among the sender nodes. Our simulation results show that RMAC outperforms other sender- driven, TDMA-based MAC protocols in terms of the packet latency and power consumption. We also devised a mechanism to enable unused timeslots to be "stolen" by other sender nodes and show that in the case of uniform timeslots assignment among the sender nodes, "timeslots stealing" increases the network capacity by as much as 200%. In addition, we propose a simple timeslots reassignment procedure to allow the receiver nodes to redistribute the timeslots among the sender nodes according to their offered traffic load, and show that it enables the network to efficiently reduce the packet latency in the face of asymmetric, bursty traffic patterns.

Data reliability and real-time delivery of critical information are very crucial in many wireless sensor network applications such as intruder detection and surveillance. In this paper, we explore different mechanisms to provide differentiated services for time-critical information flows. We compare their performances in terms of the packet delivery ratio and end-to-end latency for a high-priority information flow. Our simulation and delay analysis results show that an approach where the wireless medium is reserved along the path from the source to the sink for a high-priority information flow, can provide guaranteed and low latency delivery for a high-priority flow, with acceptable delay impact to the low-priority flows.

Distributed denial-of-service (DDoS) attacks pose a significant threat to the Internet. Most solutions proposed to-date face scalability problems as the size and speed of the network increase, with no widespread DDoS solution deployed in the industry. PacketScore has been proposed as a proactive DDoS defense scheme, which detects DDoS attacks, differentiates attack packets from legitimate ones with the use of packet scoring (where the score of a packet is calculated based on attribute values it possesses), and discards packets whose scores are lower than a dynamic threshold. In this paper, we propose ALPi, a new scheme which extends the packet scoring concept with reduced implementation complexity and enhanced performance. More specifically, a leaky-bucket overflow control scheme simplifies the score computation, and facilitates high-speed implementation. An attribute-value-variation scoring scheme analyzes the deviations of the current traffic attribute values, and increases the accuracy of detecting and differentiating attacks. An enhanced control-theoretic packet discarding method allows both schemes to be more adaptive to challenging attacks such as those with ever-changing signatures and intensities. When combined together, the proposed extensions not only greatly reduce the memory requirement and implementation complexity but also substantially improve the accuracies in attack detection and packet differentiation. This makes ALPi an attractive DDoS defense system amenable for high-speed hardware implementation.

Distributed denial-of-service (DDoS) attacks are a critical threat to the Internet. This paper introduces a DDoS defense scheme that supports automated online attack characterizations and accurate attack packet discarding based on statistical processing. The key idea is to prioritize a packet based on a score which estimates its legitimacy given the attribute values it carries. Once the score of a packet is computed, this scheme performs score-based selective packet discarding where the dropping threshold is dynamically adjusted based on the score distribution of recent incoming packets and the current level of system overload. This paper describes the design and evaluation of automated attack characterizations, selective packet discarding, and an overload control process. Special considerations are made to ensure that the scheme is amenable to high-speed hardware implementation through scorebook generation and pipeline processing. A simulation study indicates that packetscore is very effective in blocking several different attack types under many different conditions.

An adaptive sleeping and awakening protocol (ASAP) is proposed for nodes in a synchronous adhoc sensor network. In order to increase energy efficiency, nodes within the network enter into a sleep mode and awaken at pre-determined time slot(s) to listen for transmissions from its immediate neighbors. Implicit knowledge of awakening slots for neighboring nodes is used to schedule transmissions within the neighborhood. Finally, nodes adapt their sleeping cycles based on neighbor topology and remaining battery life in order to maximize the network lifetime while satisfying the latency requirements of the underlying sensor application. Simulation results show that with delay constrained routing, ASAP can achieve twice the energy efficiency (or battery life) of a synchronous awakening approach.

Distributed denial of service (DDoS) attack is a critical threat to the Internet. Recently we have proposed the PacketScore scheme, a DDoS defense architecture that supports automated attack detection, on-line attack characterization and attack blocking. Its key idea is to use a statistics-based packet scoring mechanism to distinguish between legitimate and non-legitimate packets and discard packets based on the packet scores. In order for such an approach to work, we need to perform on-line traffic characterizations, and compare such characterizations with the nominal profiles (generated from past history or off-line analysis). The threshold used for the score-based selective packet discard decision is dynamically adjusted based on the score distribution of recent incoming packets. In our previous paper [Kim et al. 2004], we discuss how our proposed system performs in different attack scenarios. In this paper, we first give a brief review of the PacketScore approach and further elaborate on the transient performance under varying attack types and intensities, which may be exploited in more sophisticated attacks. We then show that PacketScore is well capable of blocking such sophisticated attacks by simply adjusting the measurement window time scale to closely track the attack profile.

Distributed denial of service (DDoS) attack is a critical threat to the Internet. Currently, most ISPs merely rely on manual detection of DDoS attacks after which offline fine-grain traffic analysis is performed and new filtering rules are installed manually to the routers. The need of human intervention results in poor response time and fails to protect the victim before severe damages are realized. The expressiveness of existing filtering rules is also too limited and rigid when compared to the ever-evolving characteristics of the attacking packets. Recently, we have proposed a DDoS defense architecture that supports distributed detection and automated on-line attack characterization. We focus on the design and evaluation of the automated attack characterization, selective packet discarding and overload control portion of the proposed architecture. Our key idea is to prioritize packets based on a per-packet score which estimates the legitimacy of a packet given the attribute values it carries. Special considerations are made to ensure that the scheme is amenable to high-speed hardware implementation. Once the score of a packet is computed, we perform score-based selective packet discarding where the dropping threshold is dynamically adjusted based on (1) the score distribution of recent incoming packets and (2) the current level of overload of the system.

Multiple access control (MAC) of the uplink in a wireless mobile computing system is one of the most important resource allocation problems in that the response time and throughput of user applications (e.g., wireless web surfing) are critically affected by the efficiency of the MAC protocol. Compared with a traditional MAC problem (e.g., wireline Ethernet), there are two important new challenges in a modern wireless network: (1) multimedia data with diverse traffic requirements are involved; and (2) the wireless channel has a time-varying quality for each user. Furthermore, a more prominent user requirement is fairness among different users, possibly, with different traffic demands. While some protocols have been suggested to handle multimedia data and/or tackling the time-varying channel, there are a number of drawbacks in these existing protocols. The most notable drawback is that the channel model is rather unrealistic - just using a two state Markov chain instead of relying on accurate models of multipath fading and shadowing effects. Another common deficiency is that fairness is ignored. In this paper, we propose to use a new notion of fairness that can capture a realistic channel model, and to integrate a fair queuing scheduling algorithm in a MAC protocol to optimize performance while maintaining fairness among users regardless of their channel states and data types.

CDMA (code division multiple access) systems are critical building blocks of future high performance wireless and mobile computing systems. While CDMA systems are very mature for voice services, their potentials in delivering high quality data services are yet to be investigated. One of the most crucial component in an advanced wideband CDMA system is the judicious allocation of bandwidth resources to both voice and high data rate services so as to maximize utilization while satisfying the respective quality of service requirements. Specifically, in a multicode CDMA system, the problem is to intelligently allocate codes to the users' requests. While previous work in the literature has addressed this problem from a capacity point of view, the fairness aspect, which is also important from the users' point of view, is largely ignored. In this paper, we propose a new code allocation approach that is channel adaptive and can guarantee fairness with respect to the users' channel conditions. Simulation results show that out approach is more effective than the proportional fair approach.

UMTS radio link control (RLC) contains a suite of features and options that make it a challenging task for performance evaluation. We develop a periodic-polling-based retransmission model to analyze the RLC protocol. We derive the evolution of the queue length distribution that can be used to construct a Markov chain. While the task of obtaining a closed-form solution for this Markov chain given a general set of system parameters seems to be formidable, we have been able to obtain a closed-form solution for the average system occupancy for some interesting special cases. To validate the efficacy of the analytical model, we perform numerical calculation on the upper and lower bounds of the average packet delay and compare it with the simulation results. The results show that the lower bound derived is very tight.

The Internet is organized as an interconnection of separate administrative domains called autonomous systems (ASs). The border gateway protocol (BGP) is the de facto standard for controlling the routing of traffic across different ASs. It supports scalable distribution of reachability and routing policy information among different ASs. In this paper, we study a network design problem which determines (1) the optimal placement of border router(s) within a domain and (2) the corresponding inter- and intra-domain traffic patterns within an AS. Practical constraints imposed by BGP and other standard shortest-path-based intra-domain routing protocols are considered. The problem is formulated as a variant of the uncapacitated network design problem (UNDP). While it is feasible to use a brute-force, integer-programming-based approach for tackling small instances of this problem, we have resorted to a dual-ascent approximation approach for mid/large-scale instances. The quality of the approximation approach is evaluated in terms of its computational efficiency and network cost sub-optimality. Sensitivity analysis w.r.t. various network/traffic parameters are also conducted. We then describe how one can apply our optimization results to better configure BGP as well as other intra-domain routing protocols. This serves as a first-step towards the auto-configuration of Internet routing protocols, BGP in particular, which is "well-known" for its tedious and error-prone configuration needs.

Wireless fair queueing algorithms have been extensively studied recently. However, a major drawback in existing approaches is that the channel model is overly simplified - a two states (good or bad) channel is assumed. While it is relatively easy to analyze the system using such a simple model, the algorithms so designed are of a limited applicability in a practical environment, in which the level of burst errors are time-varying and can be exploited by using channel adaptive coding and modulation techniques. In this paper, we first argue that the existing algorithms cannot cater for a more realistic channel model and the traditional notion of fairness is not suitable. We then propose a new notion of fairness, which bounds the actual throughput normalized by channel capacity of any two sessions. Using the new fairness definition, we propose a new fair queueing algorithm called CAFQ (channel adaptive fair queueing), which, as indicated in our numerical studies, outperforms other algorithms in terms of overall system throughput and fairness among error prone sessions.

Self-similar traffic is distinguished by positive correlation, which can be exploited for better traffic management. Inspired by measurement-based admission control schemes, a measurement-based congestion alarm is proposed. The aggregate traffic at an output port of a switch or router in a high-speed network is modeled by a fractional Gaussian noise process. Traffic measurements are performed in regular time intervals to determine the current traffic loading. This information is then used to predict the loading situation in the near future. If congestion is likely to occur, a congestion alarm is set off and appropriate network management functions taken to alleviate the possible congestion. The above constitutes a closed loop feedback control mechanism that maintains high resource utilization. Simulation results show that the proposed scheme, when used with dynamic bandwidth allocation, reduces bandwidth requirements by more than 20%.

Most of the existing ATM available bit rate (ABR) flow control algorithms are designed based on the assumption of a simple output-buffered switch architecture. Under such an assumption, congestion can only occur at the output ports of the switch. Moreover, multiple output ports of an ATM switch can be modeled as independent queues whose congestions are independent of each other. Previously, however, research/commercial ATM switches have been evolving towards a multiple-stage architecture which contains both input and output queueing to improve capacity scalability. With the new architectures, congestion can develop at different locations within a switch. More importantly, the onset of these congestions may dependent on each other. It therefore becomes necessary for any ABR flow control algorithm to handle multiple dependent bottlenecks under such architecture. In this paper, we describe a unified ABR flow control strategy for the new generation ATM switches. Our design is geared towards the multi-stage, input/output-queueing architecture. Our strategy can be used to adapt any existing output-buffering focused, queue-length based ABR algorithm for the new architecture. As a concrete example, we discuss the adaptation of the DMRCA ABR flow control algorithm for a multiple-stage input/output queueing switch. The result is a utilization-based adaptive dual DMRCA algorithm which achieves (1) low cell-loss, (2) high switch utilization and (3) per-VC fairness in bandwidth allocation for VCs across multiple ingress buffers when traffic patterns permit. We also present results from simulation studies.

We study the effectiveness of statistical multiplexing and buffer sharing under the multimedia high-speed networking environment. We focus on the impact of frequency-domain source characteristics on dynamic resource sharing. By applying a novel statistical matching technique, we can, for the first time, investigate the multiplexing performance of a wide-range of realistic traffic sources using sophisticated traffic models. It has been shown that the effectiveness of statistical multiplexing and buffer sharing highly depends on the frequency-domain characteristics of the traffic as well as the corresponding QoS requirements. For practical "low-frequency" sources; e.g., VBR-video streams and LAN-to-LAN traffic, we show that significant savings in bandwidth and buffer-space can be achieved via resource sharing under practical loss and delay constraints. These findings re-illustrate the important role of traffic characteristics in the design/selection of network control strategies. The trade-offs among different design alternatives (e.g., multiplexing versus buffering) and the implications on some control schemes, e.g., traffic shaping/input-rate control, are also discussed.

In this paper, we study the sojourn-time statistics and the temporal behavior of nodal congestion in integrated broadband networks. The node is modeled as a finite quasi-birth-death (QBD) process with level-dependent transitions. By formulating the problem as one which is amenable to the generalized folding algorithm (GFA), we are, for the first time, able to analyze realistic systems with large buffer and complex input traffic. The dynamics of the system under realistic traffic environment and different operating regimes are studied. The effects of various modeling artifacts such as fluid-flow and infinite-buffer approximations are also investigated. The potential of statistical multiplexing in reducing bursty cell loss is demonstrated. The trade-offs between different system design alternatives, e.g., buffering vs. statistical multiplexing, are discussed. We also investigate the controlling effect of preemptive cell discarding on steady-state and transient system performance. Both single-level and two-level overload control with hysteresial-switching mechanisms are considered. The use of sojourn-time based QoS metrics to supplement long-term steady-state metrics is also discussed.

The conditions under which nodal decomposition can be applied for networkwide, multimedia traffic analysis are determined. Through extensive simulation studies of individual departure source characteristics and intersource cross-correlation at the output side of a network node, the nodal decomposition approach is validated for large-scale high-speed, integrated networks. Both homogeneous and heterogeneous traffic environments in which individual sources are modeled as various two-state/multiple-state Markov-modulated processes are considered. By applying the validated nodal decomposition approach, the problem of analyzing the performance of a multimedia network as a whole becomes tractable. Each ATM node is modeled by a queue with infinite buffers and a deterministic server.>