As deep image forgery powered by AI generative models, such as GANs, continues to challenge today's digital world, detecting AI-generated forgeries has become a vital security topic. Generalizability and robustness are two critical concerns of a forgery detector, determining its reliability when facing unknown GANs and noisy samples in an open world. Although many studies focus on improving these two properties, the root causes of these problems have not been fully explored, and it is unclear if there is a connection between them. Moreover, despite recent achievements in addressing these issues from image forensic or anti-forensic aspects, a universal method that can contribute to both sides simultaneously remains practically significant yet unavailable. In this paper, we provide a fundamental explanation of these problems from a frequency perspective. Our analysis reveals that the frequency bias of a DNN forgery detector is a possible cause of generalization and robustness issues. Based on this finding, we propose a two-step frequency alignment method to remove the frequency discrepancy between real and fake images, offering double-sided benefits: it can serve as a strong black-box attack against forgery detectors in the anti-forensic context or, conversely, as a universal defense to improve detector reliability in the forensic context. We also develop corresponding attack and defense implementations and demonstrate their effectiveness, as well as the effect of the frequency alignment method, in various experimental settings involving twelve detectors, eight forgery models, and five metrics

Advancements in edge computing and container technology have made it increasingly popular and convenient to deploy Large Language Models (LLMs) through containers at the edge. However, the limited GPU resources of edge servers make it impractical to retain the model in GPU memory for long periods due to the high memory cost, especially when they remain idle without user requests. Existing work unloads the entire idle models to reduce memory costs on edge servers, but reloading them introduces significant loading delays that affect task Quality of Service (QoS). Therefore, efficient management of idle models is a critical issue that has been largely neglected in existing research and requires urgent attention. To address this gap, this paper studies the problem of idle model management from the perspective of the trade-off between memory cost and loading delay under the QoS constraint. A novel layer-granularity model unloading method is proposed, which leverages the layered characteristics of the model. We formulate an online joint optimization problem to determine which layers to unload and when, and present a layer-granularity unloading strategy inspired by the ski rental problem to solve it. We implement a real system with layer-granularity unloading for LLMs on NVIDIA GPUs and validate the effectiveness of the proposed method. Experimental results show it effectively trades off memory cost and loading delay, improving overall performance by up to 39.6%.

The inference services of Large Language Models (LLMs) play a crucial role in many fields. Deploying LLMs at the network edge can effectively reduce response latency and enhance domain-specific knowledge. However, due to the dynamic and unpredictable nature of edge user requests and the limited resources of edge servers, improper request scheduling can lead to server load imbalance and increased inference latency. To address this challenge, we model edge LLM inference under dynamic workloads and constrained edge resources by fully considering mutual influences and trade-offs between inference performance, inference latency, and edge resource utilization. We propose a Workload Prediction and Dynamic Request Scheduling (WPDS) algorithm for edge computing environments. The WPDS algorithm first evaluates and prioritizes heterogeneous requests by extracting features and importance scores from user requests. A Transformer-based encoder is used to extract load characteristics of edge servers over different time periods to predict future GPU resource demands. Then, a soft actor-critic reinforcement learning model dynamically schedules requests to appropriate LLM instances, capturing the dynamic relationship between request processing and edge resource utilization from complex state spaces. We evaluate our algorithm in a real Kubernetes-based edge inference prototype system. Experimental results indicate that our approach reduces average inference time by approximately 16.6% compared to the best-performing heuristic baseline algorithm, while also achieving more balanced GPU utilization across edge servers.

Using Clustered Vehicular Federated Learning (CVFL) in vehicular networks can enhance model intelligence through distributed collaboration while preserving data privacy. CVFL groups clients with similar data distributions to reduce the impact of non-independent and identically distributed (non-iid) data on federated learning efficiency, thereby supporting realtime and dynamic traffic decision-making. However, in practical applications, the high mobility of vehicles and the intermittent connectivity of communication links make it challenging to flexibly determine the number of clusters and the vehicles within each cluster. To address these issues, we propose a Graph Neural Network(GNN)-based clustering scheme called GNN-CVFL. Our proposed scheme includes two modules: clustering and resource allocation. In the clustering module, we treat the clustering problem of vehicle clients as a node classification problem in GNN, using a GNN-based method to cluster clients accurately based on their data distribution. The proposed method can automatically determine the number of clusters and the vehicles within each cluster in real-time. Moreover, based on the clustering results, We use the Lagrangian relaxation method to dynamically allocate available bandwidth resources and CPU frequencies to minimize system latency, ensuring efficient and flexible service for all vehicles. Numerical results demonstrate the feasibility and efficiency of our proposed scheme.

The widespread deployment of cameras has led to an exponential increase in video data, creating vast opportunities for applications such as traffic management and crime surveillance. However, querying specific objects from large-scale video datasets presents challenges, including (1) processing massive and continuously growing data volumes, (2) supporting complex query requirements, and (3) ensuring low-latency execution. Existing video analysis methods struggle with either limited adaptability to unseen object classes or suffer from high query latency. In this paper, we present LOVO, a novel system designed to efficiently handle compLex Object queries in large-scale VideO datasets. Agnostic to user queries, LOVO performs one-time feature extraction using pre-trained visual encoders, generating compact visual embeddings for key frames to build an efficient index. These visual embeddings, along with associated bounding boxes, are organized in an inverted multi-index structure within a vector database, which supports queries for any objects. During the query phase, LOVO transforms object queries to query embeddings and conducts fast approximate nearest-neighbor searches on the visual embeddings. Finally, a cross-modal rerank is performed to refine the results by fusing visual features with detailed textual features. Evaluation on real-world video datasets demonstrates that LOVO outperforms existing methods in handling complex queries, with near-optimal query accuracy and up to 85x lower search latency, while significantly reducing index construction costs. This system redefines the state-of-theart object query approaches in video analysis, setting a new benchmark for complex object queries with a novel, scalable, and efficient approach that excels in dynamic environments.

Graph Neural Networks (GNNs) excel in many applications but struggle when trained with noisy labels, especially as noise can propagate through the graph structure. Despite recent progress in developing robust GNNs, few methods exploit the intrinsic properties of graph data to filter out noise. In this paper, we introduce ProCon, a novel framework that identifies mislabeled nodes by measuring label consistency among semantically similar peers, which are determined by feature similarity and graph adjacency. Mislabeled nodes typically exhibit lower consistency with these peers, a signal we measure using pseudo-labels derived from representational prototypes. A Gaussian Mixture Model is fitted to the consistency distribution to identify clean samples, which refine prototype quality in an iterative feedback loop. Experiments on multiple datasets demonstrate that ProCon significantly outperforms state-of-the-art methods, effectively mitigating label noise and enhancing GNN robustness.

Graph Neural Networks (GNNs) achieve strong performance in node classification tasks but exhibit substantial performance degradation under label noise. Despite recent advances in noise-robust learning, a principled approach that exploits the node-neighbor interdependencies inherent in graph data for label noise detection remains underexplored. To address this gap, we propose GD$^2$, a noise-aware \underline{G}raph learning framework that detects label noise by leveraging \underline{D}ual-view prediction \underline{D}iscrepancies. The framework contrasts the \textit{ego-view}, constructed from node-specific features, with the \textit{structure-view}, derived through the aggregation of neighboring representations. The resulting discrepancy captures disruptions in semantic coherence between individual node representations and the structural context, enabling effective identification of mislabeled nodes. Building upon this insight, we further introduce a view-specific training strategy that enhances noise detection by amplifying prediction divergence through differentiated view-specific supervision. Extensive experiments on multiple datasets and noise settings demonstrate that \name~achieves superior performance over state-of-the-art baselines.

Federated Learning with Cloud-Edge Collaboration (FL-CEC) has emerged as a cutting-edge paradigm in distributed learning. Efficient resource investment incentive mechanisms are crucial to encouraging clients in FL-CEC to contribute the necessary data and computational resources for training. However, existing studies are inadequate in meeting the incentive design requirements under multi-level information-sharing scenarios. Moreover, current works often rely on specific functional relationships between resource investment and global model accuracy. To bridge these gaps, this paper investigates the incentive problem for data and computational resource investment under multi-level information-sharing levels. We design a resource investment incentive mechanism based on a weighted potential game without depending on any specific functional relationship between data investment and model accuracy. Furthermore, we propose four algorithms to solve resource investment strategies for different levels of information sharing. The complexity and convergence rates of the proposed algorithms are thoroughly analyzed. Finally, we construct a simulation incentive platform on the Aliyun. Extensive evaluations demonstrate that the proposed scheme effectively enhances social welfare, and improves collaborative training accuracy and efficiency.

Machine unlearning enables pre-trained models to remove the effect of certain portions of training data. Previous machine unlearning schemes have mainly focused on unlearning a cluster of instances or all instances belonging to a specific class. These types of unlearning might have a significant impact on the model utility; and they may be inadequate for situations where we only need to unlearn features within instances, rather than the whole instances. Due to the different granularity, current unlearning methods can hardly achieve feature-level unlearning. To address the challenges of utility and granularity, we propose a refined granularity unlearning scheme referred to as “feature unlearning”. We first explore two distinct scenarios based on whether the annotation information about the features is given: feature unlearning with known annotations and feature unlearning without annotations. Regarding unlearning with known annotations, we propose an adversarial learning approach to automatically remove effects about features. For unlearning without annotations, we initially enable the output of one model's layer to identify different pattern features using model interpretability techniques. We proceed to filter features from instances based on these outputs with identifying ability. So that we can remove the feature impact based on filtered instances and the fine-tuning process. The effectiveness of our proposed approach is demonstrated through experiments involving diverse models on various datasets in different scenarios.

Privacy-preserving federated learning (PPFL) is a promising secure distributed learning paradigm, which enables collaborative training of a global machine learning model through sharing encrypted local models instead of sensitive raw data. PPFL, however, is vulnerable to model poisoning attacks. Most existing Byzantine-robust PPFL solutions typically employ two non-colluding servers to achieve secure model detection and aggregation by executing interactive security protocols, which incur considerable computation and communication overheads. To tackle this issue, we propose an efficient and secure federated learning (ESFL) technique to accelerate the detection of poisonous models in PPFL. First, to improve computational efficiency, we construct a lightweight non-interactive efficient decryption functional encryption (NED-FE) scheme to protect the data privacy of local models. Then, to ensure high communication performance, we elaborately design a non-interactive privacy-preserving robust aggregation strategy, which efficiently detects the blind poisonous models and aggregates benign models. Finally, we implement ESFL and conduct extensive theoretical analysis and experiments. The numerical results demonstrate that ESFL not only achieves the confidentiality and robustness design goals but also maintains high efficiency. Compared with the baseline, ESFL effectively reduces the aggregation latency by up to 88%.

As the adoption of electric vehicles continues to grow, the demand for extensive charging infrastructure in urban areas is concurrently rising. In response to the evolving charging infrastructure shortage, private charging piles have emerged as crucial supplementary energy sources, especially in areas lacking public charging infrastructure. The sharing of private charging piles, however, introduces several challenges. Notably, the variable availability time and extremely limited usage space of private charging piles pose scheduling complexities for charging pile owners. Furthermore, the completely peer-to-peer operation of private charging piles may lead to suboptimal solutions for fulfilling overall charging demand. To comprehensively address these challenges, we explore the potential for cooperation among geographically proximate charging piles. We introduce a novel online booking mechanism paired with specialized scheduling algorithms designed for scenarios involving both multiple private charging piles and single private charging piles. Our objective is to maximize the attained revenue of charging pile owners under fully dynamic conditions on both the supply and demand sides. Through meticulous theoretical proofs, we show that our mechanism achieves advantageous competitive ratios for both scenarios when compared to the offline optimal solutions. Numerous experiments, conducted with real charging sessions, consistently demonstrate that the proposed mechanism achieves the highest revenue, providing substantial evidence for its superior performance.

Federated learning (FL) has gained significant attention as it facilitates collaborative machine learning among multiple clients without centralizing their data on a server. FL ensures the privacy of participating clients by locally storing their data, which creates new challenges in fairness. Traditional debiasing methods assume centralized access to sensitive information, rendering them impractical for the FL setting. Additionally, FL is more susceptible to fairness issues than centralized machine learning due to the diverse client data sources that may be associated with group information. Therefore, training a fair model in FL without access to client local data is important and challenging. This article presents AFed, a straightforward, yet effective framework for promoting group fairness in FL. The core idea is to circumvent restricted data access by learning the global data distribution. This article proposes two approaches: AFed-G, which uses a conditional generator trained on the server side, and AFed-GAN, which improves upon AFed-G by training a conditional GAN on the client side. We augment the client data with the generated samples to help remove bias. Our theoretical analysis justifies the proposed methods, and empirical results on multiple real-world datasets demonstrate a substantial improvement in AFed over several baselines.

Machine unlearning is an emerging technology that has come to attract widespread attention. A number of factors, including regulations and laws, privacy, and usability concerns, have resulted in this need to allow a trained model to forget some of its training data. Existing studies of machine unlearning mainly focus on unlearning requests that forget a cluster of instances or all instances from one class. While these approaches are effective in removing instances, they do not scale to scenarios where partial targets within an instance need to be forgotten. For example, one would like to only unlearn a person from all instances that simultaneously contain the person and other targets. Directly migrating instance-level unlearning to target-level unlearning will reduce the performance of the model after the unlearning process, or fail to erase information completely. To address these concerns, we have proposed a more effective and efficient unlearning scheme that focuses on removing partial targets from the model, which we name "target unlearning." Specifically, we first construct an essential graph data structure to describe the relationships between all important parameters that are selected based on the model explanation method. After that, we simultaneously filter parameters that are also important for the remaining targets and use the pruning-based unlearning method, which is a simple but effective solution to remove information about the target that needs to be forgotten. Experiments with different training models on various datasets demonstrate the effectiveness of the proposed approach.

Containers have emerged as a pivotal tool for service deployment in edge computing. Before running the container, an image composed of several layers must exist locally. Recent strategies have utilized layer-sharing in images to reduce deployment delays. However, existing research only focuses on a single aspect of container orchestration, like container placement, neglecting the joint optimization of the entire orchestration process. To fill in such gaps, this article introduces an online strategy that considers layer-aware container orchestration, encompassing request scheduling, container placement, and resource provision. The goal is to reduce costs, adapt to evolving user demands, and adhere to system constraints. We present an online optimization problem that accounts for various real-world factors in orchestration, including container and server expenses. An online algorithm is proposed, integrating a regularization-based approach and stepwise rounding to address this optimization problem efficiently. The regularization approach separates time-dependent container placement and server wake-up costs, requiring only current information and past decisions. The stepwise rounding process generates feasible solutions that meet system constraints, reducing computational costs. Additionally, a competitive ratio proof is provided for the proposed algorithm. Extensive evaluations demonstrate that our approach achieves about 20% performance enhancement compared to baseline algorithms.

Extending serverless computing to the edge has emerged as a promising approach to support service, but startup containerized serverless functions lead to the cold-start delay. Recent research has introduced container caching methods to alleviate the cold-start delay, including cache as the entire container or the Zygote container. However, container caching incurs memory costs. The system must ensure fast function startup and low memory cost of edge servers, which has been overlooked in the literature. This paper aims to jointly optimize startup delay and memory cost. We formulate an online joint optimization problem that encompasses container scheduling decisions, including invocation distribution, container startup, and container caching. To solve the problem, we propose an online algorithm with a competitive ratio and low computational complexity. The proposed algorithm decomposes the problem into two subproblems and solves them sequentially. Each container is assigned a randomized strategy, and these container-level decisions are merged to constitute overall container caching decisions. Furthermore, a greedy-based subroutine is designed to solve the subproblem associated with invocation distribution and container startup decisions. Experiments on the real-world dataset indicate that the algorithm can reduce average startup delay by up to 23% and lower memory costs by up to 15%.

Federated learning (FL) is a technique that enables clients to collaboratively train a model by sharing local models instead of raw private data. However, existing reconstruction attacks can recover the sensitive training samples from the shared models. Additionally, the emerging poisoning attacks also pose severe threats to the security of FL. However, most existing Byzantine-robust privacy-preserving federated learning solutions either reduce the accuracy of aggregated models or introduce significant computation and communication overheads. In this paper, we propose a novelBlockchain-basedSecure andRobustFederatedLearning (BSR-FL) framework to mitigate reconstruction attacks and poisoning attacks. BSR-FL avoids accuracy loss while ensuring efficient privacy protection and Byzantine robustness. Specifically, we first construct a lightweight non-interactive functional encryption (NIFE) scheme to protect the privacy of local models while maintaining high communication performance. Then, we propose a privacy-preserving defensive aggregation strategy based on NIFE, which can resist encrypted poisoning attacks without compromising model privacy through secure cosine similarity and incentive-based Byzantine-tolerance aggregation. Finally, we utilize the blockchain system to assist in facilitating the processes of federated learning and the implementation of protocols. Extensive theoretical analysis and experiments demonstrate that our new BSR-FL has enhanced privacy security, robustness, and high efficiency.

Model stealing attacks involve creating copies of machine learning models that have similar functionalities to the original model without proper authorization. Such attacks raise significant concerns about the intellectual property of the machine learning models. Nonetheless, current defense mechanisms against such attacks tend to exhibit certain drawbacks, notably in terms of utility, and robustness. For example, watermarking-based defenses require victim models to be retrained for embedding watermarks, which can potentially impact the main task performance. Moreover, other defenses, especially fingerprinting-based methods, often rely on specific samples like adversarial examples to verify ownership of the target model. These approaches might prove less robust against adaptive attacks, such as model stealing with adversarial training. It remains unclear whether normal examples, as opposed to adversarial ones, can effectively reflect the characteristics of stolen models. To tackle these challenges, we propose a novel method that leverages a neural network as a decoder to inverse the suspicious model’s outputs. Inspired by model inversion attacks, we argue that this decoding process will unveil hidden patterns inherent in the original outputs of the suspicious model. Drawing from these decoding outcomes, we calculate specific metrics to determine the legitimacy of the suspicious models. We validate the efficacy of our defense technique against diverse model stealing attacks, specifically within the domain of classification tasks based on deep neural networks.

In edge computing, applications can be scheduled in the granularity of inter-dependent tasks to proximate edge servers to achieve high performance. Before execution, the edge server must initialize the corresponding runtime environment, named task startup. However, existing studies on dependent task scheduling severely ignore bandwidth constraints during task startups, which is impractical and incurs a long startup latency. To fill in this gap, we first model the task startup process with bandwidth constraints on edge servers. Then, we formulate the dependent task scheduling problem with startup latency in heterogeneous edge computing. To efficiently generate schedules and satisfy the real-time requirements in edge computing, a novel low-complexity list scheduling algorithm integrated with cloud clone, Startup-aware Dependent Task Scheduling (SDTS), is proposed. Constrained by bandwidth and computation resources, SDTS first coordinates task startup, dependent data transmission, and task execution to optimize each task’s finish time. Then, a cloud clone for each task is deployed to utilize scalable resources and initialized runtime environments. Furthermore, task scheduling refinement is designed to release the bandwidth and computation resources consumed by redundant tasks and improve the schedule. Extensive simulations based on real-world datasets show that SDTS substantially reduces 30%-60% makespan compared with existing baselines.

Containers have gained popularity in Edge Computing (EC) networks due to their lightweight and flexible deployment advantage. In resource-constrained EC environments, overbooking container resources can substantially improve resource utilization. However, existing work overlooks the complex interplay between resource provisioning and container scheduling, which may result in performance degradation or inefficient resource utilization due to highly dynamic resource heterogeneity in EC. To address this issue, this paper presents a novel joint Resource Overbooking and Container Scheduling (ROCS) algorithm. Our approach accounts for resource heterogeneity and the geographical distribution of edge nodes, and we formulate the ROCS problem to consolidate various costs and revenues into a single profit metric for service providers. To enhance resource utilization and maximize the profit of the service providers, we develop an efficient algorithm that operates within a hybrid action space scheme by leveraging soft actor-critic reinforcement learning. Furthermore, we introduce a risk assessment mechanism to mitigate overbooking risks. Large-scale simulations with real-world data traces demonstrate the efficacy of our proposed ROCS algorithm, validating its advantage of improving resource utilization within EC networks.

In edge-assisted vehicular networks, containers are very suitable for deploying applications and providing services due to their lightweight and rapid deployment. To provide high-quality services, many existing studies show that the containers need to be migrated to follow the vehicles’ trajectory. However, it has been conspicuously neglected by existing work that making full use of the complex layer-sharing information of containers among multiple users can significantly reduce migration latency. In this paper, we propose a novel online container migration algorithm to reduce the overall task latency. Specifically: 1) we model the multi-user layer-aware online container migration problem in edge-assisted vehicular networks, comprehensively considering the initialization latency, computation latency, and migration latency. 2) A feature extraction method based on attention and long short-term memory is proposed to fully extract the multi-user layer-sharing information. Then, a policy gradient-based reinforcement learning algorithm is proposed to make the online migration decisions. 3) The experiments are conducted with real-world data traces. Compared with the baselines, our algorithms effectively reduce the total latency by 8% to 30% on average.

In Mobile Edge Computing (MEC), Internet of Things (IoT) devices offload computationally-intensive tasks to edge nodes, where they are executed within containers, reducing the reliance on centralized cloud infrastructure. Cluster software upgrades are essential to maintain the efficient and secure operation of edge clusters. However, traditional cloud cluster upgrade strategies are ill-suited for edge clusters due to their geographically distributed nature and resource limitations. Therefore, it is crucial to properly schedule containers during edge cluster upgrades to minimize the impact on running tasks. This article proposes a latency-aware container scheduling algorithm for efficient edge cluster upgrading. Specifically: 1) We formulate the online container scheduling problem for edge cluster upgrade to minimize the total task latency. 2) We propose a policy gradient-based reinforcement learning algorithm that addresses this problem by considering the characteristics of MEC, including heterogeneous resources, image distribution, and low-latency requirements. Subsequently, a location feature extraction method based on self-attention is designed to fully extract and utilize edge node distribution. 3) Experiments based on simulated and real-world data traces demonstrate that our algorithm reduces total task latency by approximately 30% compared to baseline algorithms.

Edge Computing (EC) with cloud-like Quality of Service (QoS) can find its wide applications in various resource-constrained smart cities where the resource requirements can be different during peak and off-peak periods. During off-peak periods, there are often many resources that have been requested but not used, which can be reused to obtain higher profit. However, to the best of our knowledge, there is no effective pricing model or overbooking mechanism in EC. To fill in this gap, a novel pricing model for dynamic resource overbooking is proposed in this paper, specifically: 1) To meet the needs of different users in EC, methods of on-demand, daily, auction, and the new spot billing are designed, in which resources can be overbooked. 2) An auction approach with pricing rule and winner determination rule is designed for auction billing, which is proved to guarantee individual rationality, computational efficiency, and truthfulness. 3) To make more use of the auction approach to utilize idle resources, a dynamic resource overbooking mechanism is introduced, including a cancellation policy and a resource prediction method. The mechanism is validated with real-world data-trace. Experimental results show that the dynamic resource overbooking mechanism maximizes the profit of edge nodes with a high QoS Satisfaction ratio of on-demand and daily billing.

With the ubiquity of social media, privacy leakage has become a urgent problemfor social media managers. Studying how the privacy information diffuses through social media has attracted much attention. As a prerequisite, modeling privacy information diffusion is important research. Current approaches for modeling information diffusion are not available for privacy information since they did not consider the propagation features of privacy information in social media. Thispaper discusses the problem of modeling privacy information in social media and its challenges. We first analyse the information diffusion paths in the basic parameters of complex network and the high-order structures. We find that the privacy information is different in propagation features and the size of star structures. Second, a new information diffusion model is illustrated to simulate the diffusion process of information in social media by considering the following three parameters: 1) the probability of users receiving this message, 2) the probability that users have a tendency to forward this message and 3) the interest the users hold for this message. Finally, a block mechanism is designed to congest the diffusion of privacy information in social media.

Social media has become a ubiquitous tool for spreading news, messages, and generally allowing for communication between individuals. Hence, studying how our privacy information might also spread across social media is important research. To date, many studies have used information diffusion models to simulate and then examine how information flows through social networks. But these models are theoretical, and newsworthy information may not behave in the same way as privacy information, raising the question: Are the observed phenomena indicative of real privacy propagation? To explore this question, we assembled a dataset from Twitter comprising propagated information flows for both private and normal information. We then built a graph convolutional network to trace and classify differences in the way each type of information spreads throughout the platform. The results reveal that there are indeed key differences in the diffusion processes of the two types of information. More importantly, we design privacy-preserving methods to reduce the privacy propagation in social media.

In Mobile Edge Computing (MEC), latency-sensitive mobile applications comprising dependent tasks can be scheduled to edge or cloud servers to reduce latency and execution costs. However, existing algorithms based on deadline distribution can hardly satisfy tight application deadlines in heterogeneous MEC due to lacking a global view of the future impacts on descendant tasks. To fill in this gap, we formulate the deadline-constrained cost optimization problem for dependent task scheduling in MEC and propose a low-complexity scheduling algorithm that considers a single task's future impacts in two stages. Specifically: (1) In the edge scheduling stage, each task is scheduled according to its successors’ latest start times instead of its sub-deadline to alleviate the lateness of its successors. An edge-only schedule plan is generated by scheduling tasks only on edge servers to save execution costs. (2) In the cloud offloading stage, in order to utilize the powerful cloud resources to satisfy the deadline, the edge-only schedule plan missing the deadline is efficiently modified by properly offloading multiple successive tasks to the cloud. Simulation results show the substantial advantage of the proposed algorithm over baselines in both online and offline scenarios.

In this article, the problem of tracking control for a class of nonlinear time-varying full state constrained systems is investigated. By constructing the time-varying asymmetric barrier Lyapunov function (BLF) and combining it with the backstepping algorithm, the intelligent controller and adaptive law are developed. Neural networks (NNs) are utilized to approximate the uncertain function. It is well known that in the past research of nonlinear systems with state constraints, the state constraint boundary is either a constant or a time-varying function. In this article, the constraint boundaries both related to state and time are investigated, which makes the design of control algorithm more complex and difficult. Furthermore, by employing the Lyapunov stability analysis, it is proven that all signals in the closed-loop system are bounded and the time-varying full state constraints are not violated. In the end, the effectiveness of the control algorithm is verified by numerical simulation.

Containers are becoming a popular way of running applications in edge computing. Before running the application, the edge node must download the application’s container image consisting of multiple layers. However, given the limited bandwidth in edge computing, the container startup latency due to long image download time seriously affects the real-time performance. In this article, we jointly determine the container assignment and the layer download sequence to reduce the total startup latency. We formulate the Container Assignment and Layer Sequencing (CALS) problem and prove its NP-hardness. A Layer-Aware Scheduling Algorithm (LASA) is proposed, fully considering layer sharing among images. First, layers shared by the same set of images are grouped to reduce CALS’s problem scale without affecting the optimal result. Second, considering both layer sharing and existing layer size on edge nodes, a layer-aware algorithm is designed to assign containers to appropriate edge nodes. Finally, to determine the layer download sequence on each edge node, an approximation algorithm is proposed. We further analyze the approximation ratio of LASA in the case of identical edge nodes with sufficient capacity. Extensive experiments based on real-world data show the effectiveness of LASA, which reduces the total startup latency by 40% to 60%.

Sharing private parking spaces during their idle time periods has shown great potential for addressing urban traffic congestion and illegitimate parking problems in smart cities. In this article, aiming to address the online parking-space sharing issue while ensuring the privacy of customer parking destination locations, we propose a novel destination privacy-preserving online parking sharing (DPOPS) incentive scheme. In particular, the online parking-space sharing problem is formalized as a social welfare maximization problem in a two-sided market, where parking-space providers (PSPs) and customers are regarded as sellers and buyers. Then, novel threshold value-based rules are designed to determine winners, payments, and reimbursement. Finally, winners are matched by solving a mixed-integer nonlinear programming problem, aiming to minimize the distance between customer’s destination and allocated parking space. In addition, the location privacy of the customers’ destinations is protected by the Laplace mechanism. We prove that DPOPS achieves several economically effective properties and approximate differential privacy. We analyze the upper bound of the efficiency loss of our scheme. Extensive evaluation results demonstrate that our scheme can not only achieve good performance regarding social welfare, PSP satisfaction ratio, privacy preservation, and computation overhead but also leads to shorter travel distances for customers comparing to the baseline scheme.Note to Practitioners—In this article, we address the online parking-space sharing issue with considering the parking-space providers (PSPs) and customers’ individual utility while preserving the location privacy of customers’ destinations. Most of the previous works focused on designing a centralized mechanism for allocating parking spaces without considering the protection of the customers’ location privacy. In particular, we propose an online parking-space sharing scheme called DPOPS, including a novel threshold value-based winner determination rule and a parking-space allocation rule. The proposed scheme DPOPS allows the PSPs and customers submit their bids and asks according to their own willingness and is able to improve the utilization of private parking spaces during their idle time periods. Moreover, the location privacy of customers’ destinations is protected by the Laplace mechanism. The experiments demonstrate that the proposed approach outperforms the exponential-based scheme in terms of PSP satisfaction ratio and the travel distance for parking-space customer. The proposed scheme is helpful in managing the vacant parking space in a competitive market and can be readily implemented in the real-world online parking-space sharing systems.

In recent years, edge computing has attracted significant attention because it can effectively support many delay-sensitive applications. Despite such a salient feature, edge computing also faces many challenges, especially for efficiency and security, because edge devices are usually heterogeneous and may be untrustworthy. To address these challenges, we propose a unified framework to provide efficiency and confidentiality by coded distributed computing. Within the proposed framework, we use matrix multiplication, a fundamental building block of many distributed machine learning algorithms, as the representative computation task. To minimize resource consumption while achieving information-theoretic security, we investigate two highly-coupled problems, (1) task allocation that assigns data blocks in a computing task to edge devices and (2) linear code design that generates data blocks by encoding the original data with random information. Specifically, we first theoretically analyze the necessary conditions for the optimal solution. Based on the theoretical analysis, we develop an efficienttask allocationalgorithm to obtain a set of selected edge devices and the number of coded vectors allocated to them. Using the task allocation results, we then designsecure coded computingschemes, for two cases, (1) with redundant computation and (2) without redundant computation, all of which satisfy the availability and security conditions. Moreover, we also theoretically analyze the optimization of the proposed scheme. Finally, we conduct extensive simulation experiments to demonstrate the effectiveness of the proposed schemes.

The rapid and wide adoption of microgrids (MGs) and the increasing popularity of electric vehicles (EVs) have created a unique opportunity for the integration of these technologies. In this article, we address the issue of demand response of EVs during MG outages by leveraging Vehicle-to-Grid (V2G) technology. Particularly, we investigate an auction trading market that allows EVs with surplus energy to act as sellers, and EVs that want to be charged to act as buyers. A novel distributed double auction scheme is proposed to allow each buyer EV to submit multiple bids to seller EVs in different parking lots. Nonetheless, the locations of buyer EVs could be inferred by an adversary through analyzing the valuations, posing serious privacy and security risks. In this regard, a valuation-based attack scheme is investigated to validate the potential privacy risk. To defend against such an attack, we present a location privacy-preserving double auction scheme, in which the MicroGrid Central Controller (MGCC) acts as the auctioneer, solving the social welfare maximization problem of matching buyers to sellers, and the cloud is used to conduct calculations for the auctioneer, protecting the privacy of participants via homomorphic encryption. Theoretical analysis is conducted to validate our auction scheme in satisfying the designed economic and privacy properties (e.g., strategy-proofness and$k$-anonymity). The experimental results show that our auction scheme can not only mitigate the demand response problem in MGs, but also provides good performance with respect to social welfare, satisfaction ratio, computational and communication overhead, and privacy leakage.

Hyperledger Fabric is a popular permissioned Blockchain framework for a consortium of organizations to develop Blockchain based applications and transact within the consortium. Hyperledger Fabric introduces a fine-grained access control mechanism called the private data collection (PDC), which allows private data to be shared by only a subset of participants. In this paper, we analyze PDC and show three classes of use cases in which misuse of Hyperledger Fabric features may endanger implemented Hyperledger Fabric systems. We present two groups of potential attacks including fake PDC results injection and PDC leakage against the misuse of the policy based consensus protocol. We use prototype systems to validate the discovered attacks. We also collected 6392 Hyprledger Fabric projects on GitHub and built a tool to statically analyse them. We find that 86.51% of the PDC related projects are potentially vulnerable to the fake PDC results injection attacks, and 91.67% have PDC leakage issues. We design new features for the Hyper-ledger Fabric framework to mitigate the attacks and show that the new features have minor impact on the system performance.

IoT security and privacy has raised grave concerns. Efforts have been made to design tools to identify and understand vulnerabilities of IoT systems. Most of the existing protocol security analysis techniques rely on a well understanding of the underlying communication protocols. In this article, we systematically present the first manual reverse engineering framework for discovering communication protocols of embedded Linux-based IoT systems. We have successfully applied our framework to reverse engineer a number of IoT systems. As an example, we present a detailed use of the framework reverse engineering the WeMo smart plug communication protocol by extracting the firmware from the flash, performing static and dynamic analysis of the firmware, and analyzing network traffic. The discovered protocol exposes severe design flaws that allow attackers to control or deny the service of victim plugs. Our manual reverse engineering framework is generic and can be applied to both read-only and writable embedded Linux filesystems.

The vigorously rising of social media brings a new opportunity for information diffusion in online social networks. However, the existing models of information diffusion only consider the single information, such as rumor. What's more, most of intervention frameworks are modeled under the ideal circumstances without reality constraints. In this article, we propose a novel model of competitive information coupling diffusion to describe the complex process of information diffusion in online social networks. Especially, in order to intervene the process of competitive information coupling diffusion, we introduce three intervention strategies and propose an intervention framework. More importantly, we take the dynamic constraints into consideration such as the budget of intervention and current state of the system, and further propose the constrained intervention model. To reduce the system loss, we establish an optimal control problem with constraints to achieve the optimal allocation of intervention strategies over time and minimize the total loss. We theoretically prove the existence and uniqueness of the optimal solution of the problem, and derive the optimal control solution. Through the experiments, we verify the effectiveness of the model and analyze the efficiency of different intervention strategies about competitive information coupling diffusion with or without constraints, respectively. The results show that the collaborative intervention strategies can effectively impact the process of diffusion and get the minimum system loss. This article provides high realistic significance to the commercial marketing in online social networks.

This article investigates an adaptive finite-time neural control for a class of strict feedback nonlinear systems with multiple objective constraints. In order to solve the main challenges brought by the state constraints and the emergence of finite-time stability, a new barrier Lyapunov function is proposed for the first time, not only can it solve multiobjective constraints effectively but also ensure that all states are always within the constraint intervals. Second, by combining the command filter method and backstepping control, the adaptive controller is designed. What is more, the proposed controller has the ability to avoid the "singularity" problem. The compensation mechanism is introduced to neutralize the error appearing in the filtering process. Furthermore, the neural network is used to approximate the unknown function in the design process. It is shown that the proposed finite-time neural adaptive control scheme achieves a good tracking effect. And each objective function does not violate the constraint bound. Finally, a simulation example of electromechanical dynamic system is given to prove the effectiveness of the proposed finite-time control strategy.

Mobile social networks (MSNs) provide real-time information services to individuals in social communities through mobile devices. However, due to their high openness and autonomy, MSNs have been suffering from rampant rumors, fraudulent activities, and other types of misuses. To mitigate such threats, it is urgent to control the spread of fraud information. The research challenge is: how to design control strategies to efficiently utilize limited resources and meanwhile minimize individuals' losses caused by fraud information? To this end, we model the fraud information control issue as an optimal control problem, in which the control resources consumption for implementing control strategies and the losses of individuals are jointly taken as a constraint called total cost, and the minimum total cost becomes the objective function. Based on the optimal control theory, we devise the optimal dynamic allocation of control strategies. Besides, a dynamics model for fraud information diffusion is established by considering the uncertain mental state of individuals, we investigate the trend of fraud information diffusion and the stability of the dynamics model. Our simulation study shows that the proposed optimal control strategies can effectively inhibit the diffusion of fraud information while incurring the smallest total cost. Compared with other control strategies, the control effect of the proposed optimal control strategies is about 10% higher.

Distantly supervised relation extraction has been widely applied in knowledge base construction due to its less requirement of human efforts.However, the automatically established training datasets in distant supervision contain low-quality instances with noisy words and overlapped relations, introducing great challenges to the accurate extraction of relations.To address this problem, we propose a novel Regularized Attentive Capsule Network (RA-CapNet) to better identify highly overlapped relations in each informal sentence.To discover multiple relation features in an instance, we embed multi-head attention into the capsule network as the low-level capsules, where the subtraction of two entities acts as a new form of relation query to select salient features regardless of their positions.To further discriminate overlapped relation features, we devise disagreement regularization to explicitly encourage the diversity among both multiple attention heads and low-level capsules.Extensive experiments conducted on widely used datasets show that our model achieves significant improvements in relation extraction.

Software-Defined Networking (SDN) is an innovational network architecture which gives network administrators the ability to directly control the whole network by programming on a centralized controller. Due to network complexity, networks are unlikely to be bug-free. The ability to verify data plane properties will make network management easier for network administrators in SDN. In this paper, we present a novel atomic predicates based data plane properties verification method for SDN using Spark which is a big data processing framework. First, we verify packet reachability which is a fundamental data plane property. Then, we verify other data plane properties such as loop-freedom and nonexistence of black holes. In addition, the proposed method can detect a security threat existing in SDN called firewall bypass threat with packet reachability verification. By adopting atomic predicates, we achieve less computational and storage overhead. We implement the methods and study the performance. The results of experiments show that we can efficiently and accurately detect loops, black holes and firewall bypass threats.

Driver fatigue is a leading factor in road accidents that can cause severe fatalities. Existing fatigue detection works focus on vision and electroencephalography (EEG) based means of detection. However, vision-based approaches suffer from view-blocking or vision distortion problems and EEG-based systems are intrusive, and the drivers have to use/wear the devices with inconvenience or additional costs. In our work, we propose a novel Wi-Fi signals based fatigue detection approach, called WiFind to overcome the drawbacks as associated with the current works. WiFind is simple and (wearable) device-free. It can detect the fatigue symptoms in the vehicle without relying on any visual image or video. By applying self-adaptive method, it can recognize the body features of drivers in multiple modes. It applies Hilbert-Huang transform (HHT) based pattern extract method results in accuracy increase in motion detection mode. WiFind can be easily deployed in a commodity Wi-Fi infrastructure, and we have evaluated its performance in real driving environments. The experimental results have shown that WiFind can achieve the recognition accuracy of 89.6 percent in a single driver scenario.

In this paper, to address the issue of demand response in the smart grid with island MicroGrids (MGs), we introduce an effective and secure auction market that allows electric vehicles (EVs) having surplus energy to act as sellers, and the EVs having insufficient energy in the island MGs to act as buyers. There are two primary challenges in designing an effective auction market in the smart grid. First, the auction market scheme shall be online, allowing buyers and sellers to enter the market at any time, and satisfy several critical economic properties (individual rationality, incentive compatibility, and so on.). Second, the sensitive information of participants shall be protected in the auction process. To address these challenges, we present a novel privacy-preserving online double auction scheme based on differential privacy. In our auction market, the MicroGrid Center Controller (MGCC) acts as the auctioneer, aiming at solving the social welfare maximization problem to match buyers and sellers. The principle of differential privacy is leveraged to protect the privacy of EVs' sensitive bidding information. Via theoretical analysis, we demonstrate that our designed auction scheme satisfies both economic and privacy-preserving properties, including individual rationality, incentive compatibility, weak budget balance, and ε-differential privacy. We conduct an extensive performance evaluation to measure the effectiveness of our proposed scheme. Our experimental results show that the proposed auction scheme can not only ensure the privacy of participants but also effectively facilitates demand response in the smart grid, with respect to social welfare, satisfaction ratio, social efficiency, and computational overhead.

In recent years, edge computing has attracted increasing attention for its capability of facilitating delay-sensitive applications. In the implementation of edge computing, however, data confidentiality has been raised as a major concern because edge devices may be untrustable. In this paper, we propose a design of secure and efficient edge computing by linear coding. In general, linear coding can achieve data confidentiality by adding random information to the original data before they are distributed to edge devices. To this end, it is important to carefully design code such that the user can successfully decode the final result while achieving security requirements. Meanwhile, task allocation, which selects a set of edge devices to participate in a computation task, affects not only the total resource consumption, including computation, storage, and communication, but also coding design. In this paper, we study task allocation and coding design, two highly-coupled problems in secure coded edge computing, in a unified framework. In particular, we take matrix multiplication, a fundamental building block of many distributed machine learning algorithms, as the representative computation task, and study optimal task allocation and coding design to minimize resource consumption while achieving information-theoretic security.

With an unparalleled number of Machine-to-Machine (M2M) devices being deployed to support a variety of smart-world systems powered by Internet of Things (IoT) technologies, the heterogeneity, uncertainty, and complexity of M2M communications have increased enormously. Thus, how to conduct network resource planning (NRP) has become a challenging issue. In this paper, we propose a novel time series framework (TSF) to model and forecast timescale network traffic dynamics in M2M communications that is capable of providing useful guidance for effective NRP. Specifically, our TSF utilizes the statistical techniques INGARCH(p,q) (integer valued generalized autoregressive conditional heteroskedasticity) and βARMA(p,q) (beta autoregressive moving average) to accurately capture both the internal and external impact factors of the asynchronous and synchronous M2M traffic dynamics over a large time scale, and produces forecasts for multiple upcoming time points by leveraging conditional maximum-likelihood estimators (CMLE). Through a combination of theoretical analysis and extensive simulation, we have validated the modeling and forecasting efficacy of TSF. Our experimental results demonstrate that TSF achieves superior performance with respect to goodness-of-fit and prediction accuracy.

In this paper, we address the issue of the energy trading in the scenario of electric vehicles (EVs) charging in the smart grid. The EVs energy trading problems have attracted growing attention with the popularity of EVs. As the traditional first-reserve-first-serve scheme in the energy trading market impairs the benefits of both buyers and seller, we consider an auction scheme, called progressive second price (PSP), which has been proved to be an efficient way to conduct resource allocation in the trading market. Compared with other auction schemes, the PSP scheme can achieve both incentive compatibility and Nash equilibrium, which are important properties for the market. Nonetheless, the PSP auction scheme is not designed for online auction and it cannot guarantee that the seller can provide an enough number of charging piles to satisfy the demand of winners. To tackle these issues, in this paper we propose a novel online continuous PSP-based auction scheme, which is capable of not only achieving the property of online energy trading but also guaranteeing that the number of winners is limited to be no more than the number of charging piles. Further, we prove that our auction scheme achieves incentive compatibility and Nash equilibrium. The extensive experimental results demonstrate that our auction scheme achieves good performance with respect to social welfare, the seller satisfaction ratio, the buyer satisfaction ratio, as well as computation overhead.

Time-sync comments (TSCs) reveal a new way of extracting the online video tags. However, such TSCs have lots of noises due to users’ diverse comments, introducing great challenges for accurate and fast video tag extractions. In this article, we propose an unsupervised video tag extraction algorithm named Semantic Weight-Inverse Document Frequency (SW-IDF). Specifically, we first generate corresponding semantic association graph (SAG) using semantic similarities and timestamps of the TSCs. Second, we propose two graph cluster algorithms, i.e., dialogue-based algorithm and topic center-based algorithm, to deal with the videos with different density of comments. Third, we design a graph iteration algorithm to assign the weight to each comment based on the degrees of the clustered subgraphs, which can differentiate the meaningful comments from the noises. Finally, we gain the weight of each word by combining Semantic Weight (SW) and Inverse Document Frequency (IDF). In this way, the video tags are extracted automatically in an unsupervised way. Extensive experiments have shown that SW-IDF (dialogue-based algorithm) achieves 0.4210 F1-score and 0.4932 MAP (Mean Average Precision) in high-density comments, 0.4267 F1-score and 0.3623 MAP in low-density comments; while SW-IDF (topic center-based algorithm) achieves 0.4444 F1-score and 0.5122 MAP in high-density comments, 0.4207 F1-score and 0.3522 MAP in low-density comments. It has a better performance than the state-of-the-art unsupervised algorithms in both F1-score and MAP.

Today's data center operators deploy network policies in both physical (e.g., middleboxes, switches) and virtualized (e.g., virtual machines on general purpose servers) network function boxes (NFBs), which reside in different points of the network, to exploit their efficiency and agility respectively. Nevertheless, such heterogeneity has resulted in a great number of independent network nodes that can dynamically generate and implement inconsistent and conflicting network policies, making correct policy implementation a difficult problem to solve. Since these nodes have varying capabilities, services running atop are also faced with profound performance unpredictability. In this paper, we propose a Heterogeneous netwOrk Policy Enforcement (HOPE) scheme to overcome these challenges. HOPE guarantees that network functions (NFs) that implement a policy chain are optimally placed onto heterogeneous NFBs such that the network cost of the policy is minimized. We first experimentally demonstrate that the processing capacity of NFBs is the dominant performance factor. This observation is then used to formulate the Heterogeneous Network Policy Placement problem, which is shown to be NP-Hard. To solve the problem efficiently, an online algorithm is proposed. Our experimental results demonstrate that HOPE achieves the same optimality as Branch-and-bound optimization but is 3 orders of magnitude more efficient.

Fog Computing (FC) is a flexible architecture to support distributed domain-specific applications with cloud-like quality of service. However, current FC still lacks the mobility support mechanism when facing many mobile users with diversified application quality requirements. Such mobility support mechanism can be critical such as in the industrial internet where human, products, and devices are moveable. To fill in such gaps, in this paper we propose novel container migration algorithms and architecture to support mobility tasks with various application requirements. Our algorithms are realized from three aspects: 1) We consider mobile application tasks can be hosted in a container of a corresponding fog node that can be migrated, taking the communication delay and computational power consumption into consideration; 2) We further model such container migration strategy as multiple dimensional Markov Decision Process (MDP) spaces. To effectively reduce the large MDP spaces, efficient deep reinforcement learning algorithms are devised to achieve fast decision-making and 3) We implement the model and algorithms as a container migration prototype system and test its feasibility and performance. Extensive experiments show that our strategy outperforms the existing baseline approaches 2.9, 48.5 and 58.4 percent on average in terms of delay, power consumption, and migration cost, respectively.

In this paper, we investigate the threat of drones equipped with recording devices, which capture videos of individuals typing on their mobile devices and extract the touch input such as passcodes from the videos. Deploying this kind of attack from the air is significantly challenging because of camera vibration and movement caused by drone dynamics and the wind. Our algorithms can estimate the motion trajectory of the touching finger, and derive the typing pattern and then touch inputs. Our experiments show that we can achieve a high success rate against both tablets and smartphones with a DJI Phantom drone from a long distance. A 2.5" NEUTRON mini drone flies outside a window and also achieves a high success rate against tablets behind the window. To the best of our knowledge, we are the first to systematically study drones revealing user inputs on mobile devices and use the finger motion trajectory alone to recover passcodes typed on mobile devices.

Android represents an ever-increasing share of the worldwide smart device market. The platform's ubiquity and open nature make Android a prime target for malicious actors. Unfortunately, device fragmentation among manufacturers makes maintaining cyber security difficult, invoking the need for third party security software. We present a framework for detecting and countering deceptive user interface attacks on the Android platform via inspection and analysis of inter-process communication transactions in the operating system. We evaluate our proof of concept implementation on a known class of malware that exploits the Android display system, allowing a malicious application to control the screen and mimic any application launched by the user. We achieve 100% detection rate of this malicious behavior with no false alarms.

In this paper, we propose a secure lightweight and thing-centered IoT communication system based on MQTT, SecT, in which a device/thing authenticates users. Compared with a server-centered IoT system in which a cloud server authenticates users, a thing-centered system preserves user privacy since the cloud server is primarily a relay between things and users and does not store or see user data in plaintext. The contributions of this work are three-fold. First, we explicitly identify critical functionalities in bootstrapping a thing and design secure pairing and binding strategies. Second, we design a strategy of end-to-end encrypted communication between users and things for the sake of user privacy and even the server cannot see the communication content in plaintext. Third, we design a strong authentication system that can defeat known device scanning attack, brute force attack and device spoofing attack against IoT. We implemented a prototype of SecT on a $10 Raspberry Pi Zero W and performed extensive experiments to validate its performance. The experiment results show that SecT is both cost-effective and practical. Although we design SecT for the smart home application, it can be easily extended to other IoT application domains.

Received Signal Strength (RSS) is considered to be a promising measurement for indoor positioning. Many RSS range-based localization methods have been proposed due to the convenience and low cost of RSS measurements. However, a fundamental problem has not been answered, that is, how accurate are these methods? We think a key reason leading to this situation is the inappropriate assumption on RSS range models and measurement errors, which results in oversimplified analysis on those methods. In this paper, we use a more general range model and recognize the Generalized Least Square (GLS) method as an optimal estimator whose estimation error equals to the Cramer-Rao lower bound (CRLB). Through mathematical, techniques, we derive the analytic expression of the localization error for the GLS method, which reveals the key factors that affect the localization accuracy. Further studies on the minimal localization error disclose the proportional relationship between the localization accuracy and the above key factors.

No abstract available.

In this paper, we present theory and a design of the online double auction for the trading of energy within a smart grid with microgrids (MGs). The online double auction has the potential to enable the allocation of surplus electricity to the MGs that need electricity with the highest gain in the real-time market. Nonetheless, two critical issues remain challenging when designing an effective online double auction scheme in such a system. First, as the agents are allowed to arrive and depart at any time, the auctioneer needs to make decisions without the information of further bids and asks. Second, the economic properties of strategy-proof, individual rational, and (weak) budget balance should be satisfied. To address these issues and enable multiunit electricity trading among local MGs, in this paper, we propose a strategy-proof online double auction (SODA) scheme, in which the surplus and insufficient MGs in the system are treated as sellers and buyers, respectively, and the MG center controller is capable of maximizing the social welfare of MGs by appropriately matching buyers and sellers. Via theoretical analysis, we prove that SODA can achieve the properties of individual rationality, (weak) budget balance, strategy-proofness, and computational efficiency. Experiments also show that SODA is capable of reducing the energy purchasing cost of the MGs and shifting the peak-load, while achieving great performance with respect to social welfare, seller/buyer satisfaction ratio, social efficiency, and computation overhead.

Visual (V) surveillance systems are extensively deployed and becoming the largest source of big data. On the other hand, electronic (E) data also plays an important role in surveillance and its amount increases explosively with the ubiquity of mobile devices. One of the major problems in surveillance is to determine human objects' identities among different surveillance scenes. Traditional way of processing big V and E datasets separately does not serve the purpose well because V data and E data are imperfect alone for information gathering and retrieval. Matching human objects in the two datasets can merge the good of the two for efficient large-scale surveillance. Yet such matching across two heterogeneous big datasets is challenging. In this paper, we propose an efficient set of parallel algorithms, called EV-Matching, to bridge big E and V data. We match E and V data based on their spatiotemporal correlation. The EV-Matching algorithms are implemented on Apache Spark to further accelerate the whole procedure. We conduct extensive experiments on a large synthetic dataset under different settings. Results demonstrate the feasibility and efficiency of our proposed algorithms.

In this research, we conduct a comprehensive measurement study on the predictability of human mobility with respect to demographic differences. We leverage an extensive WLAN dataset collected on a large university campus. Specifically, our dataset includes over 41 million WLAN entries gathered from over 5,000 students (with demographic information) during a four-month period in 2015. We observed surprising patterns on large increases of long-term mobility entropy by age, and the impact of academic majors on students long-term mobility entropy. The distribution of long-term entropy follows a bimodal distribution, which is different from previous studies. We also find that the predictability of students' short-term (daily or weekly) mobility varies on different days of the week and with student gender. Because of the large campus size, our results can mimic people's mobility patterns in metropolitan areas. We also anticipate that our results will provide insight that guides academic administrators' decisions regarding facilities planning, emergency management, etc. on campus.

In this paper, we address the issue of data trading in big data markets. Data trading problems have attracted increased attention recently, as the economic benefits and potential of big data trading are substantial and varied. However, how to effectively trade data between the data owners (sellers) and data collectors/users (buyers) is far from settled, and requires careful design. Auction mechanisms have been applied across many fields, and have significant potential to facilitate data transactions in a fair, truthful, and secure way. Nonetheless, a truthful auction must ensure the property of incentive compatibility, meaning that the bidders can obtain highest utility if and only if they submit their bids and asks truthfully. Furthermore, a truthful and fair auction should also protect the optimal auction results from being manipulated by false-name bidding attacks, where users (participants) utilize multiple identities or accounts to influence the auction results. To tackle these issues, we propose a Multi-round False-name Proof Auction (MFPA) scheme, which enables data trading among data owners (sellers) and data collectors (buyers). We prove that our MFPA scheme achieves the properties of incentive compatibility, false-name bidding proofness, and computational efficiency. The experimental results demonstrate that MFPA achieves good performance in terms of social surplus, satisfaction ratio, and computation overhead.

In this paper, we address the problem of demand response of electrical vehicles (EVs) during microgrid outages in the smart grid through the application of Vehicle-to-Grid (V2G) technology. Particularly, we present a novel privacy-preserving double auction scheme. In our auction market, the MicroGrid Center Controller (MGCC) acts as the auctioneer, solving the social welfare maximization problem of matching buyers to sellers, and the cloud is used as a broker between bidders and the auctioneer, protecting privacy through homomorphic encryption. Theoretical analysis is conducted to validate our auction scheme in satisfying the intended economic and privacy properties (e.g., strategy-proofness and k-anonymity). We also evaluate the performance of the proposed scheme to confirm its practical effectiveness.

In this paper, we study vision-based localization for robots. We anticipate that numerous mobile robots will serve or interact with humans in indoor scenarios such as healthcare, entertainment, and public service. Such scenarios entail accurate and scalable indoor visual robot localization, the subject of this work. Most existing vision-based localization approaches suffer from low localization accuracy and scalability issues due to visual environmental features' limited effective range and detection accuracy. In light of infrastructural cameras' wide indoor deployment, this paper proposes BRIDGELOC, a novel vision-based indoor robot localization system that integrates both robots' and infrastructural cameras. BRIDGELOC develops three key technologies: robot and infrastructural camera view bridging, rotation symmetric visual tag design, and continuous localization based on robots' visual and motion sensing. Our system bridges robots' and infrastructural cameras' views to accurately localize robots. We use visual tags with rotation symmetric patterns to extend scalability greatly. Our continuous localization enables robot localization in areas without visual tags and infrastructural camera coverage. We implement our system and build a prototype robot using commercial off-the-shelf hardware. Our real-world evaluation validates BRIDGELOC's promise for indoor robot localization.

Microgrids (MGs) have attracted growing attention due to self-sufficiency and self-healing properties. Nonetheless, the intermittent nature and uncertainty of distributed energy resources and load demands remain challenging issues in balancing demands and managing energy resources in MGs. Existing research efforts mainly focus on developing techniques to enable interactions between local MGs and the utility grid, which leads to high line power losses and operation costs. In this paper, we present the Sto2Auc framework to address the issue of stochastic optimal bidding problem for a system with MGs. First, the optimal bidding problem is formulated as a two-stage stochastic programming process, which aims to minimize the system operation cost and obtain optimal energy capacity of MGs by the MG center controller (MGCC). Uncertainties arise from both energy supply and demand, which are considered in the stochastic model, and random parameters representing those uncertainties are captured by using the Monte Carlo method. Second, to enable optimal electricity trading between the insufficient and surplus MGs, we propose a distributed double auction (DDA)-based scheme, which is proven to converge to the optimal social welfare of the system with MGs, and achieves the economical properties of being strategy-proof, individually rational, and (weak) budget balanced. Extensive experiments on an MG system composed of IEEE-33 buses demonstrate the effectiveness of proposed scheme. The experimental results show that Sto2Auc framework is capable of reducing the operational cost of MG systems, while the implemented DDA scheme achieves good performance with respect to social welfare, demand insufficiency, and MGCC profit.

Fog/edge computing has been proposed to be integrated with Internet of Things (IoT) to enable computing services devices deployed at network edge, aiming to improve the user's experience and resilience of the services in case of failures. With the advantage of distributed architecture and close to end-users, fog/edge computing can provide faster response and greater quality of service for IoT applications. Thus, fog/edge computing-based IoT becomes future infrastructure on IoT development. To develop fog/edge computing-based IoT infrastructure, the architecture, enabling techniques, and issues related to IoT should be investigated first, and then the integration of fog/edge computing and IoT should be explored. To this end, this paper conducts a comprehensive overview of IoT with respect to system architecture, enabling technologies, security and privacy issues, and present the integration of fog/edge computing and IoT, and applications. Particularly, this paper first explores the relationship between cyber-physical systems and IoT, both of which play important roles in realizing an intelligent cyber-physical world. Then, existing architectures, enabling technologies, and security and privacy issues in IoT are presented to enhance the understanding of the state of the art IoT development. To investigate the fog/edge computing-based IoT, this paper also investigate the relationship between IoT and fog/edge computing, and discuss issues in fog/edge computing-based IoT. Finally, several applications, including the smart grid, smart transportation, and smart cities, are presented to demonstrate how fog/edge computing-based IoT to be implemented in real-world applications.

A typical cyber-physical system (CPS) refers to a system that features a tight integration of computation, networking, and physical elements for interactions between cyber and physical spaces. The Internet of Things (IoT) is considered to be the networking infrastructure of CPS. Applications of CPS cover numerous smart-world research areas that our daily life depends upon, including smart transportation, smart electrical power grid, smart cities, smart medical systems, smart manufacturing systems, and others. While major research on improving the efficiency and reliability of CPS by using advanced information and communication technologies has been conducted, the risks of cyberspace security and privacy breaches in CPS need to be seriously investigated before a massive deployment of CPS technologies can or should be realized.

State estimation plays a critical role in self-detection and control of the smart grid. Data integrity attacks (also known as false data injection attacks) have shown significant potential in undermining the state estimation of power systems, and corresponding countermeasures have drawn increased scholarly interest. Nonetheless, leveraging optimal phasor measurement unit (PMU) placement to defend against these attacks, while simultaneously ensuring the system observability, has yet to be addressed without incurring significant overhead. In this paper, we enhance the least-effort attack model, which computes the minimum number of sensors that must be compromised to manipulate a given number of states, and develop an effective greedy algorithm for optimal PMU placement to defend against data integrity attacks. Regarding the least-effort attack model, we prove the existence of smallest set of sensors to compromise and propose a feasible reduced row echelon form (RRE)-based method to efficiently compute the optimal attack vector. Based on the IEEE standard systems, we validate the efficiency of the RRE algorithm, in terms of a low computation complexity. Regarding the defense strategy, we propose an effective PMU-based greedy algorithm, which cannot only defend against data integrity attacks, but also ensure the system observability with low overhead. The experimental results obtained based on various IEEE standard systems show the effectiveness of the proposed defense scheme against data integrity attacks.

Policies play an important role in network configuration and therefore in offering secure and high performance services especially over multi-tenant Cloud Data Center (DC) environments. At the same time, elastic resource provisioning through virtualization often disregards policy requirements, assuming that the policy implementation is handled by the underlying network infrastructure. This can result in policy violations, performance degradation and security vulnerabilities. In this paper, we define PLAN, a PoLicy-Aware and Network-aware VM management scheme to jointly consider DC communication cost reduction through Virtual Machine (VM) migration while meeting network policy requirements. We show that the problem is NP-hard and derive an efficient approximate algorithm to reduce communication cost while adhering to policy constraints. Through extensive evaluation, we show that PLAN can reduce topology-wide communication cost by 38 percent over diverse aggregate traffic and configuration policies.

Massive visual traffic data have become available recently. Though it opens the realm of intelligent traffic analysis, processing the data in a timely manner is difficult yet critical to time sensitive decisions, which are typical to traffic related management. In this paper, we study time-bounded aggregation analytics on large visual traffic data including traffic images and videos. We first find that current MapReduce framework can not work well due to two challenges: first, significant dual diversities exist on data distributions and processing time; second, apriori knowledge on these distributions and time costs are not always available. However, we also observe spatial and temporal locality on data values and processing time. Based on the examination, we design Traffic At-a-Glance (TaG), an augmented MapReduce framework for time-bounded traffic analytics jobs. Particularly, we propose a novel sampling algorithm that exploits traffic data localities and stratifies samples based on data distributions and processing time. It runs in an iterative, adaptive manner without apriori knowledge. Moreover, we propose a heuristic scheduling algorithm with considerations of batch processing overhead. Further, we refine the load balancing mechanism based on data processing time locality to respect job time bounds. In addition, we extend TaG to well handle traffic videos by sampling video data based on motion information encoded in the videos. We implement TaG on Hadoop and conduct extensive experiments on a large visual traffic dataset. The evaluations on different data sizes show TaG is able to achieve high accuracy within time bounds.

To protect users from numerous password inference attacks, we invent a novel context aware privacy enhancing keyboard (PEK) for Android touch-based devices. Usually PEK would show a QWERTY keyboard when users input text like an email or a message. Nevertheless, whenever users enter a password in the input box on his or her touch-enabled device, a keyboard will be shown to them with the positions of the characters shuffled at random. PEK has been released on the Google Play since 2014. However, the number of installations has not lived up to our expectation. For the purpose of usable security and privacy, we designed a two-stage usability test and performed two rounds of iterative usability testing in 2016 and 2017 summer with continuous improvements of PEK. The observations from the usability testing are educational: (1) convenience plays a critical role when users select an input method; (2) people think those attacks that PEK prevents are remote from them.

In this paper, we address the issue of designing an effective distributed real-time pricing scheme in the smart grid and investigating its security resilience when the data integrity attack is in place. Different from existing research efforts, in this paper we develop a distributed real-time pricing scheme, which can maximize the welfare of all participants and improve the resilience to system failures, as well as consider both renewable and traditional power resources. By leveraging the distributed approach, we leverage the gradient projection mechanism to solve the distributed real-time pricing problem in participants' smart meters to improve the resilience to system failures. We also investigate the vulnerabilities of the distributed real-time pricing scheme by considering one typical data integrity attack, which can inject false data into communication interfaces. Via a combination of both theoretical analysis and performance evaluation, we demonstrate that the proposed distributed scheme can effectively guide the participants to achieve individual welfare maximization. Our findings also show that data integrity attacks can disrupt the distributed real-time pricing, posing a damage to the welfare of participants.

Many mobile robots are expected to work for or interact with humans indoors in applications such as guided shopping, policing, and senior care. Mobile robots' sensors alone are insufficient in order to realize these applications, infrastructural support is needed. Existing support for mobile robots requires heavy or expensive infrastructures with limited scalability or deployment of unsightly lines or magnetic strips. This paper presents S-Mirror, a novel approach that "reflects" various ambient signals towards mobile robots, greatly extending their sensing abilities. S-Mirror forms a network of S-Mirror nodes that mainly reflect visual signals (as well as electronic and acoustic signals) to assist mobile robots. To illustrate the advantages of S-Mirror, we develop a localization approach for mobile robots that integrates S-Mirror and robots' on-board motion sensors. We implement S-Mirror and a mobile robot prototype on commercial off-the-shelf hardware. Our real-world experimental validation shows that S-Mirror achieves accurate timely localization with low network bandwidth consumption as well as robustness and scalability to many mobile robots.

In recent years, Internet of Things (IoT) has attracted great attention from academia, industry, and government. IoT is considered to be a networking infrastructure that can connect enormous physical objects and has great potential to extend mankind's capabilities in monitoring, analyzing, and controlling the physical space using cyber technologies. Extensive studies on IoT have been carried out and many IoT prototype systems have been built. However, most of these systems are usually suitable for domain-specific applications and operate in a local region. They are really “Nets of Things (NoT)” as they miss mechanisms for large-scale interconnection. As such, how to build a globally interconnected IoT is still an open problem. In this article, by reviewing the development of the Internet, we derive a pathway that may lead to successful development and deployment of a global IoT. We propose and examine a novel IoT architecture, namely, WInternet, which aims at interconnecting small-scale domain-specific NoTs into a globally connected IoT.

Camera sensor networks (CSNs) are gradually being used in a tele-intensive care unit (tele-ICU), providing useful patient information to remote intensivists. Intensivists wish to focus on different regions of interest (RoIs) containing their patients. We consider a situation where preinstalled camera sensors' locations remain static and they can change the fields of view only by rotating orientations, while the RoIs are dynamically changed in location and size because of changes in the number of patients and care unit configuration. Therefore, an important issue is how to enhance the coverage of these RoIs by controlling the camera sensors' orientations. Previous studies on coverage optimization either focus on single area coverage or point(s) coverage. However, ignoring those multiple RoIs or simply treating them as points can cause unwanted coverage, resulting in performance degradation. In this paper, we investigate a novel multiple RoI coverage (MRC) problem in a CSN-based tele-ICU, aiming to maximize the lowest coverage ratio of all RoIs. The MRC problem is nondeterministic polynomial-time hard, so we propose an efficient heuristic algorithm MRC-Priority to solve it. We have implemented a CSN testbed to evaluate the performance of our proposed algorithm. Experimental results show that our proposed algorithm can improve the lowest coverage ratio up to 200% as compared with existing solutions.

Policies play an important role in network configuration and, therefore, in offering secure and high performance services, especially over multi-tenant Cloud Data Center (DC) environments. At the same time, elastic resource provisioning through virtualization often disregards policy requirements, assuming that the policy implementation is handled by the underlying network infrastructure. In this paper, we define PLAN, a Policy-Aware virtual machine management scheme to jointly consider DC communication cost reduction through Virtual Machine (VM) migration while meeting network policy requirements.

In an intelligence transportation system (ITS), to increase traffic efficiency, a number of dynamic route guidance schemes have been designed to assist drivers in determining the optimal route for their travels. In order to determine optimal routes, it is critical to effectively predict the traffic condition of roads along the guided routes based on real-time traffic information to mitigate traffic congestion and improve traffic efficiency. In this paper, we propose a Dynamic En-route Decision real-time Route guidance (DEDR) scheme to effectively mitigate road congestion caused by the sudden increase of vehicles and reduce travel time. Particularly, DEDR considers real-time traffic information generation and transmission. Based on the shared traffic information, DEDR introduces Trust Probability to predict traffic conditions and dynamically en-route determine alternative optimal routes. In addition, DEDR considers multiple metrics to comprehensively assess traffic conditions and drivers can determine optimal route with individual preference of these metrics during travel. DEDR also considers effects of external factors (e.g., Bad weather, incidents, etc.) on traffic conditions. Through a combination of extensive theoretical analysis and simulation experiments, our data shows that DEDR can greatly increase the efficiency of an ITS in terms of great time efficiency and balancing efficiency in comparison with existing schemes.

Human tracking in video has many practical applications such as visual guided navigation, assisted living, etc. In such applications, it is necessary to accurately track multiple humans across multiple cameras, subject to real-time constraints. Despite recent advances in visual tracking research, the tracking systems purely relying on visual information fail to meet the accuracy and real-time requirements at the same time. In this paper, we present a novel accurate and real-time human tracking system called VM-Tracking. The system aggregates the information of motion (M) sensor on human, and integrates it with visual (V) data based on physical locations. The system has two key features, i.e. location-based VM fusion and appearance-free tracking, which significantly distinguish itself from other existing human tracking systems. We have implemented the VM-Tracking system and conducted comprehensive experiments on challenging scenarios.

In Cyber-Physical Networked Systems (CPNS), the adversary can inject false measurements into the controller through compromised sensor nodes, which not only threaten the security of the system, but also consume network resources. To deal with this issue, a number of en-route filtering schemes have been designed for wireless sensor networks. However, these schemes either lack resilience to the number of compromised nodes or depend on the statically configured routes and node localization, which are not suitable for CPNS. In this paper, we propose a Polynomial-based Compromise-Resilient En-route Filtering scheme (PCREF), which can filter false injected data effectively and achieve a high resilience to the number of compromised nodes without relying on static routes and node localization. PCREF adopts polynomials instead of Message Authentication Codes (MACs) for endorsing measurement reports to achieve resilience to attacks. Each node stores two types of polynomials: authentication polynomial and check polynomial, derived from the primitive polynomial, and used for endorsing and verifying the measurement reports. Through extensive theoretical analysis and experiments, our data shows that PCREF achieves better filtering capacity and resilience to the large number of compromised nodes in comparison to the existing schemes.

In this paper, we introduce a novel computer vision based attack that automatically discloses inputs on a touch-enabled device while the attacker cannot see any text or popup in a video of the victim tapping on the touch screen. We carefully analyze the shadow formation around the fingertip, apply the optical flow, deformable part-based model (DPM), k-means clustering and other computer vision techniques to automatically locate the touched points. Planar homography is then applied to map the estimated touched points to a reference image of software keyboard keys. Recognition of passwords is extremely challenging given that no language model can be applied to correct estimated touched keys. Our threat model is that a webcam, smartphone or Google Glass is used for stealthy attack in scenarios such as conferences and similar gathering places. We address both cases of tapping with one finger and tapping with multiple fingers and two hands. Extensive experiments were performed to demonstrate the impact of this attack. The per-character (or per-digit) success rate is over 97% while the success rate of recognizing 4-character passcodes is more than 90%. Our work is the first to automatically and blindly recognize random passwords (or passcodes) typed on the touch screen of mobile devices with a very high success rate.

Summary form only given. Internet of Things (IoT) is a networking infrastructure for cyber-physical systems. With IoT, physical objects should be seamlessly integrated into an Internet-like system so that the physical objects and cyber-agents can interact each other in order to achieve mission-critical objectives. Given its tremendous application potential, IoT has become popular in recent years, attracting great attentions from both academic research and industrial development. In this talk, we will first focus on fundamental issues related to IoT. We address principles that should guide research and development of IoT. We will then present several approaches that may lead to implementation of IoT and analyze their advantages and disadvantages. We will show an implementation of IoT called “WInternet” and demonstrate its application. Finally, we will discuss critical issues that must be addressed in order to fully realize the objectives and potentials of IoT.

It is critical for a power system to estimate its operation state based on meter measurements in the field and the configuration of power grid networks. Recent studies show that the adversary can bypass the existing bad data detection schemes, posing dangerous threats to the operation of power grid systems. Nevertheless, two critical issues remain open: 1) how can an adversary choose the meters to compromise to cause the most significant deviation of the system state estimation, and 2) how can a system operator defend against such attacks? To address these issues, we first study the problem of finding the optimal attack strategy--i.e., a data-injection attacking strategy that selects a set of meters to manipulate so as to cause the maximum damage. We formalize the problem and develop efficient algorithms to identify the optimal meter set. We implement and test our attack strategy on various IEEE standard bus systems, and demonstrate its superiority over a baseline strategy of random selections. To defend against false data-injection attacks, we propose a protection-based defense and a detection-based defense, respectively. For the protection-based defense, we identify and protect critical sensors and make the system more resilient to attacks. For the detection-based defense, we develop the spatial-based and temporal-based detection schemes to accurately identify data-injection attacks.

In many wireless localization applications, we rotate a directional antenna to derive the angle of arrival (AOA) of wireless signals transmitted from a target mobile device. The AOA corresponds to the direction in which the maximum received signal strength (RSS) is sensed. However, an unanswered question is how to make sure the directional antenna picks up packets producing the maximum RSS while rotating. We propose a set of novel RSS sampling theory to answer this question. We recognize the process that a directional antenna measures RSS of wireless packets while rotating as the process that the radiation pattern of the directional antenna is sampled. Therefore, if RSS samples can reconstruct the antenna's radiation pattern, the direction corresponding to the peak of the radiation pattern is the AOA of the target. We derive mathematical models to determine the RSS sampling rate given the target's packet transmission rate. Our RSS sampling theory is applicable to various types of directional antennas. To validate our RSS sampling theory, we developed BotLoc, which is a programmable and self-coordinated robot armed with a wireless sniffer. We conducted extensive real-world experiments and the experimental results match the theory very well. A video of BotLoc is at www.youtube.com/watch?v=WtUt0IqhXRU&feature=youtu.be.

Human localization is an enabling technology for many mobile applications. As more and more people carry mobile phones with them, we can now localize a person by localizing his mobile phone. However, it is observed that presence of human bodies introduces heavy interference to mobile phone signals. This has been one of the major causes of inaccurate wireless localization for humans. In this paper, we propose using video cameras to help estimate human body's interference on mobile device's signals. We combine human orientation detection and human/phone/AP relative position inference estimation to better measure how a human blocks or reflects wireless signals. We have also developed a signal distortion compensation model. Based on these technologies, we have implemented a human localization system called EV-Human. Real world experiments show that our EV-system can accurately and robustly localize humans.

Traffic monitoring can efficiently promote urban planning and encourage better use of public transport. Efficient traffic information collection is one important part of traffic monitoring systems. Based on a technique using wireless sensor networks (WSNs), this paper provides a flexible framework for regional traffic information collection in accordance with user request. This framework serves as a basis for future research in designing and implementing traffic monitoring applications. A two-layer network architecture is established for traffic information acquisition in the context of a WSN environment. In addition, a user-customizable data-centric routing scheme is proposed for traffic information delivery, in which multiple routing-related information is considered for decision-making to meet different user requirements. Simulations have shown good performance of the proposed routing scheme compared with other traditional routing schemes on a real-world urban traffic network.

The ability to track and locate physical entities is a fundamental requirement for Cyber-Physical Systems (CPSs), especially in an ad-hoc wireless environment. In Heterogeneous Wireless Networks (HWNs), hybrid localization schemes are needed due to the coexistence of both accurate and coarse measurement mechanisms. However, current localization schemes cannot fully satisfy HWNs' accuracy requirements. Therefore, we propose a universal measurement metric called Direct Proportion Distance (DPD) that can leverage most existing measurement mechanisms such as TOA/TDOA, RSS, AOA, Link Diagnosis (LD) and Signal Coverage Detection (SCD). We also prove that DPD is directly proportional to the physical distance between two wireless nodes. Based on this metric, we present three new localization algorithms and compare them with classical methods. The experiments verify that our method performs better than previous localization algorithms when both accurate and coarse measurements are fully utilized.

In Cyber-Physical Networked Systems (CPNS), attackers could inject false measurements to the controller through compromised sensor nodes, which not only threaten the security of the system, but also consumes network resources. To deal with this issue, a number of en-route filtering schemes have been designed for wireless sensor networks. However, these schemes either lack resilience to the number of compromised nodes or depend on the statically configured routes and node localization, which are not suitable for CPNS. In this paper, we propose a Polynomial-based Compromised-Resilient En-route Filtering scheme (PCREF), which can filter false injected data effectively and achieve a high resilience to the number of compromised nodes without relying on static routes and node localization. Particularly, PCREF adopts polynomials instead of MACs (message authentication codes) for endorsing measurement reports to achieve the resilience to attacks. Each node stores two types of polynomials: authentication polynomial and check polynomial derived from the primitive polynomial, and used for endorsing and verifying the measurement reports. Via extensive theoretical analysis and simulation experiments, our data show that PCREF achieves better filtering capacity and resilience to the large number of compromised nodes in comparison to the existing schemes.

In a large-scale wireless sensor traffic network, collecting and processing of the global real-time traffic information are often unreliable. Making real-time navigation decision becomes an arduous task. To address this issue, an efficient real-time vehicle navigation algorithm is proposed, in which multiple local traffic information are considered to make navigation decision in a quick and accurate way. At the same time, a general distance metric is defined for the processing of both exact and fuzzy data. In addition, the algorithm can provide various navigation decisions according to the choice of different attributes to meet the diverse navigation requirements of drivers. Simulation results show the suitability and efficiency of the proposed algorithm.

In a large-scale wireless sensor traffic network, collecting and processing of the global real-time traffic information are often unreliable. Making real-time navigation decision becomes an arduous task. To address this issue, an efficient wireless-sensor-network-based real-time vehicle navigation algorithm is proposed, in which multiple local traffic information is considered to make a navigation decision in a quick and accurate way. At the same time, a general distance metric is defined for the processing of both exact and fuzzy data. In addition, the algorithm can provide various navigation decisions according to the choice of different attributes to meet the diverse navigation requirements of drivers. Simulation results show the suitability and efficiency of the proposed algorithm.

"The Marauder's Map,” a magical map in J.K. Rowling's fantasy series Harry Potter and the Prisoner of Azkaban [CHECK END OF SENTENCE], can be used as a surveillance tool to show all moving objects within the boundary of "Hogwarts School of Witchcraft and Wizardry” at a spell. In this paper, we introduce a similar forensic surveillance tool for wireless networks. Our system, the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location for instant usage without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range ($r_{\rm c}$) is relatively small compared to their sensing range ($r_{\rm s}$), and prove their optimality. In this study, we discover an interesting phenomenon—pattern mutation. To the best of our knowledge, this is the first time that mutation in pattern deployments has been discovered. This phenomenon, which contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern deployment, significantly furthers our understanding of optimal patterns in WSNs.

The operating state estimation of power system is a critical process for providing a best-fit state estimation based on the meter measurements in the field and the configuration of power-grid network. To deal with the bad meter measurements caused by various faults in state estimation, power system researchers have developed numerous detection schemes in the past. Liu et al. recently proposed a new stealthy false data injection attack, which can bypass the existing bad data detection schemes and arbitrarily manipulate the states of power system, posing dangerous threats to the control of a power system. Nevertheless, their results did not show the detailed information of meters to be compromised. In this paper, we tend to tackle this issue and develop mechanisms to efficiently compute the optimal set of meter measurements given a number of state variables to be manipulated in a power-grid network. We formalize the problem of finding the optimal set of meter measurements as a known NP-hard problem and propose a heuristic approach to derive the near-optimal set of meter measurements efficiently. We implement our proposed scheme on the IEEE 9-bus, 14-bus, 30-bus, 118-bus and 300-bus systems and our data shows its efficiency and effectiveness.

This paper addresses the problem of target counting based on the Monte Carlo simulation. We rely on an Accept-Reject process to guide the placement of virtual targets in a virtual sensor field, which has exactly the same sensor layout as the real one. The objective of this construction is to generate a virtual target energy landscape whose shape is close enough to an energy landscape estimated from the real sensor readings. Based on the number of virtual targets placed on the virtual field and the total virtual and real target energy volumes, the number of real targets can be estimated. We consider both single-epoch and multi-epoch sensor readings and our theoretical analysis indicates that by exploiting the information from multiple epochs, our approach yields a target count that approximately converges to the true target count when the number of epochs is large enough. Extensive comparison based simulation study has been performed and the results verify the effectiveness of our target counting algorithms.

The network address translation technique (NAT) is widely used in wireless routers. It is a low cost solution to IPv4 address space limitations. However, cyber criminals may abuse NAT and hide behind wireless routers to use mobile devices and conduct crimes. To identify a suspect mobile device, we should be able to map the suspect public traffic on the Internet to the private traffic behind the wireless router in WLAN. In this paper, we propose a suite of novel packet size based traffic marking techniques to identify suspect mobiles in encrypted wireless networks as well as open wireless networks. To cope with severe packet loss during wireless sniffing, we proposed to use error correcting codes to improve detection rate. We conducted extensive analysis and experiments to demonstrate the efficiency and accuracy of our schemes, which achieve high detection rate and very small false positive rate. The proposed strategies can be used for law enforcement for combatting cyber crimes in wireless network crime scene investigations.

Location-based services (LBS) have become an immensely valuable source of real-time information and guidance. Nonetheless, the potential abuse of users' sensitive personal data by an LBS server is evolving into a serious concern. Privacy concerns in LBS exist on two fronts: location privacy and query privacy. In this paper we investigate issues related to query privacy. In particular, we aim to prevent the LBS server from correlating the service attribute, e.g., bar/tavern, in the query to the user's real-world identity. Location obfuscation using spatial generalization aided by anonymization of LBS queries is a conventional means to this end. However, effectiveness of this technique would abate in continuous LBS scenarios, i.e., where users are moving and recurrently requesting for LBS. In this paper, we present a novel query-perturbation-based scheme that protects query privacy in continuous LBS even when user-identities are revealed. Unlike most exiting works, our scheme does not require the presence of a trusted third party.

Active worms pose major security threats to the Internet. This is due to the ability of active worms to propagate in an automated fashion as they continuously compromise computers on the Internet. Active worms evolve during their propagation, and thus, pose great challenges to defend against them. In this paper, we investigate a new class of active worms, referred to as Camouflaging Worm (C-Worm in short). The C-Worm is different from traditional worms because of its ability to intelligently manipulate its scan traffic volume over time. Thereby, the C-Worm camouflages its propagation from existing worm detection systems based on analyzing the propagation traffic generated by worms. We analyze characteristics of the C-Worm and conduct a comprehensive comparison between its traffic and nonworm traffic (background traffic). We observe that these two types of traffic are barely distinguishable in the time domain. However, their distinction is clear in the frequency domain, due to the recurring manipulative nature of the C-Worm. Motivated by our observations, we design a novel spectrum-based scheme to detect the C-Worm. Our scheme uses the Power Spectral Density (PSD) distribution of the scan traffic volume and its corresponding Spectral Flatness Measure (SFM) to distinguish the C-Worm traffic from background traffic. Using a comprehensive set of detection metrics and real-world traces as background traffic, we conduct extensive performance evaluations on our proposed spectrum-based detection scheme. The performance data clearly demonstrates that our scheme can effectively detect the C-Worm propagation. Furthermore, we show the generality of our spectrum-based scheme in effectively detecting not only the C-Worm, but traditional worms as well.

We address issues related to the protection of private information in Online Analytical Processing (OLAP) systems, where a major privacy concern is the adversarial inference of private information from OLAP query answers. Most previous work on privacy-preserving OLAP focuses on a single aggregate function and/or addresses only exact disclosure, which eliminates from consideration an important class of privacy breaches where partial information, but not exact values, of private data is disclosed (i.e., partial disclosure). We address privacy protection against both exact and partial disclosure in OLAP systems with mixed aggregate functions. In particular, we propose an information-theoretic inference control approach that supports a combination of common aggregate functions (e.g., COUNT, SUM, MIN, MAX, and MEDIAN) and guarantees the level of privacy disclosure not to exceed thresholds predetermined by the data owners. We demonstrate that our approach is efficient and can be implemented in existing OLAP systems with little modification. It also satisfies the simulatable auditing model and leaks no private information through query rejections. Through performance analysis, we show that compared with previous approaches, our approach provides more effective privacy protection while maintaining a higher level of query-answer availability.

In this paper, we propose and analyze a new GPS positioning algorithm. Our algorithm uses the direct linearization technique to reduce the computation time overhead. We invoke the general least squares method in order to achieve optimality in the situation when the trilateration system of equations becomes over-determined. We systematically evaluate our new algorithms and show that they indeed take much less computation time than the traditional GPS method while maintaining reasonable accuracy.

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range (rc) is relatively small compared with their sensing range (rs), and prove their optimality among regular patterns. In this study, we discover a surprising and interesting phenomenon-pattern mutation. This phenomenon contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern evolution and that pattern evolution is continuous. For example, we find mutation happens among the patterns for full-coverage and 3-connectivity when rc/rs= 1.0459, among the patterns for full-coverage and 4-connectivity when rc/rs= 1.3903, and among the patterns for full-coverage and 5-connectivity when rc/rs= 1.0406. To the best of our knowledge, this is the first time that mutation in pattern evolution has been discovered. Also, our work further completes the exploration of optimal patterns in WSNs.

In real-time systems, utilization-based schedulability test is a common approach to determine whether or not tasks can be admitted without violating deadline requirements. The test is extremely simple, since it only needs to compare the utilization of the tasks with a predetermined bound. As such, utilization-based schedulability tests are suitable for online use. The challenge is how to derive a reasonable utilization bound for a given system. Most existing results are obtained on a case-by-case basis because of their analytical complexity. In this paper, we develop a flexible and unified representation framework of real-time systems (i.e., tasks and schedulers) based on network calculus techniques. Our representation framework, together with the proposed bound derivation method, leads to a general bound result, which is applicable to a large family of real-time systems.

Abstract—Internet Threat Monitoring (ITM) systems are a widely deployed facility to detect, analyze, and characterize dangerous Internet threats such as worms and distributed denial-of-service (DDoS) attacks. Nonetheless, an ITM system can also become the target of attacks. In this paper, we address localization attacks against ITM systems in which an attacker impairs the effectiveness of an ITM system by identifying the locations of ITM monitors. We propose an information-theoretic framework that models localization attacks as communication channels. Based on this model, we generalize all existing attacks as “temporal attacks”, derive closed formulae of their performance, and propose an effective attack detection approach. The information-theoretic model also inspires a new attack called a spatial attack and motivates the corresponding detection approach. We show simulation results that support our theoretic findings.

This paper presents a theoretical representation of a stochastic traffic bound (σ',ρ') that consists of two items, the burstiness bound σ' and the bound of long-term average rate ρ'. The novelty of the suggested representation is that the burstiness bound and the bound of long-term average rate are separately connected to the fractal dimension D that is the measure of the local self-similarity together with the small-scale factor r and the Hurst parameter H that is the measure of the long-range dependence (LRD) together with the large-scale factor a of traffic. More precisely, we obtain σ' = r2D-5σ and ρ' = a-Hρ, where σ is the conventional bound of burstiness and ρ the conventional bound of long-term average rate, respectively. Thus, the present bound (σ',ρ') takes the conventional bound, say (σ,ρ), as a special case when r = 1 and a = 1. Hence, the proposed representation provides us with a flexible way to tighten a traffic bound. Since we study the stochastically bounded modeling of traffic by taking into account the parameters in stochastic modeling, namely, D, H, r, and a, as well as the parameters in the deterministic modeling of traffic, i.e., σ and ρ, a new outlook regarding the stochastically bounded modeling of traffic is revealed. In addition, we open a problem to estimate r and a with respect to the possible applications of the proposed bound to the practice.

In this paper, we address issues related to the modeling, analysis, and countermeasures of worm attacks on the Internet. Most previous work assumed that a worm always propagates itself at the highest possible speed. Some newly developed worms (e.g., “Atak” worm) contradict this assumption by deliberately reducing the propagation speed in order to avoid detection. As such, we study a new class of worms, referred to as self-disciplinary worms. These worms adapt their propagation patterns in order to reduce the probability of detection, and eventually, to infect more computers. We demonstrate that existing worm detection schemes based on traffic volume and variance cannot effectively defend against these self-disciplinary worms. To develop proper countermeasures, we introduce a game-theoretic formulation to model the interaction between the worm propagator and the defender. We show that an effective integration of multiple countermeasure schemes (e.g., worm detection and forensics analysis) is critical for defending against self-disciplinary worms. We propose different integrated schemes for fighting different self-disciplinary worms, and evaluate their performance via real-world traffic data.

In this paper, we address attacks that exploit the timing behavior of TCP and other protocols and applications in low-latency anonymity networks. Mixes have been used in many anonymous communication systems and are supposed to provide countermeasures to defeat traffic analysis attacks. In this paper, we focus on a particular class of traffic analysis attacks, flow-correlation attacks, by which an adversary attempts to analyze the network traffic and correlate the traffic of a flow over an input link with that over an output link. Two classes of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze the performance of mixes. We find that all but a few batching strategies fail against flow-correlation attacks, allowing the adversary to either identify ingress and egress points of a flow or to reconstruct the path used by the flow. Counterintuitively, some batching strategies are actually detrimental against attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and mechanisms to be used to counter flow-correlation attacks.

"The Marauder's Map" is a magical map in J. K. Rowling's fantasy series, "Harry Potter and the Prisoner of Azkaban". It shows all moving objects within the boundary of the "Hogwarts School of Witchcraft and Wizardry". In this paper, we introduce a similar attack to location privacy in wireless networks. Our system, namely the digital Marauder's map, can reveal the locations of WiFi-enabled mobile devices within the coverage area of a single high-gain antenna. The digital Marauder's map is built solely with off-the-shelf wireless equipments, and features a mobile design that can be quickly deployed to a new location and instantly used without training. We present a comprehensive set of theoretical analysis and experimental results which demonstrate the coverage and localization accuracy of the digital Marauder's map.

We address issues related to privacy protection in location-based services (LBS). Most existing research in this field either requires a trusted third-party (anonymizer) or uses oblivious protocols that are computationally and communicationally expensive. Our design of privacy-preserving techniques is principled on not requiring a trusted third-party while being highly efficient in terms of time and space complexities. The problem has two interesting and challenging characteristics: First, the degree of privacy protection and LBS accuracy depends on the context, such as population and road density, around a user's location. Second, an adversary may violate a user's location privacy in two ways: (i) based on the user's location information contained in the LBS query payload, and (ii) by inferring a user's geographical location based on its device's IP address. To address these challenges, we introduce CAP, a Context-Aware Privacy-preserving LBS system with integrated protection for data privacy and communication anonymity. We have implemented CAP and integrated it with Google Maps, a popular LBS system. Theoretical analysis and experimental results validate CAP's effectiveness on privacy protection, LBS accuracy, and communication Quality-of-Service.

This paper considers trellis coded quantization (TCQ) and low-density parity-check (LDPC) codes for the quadratic Gaussian Wyner-Ziv coding problem. After TCQ of the source X, LDPC codes are used to implement Slepian-Wolf coding of the quantized source Q(X) with side information Y at the decoder. Assuming 256-state TCQ and ideal Slepian-Wolf coding in the sense of achieving the theoretical limit H(Q(X)|Y ), we experimentally show that Slepian-Wolf coded TCQ performs 0.2 dB away from the Wyner-Ziv distortion-rate function DWZ(R) at high rate. This result mirrors that of entropy-constrained TCQ in classic source coding of Gaussian sources. Furthermore, using 8,192-state TCQ and assuming ideal Slepian-Wolf coding, our simulations show that Slepian-Wolf coded TCQ performs only 0.1 dB away from DWZ(R) at high rate. These results establish the practical performance limit of Slepian-Wolf coded TCQ for quadratic Gaussian Wyner-Ziv coding. Practical designs give performance very close to the theoretical limit. For example, with 8,192-state TCQ, irregular LDPC codes for Slepian-Wolf coding and optimal non-linear estimation at the decoder, our performance gap to DWZ(R) is 0.20 dB, 0.22 dB, 0.30 dB, and 0.93 dB at 3.83 bit per sample (b/s), 1.83 b/s, 1.53 b/s, and 1.05 b/s, respectively. When 256-state 4-D trellis-coded vector quantization instead of TCQ is employed, the performance gap to DWZ(R) is 0.51 dB, 0.51 dB, 0.54 dB, and 0.80 dB at 2.04 b/s, 1.38 b/s, 1.0 b/s, and 0.5 b/s, respectively.

Following recent works on the rate region of the quadratic Gaussian two-terminal source coding problem and limit-approaching code designs, this paper examines multiterminal source coding of two correlated, i.e., stereo, video sequences to save the sum rate over independent coding of both sequences. Two multiterminal video coding schemes are proposed. In the first scheme, the left sequence of the stereo pair is coded by H.264/AVC and used at the joint decoder to facilitate Wyner-Ziv coding of the right video sequence. The first I-frame of the right sequence is successively coded by H.264/AVC Intracoding and Wyner-Ziv coding. An efficient stereo matching algorithm based on loopy belief propagation is then adopted at the decoder to produce pixel-level disparity maps between the corresponding frames of the two decoded video sequences on the fly. Based on the disparity maps, side information for both motion vectors and motion-compensated residual frames of the right sequence are generated at the decoder before Wyner-Ziv encoding. In the second scheme, source splitting is employed on top of classic and Wyner-Ziv coding for compression of both I-frames to allow flexible rate allocation between the two sequences. Experiments with both schemes on stereo video sequences using H.264/AVC, LDPC codes for Slepian-Wolf coding of the motion vectors, and scalar quantization in conjunction with LDPC codes for Wyner-Ziv coding of the residual coefficients give a slightly lower sum rate than separate H.264/AVC coding of both sequences at the same video quality.

Internet threat monitoring (ITM) systems have been deployed to detect widespread attacks on the Internet in recent years. However, the effectiveness of ITM systems critically depends on the confidentiality of the location of their monitors. If adversaries learn the monitor locations of an ITM system, they can bypass the monitors and focus on the uncovered IP address space without being detected. In this paper, we study a new class of attacks, the invisible LOCalization (iLOC) attack. The iLOC attack can accurately and invisibly localize monitors of ITM systems. In the iLOC attack, the attacker launches low-rate port-scan traffic, encoded with a selected pseudonoise code (PN-code), to targeted networks. While the secret PN-code is invisible to others, the attacker can accurately determine the existence of monitors in the targeted networks based on whether the PN-code is embedded in the report data queried from the data center of the ITM system. We formally analyze the impact of various parameters on attack effectiveness. We implement the iLOC attack and conduct the performance evaluation on a real-world ITM system to demonstrate the possibility of such attacks. We also conduct extensive simulations on the iLOC attack using real-world traces. Our data show that the iLOC attack can accurately identify monitors while being invisible to ITM systems. Finally, we present a set of guidelines to counteract the iLOC attack.

Internet threat monitoring (ITM) systems are a widely deployed facility to detect, analyze, and characterize dangerous Internet threats such as worms and distributed denial-of-service (DDoS) attacks. Nonetheless, an ITM system can also become the target of attack. In this paper, we address localization attacks against ITM systems in which an attacker impairs the effectiveness of ITM systems by identifying the locations of ITM monitors. We propose an information-theoretic framework for the modeling of localization attacks as communication channels. Based on the information-theoretic model, we generalize all existing attacks as ldquotemporal attacksrdquo, derive closed formulae of their performance, and propose an effective detection approach. The information-theoretic model also inspires a new attack called a spatial attack and motivates the corresponding detection approach. We show simulation results that support our theoretic findings.

In this paper, we propose the expected schedulability to characterize the schedulability for the stochastic tasks on a single real-time computer processor. Our results show that the stochastic model has more flexibility to characterize the real-time tasks than the deterministic model. The expected schedulability is related to the real-time t at tasks arrival and may show that a sub-set of task would be scheduled at any given real-time interval. The numerical analysis based on our theoretic results is consistent with the simulation analysis. Both numerical and simulation results show that the tasks would be scheduled for real-time tasks in realtime systems if the traffic load is less than a specific value which is more than 69%, which was provided in some deterministic situations. This observation implies that the expected schedulability based on the stochastic model would provide a bigger threshold for the real-time tasks to be scheduled.

Tor is a real-world, circuit-based low-latency anonymous communication network, supporting TCP applications on the Internet. In this paper, we present a new class of attack, the replay attack, against Tor. Compared with other existing attacks, the replay attack can confirm communication relationships quickly and accurately and poses a serious threat against Tor. In this attack, a malicious entry onion router duplicates cells of a stream from a sender. The original cell and duplicate cell traverse middle onion routers and arrive at an exit onion router along a circuit. Since Tor uses the counter mode AES (AES-CTR) for encryption of cells, the duplicate cell disrupts the normal counter at middle and exit onion routers and the decryption at the exit onion router incurs cell recognition errors. If an accomplice of the attacker at the entry onion router controls the exit onion router and detects such decryption errors, the communication relationship between the sender and receiver will be discovered. The replay attack can also be used as a denial of service attack. We implement the replay attack on Tor and our experiments validate the feasibility and effectiveness of the attack. We also present guidelines to defending against the replay attack.

In this paper, we study a new class of attacks, theinvisibleLOCalization (iLOC) attack, which can accurately and invisibly localize monitors of Internet threat monitoring (ITM) systems, a class of widely deployed facilities to characterize Internet threats, such as worm propagation, denial-of-service (DoS) attacks. In theiLOCattack, the attacker launches low-rate port-scan traffic, encoded with a selectedpseudo-noisecode(PN- code), to targeted networks. While the secret PN-code is invisible to others, the attacker can accurately determine the existence of monitors in the targeted networks based on whether the PN-code is embedded in the report data queried from the data center of the ITM system. We conduct extensive simulations on theiLOCattack using real-world traces. Our data demonstrate that theiLOCattack can accurately identify monitors while remaining invisible to the ITM. Finally, we present a set of guidelines to counteract theiLOCattack.

Multiterminal (MT) source coding refers to separate lossy encoding and joint decoding of multiple correlated sources. Recently, the rate region of bothdirectandindirectMT source coding in the quadratic Gaussian setup with two encoders was determined. We are thus motivated to design practical MT source codes that can potentially achieve the entire rate region. In this paper, we present two practical MT coding schemes under the framework of Slepian–Wolf coded quantization (SWCQ) for both direct and indirect MT problems. The first,asymmetricSWCQ scheme relies on quantization and Wyner–Ziv coding, and it is implemented via source splitting to achieve any point on the sum–rate bound. In the second, conceptually simpler scheme,symmetricSWCQ, the two quantized sources are compressed using symmetric Slepian–Wolf coding via a channel code partitioning technique that is capable of achieving any point on the Slepian–Wolf sum–rate bound. Our practical designs employ trellis-coded quantization and turbo/low-density parity-check (LDPC) codes for both asymmetric and symmetric Slepian–Wolf coding. Simulation results show a gap of only 0.139–0.194 bit per sample away from the sum–rate bound for both direct and indirect MT coding problems.

We address issues related to sharing information in a distributed system consisting of autonomous entities, each of which holds a private database. We consider threats from malicious adversaries that can deviate from the designated protocol and change their input databases. We classify malicious adversaries into two widely existing subclasses, namely weakly and strongly malicious adversaries, and propose protocols that can effectively and efficiently protect privacy against malicious adversaries.

Following recent works on the rate region of the quadratic Gaussian two-terminal source coding problem and limit-approaching code designs, this paper examines multiterminal source coding of two correlated video sequences to save the sum rate over independent coding. Specifically, the first video sequence is coded by H.264 and used at the joint decoder to facilitate Wyner-Ziv coding of the second video sequence. The first I-frame of the right sequence is successively coded by H.264 and Slepian-Wolf coding. An efficient stereo matching algorithm based on loopy belief propagation is then adopted at the decoder to produce pixel-level disparity maps between the corresponding frames of the two decoded video sequences on the fly. Based on the disparity maps, side information for both motion vectors and motion-compensated residual frames of the second sequence are generated at the decoder before Wyner-Ziv encoding. Experimental results on stereo video sequences using H.264, LDPC codes for Slepian-Wolf coding of the motion vectors and scalar quantization in conjunction with LDPC codes for Wyner-Ziv coding of the residual coefficients show savings in terms of the sum-rate when compared to separate H.264 coding at the same video quality.

Schedulability analysis is a cornerstone of modern real-time scheduling theory development. Utilization- bound based schedulability test is considered one of most efficient and effective schedulability tests, because of its extremely low runtime overhead. Deriving the utilization bound for a given real-time system has, nevertheless, been a challenging task as it usually requires comprehensive modeling and understanding of the system and payload tasks. This paper is focused on deriving utilization bounds for weighted round robin schedulers. We demonstrate how to establish a unified modeling framework and then use it to derive utilization bounds. We obtain the optimal parameter selection that maximizes the utilization bound, then compare the new bound with those of fixed priority schedulers, and timed token ring schedulers. The new bound is further extended to systems with sporadic job requests. We argue that our modeling framework is highly versatile, and hence, can be easily tailored for analysis of other types of real-time systems.

Law enforcement agencies need the ability to conduct electronic surveillance to combat crime, terrorism, or other malicious activities exploiting the Internet. However, the proliferation of anonymous communication systems on the Internet has posed significant challenges to providing such traceback capability. In this paper, we develop a new class of flow marking technique for invisible traceback based on direct sequence spread spectrum (DSSS), utilizing a pseudo-noise (PN) code. By interfering with a sender's traffic and marginally varying its rate, an investigator can embed a secret spread spectrum signal into the sender's traffic. The embedded signal is carried along with the traffic from the sender to the receiver, so the investigator can recognize the corresponding communication relationship, tracing the messages despite the use of anonymous networks. The secret PN code makes it difficult for others to detect the presence of such embedded signals, so the traceback, while available to investigators is, effectively invisible. We demonstrate a practical flow marking system which requires no training, and can achieve both high detection and low false positive rates. Using a combination of analytical modeling, simulations, and experiments on Tor (a popular Internet anonymous communication system), we demonstrate the effectiveness of the DSSS-basedflow marking technique.

Active worms pose major security threats to the Internet. In this paper, we investigate a new class of active worms, i.e., camouflaging worm (C-Worm in short). The C-Worm has the capability to intelligently manipulate its scan traffic volume over time, thereby camouflaging its propagation from existing worm detection systems. We analyze characteristics of the C-Worm and conduct a comprehensive comparison between its traffic and non-worm traffic. We observe that these two types of traffic are barely distinguishable in the time domain, however, their distinction is clear in the frequency domain, due to the recurring manipulative nature of the C-Worm. Motivated by our observations, we design a novel spectrum-based scheme to detect the C-Worm. Our scheme uses the power spectral density (PSD) distribution of the scan traffic volume and its corresponding spectral flatness measure (SFM) to distinguish the C-Worm traffic from non-worm traffic. We conduct extensive performance evaluations on our proposed detection scheme against the C-Worm. The performance data clearly demonstrates that our proposed scheme can effectively detect the C-Worm propagation

Finite difference (FD) methods are the most prevalent numerical modelling algorithms for evaluating initial or boundary value problems in scientific and engineering applications. Unfortunately, simulating time evolutions for transient physical phenomenon is computationally demanding and data-intensive. This paper introduces an efficient implementation of FD computing engine on FPGA-based reconfigurable computing (RC) platform. Instead of following the formal high-order FD expressions with standard IEEE-754 compliant floating point arithmetic units, a new class of optimized finite-accurate FD schemes was proposed, whose FD coefficients are optimized to be represented with only a few binary bits without deteriorating numerical accuracy criterions. Furthermore, in order to simplify the implementation of floating-point summations, the conventional costly floating-point adder tree was replaced by a floating-point/fixed-point hybrid accumulator using group-alignment technology. The resulting fully-pipelined FD computing engine with finite accurate coefficients can provide us similar or even better worst case relative and absolute rounding errors than standard floating-point arithmetic, but consumes only a fraction of hardware resources. This new design can be easily applied to our previous work (He et al., 2005) and result in a more efficient and compact implementation with higher computational performance

Time domain or frequency domain Finite Difference (FD) methods are one of the most popular numerical modelling techniques in the solution of scientific and engineering problems. However, these simulations are still time-consuming and cannot be used routinely except in institutes that can afford the high cost of running and maintaining supercomputers or large PC-cluster systems. In this paper, we present an efficient implementation of FPGA-based FD computing engine using acoustic wave modeling problems as an example. Instead of following the formal high-order FD expressions with standard IEEE-754 compliant floating-point multipliers and adders, we propose a new class of optimized FD schemes, whose FD coefficients are optimized to be only a few binary bits so that much fewer Logic Cell (LC) resources or on-chip multipliers are needed without deteriorating numerical accuracy criterions. Furthermore, we simplify the implementation of following floatingpoint summations by group-alignment technology. A floating-point/fixed-point hybrid accumulator with similar relative and absolute rounding errors now replaces the conventional costly floating-point adder tree.

Computing and networking systems have been widely used in almost every sector of society. However, they are limited by their capabilities in terms of security, reliability, performance, and scale-ability. We will discuss the various challenges posed by the design and implementation of the computing and networking systems. We will introduce some major initiatives taken by the National Science Foundation which aim to address these challenges. Examples of such initiatives include the GENI and ICER programs.

In this paper, we address issues in implementing voice over IP (VoIP) services in packet switching networks. VoIP has been identified as a critical real-time application in the network QoS research community and has been implemented in commercial products. To provide competent quality of service for VoIP systems comparable to traditional PSTN systems, a call admission control (CAC) mechanism has to be introduced to prevent packet loss and over-queuing. Several well-designed CAC mechanisms, such as the site-utilization-based CAC-and the link-utilization-based CAC mechanisms have been in place. However, the existing commercial VoIP systems have not been able to adequately apply and support these CAC mechanisms and, hence, have been unable to provide QoS guarantees to voice over IP networks. We have designed and implemented a QoS-provisioning system that can be seamlessly integrated with the existing VoIP systems to overcome their weakness in offering QoS guarantees. A practical implementation of our QoS-provisioning system has been realized.

Multiterminal (MT) source coding refers to separate lossy encoding and joint decoding of multiple correlated sources. This paper presents two practical MT coding schemes under the same general framework of Slepian-Wolf coded quantization (SWCQ) for both direct and indirect quadratic Gaussian MT source coding problems with two encoders. The first asymmetric SWCQ scheme relies on quantization and Wyner-Ziv coding, and is implemented via source-splitting to achieve any point on the inner sum-rate bound for both direct and indirect MT coding problems. In the second symmetric SWCQ scheme, the two quantization outputs are compressed using multilevel symmetric Slepian-Wolf coding. This scheme is conceptually simpler and can potentially achieve most of the points on the inner sum-rate bound. Our practical designs employ trellis coded quantization, LDPC code based asymmetric Slepian-Wolf code, and arithmetic code and turbo code based symmetric Slepian-Wolf code. Simulation results show a gap of only 0.24-0.29 bit per sample away from the inner sum-rate bound for both direct and indirect MT coding problems.

A successful application-oriented reconfigurable coprocessor design requires not only a powerful FPGA-based computing engine along with suitable hardware architecture, but also an efficient algorithm tailored for this special application. In this paper, we present our hardware architecture and numerical algorithms designed to speedup the time-domain finite-difference simulation of linear wave propagation problems in 2D and 3D space on FPGA-based reconfigurable platforms. Application fields of this work include seismic modeling and migration, computational electromagnetics, aeroacoustics, marine acoustics, to name a few. By writing first-order linear wave equations into second-order form, we halve the number of unknowns and simplify the treatment of parameters. We also adopt higher-order finite-difference (FD) schemes to further reduce the number of unknowns at the cost of increasing floating-point computations per discrete grid point. By doing so, we relief the bandwidth requirements between the FPGA and onboard memories but put more burden on the computing engine to take full advantage of FPGA's computational potentials. The speed of our design implemented on a Xilinx ML401 Virtex-4 evaluation platform is about 1.5/spl sim/4 times faster than a pure software implementation of the same algorithm running on a 3.0 GHz DELL workstation. This impressive result is mainly attributed to the memory architecture design, which is well-tuned for our numerical higher-order FD algorithms and can utilize onboard memory bandwidth more wisely. Furthermore, the good scalability of our design makes it compatible with most commercial reconfigurable coprocessor platforms and correspondingly, the performance would be proportional to their onboard memory bandwidth.

Mix networks are designed to provide anonymity for users in a variety of applications, including anonymous Web browsing and numerous E-commerce systems. Such networks have been shown to be susceptible to flow correlation attacks empirically. In this paper, we model the effectiveness of flow correlation attacks. Our results illustrate the quantitative relationship among system parameters such as sample size, noise level, payload flow rate, and detection rate. Our analysis quantitatively predicts how existing flow-based anonymous systems would fail under flow-correlation attacks, thus providing useful guidelines for the design of future anonymous systems.

This paper studies the degradation of anonymity in a flow-based wireless mix network under flow marking attacks, in which an adversary embeds a recognizable pattern of marks into wireless traffic flows by electromagnetic interference. We find that traditional mix technologies are not effective in defeating flow marking attacks, and it may take an adversary only a few seconds to recognize the communication relationship between hosts by tracking such artificial marks. Flow marking attacks utilize frequency domain analytical techniques and convert time domain marks into invariant feature frequencies. To counter flow marking attacks, we propose a new countermeasure based on digital filtering technology, and show that this filter-based counter-measure can effectively defend a wireless mix network from flow marking attacks.

We address privacy-preserving classification problem in a distributed system. Randomization has been the approach proposed to preserve privacy in such scenario. However, this approach is now proven to be insecure as it has been discovered that some privacy intrusion techniques can be used to reconstruct private information from the randomized data tuples. We introduce an algebraic-technique-based scheme. Compared to the randomization approach, our new scheme can build classifiers more accurately but disclose less private information. Furthermore, our new scheme can be readily integrated as a middleware with existing systems.

For many Internet applications, the ability to protect the identity of participants and the characteristics of their communication in distributed applications is critical. For such applications, a number of traffic camouflaging systems have been developed over the past several years. The effectiveness of these systems relies greatly on (1) the protocol by which messages are (re-)routed among the participants and (2) the scheme by which links are padded. In this talk, we will discuss our recent discoveries on the effectiveness of these camouflaging methods. Our results contradict some of the methods that have been commonly used. For example, we find that using more agents in re-routing may not necessarily increase the probability that a sender can be identified. Furthermore, padding links with a constant-bit rate pattern may result in the worst probability; that an adversary can identify the underlying payload status. We will discuss how to develop optimal strategies for these traffic camouflaging systems.

Component technology has become a central focus of software engineering in research and development. Reusability is a key factor that contributes to its success. The reuse of components can lead to a shortening of software development cycles and savings in software development costs. However, existing component models provide no support for real-time services and some real-time extensions of component models lack of consideration for reusability of components in providing real-time services. In this work, we develop a real-time component-based system that maintains the reusability of components.

While utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound itself. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this paper, we develop a general framework that allows one to effectively derive schedulability bounds for a wide range of real-time systems with different workload patterns and schedulers. Our analytical model is capable of describing a wide range of tasks and schedulers' behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform derivation of schedulability bounds. We derive a parameterized schedulability bound for static priority schedulers with arbitrary priority assignment. Existing utilization bounds for different priority assignments and task releasing patterns can be derived from our closed-form formula by simple assignments of proper parameters.

In multimode distributed systems, active task sets are assigned to their distributed components for realizing one or more functions. Many of these systems encounter runtime task variations at the input and across the system while processing their tasks in real time. Very few efforts have been made to address energy efficient scheduling in these types of distributed systems. In this paper, we propose an analytical model for energy efficient scheduling in distributed real-time embedded systems to handle time-varying task inputs. A new slack distribution scheme is introduced and adopted during the schedule of the task sets in the system. The slack distribution is made according to the service demand at the nodes which affects the energy consumption in the system. The active component at a node periodically determines the service rate and applies voltage scaling according to the dynamic traffic condition observed at various network nodes. The proposed approach uses a comprehensive traffic description function at nodes and provides adequate information about the worst-case traffic behavior anywhere in the distributed network, thereby enhancing the system power management capabilities. We evaluate the proposed technique using several benchmarks employing an event driven simulator and demonstrate its performance for multimode applications. Experimental results indicate significant energy savings in various examples and case studies.

Asymmetric code design for remote multiterminal source coding in the quadratic Gaussian case is presented in this paper. For remote multiterminal source coding of X, to achieve the minimum sum rate of the two independent encoders subject to a fidelity criterion d, theoretical bounds were derived independently. The main idea is to quantize the first observation Y/sub 1/ and apply Wyner-Ziv coding on Y/sub 2/ by using the quantized version of Y/sub 1/ as side information in an efficient asymmetric coding scheme. The practical code design gives results that are very close to the sum-rate bound.

We address the inference control problem in data cubes with some data known to users through external knowledge. The goal of inference controls is to prevent exact values of sensitive data from being inferred through answers to online analytical processing (OLAP) queries. We present an information theoretic approach for cardinality-based inference control, which simply counts the number of cells that all queries have covered thus far to determine whether a new query should be answered. Compared to previous approaches in sum-only data cubes, our new approach has a more general framework (applies to MIN, MAX and SUM) and is more effective.

We propose a confidential logging and auditing service for distributed information systems. We propose a cluster-based TTP (trusted third party) architecture for the event log auditing services, so that no single TTP node can have the full knowledge of the logs, and thus no single node can misuse the log information without being detected. On the basis of a relaxed form of secure distributed computing paradigms, one can implement confidential auditing service so that the auditor can retrieve certain aggregated system information, e.g. the number of transactions, the total volume, the event traces, etc., without having to access the full log data. Similar to the peer relationship of routers to provide global network routing services, the mutually supported, mutually monitored cluster TTP architecture allows independent systems to collaborate in network-wide auditing without compromising their private information.

We study the delay performance of policed traffic to provide real-time guarantees over wireless networks. A number of models have been presented in the literature to describe wireless (radio or optical) networks in terms of the wireless channel and the underlying error control mechanisms. We describe a general framework to incorporate such models into delay guarantee computations for real-time traffic. Static-priority scheduling is considered, and two different admission control mechanisms are used to achieve the trade-off between resource utilization and admission overhead.

AIMD is a widely-used network congestion control scheme. Despite its discontinuous control behavior, the majority of contemporary literature employed a statistically-averaged continuous model to approximate AIMD without considering its discontinuity. The design of a discontinuous control system must be based on rules that are entirely different from that of continuous control systems. Ignoring discontinuity issues results in great discrepancy between analytical models and the practice. In this paper we use the sliding mode control (SMC) theory to investigate congestion control without ignoring its discontinuity. Based on the SMC theory, the design of discontinuous (congestion) control systems must consider the relative degree and zero dynamics of the system, in order to guarantee asymptotic stability. This framework can precisely reflect the behavior of the control rules and the controlled objective of a congestion control system. We show that the relative degree of the control system of rate-based, AIMD flow-control algorithms is two. That is, to apply sound control principles to the design of AIMD algorithms, one should use both the queue length error and its first order time derivative to construct the switching function of the control model of an active queue management scheme. Based on the SMC model, one can quantify the tradeoffs among the convergence speed, the amount of throttling adjustments, and the degree of oscillations. We show quantitatively that one can guarantee stability conditions, drastically reduce oscillation of AIMD without significant loss of fairness and stability, and quantitative understanding of the tradeoffs among oscillation, delay and fairness.

Providing efficient data services is one of the fundamental requirements for wireless sensor networks. The data service paradigm requires that the application submit its requests as queries and the sensor network transmits the requested data to the application. While most existing work in this area focuses on data aggregation, not much attention has been paid to query aggregation. For many applications, especially ones with high query rates, query aggregation is very important. We study a query aggregation-based approach for providing efficient data services. In particular: (1) we propose a multi-layered overlay-based framework consisting of a query manager and access points (nodes), where the former provides the query aggregation plan and the latter executes the plan; (2) we design an effective query aggregation algorithm to reduce the number of duplicate/overlapping queries and save overall energy consumption in the sensor network Our performance evaluations show that by applying our query aggregation algorithm, the overall energy consumption can be significantly reduced and the sensor network lifetime can be prolonged correspondingly.

In this paper, we propose and analyze a methodology for providing absolute differentiated services for real-time applications. We develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and, hence, is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. In this paper, we show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.

Anycasting has recently become an important research topic, especially for replicated servers. With anycasting, applications can request the "nearest" server for provision of desired (multimedia) service. In this paper, we study efficient distributed admission control (DAC) for anycast flows. We focus on algorithms that perform destination selection and efficient path establishment. Taking advantage of anycasting, our distributed algorithms differ from each other in their dependence on system status information. Performance data obtained through mathematical analysis and simulations show that, in terms of admission probabilities, DAC systems that are based on local status information have performance levels close to those that utilize global and dynamic status information. This renders our DAC algorithms useful not only for the network layer, but also for the application layer admission control for anycast flows.

This paper quantitatively analyzes anonymous communication systems (ACS) with regard to anonymity properties. Various ACS have been designed & implemented. However, there are few formal & quantitative analyzes on how these systems perform. System developers argue the security goals which their systems can achieve. Such results are vague & not persuasive. This paper uses a probabilistic method to investigate the anonymity behavior of ACS. In particular, this paper studies the probability that the true identity of a sender can be discovered in an ACS, given that some nodes have been compromised. It is through this analysis that design guidelines can be identified for systems aimed at providing communication anonymity. For example, contrary to what one would intuitively expect, these analytic results show that the probability that the true identity of a sender can be discovered might not always decrease as the length of communication path increases.

We propose an approach to analyze the resilience to failures of structured P2P systems. The approach is Markov-chain based, and can be applied to systems with relatively stable size and uniformly distributed nodes. We apply our method to several well-known structured P2P systems. We find that finger neighbors and special neighbors have different influences on the resilience features of P2P systems. More particularly, finger neighbors have significant influence on the average path length while special neighbors influence the hit ratio. Following the above observation, we propose to add some finger neighbor(s) to nodes of the CAN (content-addressable network) system which originally have no such finger neighbor(s). We use the small-world phenomenon to form the CAN-small-world (CAN-SW) system. We then apply the proposed Markov-chain based approach to analyze its resilience. We find that the performance of the system under failures or not, has been improved significantly, particularly, in terms of the average path length.

Traffic analysis attacks aim at deriving mission critical information from the analysis of the traffic transmitted over a network. Countermeasures for such attacks are usually realized by properly "padding" the payload traffic so that the statistics of the overall traffic become significantly different from that of the payload traffic. In this paper, we propose a analytical framework for traffic analysis attacks based on statistical pattern recognition techniques. We study the effectiveness of countermeasures for traffic analysis attacks within our proposed framework. Two basic countermeasure strategies are (a) to pad the traffic with constant interarrival times of packets (CIT) or (b) to pad the traffic with variable interarrival times (VIT). Our experiments show that CIT countermeasures fail when the adversary uses sample variance or sample entropy of packet interarrival times for statistical analysis. On the other hand, VIT countermeasures are effective regardless of which sample statistics are used by the adversary. These observations are validated by analysis of detection rates based on sample distributions of packet interarrival times.

This paper presents a new method to control the delay performance for high rate heterogeneous real-time traffic flows based on a novel traffic control algorithm which is a generalization of traditional (/spl sigma/, /spl rho/) regulator. Our new control algorithm operates like the traditional regulator under the normal loading situation, but provides more regulation for the high rate (heavy load condition) of the traffic. For a set of heterogenous real-time traffic flows R we can show that D/sub r/(R) /spl les/ D(R) where D/sub r/(R) and D(R) are the worst-case delay bounds with our new control algorithm and that with (/spl sigma/, /spl rho/) regulator respectively. More specifically, we develop a set of formula that can be used to set the parameters in our new traffic controller so that the worst case delay bound is minimized by streaming the traffic flow. We can prove that there exists a minimum (average) input rate p* such that D/sub r/(R) = D(R) for /spl rho/ /spl les/ /spl rho/* and D/sub r/(R)/spl rho/*. Using the extended regulator can effectively control the delay when the average heterogeneous traffic rate is high. The issues are particularly useful for Integrated Services where a flow may over claim its share of resource and for Differentiated Services where a class of traffic flows may possess very high rates.

We study countermeasures to traffic analysis attacks. A common strategy for such countermeasures is link padding. We consider systems where payload traffic is padded so that packets have either constant inter-arrival times or variable inter-arrival times. The adversary applies statistical recognition techniques to detect the payload traffic rates by using statistical measures like sample mean, sample variance, or sample entropy. We evaluate quantitatively the ability of the adversary to make a correct detection and derive closed-form formulas for the detection rate based on analytical models. Extensive experiments were carried out to validate the system performance predicted by the analytical method. Based on the systematic evaluations, we develop design guidelines for the proper configuration of a system in order to minimize the detection rate

We address the issues related to aggregation of anycast groups for scalable anycast routing. Anycast is a new network service that allows a sender to access anyone in a group that shares the same anycast address. Anycast has numerous potential applications. However, it also introduces new issues. One of the issues is that the size of the anycast routing tables is significantly increased The main goals of this study are to reduce the size of routing tables and to improve network end-to-end performance. Particularly, we propose three group-aggregation algorithms with different objectives: (1) group-aggregation for minimizing the routing table size, (2) group-aggregation for balancing interface load, and (3) integrated group-aggregation. These algorithms take full advantages of the anycast semantics. Our evaluation results show that our group-aggregation algorithms can efficiently reduce the size of routing tables by 90% while achieving high network performance in terms of the average end-to-end delay.

In this paper, we propose and analyze a methodology for providing statistical guarantees within the diffserv model in a network, that uses static-priority schedulers. We extend the previous work on statistical delay analysis and develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and hence is scalable to large systems. We systematically analyze the performance of our approaches in terms of system utilization. As expected, our experimental data show that statistical services can achieve much higher utilization than deterministic services.

ESEARCH in the area of security of computing systems has always been of utmost importance, particularly in recent years as orchestrated attacks have sought to cripple critical infrastructures. Security issues in distributed computing systems involve reducing vulnerabilities as well as giving system management the insight and control needed to defend distributed information systems. All aspects of business and government operations and services are dependent upon the security and integrity of our information and communication infrastructures. Critical sectors such as energy, health, transportation, social and emergency services, manufacturing, processing, and logistics and distribution functions rely almost entirely on data processing and interchange. The recent attacks on government and commercial computers indicate that “hacking” has gone beyond the realm of domestic pranks and has entered the domain of state sponsored cyber-terrorism. Clearly, these information security threats to vital national infrastructures present risks of debilitating impact on the defense and economic security of the nation and the state. As such, these issues pose new challenges to researchers. Advances are rapidly being made in the following areas: anonymity and camouflaging, intrusion detection, dynamic coalition, distributed denial of service, security protocols, authentication and verification, and mobile code and agent security. This special section of IEEE Transactions on Parallel and Distributed Systems is targeted at related issues in security of distributed computing systems. Response to the call for papers was overwhelming. From these excellent submissions, seven were accepted for publication in this special section. The first paper by M. Ahamad, S. Lakshmanan, and H. Venkateswaran explores the subject of responsive security for stored data. X. Zhang, L. Xiao, and Z. Xu discuss low-cost and reliable mutual anonymity protocols in peer-to-peer networks. Integrated access control and intrusion detection for Web servers is explained by T. Ryutov, C. Neuman, D. Kim, and L. Zhou. The paper by L. Wang, X. Zhao, D. Pei, R. Bush, D. Massey, and L. Zhang explores ways to protect BGP routes to top-level DNS servers. J. Xu and M. Sung introduce a technique for defending against internet DDoS attacks. The next paper, by H. Wang and K. Shin, describes a built-in protection mechanism to counter DDoS attacks, known as TransportAware IP Routers. The final paper from A. Mei, L. Mancini, and S. Jajodia discusses a secure dynamic fragment and replica allocation in large-scale distributed file systems. Finally, I would like to take this time to thank the contributing authors, reviewers, and the Editor-in-Chief, Dr. Pen-Chung Yew. Additional thanks goes to Mr. Shengquan Wang for Web management and Ms. Larisa Archer for administration of the review process. Without their contributions and support, this special section would not be possible.

For many Internet applications, the ability to protect the identity of participants in a distributed applications is critical. For such applications, a number of anonymous communication systems have been realized over the recent years. The effectiveness of these systems relies greatly on the way messages are routed among the participants. (We call this the route selection strategy.) In this paper we describe how to select routes so as to maximize the ability of the anonymous communication systems to protect anonymity To measure this ability, we define a metric (anonymity degree), and we design and evaluate an optimal route selection strategy that maximizes the anonymity degree of a system. Our analytical and experimental data shows that the anonymity degree may not always monotonically increase as the length of communication paths increase. We also found that variable path-length strategies perform better than fixed-length strategies.

A novel efficient and effective Internet multicast routing protocol is presented with short delay, high throughput, resource utilization and scalability for a single multicast group g. The protocol has two features: (1) multiple shared-trees (MST) are configured to provide efficient, dynamic and quality multicast routing; (2) an anycasting approach is used to form the tree roots into an anycast group so that the multicast packets can be anycast to the nearest node at one of the shared trees to achieve the best routing service for the multicast packets. The performance of the MST protocol is analyzed through extensive simulations and compared with well-known source tree and shared-tree routing.

A novel efficient and dynamic integrated routing protocol for multicast and anycast messages is presented. The contributions of the protocol differ from well-known shared-tree systems in two aspects: (1) Off-tree anycast configuration and routing: multicast sources use anycast routing to select a better path from the source to one router in the group in order to avoid congestion or any fault in the network. (2) On-tree router anycast configurations: The nodes in the shared-tree are formed into a virtual anycast group. The shared-tree approach is extended with capability of a group cores (anycast group). The simulation data demonstrates the efficiency of the protocol.

We propose and analyze a methodology for providing absolute differentiated services for real-time applications in networks that use static-priority schedulers. We extend previous work on worst-case delay analysis and develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and hence is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms, and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. We show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.

We propose and analyze a methodology for providing absolute differentiated services with statistical performance guarantees for real-time applications in networks that use class-based (as opposed to flow-aware) static priority schedulers. We develop a method that can be used to derive statistical delay guarantees in a flow-unaware fashion. Traditionally, both deterministic and statistical delay analysis methods either depend on schedulers that keep per-flow state information, or require detailed information about flow population at delay analysis time. The fact that no such information is needed for delay analysis allows us to perform deadline tests during system (re-)configuration time. We are so able to reduce the runtime admission control to a simple utilization test. No explicit delay computation is necessary at admission time, making this approach scalable to large systems.

This letter presents: 1) a delay analysis model, which is specially for the admission control of real-time multicast connections in ATM networks; 2) a distributed multicast routing algorithm, which generates suboptimal routing trees under real-time constraints; and 3) a connection setup method that integrates multicast routing with admission control.

This paper presents the general approach, design, implementation, and evaluation of NetCamo, which is a system to prevent traffic analysis in systems with real-time requirements. Integrated support for both security and real-time is becoming necessary for computer networks that support mission critical applications. This study focuses on how to integrate both the prevention of traffic analysis and guarantees for worst-case delays in an internetwork. We propose and analyze techniques that efficiently camouflage network traffic and correctly plan and schedule the transmission of payload traffic so that both security and real-time requirements are met. The performance evaluation shows that our NetCamo system is effective and efficient. By using the error between target camouflaged traffic and the observed (camouflaged) traffic as metric to measure the quality of the camouflaging, we show that NetCamo achieves very high levels of camouflaging without compromising real-time requirements.

We propose an approach to flow-unaware admission control which is a combination with an aggregate packet forwarding scheme, improving scalability of networks while guaranteeing end-to-end deadlines for real-time applications. We achieve this by using an off-line delay computation and verification step, which allows to reduce the overhead at admission control while keeping admission probability and resource utilization high. Our evaluation data show that our system's admission probabilities are very close to those of significantly more expensive flow-aware approaches. At the same time, the admission control overhead during flow establishment is very low. Our results therefore support the claim from the DS architecture literature that scalability can be achieved through flow aggregation without sacrificing resource utilization and with significant reduction in run time overhead.

In this paper, we present a methodology to use utilization-based admission control in guaranteed real-time communication in a scalable fashion. We make admission control scalable by using a configuration-time test to determine a safe utilization level of servers. Admission control at run-time then is reduced to simple utilization tests on the servers along the path of the new flow. Furthermore, we discuss how appropriate route selection improve utilization levels, design a safe route selection heuristic algorithm to achieve high utilization of resources, and derive two bounds on the maximum utilization level for given traffic in a network. We compare the results of our route selection heuristics with that of a shortest-path based algorithm, and find that our heuristics can achieve a much higher maximum utilization level than that of the shortest-path based algorithm.

Recent experimental research has revealed that the nature of WWW traffic is self-similarity (M.E. Crovella and A. Bestavros, 1997). That is, the behavior of WWW traffic is well modeled by second-order self-similar processes with long-range dependence. A closed form of autocorrelation functions about asymptotically self-similar processes is presented. The verification shows that this form is best for real traffic data on an Ethernet.

An anycast packet is one that should be delivered to one member in a group of designated recipients. Using anycast services may considerably simplify some applications. Little work has been done on routing anycast packets. In this paper, we propose and analyze a routing protocol for anycast message. It is composed of two subprotocols: the routing table establishment subprotocol and the packet forwarding subprotocol. In the routing table establishment subprotocol, we propose four methods (SSP, MIN-D, SET, and GET) for enforcing an order among routers for the purpose of loop prevention. These methods differ from each other on information used to maintain orders, the impact on QoS, and the compatibility to the existing routing protocols. In the packet forwarding subprotocol, we propose a Weighted-Random Selection (WRS) approach for multiple path selection in order to balance network traffic. In particular, the fixed and adaptive methods are proposed to determine the weights. Both of them explicitly take into account the characteristics of distribution of anycast recipient group while the adaptive method uses the dynamic information of the anycast traffic as well. Correctness property of the protocol is formally proven. Extensive simulation is performed to evaluate our newly designed protocol. Performance data shows that the loop-prevention methods and the WRS approaches have great impact on the performance in terms of average end-to-end packet delay. In particular, the protocol using the SET or CBT loop-prevention methods and the adaptive WRS approach performs very close to a dynamic optimal routing protocol in most cases.

In this paper, we study an efficient fault-tolerant CBT multicast routing protocol. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost.

The implementation of bounded-delay services over integrated services networks relies admission control mechanisms that in turn use end-to-end delay computation algorithms. For guaranteed-rate scheduling algorithms such as fair queueing, delay computation based on Cruz's service curve model performs very well. Many currently deployed networks, be they packet-switched or ATM based, rely on non-guaranteed-rate disciplines, most prominently FIFO and static-priority disciplines. We show that for this class of disciplines the service curve model performs poorly. We propose the Integrated Approach as alternative to the service curve model to cluster servers for delay computation purposes, and show in a series of evaluations that this new approach outperforms approaches based on the service curve model as well as other currently used approaches.

Considers the support of hard real-time connections in ATM networks. In an ATM network, a set of hard real-time connections can be admitted only if the worst-case end-to-end delays of cells belonging to individual connections are less than their deadlines. There are several approaches to managing the network resources in order to meet the delay requirements of connections. This paper focuses on the use of traffic regulation to achieve this objective. Leaky buckets provide simple and user-programmable means of traffic regulation. An efficient optimal algorithm for selecting the burst parameters of leaky buckets to meet connections' deadlines is designed and analyzed. The algorithm is optimal in the sense that it always selects a set of burst parameters whose mean value is minimal and by which the delay requirements of hard real-time connections can be met. The exponential size of the search space makes this problem a challenging one. The algorithm is efficient through systematically pruning the search space. There is an observed dramatic improvement in the system performance in terms of the connection admission probability when traffic is regulated using this algorithm.

In this paper, we design and analyze an efficient fault-tolerant multicast routing protocol. Reliable multicast communication is critical for the success of many Internet applications. Multicast routing protocols with core-based tree techniques (CBT) have been widely used because of their scalability and simplicity. We enhance the CBT protocol with fault tolerance capability and improve its efficiency and effectiveness. With our strategy, when a faulty component is detected, some pre-defined backup path(s) is (are) used to bypass the faulty component and enable the multicast communication to continue. Our protocol only requires that routers near the faulty component be reconfigured, thus reducing the runtime overhead without compromising much of the performance. Our approach is in contrast to other approaches that often require relatively large tree reformation when faults occur. These global methods are usually costly and complicated in their attempt to achieve theoretically optimal performance. Our performance evaluation shows that our new protocol performs nearly as well as the best possible global method while utilizing much less runtime overhead and implementation cost.

This paper presents a new schedulability analysis methodology for distributed hard real-time systems with bursty job arrivals. The schedulability is analyzed by comparing worst-case response times of jobs with their timing constraints. We compute response times with a new method, which uses the amount of received service time to determine the response time of instances of a job. We illustrate how this method can be applied to exactly determine worst-case response times for processors with preemptive static priority schedulers, and how it gives a good approximation on the response times for processors with non-preemptive static-priority scheduling or first-come-first-served scheduling. Our schedulability analysis method is the first to support systems with arbitrary job arrival patterns. Nevertheless, it performs better than other known approaches used for systems with periodic job arrivals.

We propose and analyze three routing algorithms for anycast packets: source-destination based routing with weighted random selection (SD/WRS); destination based routing with weighted random selection (D/WRS); and the shortest shortest path first (SSPF) algorithms. The SSPF algorithm is a simple extension to the traditional SPF algorithm for routing unicast packets. The SD/WRS and D/WRS algorithms explicitly take into account characteristics of anycast message traffic and its recipient group. As a result, our simulation study shows that both the SD/WRS and D/WRS algorithms perform much better than SSPF in terms of average end-to-end packet delay. In particular, SD/WRS performs very close to a dynamic optimal algorithm in most cases. Our algorithms are simple, efficient and compatible with the most of existing routing technologies. We also formally prove the loop free and correctness properties for our algorithms.

We study connection-oriented service in an FDDI-ATM-FDDI heterogeneous network for real-time applications. We design and analyze an algorithm for connection admission control (CAC) for such a network. Upon a request of connection establishment, the CAC determines if the worst case delays of the requesting and existing connections can be satisfied given the available network resources. If so, the CAC allocates appropriate network resources to the requesting connection. The process of allocating resources for homogeneous networks (e.g. FDDI-only or ATM-only) may not be applied directly to a heterogeneous network environment (e.g. FDDI-ATM-FDDI network) because heterogeneity adds more complexity to the process. Hence resource allocation in a heterogeneous network needs more careful analysis than its homogeneous counterpart. We propose a CAC algorithm that will, by proper parameter tuning, allocate sufficient but not excessive network resources to the requesting connection in an FDDI-ATM-FDDI network. We show that the system can achieve satisfactory performance with this CAC algorithm. Our approach is compatible with current network standards and hence can be readily used in practical systems.

We address the issues of stability in ATM networks. A network is stable if and only if all the packets have a bounded delay. We first consider ATM networks with an FCFS scheduling policy. We then study networks with a priority driven scheduling policy. For each network, we develop criteria for testing the stability of an ATM network and methods of deriving delay bounds in a stable network. In previous work, the Cruz-Gallager-Parekh (1991, 1992) ring has been a "benchmark" architecture to study the stability problem. For example, Gallager and Parerkh (1993) claimed that the ring with a size of no more than four switches is stable when the total utilization of the links is less than 100%. We validated this result. Furthermore, we find that a ring with large number of switches is stable if the utilization of each link is less than or equal to 73%.

Static priority scheduling is popular for traffic scheduling in ATM switches because it is less costly than dynamic priority scheduling while being sensitive to the delay constraints of connections. We study delay computation and priority assignment problems in an ATM network with static priority scheduling. Given an ATM network with arbitrary topology, it is possible that the traffic on it may become unstable (i.e., packet delays become unbounded) due to the potential cyclic dependency of the traffic. An unstable network is definitely unacceptable for many delay sensitive applications. We start by formally deriving a simple condition under which the network is guaranteed to be stable. We then develop a numerical method to compute worst case end to end delays in an ATM network with arbitrary topology. Convergence of the method is formally proved and a closed form for the computing error is obtained. Despite its advantages, static priority scheduling remains sensitive to proper priority assignment. We describe two simple priority assignment methods, which we show to outperform other commonly used methods.

We present an efficient and effective method to derive the worst case delay in an ATM switch. In an ATM switch, admitting a hard real-time connection requires the delays of cells belonging to the connection meeting their deadline without violating the guarantees already provided to connections that are currently active. Previous studies have shown that the real-time connection traffic and the available service can both be described by piecewise linear functions in terms of time. By utilizing the inverse of the arrival and service functions, we obtain an efficient and effective method to complete the worst case delay of a connection to an ATM switch. We analyze and compare the performance of an ATM switch with priority driven and FIFO scheduling policies under different utilization. We also compare the performance using our proposed integrated method with the traditional independent method. From simulation experiments, we found that our method always obtains a higher admission probability and a better estimation of cell delay within an ATM switch.

We study high performance networks with wormhole routing and investigate their performance in terms of meeting message delay constraints. Traditional system uses unregulated greedy transmission control. This may result in unfairness of network access and unbounded packet blocking time, making it very difficult to efficiently support real-time applications. To overcome this problem, we propose a regulated transmission control method in which packet transmission at the source is regulated and hence unnecessary network contention is eliminated The regulated method is a generalization of the unregulated method and can be easily implemented in most of the commercially available networks.

A CAC algorithm must efficiently determine if a new connection can be admitted by verifying that its QoS requirements can be met without violating those of previously admitted connections. In hard real-time systems, the QoS requirements are specified in terms of end-to-end cell deadlines and no cell loss due to buffer overflow. A CAC algorithm must account for interdependencies among connections caused by statistical multiplexing of cells in ATM networks. Arbitrarity of network topology may lead to cyclic dependencies among various connections. We present an efficient CAC algorithm that addresses the above issues. The algorithm uses a traffic descriptor called the maximum traffic rate function to effectively compute bounds on end-to-end delays of connections and buffer requirements within the network. Our work differs from most previous work in that it does not require traffic restoration inside the network.

For any connection admission control (CAC) algorithm to work correctly and efficiently, accurate information of the traffic flow out of the host systems is required. We develop several approximation approaches for modeling the traffic flows of hard real-time connections. We show that without accurate traffic characterization, the CAC algorithm may do either of the following: (1) admit connections that may cause network congestions which results in violating connection deadline requirements; or (2) pessimistically reject many connections whose QoS can be guaranteed. We propose a traffic approximation model that can characterize the traffic correctly and efficiently, achieving a higher admission probability. From our experimental data we observe that the source traffic from a typical host is bursty. This burstiness may cause congestion within the network. To overcome this problem, we propose and analyze a simple traffic regulation mechanism at the application layer. The performance evaluation data shows that in the regulated system the traffic burstiness is lower and the probability of a connection being admitted is higher than the unregulated system.

We study a new network architecture based on standard FDDI networks. This network, called FDDI-based reconfigurable network (FBRN), is constructed using multiple FDDI token rings and has the ability to reconfigure itself in the event of extensive damage to the network. Thus, an FBRN has the potential to provide high available bandwidth even in the presence of numerous faults. Realization of this potential depends crucially on a reconfiguration algorithm that guides the reconfiguration process. We design and analyze a reconfiguration algorithm for FBRNs. Our algorithm is optimal in the sense that it always produces a configuration that results in the maximum available bandwidth for a given fault pattern. This algorithm has a polynomial time complexity. We also show that the available bandwidth of an FBRN is dramatically improved with our reconfiguration algorithm.

We address the issue of guaranteeing the end-to-end deadlines of hard real-time connections in an ATM network. In an ATM network, a set of hard real-time connections can be admitted only if the end-to-end delays of cells belonging to individual connections are not more than their deadlines. We systematically decompose an ATM network into constant delay and variable delay servers to facilitate the delay analysis. Effective traffic description is the key part of such a process. We propose a comprehensive traffic description function that provides adequate information about the worst case traffic behavior of connections anywhere in the network. We also study some simple approximations of this function that perform reasonably well in practice. We analyze and compare the performance of ATM networks with FCFS and WRR link scheduling policies under different loading conditions.

In this paper, we address issues related to providing guaranteed real-time communication in ATM local area networks. We concentrate on output link scheduling because it plays a critical role in meeting message deadlines. We are particularly interested in the weighted round robin scheduling policy because of its simple design and implementation. To use weighted round robin scheduling for hard real-time applications, the weights must be properly allocated to each of the connections. We propose and analyze two weight allocation schemes. The first scheme is heuristic, and is easy to understand and implement. The second scheme is optimal. That is, it can always guarantee a set of hard real-time connections whenever it is possible to do so. We evaluate and compare the system performance in terms of its admission probability-the probability that deadlines of all connections in a randomly chosen connection set can be met. We find that the optimal weight allocation scheme indeed performs the best. However, the heuristic scheme performs closely to the optimal scheme over a wide range of loading conditions.

This paper considers the support of hard real-time connections in ATM networks. In an ATM network, a set of hard real-time connections can be admitted only if the worst case end-to-end delays of cells belonging to individual connections are less than their deadlines. Although there are several approaches to manage the network resources in order to meet the delay requirements of connections, we focus on the use of traffic regulation to achieve this objective. Leaky buckets provide simple and user-programmable means of traffic regulation. We design and analyse an efficient optimal algorithm for selecting the burst parameters of leaky buckets to meet connections' deadlines. Our algorithm is optimal in the sense that it always selects burst parameters to meet the delay requirements of hard real-time connections whenever some such assignment exists. The exponential size of the search space makes this problem a challenging one. Our algorithm is efficient and we observe a dramatic improvement in the system performance in terms of the connection admission probability when traffic is regulated using our algorithm.

We address the issue of guaranteeing application-to-application deadlines of messages in distributed real-time systems. Most of the previous studies have focused on either host subsystem or network subsystem. Our study considers the entire integrated system. We develop two methods to test whether the message deadlines are met. The first method called the independent method, obtains conservative estimates of message delays by independently analyzing each subsystem. This method is easy to use and efficient, but may sometimes give pessimistic results. The second method called the integrated method, computes the delays more accurately by modeling interactions among the subsystems in greater detail. Performance of the two methods is evaluated an terms of the probability of guaranteeing message sets for given host utilization.

FDDI-Based Reconfigurable Networks have an architecture that is suitable for delivering messages that have hard real-time constraints as well as certain fault-tolerance requirements. This architecture uses multiple FDDI networks to connect hosts and provides for automatic reconfiguration to maintain high network bandwidth in spite of faults. An important open problem is how resources in such networks should be managed in order to guarantee that the fault-tolerant real-time requirements of messages are met. This paper presents an efficient and practical solution to this problem. Our solution consists of off-line and on-line components. On-line management deals with run-time manipulation of messages and network resources. A message grouping approach simplifies on-line management. Off-line management deals with message grouping, bandwidth allocation and schedulability verification. Three approaches are investigated: spatial redundancy, temporal redundancy and an integrated approach. It is shown that the integrated approach has the best performance. Our solution is compatible with the FDDI and SAFENET standards.

Networks used in mission-critical applications must be highly fault-tolerant. The authors propose an FDDI-based reconfigurable network (FBRN) that can survive multiple faults. An FBRN consists of multiple FDDI trunk rings and has the ability to reconfigure itself in the face of extensive damage. They consider three classes of FBRNs depending on their degree of reconfigurability: N-FBRN (nonreconfigurable), P-FBRN (partially reconfigurable) and F-FBRN (fully reconfigurable). They analyze the performance of FBRNs in terms of their available bandwidth in the presence of faults. In mission-critical systems, it is not enough to ensure that the network is connected in spite of faults; the traffic carrying capacity of the network must be sufficient to guarantee the required quality of service. They present a probabilistic analysis of the available bandwidth of FBRNs given the number of faults. They find that a fully reconfigurable FBRN can provide a high available bandwidth even in the presence of a large number of faults. A partially reconfigurable FBRN is found to be an excellent compromise between high reliability and ease of implementation.>

We study the effect of the output link scheduling discipline of an ATM switch on the ability of an ATM LAN to admit real-time connections. Three output link scheduling policies are studied: first come first served (FCFS), round robin (RR), and packet-by-packet generalized processor sharing (PGPS). We derive connection admission criteria for the three scheduling policies. To evaluate the performance of the three scheduling policies, we introduce the metric of admission probability. The admission probability gives the probability that a randomly chosen set of real-time connections will be admitted into the network. The admission probability allows system designers to study the performance of different scheduling policies over a wide range of network loads. We observe that the performance of the three scheduling policies is sensitive to message deadlines. When the deadlines are small, PGPS outperforms both RR and FCFS, and RR outperforms FCFS. When the deadlines are large, all three scheduling policies perform the same. We also note that although PGPS is better than RR and FCFS most of the time, its improved performance is achieved at the cost of high implementation complexity and run time overheads.>

We study the problem of guaranteeing synchronous message deadlines in token ring networks where the timed token medium access control protocol is employed. Synchronous bandwidth, defined as the maximum time for which a node can transmit its synchronous messages every time it receives the token, is a key parameter in the control of synchronous message transmission. To ensure the transmission of synchronous messages before their deadlines, synchronous capacities must be properly allocated to individual nodes. We address the issue of appropriate allocation of the synchronous capacities. Several synchronous bandwidth allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of synchronous messages. We show that an inappropriate allocation of the synchronous capacities could cause message deadlines to be missed, even if the synchronous traffic is extremely low. We propose a scheme, called the normalized proportional allocation scheme, which can guarantee the synchronous message deadlines for synchronous traffic of up to 33% of available utilization.>

The problem of guaranteeing synchronous message deadlines in communication networks using the timed token medium access control protocol is studied. To ensure the transmission of synchronous messages before their deadlines, synchronous capacities must be properly allocated to individual nodes. A class of local synchronous capacity allocation schemes, which allocate the synchronous capacity to a node without using information about messages on the other nodes, is developed, analyzed, and evaluated in terms of the ability of the schemes to guarantee message deadlines. It is shown that one of the local allocation schemes proposed can achieve the same performance as that of the best global allocation scheme known to date.>

Issues related to guaranteeing synchronous messages with arbitrary deadline constraints in a fiber distributed data interface (FDDI) network are addressed. It is shown that several network parameters must be set carefully if message deadlines are to be satisfied. Message deadlines can only be met if sufficient synchronous bandwidth is allocated to each mode. Thus, proper synchronous bandwidth allocation is essential if deadlines are to be guaranteed. The target token rotation time (TTRT) determines both the speed of token circulation and the network utilization available to user applications. TTRT should also be chosen carefully to ensure that the token circulates fast enough while maintaining a high available utilization. Sufficient buffer space must be provided for outgoing messages, otherwise messages could be lost due to buffer overflow. An integrated method for allocating the synchronous bandwidth and selecting TTRT so that the time constraints of synchronous messages with arbitrary deadlines are guaranteed to be met is proposed and analyzed.

We study the performance of FDDI networks in terms of their guarantee probability, i.e., the probability that a set of synchronous messages are guaranteed to meet their deadlines. Traditional techniques such as queuing analysis cannot be directly used to derive the guarantee probability. To counter this problem, we develop a new geometric model of schedulability. Based on this model, we obtain a numerical method to compute the exact values of the guarantee probability. A closed-form approximation for the guarantee probability is also derived, and is shown to be relatively accurate and computationally efficient. The network performance is then systematically examined in terms of the guarantee probability. We find that there is a high probability that a randomly chosen message set can be guaranteed even when the real-time traffic is increased beyond the worst case achievable utilization bound. Hence, FDDI networks are applicable for real-time applications in a wide range of loading conditions.>

The problem of guaranteeing synchronous message deadlines in token ring networks in which the timed token medium access control protocol is used is discussed. Synchronous capacity, defined as the maximum time for which a node can transmit its synchronous messages every time it receives the token, is a key parameter in the control of synchronous message transmission. To ensure the transmission of synchronous messages before their deadlines, synchronous capacities must be properly allocated to individual nodes. Several synchronous capacity allocation schemes are analyzed in terms of their ability to satisfy deadline constraints of synchronous messages. It is shown that an inappropriate allocation of the synchronous capacities could cause message deadlines to be missed, even if the synchronous traffic is extremely low. The normalized proportional allocation scheme, which can guarantee the synchronous message deadlines for synchronous traffic of up to 33% of available utilization is proposed.>

Recent developments in real-time communications in local-area networks are reviewed. Issues relating to the transmission of both synchronous and asynchronous messages are examined. Priority-driven protocols, global reservation protocols, and protocols with bounded access times are discussed.>

The authors study the problem of transmitting synchronous messages before their deadlines in communication networks where the timed token medium access control protocol is employed. Synchronous capacity, defined as the maximum time for which a node can transmit its synchronous message every time it receives the token, is a key parameter in the control of synchronous message transmission. To ensure the transmission of synchronous messages before their deadlines, synchronous capacities must be property allocated to individual nodes. The authors develop and analyze an optimal synchronous capacity allocation scheme. An optimal scheme can allocate the synchronous capacities in such a way that the synchronous message deadlines are guaranteed if there exists any allocation scheme that can do so. The optimality of the allocation scheme proposed here is formally proved, and the bounds for its worst case achievable utilization are derived.>

When developing distributed scheduling algorithms such as communication protocols, issues in achieving optimal policy and minimizing overhead must be addressed. This problem is examined in the context of a specific distributed system-the token ring communication network. Three token ring protocols are considered which are representative of many existing ones in the sense that they incorporate message time constraints at different levels and implement the earliest deadline first transmission (scheduling) policy at different degrees with different overheads. Through a worst-case analysis, the performance of these three token ring protocols is compared. It is concluded that to evaluate a distributed scheduling algorithm such as a communication protocol, it is necessary to not only consider the scheduling policy employed but also to take into account the overhead incurred due to the implementation of the scheduling policy.>

An extended IEEE 802.5 protocol suitable for transmitting time-constrained messages in a token ring network is studied. It differs from traditional token ring protocols in that time constraints of messages are incorporated explicitly. In this protocol, the laxities of messages are mapped into priorities. The message with the highest priority is transmitted first. As a result, this protocol approximates the optimal minimum-laxity-first policy. It is found that in the worst case the protocol can send at least 50% of the messages sent by the optimal one. This ratio is independent of the number of priorities and the priority assignment function used in the protocol. On the other hand, simulation results show that the average performance of the protocol improves as the number of priorities increases and that a simple priority assignment function is sufficient to yield satisfactory performance.>

Version selection schemes for hard real-time communications in multiaccess networks are studied. Two classes of version selection schemes are proposed: those that are based on message time constraints and those that are based on the network traffic. The authors discuss the design and implementation of both classes of version selection schemes used in conjunction with a window-based media access protocol. Integrated version selection schemes that combine both the timing- and the traffic-based approaches are discussed. The simulation results show that as the network load increases, the version selection schemes are effective at reducing the message loss by trading off the proportion of long version messages sent.>

A classification scheme is proposed which divides real-time messages into three different classes according to the impact on system performance when the deadline of a message is missed. A study is made of several multiaccess protocols that take into account the time constraints of messages as well as their classifications and that are able to given an early notice when an important message will miss its deadline. The performances of these protocols are evaluated and compared through simulation.>

The authors propose and study a window protocol suitable for transmitting time-constrained messages in a multiaccess network. The protocol differs from traditional window protocols in that it explicitly takes time constraints into account. The window is formed on the basis of the latest time to send a message (LS). A major advantage of the window protocol is that a newly arriving message is immediately considered for transmission if its LS is less than that of all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation through simulation shows that the protocol performs well in a wide range of environments, including under overloaded conditions.>

A study is made of the performance of FCFS (first-come, first-served) and improved FCFS scheduling algorithms for dynamic real-time computer systems in which tasks arrive as a random process and each task has a laxity specifying the maximum time a task can wait for the service. The general solution for M/M/1 systems in which the FCFS or an improved FCFS scheduling algorithm is used is obtained. In particular, explicit expressions for the unfinished work distribution, the task loss ratio, and the CPU utilization for M/M/1+M systems are derived. The last M in M/M/1+M means that the task laxity is exponentially distributed. The steady-state performance of those systems depends not only on the offered load rho (as in the non-real-time arena), but also on the normalized mean laxity, which is equal to the mean laxity divided by the mean service time. An analysis also shows that using the improved FCFS scheduling algorithm results in significant improvement over using the original FCFS algorithm. In many circumstances, the improved FCFS has almost identical or very similar performance to that of the minimum-laxity-first (MLF) algorithm, which has been shown to be optimal. The advantage of the improved FCFS algorithm is that it takes O(1) time while the MLF algorithm needs O(log n) time.>

A set of four heuristic algorithms is presented to schedule tasks that have headlines and resource requirements in a distributed system. When a task arrives at a node, the local scheduler at that node attempts to guarantee that the task will complete execution on that node before its deadline. If the attempt fails, the scheduling components on individual nodes cooperate to determine which other node in the system has sufficient resource surplus to guarantee the task. Simulation studies are performed to compare the performance of these algorithms with respect to each other as well to two baselines. The first baseline is the noncooperative algorithm where a task that cannot be guaranteed locally is not sent to any other node. The second is an (ideal) algorithm that behaves exactly like the bidding algorithm but incurs no communication overheads. The simulation studies examine how communication delay, task laxity, load differences on the nodes, and task computation times affect the performance of the algorithms. The results show that distributed scheduling is effective even in a hard real-time environment and that the relative performance of these algorithms is a function of the system state.>

A novel window protocol for transmitting time-constrained messages in a multiaccess network is proposed that explicitly takes time constraints into account. The window is formed on the basis of latest time to send a message (LS). A newly arriving message is immediately considered for transmission if its LS is less than those of the all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation by simulation shows that the protocol performs well in a wide range of environments, even under overloaded conditions.>

We consider the problem of scheduling a set of n preemptable tasks in a system having r resources. Each task has an arbitrary, but known, worst case processing time and a deadline, and may request simultaneous use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this paper, we develop and evaluate algorithms for determining whether or not a set of preemptive tasks is schedulable in such a real-time system, and if so, determining a schedule for it. This scheduling problem is known to be computationally intensive. In many real-time application environments, tasks are scheduled dynamically, and hence the scheduling algorithms used must have low run-time costs. To keep run-time costs low, we propose the use of suboptimal but practical algorithms that employ computationally simple heuristics. The computational complexity of our algorithms for scheduling n tasks in a system having r resources is O(rn2), which is very much lower than that of known optimal algorithms. We report on the results of simulation studies performed on such heuristic preemptive scheduling algorithms and the sensitivity of the performance of the algorithms with respect to various scheduling parameters. These studies show that due to the complexity of the problem, straightforward heuristics do not perform satisfactorily. However, an algorithm that uses combinations of such heuristics in conjunction with limited backtracks works very well.

We study virtual time CSMA protocols for hard real time communication systems, i, e., systems where messages have explicit deadlines. In this class of CSMA protocols, each node maintains two clocks; a real time clock and a virtual time clock. Whenever a node finds the channel to be idle, it resets its virtual clock. The virtual clock then runs at a higher rate than the real clock. A node transmits a waiting message when the time on the virtual clock is equal to some parameter of the message. Using different message parameters in conjunction with the virtual clock, different transmission policies can be implemented. In particular, use of message arrival time, message length, message laxity, and message deadline implements FCFS, Minimum-Length-First, Minimum-Laxity-First, and Minimum-Deadline-First transmission policies, respectively.

This paper describes a heuristic approach for solving the problem of dynamically scheduling tasks in a real-time system where tasks have deadlines and general resource requirements. The crux of our approach lies in the heuristic function used to select the task to be scheduled next. The heuristic function is composed of three weighted factors. These factors explicitly consider information about real-time constraints of tasks and their utilization of resources. Simulation studies show that the weights for the various factors in the heuristic function have to be fine-tuned in order to obtain a degree of success in the range of 75-88 percent of that obtained via exhaustive search. However, modifying the approach to use limited backtracking improves the degree of success substantially to as high as 99.5 percent. This improvement is observed even when the initial set of weights are not tailored for a particular set of tasks. Simulation studies also show that in most cases the schedule determined by the heuristic algorithm is optimal or close to optimal.