Textured high-fidelity 3D models are crucial for games, AR/VR, and film, but human-aligned evaluation methods still fall behind despite recent advances in 3D reconstruction and generation. Existing metrics, such as Chamfer Distance, often fail to align with how humans evaluate the fidelity of 3D shapes. Recent learning-based metrics attempt to improve this by relying on rendered images and 2D image quality metrics. However, these approaches face limitations due to incomplete structural coverage and sensitivity to viewpoint choices. Moreover, most methods are trained on synthetic distortions, which differ significantly from real-world distortions, resulting in a domain gap. To address these challenges, we propose a new fidelity evaluation method that is based directly on 3D meshes with texture, without relying on rendering. Our method, named Textured Geometry Evaluation TGE, jointly uses the geometry and color information to calculate the fidelity of the input textured mesh with comparison to a reference colored shape. To train and evaluate our metric, we design a human-annotated dataset with real-world distortions. Experiments show that TGE outperforms rendering-based and geometry-only methods on real-world distortion dataset.

Autonomous vehicles (AVs) rely on perception systems to detect surrounding objects using sensors such as cameras, LiDAR (Light Detection and Ranging), and millimeter-wave (mmWave) radar. However, recent studies have shown that attackers can deceive these systems by strategically placing adversarial objects (e.g., color patches, cardboard, or metal foil) in the driving environment. These attacks pose serious safety risks, yet existing defenses primarily focus on individual sensor modalities and lack generalizability across different sensing systems. To address this gap, we propose the first generalized defense mechanism capable of mitigating various attacks using adversarial objects. Our approach integrates real-time attack detection with trajectory adaptation, guiding the victim AV to positions where the attack is less effective. The defense mechanism combines a deep reinforcement learning (DRL)-based motion planning model, which dynamically adjusts the AV’s trajectory, with an uncertainty-aware filtering scheme that refines perception outputs to enhance detection robustness. Extensive experiments in both simulated and real-world environments demonstrate that our defense mechanism effectively mitigates adversarial object-based attacks across different sensing modalities and sensor fusion while maintaining safe and smooth driving behavior.

From the perspective of user experience, when optimizing resource provisioning in networks, we have to maximize social utility, which is an abstraction of what users can obtain from the service provided by a network. In quantum networks, unlike their counterparts, circuit-switched classical networks, (i) the utility obtained by a demand is not always concave for the number of Entanglement Connections (ECs) we provision to it; and (ii) each demand requires a different amount of quantum resources over each link along the path to establish an EC. As a result, the Social Utility Maximization (SUM) problem is more challenging than in classic circuit-switched networks. In this paper, we propose an approach also called SUM to maximize social utility in quantum networks by provisioning an appropriate number of ECs (and corresponding resources) to demands. We first formulate the SUM problem and analyze it based on Lagrangian relaxation and duality techniques. Accordingly, we derive the optimal EC provisioning scheme for a given Lagrangian multiplier, depending on whether the utility function of each demand is convex, concave, or sigmoid-like. After that, a primal-dual iteration algorithm is proposed to determine the optimal EC provisioning scheme to maximize social utility. We conduct extensive simulations to demonstrate that SUM outperforms the state-of-the-art approach to maximizing quantum network throughput,i.e., EFiRAP, by up to 58.4%.

Decentralized federated learning (DFL) has gained popularity for training machine learning models on massive data in edge computing, as it avoids the potential bottleneck of conventional parameter server architectures. However, the existing DFL solutions typically use deterministic topologies that struggle with both system heterogeneity and non-IID local data, resulting in high bandwidth costs and slow convergence rates. In this paper, we propose a novel mechanism called Communication-efficient Decentralized Federated Learning (CedFL) to accelerate model training. InCedFL, each worker will communicate with each of its neighbors (i.e., model exchange) according to a certain probability at each epoch, so as to reduce bandwidth consumption. To this end, we then propose an efficient algorithm to adaptively determine the optimal probability for each worker pair according to real-time system situations (e.g., data distribution and bandwidth resource). Our proposed mechanism has been extensively tested on classical models and datasets, and the results demonstrate its high effectiveness.CedFLhas been shown to reduce completion time for model training by approximately 55% and improve test accuracy by 11% under the bandwidth constraint, compared to state-of-the-art solutions.

Conventional entanglement routing approaches decide the Entanglement Paths (EPs) to establish Entanglement Connections (ECs) before trying to create Entanglement Links (ELs). By doing so, very few EL failures will result in a low network throughput. In this paper, we study how to choose the EPs to establish ECs after knowing which ELs are successfully created. This is called the Deferred EP Selection (DEPS) problem. DEPS is a generalized integer multi-commodity flow problem and we cannot solve it quickly with conventional optimization methods. To address this issue, we propose a Deep Reinforcement Learning based EP Selection (DRLEPS) approach. The salient features of DRLEPS include (i) by controlling the number of candidate EPs, DRLEPS can achieve a trade-off between time complexity and the EC establishment rate; and (ii) using candidate EPs as input, DRLEPS is robust to request variation; and (iii) by training neural networks with different topologies, a model derived by DRLEPS can be applied to various networks (even with a different number of nodes) without fine-tune. Through extensive simulations, we show that even in a network with 200 nodes, DRLEPS can solve the DEPS problem in 0.39 seconds with a Nvidia GeForce 3090 GPU. It outperforms the approach always establishing ECs through the EP with the largest success probability by up to 23.4% in EC establishment rate. It also outperforms the Integer Linear Programming (ILP) based scheme, which can achieve the maximum EC establishment rate, by up to 184.2x in network throughput.

Quantum Key Distribution (QKD) is considered to be the ultimate solution to communication security. However, current QKD devices, especially quantum photon sources, are expensive, and they can generate secret keys only at a low rate. In this paper, we first consider homogeneous trusted-relay-based QKD networks where every request has the same amount of secret key requirement and every photon source has the same key distribution rate, and design an approach named RPSP to not only minimize the number of photon sources needed in a network to ensure at least one feasible relay path exists for any potential QKD requests but also save the time to complete a batch of QKD requests by jointly optimizing the routing of relay paths and the provisioning of photon sources to distribute secret keys. Then, we extend RPSP to RPSP-HN which can be applied to heterogeneous networks where requests have different secret key requirements and photon sources distribute keys at different rates. Furthermore, we also extend RPSP to RPSP-HY, which considers that some of the nodes in a network is untrusted. Compared with existing works, RPSP and its extensions focus on more practical scenarios where only some of the nodes are equipped with photon sources and they leverage optical switching to enable dynamic photon source provisioning such that we can utilize QKD devices more efficiently. Extensive simulations show that compared with baseline schemes, RPSP, RPSP-HN, and RPSP-HY can save up to 33%, 37%, and 25% of the time to complete a batch of QKD requests in homogeneous, heterogeneous, and hybrid QKD networks, respectively.

Entanglement routing plays a vital role in supporting various applications in quantum networks. Existing works on entanglement routing either ignored the Entangled Photon Source (EPS) placement issue or simply assumed a pool of EPSes at a centralized location that can provision entanglement over arbitrary quantum links. In this paper, we propose LIGHTER and fidelity-aware LIGHTER (named F-LIGHTER) to solve the joint EPS placement and entanglement routing problem based on the assumption that EPSes are co-located with quantum nodes and each EPS can send one entangled photon at a time to one of its adjacent nodes only. The salient features of LIGHTER and F-LIGHTER include (i) LIGHTER and F-LIGHTER use a demand-agnostic EPS placement scheme to maximize network throughput and fairness for all feasible Entanglement Connection EC) establishment demands, and (ii) most requested ECs can be established over Entanglement Paths (EPs) determined offline, and only a small percentage of them will be established over online calculated EPs, resulting in fast and efficient entanglement routing. Extensive simulations show that compared with schemes without proper EPS placement or entanglement routing, LIGHTER can improve the network throughput by up to 175.6% and 37.0%, respectively. When the fidelity is considered, the network throughput improvement achieved by F-LIGHTER will be up to 135.0% and 21.5%, respectively.

Edge inference is a technology that enables real-time data processing and analysis on clients near the data source. To ensure compliance with the Service-Level Objectives (SLOs), such as a 30% latency reduction target, caching is usually adopted to reduce redundant computations in inference tasks on stream data. Due to task and data correlations, sharing cache information among clients can improve the inference performance. However, the non-independent and identically distributed (non-IID) nature of data across different clients and the long-tail distributions, where some classes have significantly more samples than others, will reduce cache hit ratios and increase latency. To address the aforementioned challenges, we propose an efficient inference framework, CoCa, which leverages a multi-client collaborative caching mechanism to accelerate edge inference. On the client side, the model is pre-set with multiple cache layers to achieve a quick inference. During inference, the model performs sequential lookups at cache layers activated by the edge server. On the server side, CoCa uses a two-dimensional global cache to periodically aggregate information from clients, mitigating the effects of non-IID data. For client cache allocation, CoCa first evaluates the importance of classes based on how frequently and recently their samples have been accessed. CoCa then selects frequently recurring classes to address long-tail distribution challenges. Finally, CoCa dynamically activates cache layers to balance lookup overhead and accuracy. Extensive experiments demonstrate that CoCa reduces inference latency by 23.0% to 45.2% on the VGG, ResNet and AST models with a slight loss of accuracy.

Inspecting the undercarriage of used vehicles is a labor-intensive task that requires inspectors to crouch or crawl underneath each vehicle to thoroughly examine it. Additionally, online buyers rarely see undercarriage photos. We present an end-to-end pipeline that utilizes a three-camera rig to capture videos of the undercarriage as the vehicle drives over it, and produces an interactive 3D model of the undercarriage. The 3D model enables inspectors and customers to rotate, zoom, and slice through the undercarriage, allowing them to detect rust, leaks, or impact damage in seconds, thereby improving both workplace safety and buyer confidence. Our primary contribution is a rig-aware Structure-from-Motion (SfM) pipeline specifically designed to overcome the challenges of wide-angle lens distortion and low-parallax scenes. Our method overcomes the challenges of wide-angle lens distortion and low-parallax scenes by integrating precise camera calibration, synchronized video streams, and strong geometric priors from the camera rig. We use a constrained matching strategy with learned components, the DISK feature extractor, and the attention-based LightGlue matcher to generate high-quality sparse point clouds that are often unattainable with standard SfM pipelines. These point clouds seed the Gaussian splatting process to generate photorealistic undercarriage models that render in real-time. Our experiments and ablation studies demonstrate that our design choices are essential to achieve state-of-the-art quality.

Adversarial attacks with real objects or lasers on car-borne LiDAR-based object detection are concerning. The existing defense approaches are often designed to address specific attacks and short of considering adaptive attackers who may adapt based on all available information about the deployed defense to maximize attack effect. This paper proposes Hyper3Def, a new defense for the function of detecting vehicle objects, which uses a Hypernet to generate an ensemble of multiple new detection models when needed at run time. The detection results of these models are fused to give the final result. As a dynamic defense, Hyper3Def revokes an important basis of the adaptive attack, i.e., the object detection model is needed to plan effective adversarial perturbations. Evaluation based on open data and real-world experiments with embedded system implementation show that, when confronting adaptive attacks, Hyper3Def outperforms various baseline defenses including the adversarial training, which is often cited as the state of the art.

Towards intelligent image editing, object removal should eliminate both the target object and its causal visual artifacts, such as shadows and reflections. However, existing image appearance-based methods either follow strictly mask-aligned training and fail to remove these casual effects which are not explicitly masked, or adopt loosely mask-aligned strategies that lack controllability and may unintentionally over-erase other objects. We identify that these limitations stem from ignoring the causal relationship between an object’s geometry presence and its visual effects. To address this limitation, we propose a geometry-aware two-stage framework that decouples object removal into (1) geometry removal and (2) appearance rendering. In the first stage, we remove the object directly from the geometry (e.g., depth) using strictly mask-aligned supervision, enabling structure-aware editing with strong geometric constraints. In the second stage, we render a photorealistic RGB image conditioned on the updated geometry, where causal visual effects are considered implicitly as a result of the modified 3D geometry. To guide learning in the geometry removal stage, we introduce a preference-driven objective based on positive and negative sample pairs, encouraging the model to remove objects as well as their causal visual artifacts while avoiding new structural insertions. Extensive experiments demonstrate that our method achieves state-of-the-art performance in removing both objects and their associated artifacts on two popular benchmarks. The project page is available at https://buxiangzhiren.github.io/GeoRemover.

In automated warehouses, efficient management and economic benefits hinge on the effective scheduling of automated guided vehicles (AGVs) to transport diverse packets. Emerging technologies such as artificial intelligence and automation control have greatly contributed to the development of packet transport schemes for AGVs. However, the development of the logistics industry results in a massive amount of packets with diverse deadlines, which brings new challenges for the AGV scheduling system. To address this, this paper treats each AGV as an agent and designs a novel hierarchical transformer reinforcement learning (HTRL) framework to generate efficient AGV scheduling policies. Specifically, this framework consists of one encoder and two decoders to produce the packet selection and path improvement actions. These two decoders are equipped with masked self-attention mechanisms to learn efficient packet selection and path improvement policies, facilitating AGV transport efficiency to meet the deadlines of packets. Moreover, we consider the kinetic features of AGVs and design a model predictive control (MPC)-based speed control method for AGVs to prevent frequent stop-and-wait of AGVs and enhance their transport efficiency. We build up a simulated warehouse environment containing packets with different deadlines and conduct extensive experiments. Experimental results validate that the proposed HTRL framework increases the delivered packets within expiration by up to 36.6% compared to other baselines.

Abstract Large multimodal language models (MLLMs) such as GPT-4V and GPT-4o have achieved remarkable advancements in understanding and generating multimodal content, showcasing superior quality and capabilities across diverse tasks. However, their deployment faces significant challenges, including slow inference, high computational cost, and impracticality for on-device applications. In contrast, the emergence of small MLLMs, exemplified by the LLava-series models and Phi-3-Vision, offers promising alternatives with faster inference, reduced deployment costs, and the ability to handle domain-specific scenarios. Despite their growing presence, the capability boundaries between large and small MLLMs remain underexplored. In this work, we conduct a systematic and comprehensive evaluation to benchmark both small and large MLLMs, spanning general capabilities such as object recognition, temporal reasoning, and multimodal comprehension, as well as real-world applications in domains like industry and automotive. Our evaluation reveals that small MLLMs can achieve comparable performance to large models in specific scenarios but lag significantly in complex tasks requiring deeper reasoning or nuanced understanding. Furthermore, we identify common failure cases in both small and large MLLMs, highlighting domains where even state-of-the-art models struggle. We hope our findings will guide the research community in pushing the quality boundaries of MLLMs, advancing their usability and effectiveness across diverse applications.

We introduce pluralistic salient object detection (PSOD), a novel task aimed at generating multiple plausible salient segmentation results for a given input image. Unlike conventional SOD methods that produce a single segmentation mask for salient objects, this new setting recognizes the inherent complexity of real-world images, comprising multiple objects, and the ambiguity in defining salient objects due to different user intentions. To study this task, we present two new SOD datasets "DUTS-MM" and "DUTS-MQ", along with newly designed evaluation metrics. DUTS-MM builds upon the DUTS dataset but enriches the ground-truth mask annotations from three aspects which 1) improves the mask quality especially for boundary and fine-grained structures; 2) alleviates the annotation inconsistency issue; and 3) provides multiple ground-truth masks for images with saliency ambiguity. DUTS-MQ consists of approximately 100K image-mask pairs with human-annotated preference scores, enabling the learning of real human preferences in measuring mask quality. Building upon these two datasets, we propose a simple yet effective pluralistic SOD baseline based on a Mixture-of-Experts (MOE) design. Equipped with two prediction heads, it simultaneously predicts multiple masks using different query prompts and predicts human preference scores for each mask candidate. Extensive experiments and analyses underscore the significance of our proposed datasets and affirm the effectiveness of our PSOD framework.

Effective multi-intersection collaboration is crucial for mitigating urban traffic congestion through reinforcement learning (RL)-based traffic signal control (TSC). Existing work mainly considers scenarios involving a single vehicle type, where cooperation is typically limited to neighboring intersections. However, in urban traffic scenarios where high priority vehicles coexist with ordinary vehicles, considering only a limited number of neighboring nodes may be insufficient to ensure the swift passage of high priority vehicles while minimizing the impact on overall traffic efficiency. Therefore, we formulate the multiple intersections’ decision-making process in urban scenarios as a Markov game and propose a novel centralized cooperative RL framework called MATLIT to solve the game. Specifically, we adopt a multi-agent transformer (MAT)-based architecture that facilitates efficient global cooperation among intersections. The attention mechanism and auto-regressive process of the MAT effectively mitigate the curse of the dimensionality problem, which guarantees MATLIT to tackle large-scale traffic scenarios. Meanwhile, the stability and sequence action generation capacity of the MAT-based architecture is further enhanced by incorporating MAT with a gated mechanism. Furthermore, considering the inherent topological constraints in urban traffic scenarios, we utilize graph attention networks (GATs) to capture graph-structured mutual influences. Additionally, in response to the urban traffic scenarios with various types of high priority vehicles that have time-varying priorities, we integrate the soft actor-critic (SAC) algorithm to enhance the exploration capabilities of our framework, allowing it to learn robust strategies in heterogeneous traffic conditions. Extensive experiments demonstrate that our proposed MATLIT framework outperforms all baselines and can reduce high priority vehicles’ waiting time by 24.57% while reducing the average waiting time of all vehicles by 18.51% in realistic urban scenarios.

Federated Learning (FL) enables distributed clients to collaboratively train models without exposing their private data. However, it is difficult to implement efficient FL due to limited resources. Most existing works compress the transmitted gradients or prune the global model to reduce the resource cost, but leave the compressed or pruned parameters under-optimized, which degrades the training performance. To address this issue, the neural composition technique constructs size-adjustable models by composing low-rank tensors, allowing every parameter in the global model to learn the knowledge from all clients. Nevertheless, some tensors can only be optimized by a small fraction of clients, thus the global model may get insufficient training, leading to a long completion time, especially in heterogeneous edge scenarios. To this end, we enhance the neural composition technique, enabling all parameters to be fully trained. Further, we propose a lightweight FL framework, called Heroes, with enhanced neural composition and adaptive local update. A greedy-based algorithm is designed to adaptively assign the proper tensors and local update frequencies for participating clients according to their heterogeneous capabilities and resource budgets. On this basis, we further propose an extension of Heroes, termed AdaHeroes, which further improves the training performance under the statistical heterogeneity scenario based on an adaptive client selection strategy. Extensive experiments demonstrate that Heroes can reduce traffic consumption by about 72.46% and provide up to$2.76\times $speedup compared to the baselines. Furthermore, with the setting of statistical heterogeneity, AdaHeroes can improve the test accuracy by about 4.77% compared with Heroes and the baselines.

Quantum Networks (QNs) typically leverage teleportation to send quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one Entanglement Connection (EC) between Alice and Bob needs to be established. Accordingly, we have to concurrently establish as many requested ECs as possible in order to maximize the network throughput. Conventional methods either assumed a known traffic matrix and calculated the Entanglement Paths (EPs) for all requests in one batch or maximized the number of ECs established between all Source-Destination (SD) pairs without considering the amount of data qubits to be teleported. These methods are not scalable in large scale QNs since it is time consuming to calculate the EPs for a batch of requests. In addition, there may be only very few data qubits to be teleported between some SD pairs. Accordingly, the latter method may establish many useless ECs. To address these issues, we propose a Dynamic Entanglement Routing (DER) scheme which determines the EPs based on stream processing. By introducing a method to derive an appropriate purification scheme along each EP, we further extend DER to Dynamic Entanglement Routing with Purification (DERP) that provides fidelity guarantee to the established ECs. Through extensive simulations, we demonstrate that DER outperforms two representative heuristics by up to 52.79% and 61.27%, respectively, in terms of average request completion time and when we have to ensure the fidelity of the established ECs, this performance improvement will become 21.05% and 48.67%, respectively, if DERP is adopted.

Entanglement routing plays a vital role in distributed quantum computing and quantum networks. Previous works on entanglement routing have addressed several design challenges due to limited quantum resources, failures to establish entanglement, and decoherence of established entanglement, but considered neither the limitations imposed by having a limited number of entangled photon sources (EPSes), nor the benefits of using all-optical (or quantum) switching to distribute entangled photons. In this paper, we first explore the problem of jointly optimizing entanglement routing and EPS assignment, assuming no all-optical switching capability. In other words, a pair of entangled photons generated by one EPS can be distributed to two neighboring quantum nodes. We then relax the above assumption so as to allow a pair of entangled photons generated by one EPS to be distributed to non-adjacent nodes using all-optical switching. We propose two corresponding solutions, namely, entanglement routing and EPS assignment (or ERSA), and ERSA with all-optical switching-based distribution (or ERSA+D) that aim to maximize the number of entanglement connections between the given set of source-destination (SD) pairs while avoiding starvation and achieving fairness among the SD pairs. In order to obtain efficient solutions in a large discrete solution space in a timely manner, we first formulate each optimization problem as an Integer Linear Programming (ILP), and then propose efficient algorithms to derive near-optimal solutions based on relaxation, Lagrangian decomposition, duality iteration, and rounding techniques. Extensive simulations show that ERSA+D can increase network throughput by up to 1652% and 113%, respectively, thanks to EPS assignment optimization, and all-optical switching based entanglement distribution.

Entanglement routing in quantum data networks plays a vital role to support various quantum applications. Existing works on entanglement routing either ignored the Entangled Photon Source (EPS) placement issue or simply assumed a pool of EPSes at a centralized location that can provision entanglement over arbitrary quantum links. In this paper, we propose LightER to solve the joint EPS placement and entanglement routing problem based on the assumption that EPSes are distributed over a quantum network, where an EPS, which is co-located with a quantum node, can send one entangled photon at a time to one of the adjacent nodes only. The salient features of LightER include (i) LightER uses a demand-agnostic EPS placement scheme to maximize network throughput and fairness for all feasible entanglement connection (EC) establishment demands, and (ii) most of the requested ECs can be established over their corresponding Entanglement Paths (EPs) determined offline, and only a small percentage of the ECs will be established over EPs that need to be calculated online, resulting in fast and efficient entanglement routing. Extensive simulations show that compared with schemes without proper EPS placement or entanglement routing, LightER can improve the network throughput by up to 215% and 56.2%, respectively.

Federated learning (FL) provides a distributed framework for multiple clients to collaboratively train models without exposing raw data. Most FL research assumes that all clients have fully labeled data, which is impractical for many real-world applications. To this end, we focus on semi-supervised FL (SSFL), where data samples of each client are partially labeled. However, existing SSFL methods ignore two inherent characteristics of FL: limited communication resources and heterogeneous data distribution, which severely hinder convergence stability and efficiency. This paper proposes a novel SSFL mechanism, called FedAC, to address the above two challenges by alternating client-to-client (C2C) collaboration. Specifically, we group all clients using different clustering strategies at two different training stages. During each global round, FedAC first performs similarity clustering based on local data distribution, which gathers the knowledge from similar clients to generate high-quality pseudo-labels for unlabeled data. Then the clients are re-grouped using dissimilarity clustering strategy to approximate the IID setting at the cluster level, thereby alleviating the bias induced by Non-IID data. FedAC adopts a reinforcement learning algorithm to achieve a balance between labeling assistance from similar clients and unbiased optimization from dissimilar clients. Extensive evaluations demonstrate that FedAC can improve model accuracy and save up to 59.65% of communication costs compared with existing benchmarks.

Recently, federated learning (FL) has emerged as a popular technique for edge AI to mine valuable knowledge in edge computing (EC) systems. To boost the performance of AI applications, large-scale models have received increasing attention due to their excellent generalized abilities. However, training and transmitting large-scale models will incur significant computing and communication burden on the resource-constrained workers, and the exchange of entire models may violate model privacy. To relax the burden of workers and protect model privacy, split federated learning (SFL) has been released by integrating both data and model parallelism. Despite resource limitations, SFL also faces two other critical challenges in EC systems, i.e., statistical heterogeneity and system heterogeneity. In order to address these challenges, we propose a novel SFL framework, termed MergeSFL, by incorporating feature merging and batch size regulation in SFL. Concretely, feature merging aims to merge the features from workers into a mixed feature sequence, which is approximately equivalent to the features derived from IID data and is employed to promote model accuracy. While batch size regulation aims to assign diverse and suitable batch sizes for heterogeneous workers to improve training efficiency. Moreover, MergeSFL explores to jointly optimize these two strategies upon their coupled relationship to better enhance the performance of SFL. Extensive experiments are conducted on a physical platform with 80 NVIDIA Jetson edge devices, and the experimental results show that MergeSFL can improve the final model accuracy by 5.82% to 26.22%, with a speedup by about 1.39x to 4.14x, compared to the baselines.

Efficient entanglement routing in Quantum Data Networks (QDNs) is essential in order to concurrently establish as many Entanglement Connections (ECs) as possible, which in turn maximizes the network throughput. In this work, we consider a new class of QDNs with wavelength division multiplexed (WDM) quantum links where each quantum repeater will perform entanglement swapping by measuring two photonic qubits coming from some entangled photon sources directly on the same wavelength. To address unique challenges in achieving a high network throughput in such QDNs, we propose QuRWA to jointly optimize the entanglement routing and wavelength assignment. To this end, we introduce a key concept named Co-Path to improve fault-tolerance: all ELs in a Co-Path set will be assigned the same wavelength and this may serve as backup for some other ELs in the same Co-Path when establishing ECs. We design efficient algorithms to optimize the Co-Path selection and wavelength assignment to maximize resource utilization and fault tolerance. Extensive simulations demonstrate that compared with the methods without introducing Co-Path, QuRWA improves the network throughput by up to 122%.

Quantum Key Distribution (QKD) is considered to be an ultimate solution to communication security. However, current QKD devices, especially quantum photon sources, are expensive, and they can generate secret keys only at a low rate. In this paper, we design a system named RPSP for trusted relay-based QKD networks to not only minimize the number of photon sources needed in a network to ensure at least one feasible relay path exists for any potential QKD requests but also save the time to complete a batch of end-to-end QKD requests by jointly optimizing the routing of relay paths and the provisioning of photon sources along each relay path. Compared with existing works, RPSP focuses on a more practical scenario where only some of the nodes are equipped with photon sources and it leverages optical switching to enable dynamic photon source provisioning such that we can utilize such QKD devices in a more efficient way. Extensive simulations show that compared with baseline schemes, RPSP can save up to 87% of the photon sources needed in a trusted relay based QKD network, and 36% of the time to complete a batch of QKD requests.

In Distributed Quantum Computing (DQC), quantum bits (qubits) used in a task may be distributed on multiple Quantum Computers (QCs) connected by a Quantum Data Network (QDN). When we have to perform a quantum gate operation involving two qubits on different QCs, an Entanglement Connection (EC) has to be established between these two QCs. Since quantum gate operations can be performed at the data speed, the completion time of a DQC task is dominated by the time to establish ECs.To minimize the DQC task completion time, we propose QuPEP to jointly optimize data qubit (i.e., dbit) placement (that determines the number of ECs we have to establish between each pair of QCs) and entangled qubit (i.e., ebit) provisioning (that minimizes the time to establish each EC). QuPEP has an offline algorithm to optimize the dbit placement based on Genetic Simulated Annealing (GSA) and an online algorithm to optimize ebit provisioning based on Lagrange’s relaxation and the stochastic gradient descent method. By setting the fitness of each chromosome in GSA as the minimum DQC task completion time that can be achieved by the proposed online ebit provisioning scheme, QuPEP joints dbit placement and ebit provisioning. Extensive simulations show that compared with only optimizing dbit placement or ebit provisioning, QuPEP can reduce the DQC task completion time by up to 38% and 95%, respectively.

Mobile devices contribute more than half of the world's web traffic, providing massive and diverse data for powering various federated learning (FL) applications. In order to avoid the communication bottleneck on the parameter server (PS) and accelerate the training of large-scale models on resource-constraint workers in edge computing (EC) system, we propose a novel split federated learning (SFL) framework, termed ParallelSFL. Concretely, we split an entire model into a bottom submodel and a top submodel, and divide participating workers into multiple clusters, each of which collaboratively performs the SFL training procedure and exchanges entire models with the PS. However, considering the statistical and system heterogeneity in edge systems, it is challenging to arrange suitable workers to specific clusters for efficient model training. To address these challenges, we carefully develop an effective clustering strategy by optimizing a utility function related to training efficiency and model accuracy. Specifically, ParallelSFL partitions workers into different clusters under the heterogeneity restrictions, thereby promoting model accuracy as well as training efficiency. Meanwhile, ParallelSFL assigns diverse and appropriate local updating frequencies for each cluster to further address system heterogeneity. Extensive experiments are conducted on a physical platform with 80 NVIDIA Jetson devices, and the experimental results show that ParallelSFL can reduce the traffic consumption by at least 21%, speed up the model training by at least 1.36X, and improve model accuracy by at least 5% in heterogeneous scenarios, compared to the baselines.

Multi-sensor fusion has been widely used by autonomous vehicles (AVs) to integrate the perception results from different sensing modalities including LiDAR, camera and radar. Despite the rapid development of multi-sensor fusion systems in autonomous driving, their vulnerability to malicious attacks have not been well studied. Although some prior works have studied the attacks against the perception systems of AVs, they only consider a single sensing modality or a camera-LiDAR fusion system, which can not attack the sensor fusion system based on LiDAR, camera, and radar. To fill this research gap, in this paper, we present the first study on the vulnerability of multi-sensor fusion systems that employ LiDAR, camera, and radar. Specifically, we propose a novel attack method that can simultaneously attack all three types of sensing modalities using a single type of adversarial object. The adversarial object can be easily fabricated at low cost, and the proposed attack can be easily performed with high stealthiness and flexibility in practice. Extensive experiments based on a real-world AV testbed show that the proposed attack can continuously hide a target vehicle from the perception system of a victim AV using only two small adversarial objects.

Quantum Data Networks (QDNs) are vital to building Distributed Quantum Computing (DQC) systems. Though several communication protocols have been proposed for QDNs, most of them are at the network layer or below. The only transport layer protocol [1] used batch processing of requests for End-to-End (E2E) quantum data transmission. It not only limits the quantum resource utilization, more importantly, it cannot guarantee reliable E2E quantum data transmission. In this paper, we propose the first asynchronous transportation layer protocol, called AQTP, for QDNs to achieve high-speed and reliable E2E quantum data transmission. AQTP has several distinct features: (i) each quantum node locally allocates quantum resources in order to improve scalability; (ii) requests are processed in an asynchronous manner, which results in a higher quantum resource utilization; and (iii) it ensures reliable data transmission even if the teleportation operations fail. Extensive simulations show that compared with a batch processed transport layer protocol, AQTP can increase the network throughput by up to 82.97%, and reduce the Average Task Completion Time (ATCT) of DQC tasks by up to 94.69%.

Connected and Autonomous Vehicles (CAVs) hold great promise to transform our current transportation system to a safer, more resilient and efficient Cyber Transportation System (CTS) that integrates advanced sensing, communications and control based on IoT, V2X and AI/ML technologies. However, many open challenges related to modeling human-automation interaction, improving resiliency to adversarial conditions, and finding “killer” applications for CAVs remain. Above all, a national CAV safety certification based on AR/VR and digital twin technologies is a key to gaining public (and market) trust and acceptance. In this talk, I will briefly describe our past and current work to address the above research and development challenges, aiming to rally all stakeholders around the establishment of a national CAV certification center.

The emerging Federated Learning (FL) permits all workers (e.g., mobile devices) to cooperatively train a model using their local data at the network edge. In order to avoid the possible bottleneck of conventional parameter server architecture, the decentralized federated learning (DFL) is developed on the peer-to-peer (P2P) communication. In DFL, model exchanging among workers is usually regarded as an atomic operation, which largely affects the total bandwidth consumption during model training. Given the limited communication resource on workers, model exchanging will pose a great challenge when meeting with the large-scale models. Herein, we propose to let workers exchange theintermediate results, instead of the entire model, with each other. We provide theoretical analysis of DFL based on intermediate result exchanging, which reveals the relationship between the training performance and the exchanging interval (i.e., the number of local updating iterations) of intermediate results. According to the convergence bound, we propose an adaptive exchanging interval (or frequency) algorithm called Fed-IR, which optimizes the trade-off between communication cost and training performance. Extensive simulation results show that compared with the model exchanging methods, our proposed algorithms can save communication traffic of around 42%$\sim$81% while still achieving the similar accuracy.

The massive data from mobile and embedded devices have huge potential for training machine learning models. Decentralized machine learning (DML) can avoid the inherent bottleneck of the parameter server (PS) by collaboratively training models in a device-to-device (D2D) fashion. However, the previous DML works often assume that the local data are fully annotated with ground-truth labels, which is unrealistic for many Internet of Things (IoT) applications. This arises a new practical DML scenario, namely semi-supervised DML, where the local data of distributed workers are partially labeled in the D2D network. The existing semi-supervised learning techniques are proposed for standalone or the PS architecture, which ignore the impact of D2D topology on the performance of semi-supervised learning. Thus, they cannot adequately leverage the unlabeled data of decentralized workers, leading to performance degradation. Herein, we propose a novel framework, called SSD, to address the problem of semi-supervised DML by exploiting D2D cooperation. The key insight behind SSD is that neighbor selection has a crucial impact on pseudo-label quality and communication overhead. In SSD, each worker adaptively selects its neighbors with high-quality models and similar data distribution under communication resource constraints, which helps to generate high-confidence pseudo-labels for local unlabeled data and further boosts the DML performance. Extensive empirical evaluations on both testbed and simulated environments show that SSD significantly outperforms other baselines.

Federated learning (FL) has emerged as a promising distributed learning paradigm that enables a large number of mobile devices to cooperatively train a model without sharing their raw data. The iterative training process of FL incurs considerable computation and communication overhead. The workers participating in FL are usually heterogeneous and the workers with poor capabilities may become the bottleneck of model training. To address the challenges of resource overhead and system heterogeneity, this article proposes an efficient FL framework, called FedMP, that improves both computation and communication efficiency over heterogeneous workers through adaptive model pruning. We theoretically analyze the impact of pruning ratio on training performance, and employ a Multi-Armed Bandit based online learning algorithm to adaptively determine different pruning ratios for heterogeneous workers, even without any prior knowledge of their capabilities. As a result, each worker in FedMP can train and transmit the sub-model that fits its own capabilities, accelerating the training process without hurting model accuracy. To prevent the diverse structures of pruned models from affecting the training convergence, we further present a new parameter synchronization scheme, called Residual Recovery Synchronous Parallel (R2SP). Besides, our proposed framework can be extended to the peer-to-peer (P2P) setting. Extensive experiments on physical devices demonstrate that FedMP is effective for different heterogeneous scenarios and data distributions, and can provide up to 4.1× speedup compared to the existing FL methods.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing (EC). Aided by EC, decentralized federated learning (DFL), which overcomes the single-point-of-failure problem in the parameter server based federated learning, is becoming a practical and popular approach for machine learning over distributed data. However, DFL faces two critical challenges,i.e., system heterogeneity and statistical heterogeneity introduced by edge devices. To ensure fast convergence with the existence of slow edge devices, we present an efficient DFL method, termed FedHP, which integrates adaptive control of both local updating frequency and network topology to better support the heterogeneous participants. We establish a theoretical relationship between local updating frequency and network topology regarding model training performance and obtain a convergence upper bound. Upon the convergence bound, we propose an optimization algorithm that adaptively determines local updating frequencies and constructs the network topology, so as to speed up convergence and improve the model accuracy. We evaluate the performance of FedHP through extensive simulation and testbed experiments. Evaluation results show that the proposed FedHP can reduce the completion time by about 51% and improve model accuracy by at least 5% in heterogeneous scenarios, compared with the baselines.

A group ofconnected and autonomous vehicleswith common interests can drive in a cooperative manner, namely cooperative driving. In such a networked control system, an efficient message dissemination scheme is critical for cooperative drivings to periodically broadcast their kinetic status, i.e.,beacon. However, most existing researches are designed for a simple or specific scenario, e.g., ignoring the impacts of the complex communication environment and emerging hybrid traffic scenarios. Worse still, the inevitable message transmission interference and the limited interaction among vehicles in harsh communication environments seriously hinder cooperation among cooperative drivings and deteriorate the beaconing performance. In this paper, we formulate the decision-making process of cooperative drivings as a Markov game. Furthermore, we propose acooperative hierarchical attention reinforcement learning (CHA)framework to solve this Markov game. Specifically, the hierarchical structure of CHA leads cooperative drivings to be foresighted. Besides, we integrate each hierarchical level of CHA separately with graph attention networks to incorporate agents' mutual influences in the decision-making process. Moreover, each hierarchical level learns a cooperative reward function to motivate each agent to cooperate with others under harsh communication conditions. Finally, we set up a simulator and conduct extensive experiments to validate the effectiveness of CHA.

In real-world urban environments, hybrid and disorder traffic brings new challenges for the intelligent traffic light control system (ITLCS). Apart from coordinating traffic flows around intersections, the ITLCS is responsive to ensuring high priority vehicles pass through intersections quickly. To this end, we formulate the multiple intersections’ decision-making problem as a Semi-Markov game and propose amulti-agent attention double actor-critic (MAADAC)framework to solve this game, integrating theoptions frameworkwithgraph attention networks (GATs). Specifically, the options framework empowers agents to learn to make a long sequence of satisfactory decisions, such as keeping a reasonable phase for a short period to ensure high priority vehicles pass through intersections quickly. Besides, we adopt GATs to capture graph-structure mutual influences among agents. We set up a simulator based on real-world city road networks and conduct extensive experiments to evaluate the performance of MAADAC. The experimental results show that MAADAC can reduce high priority vehicles’ waiting time in the interval of 18.16%-38.14% versus the density of vehicles in real-world urban scenarios over several state-of-the-art approaches. Also, our framework can guarantee the passing efficiency of high priority vehicles under various traffic conditions with the change in the proportion of high priority vehicles.

Federated learning (FL) has recently gained tremendous attention in edge computing and Internet of Things, due to its capability of enabling distributed clients to cooperatively train models while keeping raw data locally. However, the existing works usually suffer from limited communication resources, dynamic network conditions and heterogeneous client properties, which hinder efficient FL. To simultaneously tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, FedCG introduces diversity to client selection and aims to select a representative client subset considering statistical heterogeneity. These selected clients are assigned different compression ratios based on heterogeneous and time-varying capabilities. After local training, they upload sparse model updates matching their capabilities for global aggregation, which can effectively reduce the communication cost and mitigate the straggler effect. More importantly, instead of naively combining client selection and gradient compression, we highlight that their decisions are tightly coupled and indicate the necessity of joint optimization. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. On this basis, we propose the quantized extension of FedCG, termed Q-FedCG, which further adjusts quantization levels based on gradient innovation. Extensive experiments on both real-world prototypes and simulations show that FedCG and its extension can provide up to 6.4× speedup.

In edge computing (EC), federated learning (FL) enables numerous distributed devices (or workers) to collaboratively train AI models without exposing their local data. Most works of FL adopt a predefined architecture on all participating workers for model training. However, since workers' local data distributions vary heavily in EC, the predefined architecture may not be the optimal choice for every worker. It is also unrealistic to manually design a high-performance architecture for each worker, which requires intense human expertise and effort. In order to tackle this challenge, neural architecture search (NAS) has been applied in FL to automate the architecture design process. Unfortunately, the existing federated NAS frameworks often suffer from the difficulties of system heterogeneity and resource limitation. To remedy this problem, we present a novel framework, termedPeaches, to achieve efficient searching and training in the resource-constrained EC system. Specifically, the local model of each worker is stacked by base cell and personal cell, where the base cell is shared by all workers to capture the common knowledge and the personal cell is customized for each worker to fit the local data. We determine the number of base cells, shared by all workers, according to the bandwidth budget on the parameters server. Besides, to relieve the data and system heterogeneity, we find the optimal number of personal cells for each worker based on its computing capability. In addition, we gradually prune the search space during training to mitigate the resource consumption. We evaluate the performance ofPeachesthrough extensive experiments, and the results show thatPeachescan achieve an average accuracy improvement of about 6.29% and up to 3.97× speed up compared with the baselines.

Data generated at the network edge can be processed locally by leveraging the emerging technology of Federated Learning (FL). However, non-IID local data will lead to degradation of model accuracy and the heterogeneity of edge nodes inevitably slows down model training efficiency. Moreover, to avoid the potential communication bottleneck in the parameter-server-based FL, we concentrate on the Decentralized Federated Learning (DFL) that performs distributed model training in Peer-to-Peer (P2P) manner. To address these challenges, we propose an asynchronous DFL system by incorporating neighbor selection and gradient push, termed AsyDFL. Specifically, we require each edge node to push gradients only to a subset of neighbors for resource efficiency. Herein, we first give a theoretical convergence analysis of AsyDFL under the complicated non-IID and heterogeneous scenario, and further design a priority-based algorithm to dynamically select neighbors for each edge node so as to achieve the trade-off between communication cost and model performance. We evaluate the performance of AsyDFL through extensive experiments on a physical platform with 30 NVIDIA Jetson edge devices. Evaluation results show that AsyDFL can reduce the communication cost by 57% and the completion time by about 35% for achieving the same test accuracy, and improve model accuracy by at least 6% under the non-IID scenario, compared to the baselines.

Recently, edge AI has been launched to mine and discover valuable knowledge at network edge. Federated Learning, as an emerging technique for edge AI, has been widely deployed to collaboratively train models on many end devices in data-parallel fashion. To alleviate the computation/communication burden on the resource-constrained workers (e.g., end devices) and protect user privacy, Spilt Federated Learning (SFL), which integrates both data parallelism and model parallelism in Edge Computing (EC), is becoming a practical and popular approach for model training over distributed data. However, apart from the resource limitation, SFL still faces two other critical challenges in EC, i.e., system heterogeneity and context dynamics. To overcome these challenges, we present an efficient SFL method, named AdaSFL, which controls both local updating frequency and batch size to better accelerate model training. We theoretically analyze the model convergence rate and obtain a convergence upper bound regarding local updating frequency given a fixed batch size. Upon this, we develop a control algorithm to determine adaptive local updating frequency and diverse batch sizes for heterogeneous workers to enhance the training efficiency. The experimental results show that AdaSFL can reduce the completion time by about 43% and the network traffic consumption by about 31% for achieving the similar test accuracy, compared to the baselines.

In a multi-tenant cloud, the cloud service provider (CSP) leases physical resources to tenants in the form of virtual machines (VMs) with an agreed service level agreement (SLA). As the most important indicator of SLA, we should guarantee the service availability of tenants when placing the VMs. However, previous works about VM placement mainly concentrate on optimizing the cloud resource utilization, but only a few works consider the service availability by measuring the hardware availability. In fact, abnormal tenants can make the corresponding service unavailable by launching network attacks. That is, both the hardware availability and the tenant uncertainty will affect the service availability of VMs on physical machines (PMs). Without considering this factor, the CSP may fail to meet the tenant’s SLA requirements, leading to a reduction in revenue. To solve such a problem, this paper considers the service availability in terms of both the hardware availability and the tenant uncertainty, and studies the service availability-guaranteed VM placement in multi-tenant clouds (SAG-VMP) problem. This problem is very challenging since the service availability actually changes with the tenants served on the PM. To address this issue, we propose a two-phase approach: PM assignment and VM placement. The first phase determines the availability of each PM through a long-term tenant-PM mapping algorithm and the second phase places each VM on a PM that meets the service availability requirement based on a primal-dual online algorithm. Two algorithms with bounded approximation factors are proposed for these two phases, respectively. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

With the increase in both the model size and dataset size of distributed training (DT) tasks, communication between the workers and parameter servers (PSs) in a cluster has become a bottleneck. In-network aggregation (INA) enabled by programmable switches has been proposed as a promising solution to alleviate the communication bottleneck. However, existing works focused on in-network aggregation implementation based on simple DT placement and fixed routing policies, which may lead to a large communication overhead and inefficient use of resources (e.g., storage, computing power and bandwidth). In this paper, we propose PARING, the first-of-its-kind INA approach that jointly optimizes DT task placement and routing in order to reduce traffic volume and minimize communication time. We formulate the problem as a nonlinear multi-objective mixed-integer programming problem, and prove its NP-Hardness. Based on the concept of Steiner trees, an algorithm with bounded approximation factors is proposed for this problem. Large-scale simulations show that our algorithm can reduce communication time by up to 81.0% and traffic volume by up to 19.1% compared to the state-of-the-art algorithms.

Distributed training includes two important operations: gradient transmission and gradient aggregation, which will consume massive bandwidth and computing resources. To achieve efficient distributed training, one must overcome two critical challenges: heterogeneity of bandwidth resources and limitation of computing resources among compute nodes. Existing architectures based on Parameter Server (PS) and All-Reduce (AR) fail to cope with these challenges because the PS will aggregate gradients from all workers and suffers from bandwidth bottlenecks, while AR intends to alleviate bandwidth bottlenecks at the PS, but the workers need to process many gradient packets thus can be overloaded. To address these shortcomings, we design a new distributed training system called ALEPH. In the control plane, ALEPH uses an efficient algorithm to group workers into clusters with different sizes so as to fully utilize heterogeneous bandwidth. We show that the proposed algorithm can achieve a good approximation performance. In the data plane, ALEPH leverages, for the first time, extended Berkeley Packet Filter (eBPF) programs to aggregate and forward gradient packets to reduce computation overhead. We show how to overcome several hurdles in using eBPF for distributed training. We implement ALEPH and evaluate its performance on a small-scale testbed and large-scale simulations. Experimental results show that ALEPH reduces training time by 20%-31% and increases bandwidth utilization by 88% compared with state-of-the-art frameworks.

There are two conventional methods to establish an entanglement connection in a Quantum Data Networks (QDN). One is to create single-hop entanglement links first and then connect them with quantum swapping, and the other is forwarding one of the entangled photons from one end to the other via all-optical switching at intermediate nodes to directly establish an entanglement connection. The two methods both have pros and cons. Respectively, the former method has a higher success probability of constructing entanglement link, but it would consume more quantum resources. The latter method, however, has a lower success probability to deliver a photon across multiple quantum links with fewer quantum resources. Accordingly, we are expecting to establish significantly more entanglement connections with limited quantum resources by first creating entanglement segments, each spanning multiple quantum link, using all-optical switching, and then connecting them with quantum swapping. In this paper, we design SEE, a Segmented Entanglement Establishment approach that seamlessly integrates quantum swapping and all-optical switching to maximize quantum network throughput. SEE first creates entanglement segments over one or multiple quantum links with all-optical switching, and then connect them with quantum swapping. Accordingly, SEE can theoretically outperform conventional entanglement link-based approaches. Large scale simulations show that SEE can achieve up to 100.00% larger throughput compared with the state-of-the-art entanglement link-based approaches, e.g., Redundant Entanglement Provisioning and Selection (REPS).

In autonomous driving, millimeter wave (mmWave) radar has been widely adopted for object detection because of its robustness and reliability under various weather and lighting conditions. For radar object detection, deep neural networks (DNNs) are becoming increasingly important because they are more robust and accurate, and can provide rich semantic information about the detected objects, which is critical for autonomous vehicles (AVs) to make decisions. However, recent studies have shown that DNNs are vulnerable to adversarial attacks. Despite the rapid development of DNN-based radar object detection models, there have been no studies on their vulnerability to adversarial attacks. Although some spoofing attack methods are proposed to attack the radar sensor by actively transmitting specific signals using some special devices, these attacks require sub-nanosecond-level synchronization between the devices and the radar and are very costly, which limits their practicability in real world. In addition, these attack methods can not effectively attack DNN-based radar object detection. To address the above problems, in this paper, we investigate the possibility of using a few adversarial objects to attack the DNN-based radar object detection models through passive reflection. These objects can be easily fabricated using 3D printing and metal foils at low cost. By placing these adversarial objects at some specific locations on a target vehicle, we can easily fool the victim AV's radar object detection model. The experimental results demonstrate that the attacker can achieve the attack goal by using only two adversarial objects and conceal them as car signs, which have good stealthiness and flexibility. To the best of our knowledge, this is the first study on the passive-reflection-based attacks against the DNN-based radar object detection models using low-cost, readily-available and easily concealable geometric shaped objects.

We envision a wide deployment of battery-operated edge devices such as data kiosk, to provide pervasive data collection and dissemination services. Although these data kiosks can be powered by green energy sources, their batteries may deplete overtime, and have to recharged frequently to prevent power outages and potential loss of critical data. In this paper, we propose an edge device recharging system using autonomous electric vehicles as Mobile Chargers (MCs). First, we determine the numbers and locations of Dispatching Centers (DCs) for these MCs, each of which will be responsible for recharging some edge devices in a surrounding area. Then, we plan optimal routes of the MCs in order to minimize the number of MCs needed to recharge all edge devices before a deadline. To reduce the time complexity involved in optimizing the routes, we cluster the edge devices and propose efficient algorithms to plan the route of MCs for each cluster based on the relaxation and rounding of a Mixed Integer Linear Programming (MILP) model. Extensive simulations show that our approach can reduce the number of MCs required to recharge all edge devices before a deadline by up to 71.93% compared with greedy-based heuristic algorithms.

Adversarial contrastive learning (ACL) is considered an effective way to improve the robustness of pre-trained models. In contrastive learning, a projector which consists of multilayer perceptron (MLP) will project high dimension 3D point cloud feature into low dimension for calculating contrastive loss during contrastive pretraining.We propose a novel method for generating high-quality 3D adversarial examples for adversarial training, which leverages the virtual adversarial loss with the feature representations prior to projection in a contrastive learning framework. To train the self-supervised contrastive learning framework adversarially, we introduce our robust aware loss function. Additionally, we show that incorporating high difference points using the Difference of Normal (DoN) operator as an additional input for adversarial self-supervised contrastive learning can significantly enhance the adversarial robustness of the pre-trained model. Our proposed method, POINTACL, is evaluated on several downstream tasks, including 3D classification and 3D segmentation using multiple datasets. Our experimental results demonstrate that POINTACL achieves state-of-the-art performance in terms of robust accuracy when compared to other contrastive adversarial learning methods.

In Federated Learning (FL), to improve the training efficiency, we don’t need to let all of the clients join in the training process. Instead, we can select some specific clients to join in the training. In particular, if some of these selected clients become problematic due to various reasons (e.g. shortage of power, poor internet connection, or being vulnerable to attacks) and thus could not successfully complete the training process, then we can discard those clients during training, in order to improve the efficiency. However, discarding those clients could increase the data source’s bias, because the data categories that contain those clients’ data would be underrepresented during the training process. To solve this problem, in this paper, we propose a robust client selection and replacement approach called RCSR. Using RCSR, we first cluster all clients according to their data distribution, and then use normal clients in the same cluster (with similar data distributions) to replace those problematic clients during training. We apply our methods to a couple of application scenarios in edge computing, and our results show that our methods can save training costs without affecting the accuracy.

The rapid growth of cloud services has brought a significant increase in inter-datacenter traffic. To transfer data among geographically distributed datacenters, cloud providers need to purchase bandwidth from ISPs. The data transferring cost has become one of the major expenses for cloud providers. Therefore, it is essential for a cloud provider to carefully allocate inter-datacenter traffic among the ISPs' links to minimize the costs. Exiting solutions mainly focus on the situations where all links adopt the same pricing scheme. However, in practice, ISPs usually provide multiple pricing schemes for their links due to market competition, which makes the existing solutions nonoptimal. Thus, a new traffic engineering approach that considers various pricing schemes is needed. This paper presents COIN, a new framework for cost-efficient traffic engineering with various pricing schemes. We propose a partition rounding traffic engineering algorithm based on linear independence analysis. The approximation factors and time complexity are formally analyzed. We further conduct large-scale simulations with real- world topologies and datasets. Extensive simulation results show that COIN can save the data transferring cost by up to 54.54% compared with the state-of-the-art solutions.

Entanglement routing plays a vital role in quantum networks. Previous works on entanglement routing did not note that all-optical switching capacity can be used to improve the network throughput or ignored that the placement of Entangled Photon Sources (EPS), another type of precious (and costly) quantum source, which also limits the network throughput. In this paper, we propose OptEPS to jointly optimize all-optical switching and EPS placement in entanglement routing to maximize the quantum network throughput. The main challenge of OptEPS lies in two folds: i). an entanglement may fail to be created; ii). the joint optimization problem suffers from a large time complexity. To overcome these challenges, we first formulate the joint optimization problem as a link-path based model and prune out some candidate paths in order to reduce the time complexity. Then, efficient algorithms are proposed to derive a near-optimal solution in a timely manner. Extensive simulations show that compared with the solutions ignoring EPS placement or without introducing all-optical switching, OptEPS will increase the network throughput by 1557% and 109%, respectively.

To distill more information from training data, more parameters are introduced into machine learning models. As a result, communication becomes the bottleneck of Distributed Machine Learning (DML) systems. To alleviate the communication resource contention among DML jobs, which prolongs the time to train machine learning models, in machine learning clusters, JointPS is proposed in this paper. JointPS first minimizes the completion time of a single training epoch for each DML job via jointly optimizing the parameter server placement and flow scheduling, and predicts the number of remaining training epochs for each DML job by leveraging a dynamic model fitting method. Then, JointPS can estimate the remaining time to complete each DML job. According to such estimation, JointPS schedules DML jobs following the Minimum Remaining Time First (MRTF) principle to minimize the average job completion time. To the best of our knowledge, JointPS should be the first work that minimizes the average completion time of network-intensive DML training jobs by jointly optimizing the parameter server placement and flow scheduling without modifying the DML models and training procedures. Through both testbed experiments and extensive simulations, we demonstrate that JointPS can reduce the average completion time of DML jobs by up to 88% compared with state-of-the-art technology.

To unleash the power of buses, we propose a bus-pooling system that keeps the notion of bus stops and terminals but discards the concept of fixed bus lines by enabling buses to choose the next stop or terminal based on orders submitted by passengers. Each bus, unlike a taxi, must consider the additional delays experienced by the passengers already on board when deciding how to adapt its route to serve new orders. This paper treats each bus as an agent and formulates the buses’ re-routing decision-making process as a Semi-Markov game. Then, we propose a novel double graph attention actor-critic (DGAAC) framework by integrating high-level and low-level actor-critics separately with graph attention networks (GATs) to solve the game. Specifically, GATs embedded in high-level and low-level critics take a large-scale graph covering a city-scale area as input and capture graph-structured mutual influences among buses. In contrast, the high-level and low-level actors equipped with GATs only take the n-hop sub-graph with local information as the input and are employed as the distributed decision module of each bus. We conduct extensive experiments on one of the largest real-world datasets in Shenzhen, China, and validate that the proposed DGAAC framework greatly outperforms all baselines.

With the broad deployment of distributed applications on clouds, east-west traffic is now dominating the majority of cloud networks. The existing communication solutions are tightly coupled with either the control plane (e.g., preprogrammed model) or the location of compute nodes (e.g., conventional gateway model). As a result, it is difficult to flexibly respond to the rapidly expanding networks and frequent abnormal events (e.g., burst traffic and device failures). Accordingly, they may not provide high-performance east-west forwarding while ensuring scalability and robustness. To address this issue, we design Zeta, a scalable and robust east-west forwarding framework with gateway clusters for hyperscale clouds. Zeta abstracts the traffic forwarding capability as a Gateway Cluster Layer, decoupled from the logic of control plane and the location of compute nodes. Specifically, Zeta adopts gateway clusters to support large-scale networks and cope with burst traffic. Moreover, a transparent Multi IPs Migration is proposed for fast recovery from unpredictable failures. We implement Zeta based on eXpress Data Path (XDP) and evaluate its scalability and robustness through comprehensive experiments with up to 100k container instances. Our evaluation shows that Zeta reduces the 99% RTT by$5.1 {\times }$in burst video traffic, and reduces the gateway pure recovery delay by$10.8 {\times }$compared with the state-of-the-art solutions.

Quantum computing holds great promise and this work proposes to use new quantum data networks (QDNs) to connect multiple small quantum computers to form a cluster. Such a QDN differs from existing quantum key distribution (QKD) networks in that the former must deliver data quantum bits (i.e., qubits) reliably between different quantum computers. Two families of QDNs are studied, one using teleportation, named Tele-QDN, and the other using tell-and-go (TAG), named TAG-QDN. In order to provide reliable delivery of data qubits, while addressing QDN-specific constraints imposed by quantum physics laws such as the no-cloning theorem, and limited availability of quantum memory, two corresponding transport layer protocols suitable for distributed implementation are designed and evaluated. Such distributed quantum transport protocols (DTPs), named Tele-DTP and TAG-DTP, are the first-of-its-kind and are complementary to existing works on the protocol stack for QDNs which are at the network layer and below. Both analysis and extensive simulations show that the proposed DTPs can achieve high throughput and fairness. This study also offers new insights into potential tradeoffs involved in using different types of QDNs.

Recently, mobile and embedded devices worldwide generate a massive amount of data at the network edge. To efficiently exploit the data from distributed devices, we concentrate on decentralized machine learning (DML), where the workers collaboratively train models under the peer-to-peer (P2P) setting. DML avoids the bottleneck of the parameter server (PS) by enabling the workers to exchange local models with their neighbors rather than the PS. However, DML still faces some key challenges, i.e., resource limitation, system heterogeneity, network dynamics and non-IID data. In this article, we design and implement MOTOR, an efficient DML mechanism that simultaneously addresses these challenges by applying model pruning and topology construction, thus accelerating DML. Specifically, MOTOR assigns different pruning ratios to heterogeneous workers. After model pruning, each worker will train and transmit a sub-model that fits its capabilities, reducing both computation and communication overhead. Besides, MOTOR dynamically constructs the network topology considering the time-varying network conditions and non-IID data distributions. We theoretically analyze the impact of pruning ratio and network topology on model training performance. Guided by the theoretical analysis, we develop a joint optimization algorithm for pruning ratio decision and topology construction to achieve the trade-off between resource overhead and training performance. We implement MOTOR on commercial devices and evaluate the performance with different DML tasks. Extensive experiments show that MOTOR achieves up to 4.2× speedup compared to the existing DML approaches.

Recent deep networks have achieved good performance on a variety of 3d points classification tasks. However, these models often face challenges in "wild tasks" where there are considerable differences between the labeled training/source data collected by one Lidar and unseen test/target data collected by a different Lidar. Unsupervised domain adaptation (UDA) seeks to overcome such a problem without target domain labels. Instead of aligning features between source data and target data, we propose a method that uses a Generative Adversarial Network (GAN) to generate synthetic data from the source domain so that the output is close to the target domain. Experiments show that our approach performs better than state-of-the-art UDA methods in three popular 3D object/scene datasets (i.e., ModelNet, ShapeNet and ScanNet) for cross-domain 3D object classification.

Unsupervised domain adaptation has shown promising results in leveraging synthetic (source) images for semantic segmentation of real (target) images. One key issue is how to align data distributions between the source and target domains. Adversarial learning has been applied to align these distributions. However, most existing approaches focus on aligning the output distributions related to image (global) segmentation. Such global alignment may not result in effective alignment due to the inherent high dimensionality feature space involved in the alignment. Moreover, global alignment might be hindered by the noisy outputs corresponding to background pixels in the source domain. To address this limitation, we propose a local output alignment. Such an approach can also mitigate the influences of noisy background pixels from the source domain when performing the local alignment. Our experiments show that by adding local output alignment into various global alignment based domain adaptation, our joint global-local alignment methods improves semantic segmentation. Code is available at https://github.com/skrya/globallocal.

There are two conventional methods to establish an entanglement connection in a Quantum Data Network (QDN). One is to create single-hop entanglement links first and then connect them with quantum swapping, and the other is for-warding one of the entangled photons from one end to the other via all-optical switching at intermediate nodes to directly establish an entanglement connection. Since a photon is easy to be lost during a long distance transmission, all existing works are adopting the former method. However, in a room size network, the success probability of delivering a photon across multiple links via all-optical switching is not that low. In addition, with an all-optical switching technique, we can save quantum memory at the intermediate nodes. Accordingly, we are expecting to establish significantly more entanglement connections with limited quantum resources by first creating entanglement segments, each spanning multiple quantum links, using all-optical switching, and then connecting them with quantum swapping.In this paper, we design SEE, a Segmented Entanglement Establishment approach that seamlessly integrates quantum swapping and all-optical switching to maximize quantum network throughput. SEE first creates entanglement segments over one or multiple quantum links with all-optical switching, and then connect them with quantum swapping. It is clear that an entanglement link is only a special entanglement segment. Accordingly, SEE can theoretically outperform conventional entanglement link based approaches. Large scale simulations show that SEE can achieve up to 100.00% larger throughput compared with the state-of-the-art entanglement link based approach, i.e., REPS.

Federated learning (FL) has been widely adopted to train machine learning models over massive distributed data sources in edge computing. However, the existing FL frameworks usually suffer from the difficulties of resource limitation and edge heterogeneity. Herein, we design and implement FedMP, an efficient FL framework through adaptive model pruning. We theoretically analyze the impact of pruning ratio on model training performance, and propose to employ a Multi-Armed Bandit based online learning algorithm to adaptively determine different pruning ratios for heterogeneous edge nodes, even without any prior knowledge of their computation and communication capabilities. With adaptive model pruning, FedMP can not only reduce resource consumption but also achieve promising accuracy. To prevent the diverse structures of pruned models from affecting the training convergence, we further present a new parameter synchronization scheme, called Residual Recovery Synchronous Parallel (R2SP), and provide a theoretical convergence guarantee. Extensive experiments on the classical models and datasets demonstrate that FedMP is effective for different heterogeneous scenarios and data distributions, and can provide up to 4.1× speedup compared to the existing FL methods.

An Autonomous Driving System (ADS) uses a plethora of sensors and many deep learning based tasks to aid its perception, prediction, motion planning, and vehicle control. To ensure road safety, those tasks should be synchronized and use the latest sensing data, which is challenging since 1) different sensors have different sensing periods, 2) the tasks are interdependent, 3) computing resource is limited. This work is the first that uses Age of Information (AoI) as the performance metric for task scheduling in an ADS. We show that minimizing AoI is equivalent to jointly minimizing the response time and maximizing the throughput. We formally formulate the AoI-centric task scheduling problem. To derive practical scheduling solutions, we extend the formulation and formulate the optimal AoI-centric periodic scheduling problem with a given cycle. A reinforcement learning-based solution is designed accordingly. With experiments simulated according to the Apollo driving system, we compare the scheduling performance of the AoI-centric task scheduling with Apollo’s schedulers from the perspective of AoI, throughput, and worst case response time. The experiment results show that the maximum AoI in the proposed scheduling solution with 4 cores is lower than that in Apollo’s schedulers with 8 cores.

This paper studies reliable teleportation of quantum bits (called qubits) in a quantum data network with multiple sources (S) and destinations (D) as well as repeaters. To teleport qubits for a SD pair reliably, not only an entanglement path for the SD pair, but also appropriate purification of the links along the path is required to ensure that the end-to-end (E2E) fidelity of the established entanglement connections is high enough.This is the first work on quantifying the E2E fidelity, and also using this E2E fidelity to determine critical links to achieve the most resource efficient purification. A novel approach called E2E Fidelity aware Routing and Purification (EFiRAP) is proposed to maximize network throughput, i.e., the number of entanglement connections among multiple SD pairs, with each connection having an E2E fidelity above a given required threshold. EFiRAP accomplishes this goal by first preparing multiple candidate entanglement paths and determining optimal purification schemes, and then selecting the final set of entanglement paths that can maximize network throughput under the given quantum resource constraints. Existing works only ensured the fidelity of individual links, rather than the E2E fidelity is above a given threshold. Extensive simulations show that the proposed EFiRAP can enhance network throughput by about 50% when compared with the state-of-the-art approach.

Quantum Data Networks (QDNs) typically leverage teleportation to reliably send data quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one entanglement connection between Alice and Bob needs to be established. Accordingly, we have to establish as many entanglement connections as possible with limited quantum resources in order to maximize the network throughput. Conventional methods assume a known traffic matrix and calculate the paths to establish entanglement connections in one batch using a centralized algorithm. However, these methods are not scalable in large scale QDNs since it is time consuming to optimize the entanglement paths for a batch of requests, which may result in a long time slot duration and significantly reduce the network throughput. To address this issue, we propose an Online Entanglement Routing (OER) scheme which determines the entanglement paths for each request when it arrives. In addition, OER pursues work conservation and fairness among all requests in the QDNs. Through extensive simulations, we demonstrate that OER not only outperforms two representative heuristics by up to 61.27% and 52.79%, respectively, in terms of average request completion time, but also achieves a better fairness performance than these two counterparts.

Due to the great advantage of LiDAR sensors in perceiving complex driving environments, LiDAR-based 3D object detection has recently drawn significant attention in autonomous driving. Although many advanced LiDAR object detection models have been developed, their designs are mainly based on deep learning approaches, which are usually data-hungry and expensive to train. Thus, it is common for some LiDAR perception system developers or self-driving car companies to collect training data from different sources (e.g., self-driving car users) or outsource the training work to a third party. However, these practices provide opportunities for backdoor attacks, where the attacker aims to inject a hidden trigger pattern into the victim detection model by poisoning its training set and let the model fail to detect objects when the trigger presents in the inference phase. Although backdoor attacks have posed serious security concerns, the vulnerability of LiDAR object detection to such attacks has not yet been studied. To fill the research gap, in this paper, we present the first study on backdoor attacks against LiDAR object detection in autonomous driving. Specifically, we propose a novel backdoor attack strategy based on which the attacker can achieve the attack goal by poisoning a small number of point cloud samples. In addition, the proposed attack strategy is physically realizable, and it allows the attacker to easily perform the attack using some common objects as the triggers. To make the poisoned samples difficult to be detected, we also design a stealthy attack strategy by creating some fake vehicle point clusters to hide the injected points in the point cloud. The desirable performance of our attacks is demonstrated through both simulation and real-world case study.

Vehicular communication networks (VCNs) have been widely recognized as promising solutions to support safety-related applications in urban transportation systems. However, constructing and maintaining such networks is quite challenging due to the complex traffic and communication environment. Substantial studies have focused on the design of the networking schemes and message dissemination protocols. Nonetheless, most existing designs only consider the connectivity and rapid end-to-end transmission, regardless of the network coverage and duration. In this article, we propose a novel temporary warning network (TWN) for safety message dissemination in the urban traffic environment, in which both the spatial distribution and temporal duration of the networking scheme are taken into account. Specifically, TWN is constructed by the selection of relay vehicles based on the spatiotemporal correlation of vehicle trajectory so that the safety message can be quickly disseminated within the Regions of Interest (RoIs). To maintain TWN during an accident, a reselection mechanism is also proposed, which enables newly come vehicles in the RoI to receive the messages in time. Finally, we conduct extensive numerical experiments to validate the effectiveness of our method in various traffic scenarios.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing. To fully utilize the widely distributed data, we concentrate on a wireless edge computing system that conducts model training using decentralized peer-to-peer (P2P) methods. However, there are two major challenges on the way towards efficient P2P model training: limited resources (e.g., network bandwidth and battery life of mobile devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which receives less attention in recent years. To address these two challenges, this paper studies the impact of topology construction on the P2P training performance. Specifically, we dynamically construct an efficient P2P topology, where model aggregation occurs at the edge. In a nutshell, we first formulate the topology construction for P2P learning (TCPL) problem with resource constraints as an integer programming problem. Then a learning-driven method is proposed to adaptively construct a topology at each training epoch. We evaluate the performance of our proposed algorithm through extensive simulations and physical platform. Evaluation results show that our method can improve the model training efficiency by about 11% with resource constraints, reduce the communication cost by 30% and the network traffic consumption by about 60% under the same accuracy requirement compared to the benchmarks.

This paper explicitly addresses the multi-modal traffic signal control problem in the shared space street (SSS), where there are multiple travel modes (e.g. passenger cars, buses, and light rails) competing for their spaces in the same lane. SSS widely exists in central business districts where the road space is limited and the multi-modal travel demand is high. An optimization framework with a multi-modal cell transmission model (M-CTM) is developed to model the multi-modal traffic in the network. Also, this study models the passenger’s choice of choosing among different travel modes based on travel costs. Regarding multi-modal signal coordination, a cycle-based traffic signal plan selection model is developed to choose the best offline optimized signal plan to minimize the total travel cost of all three modes. Therefore, the computation burden is significantly reduced in the optimization model. Moreover, a particle swarm optimization (PSO) method is implemented to solve the proposed optimization model. A case study in downtown Buffalo validates the proposed model with microscopic traffic simulation VISSIM.

Most existing driver models focus on predicting driving performance in normal and near-collision situations without considering the impact of collision warning parameters on driver behavior. This study develops a cognitive computational driver model based on the Queueing Network-Model Human Processor (QN-MHP) to quantify the effects of key warning parameters (i.e., warning lead time, warning reliability, and speech warning style) on driver performance in warning responses, in connected vehicle systems (CVSs). The model was validated by comparing its predictions of driver response time, response type, and braking and steering performance with data from thirty-two drivers collected in an experimental study. Once the route choice mechanism had been implemented, the driver model was found to explain the cognitive mechanism underlying how drivers process warnings in CVSs. Indeed, the validation results showed that the model was able to capture major changes in patterns of the experimental data, with R-squared values of 0.88 for warning response time, 0.69 and 0.65 for decision making in response type for the initial trial and across trials, 0.85 for braking performance, and 0.83 for steering performance. The model can be applied to optimize the interface design of CVSs based on driver needs.

Nowadays, most of the taxi drivers have become users of the relocation recommendation service offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing), which could oftentimes lead drivers to places with profitable orders. At the same time, electric taxis (e-taxis) are increasingly adopted and gradually replacing gasoline taxis in today’s public transportation systems due to their environmental-friendly nature. Though effective for traditional gasoline taxis, existing relocation recommendation schemes are rather suboptimal for e-taxi drivers’ user experience. On one hand, the existing schemes take no account of taxis’ refueling decisions, as the refueling durations of gasoline taxis are usually short enough to be ignored. However, the charging duration of the e-taxis spent at charging stations can be as long as hours. Obviously, an e-taxi’s battery could be easily depleted by the continuous relocations suggested by existing schemes, and thus will have to be charged for a long time afterwards, making the e-taxi driver miss numerous order-serving opportunities. On the other hand, charging posts are typically sparsely and unevenly distributed across a city. With no consideration of charging opportunities, existing schemes could probably send an e-taxi to an area with no charging post around, even though its battery is running low. To optimize e-taxi drivers’ user experience, in this paper, we design a jointcharging and relocation recommendation system for e-taxi drivers (CARE). We take the perspective of e-taxi drivers and formulate their decision making as a multi-agent reinforcement learning problem where each e-taxi driver aims to maximize his own cumulative rewards. More specifically, we propose a novelmulti-agent mean field hierarchical reinforcement learning (MFHRL)framework. The hierarchical architecture of MFHRL helps the proposed CARE provide far-sighted charging and relocation recommendations for e-taxi drivers. Besides, we integrate each hierarchical level of MFHRL separately with the mean field approximation to incorporate e-taxis’ mutual influences in decision making. We set up a simulator with one of the largest real-world e-taxi datasets in Shenzhen, China, which contains the GPS trajectory data and transaction data of 3848 e-taxis from June 1st to June 30th, 2017, coupled with 165 charging stations including 317 fast charging posts and 1421 slow charging posts. We adopt this simulator to generate 6 dynamic urban environments, which reflect the different real-world scenarios faced by e-taxi drivers. In all of these environments, we conduct extensive experiments to validate that the proposed MFHRL framework greatly outperforms all baselines by significantly increasing the rewards obtained by e-taxi drivers. Besides, we also show that the charging policy learned by MFHRL can effectively reduce the range anxiety of e-taxi drivers, which significantly boosts e-taxi drivers’ quality of experience.

In this paper, we propose EdgePS, an advanced parameter server approach for distributed machine learning in edge computing scenarios. Different from the Conventional Parameter Server (CPS) approach, which performs parameter aggregation after every local training epoch, EdgePS synchronizes the parameters of all workers only when the local training cannot improve the global model performance. We first analyze how the local training will impact the performance of the global model, and then design algorithms to determine when the best time is to perform the parameter aggregation. Both real testbed experiments and extensive large scale simulations demonstrate that EdgePS can train a practical machine learning model, e.g., VGG-16, with up to 59.28% less time compared with the CPS approach. With the same training time, EdgePS can improve model accuracy by up to 30.19 % compared with the state-of-the-art distributed machine learning algorithm designed for edge computing scenarios.

As an effective way to acquire accurate information about the driving environment, LiDAR perception has been widely adopted in autonomous driving. The state-of-the-art LiDAR perception systems mainly rely on deep neural networks (DNNs) to achieve good performance. However, DNNs have been demonstrated vulnerable to adversarial attacks. Although there are a few works that study adversarial attacks against LiDAR perception systems, these attacks have some limitations in feasibility, flexibility, and stealthiness when being performed in real-world scenarios. In this paper, we investigate an easier way to perform effective adversarial attacks with high flexibility and good stealthiness against LiDAR perception in autonomous driving. Specifically, we propose a novel attack framework based on which the attacker can identify a few adversarial locations in the physical space. By placing arbitrary objects with reflective surface around these locations, the attacker can easily fool the LiDAR perception systems. Extensive experiments are conducted to evaluate the performance of the proposed attack, and the results show that our proposed attack can achieve more than 90% success rate. In addition, our real-world study demonstrates that the proposed attack can be easily performed using only two commercial drones. To the best of our knowledge, this paper presents the first study on the effect of adversarial locations on LiDAR perception models' behaviors, the first investigation on how to attack LiDAR perception systems using arbitrary objects with reflective surface, and the first attack against LiDAR perception systems using commercial drones in physical world. Potential defense strategies are also discussed to mitigate the proposed attacks.

A group of connected and autonomous vehicles (CAVs) with common interests can drive in a cooperative manner, namely cooperative driving, which has been verified to significantly improve road safety, traffic efficiency, and environmental sustainability. A more general scenario with various types of cooperative driving applications such as truck platooning and vehicle clustering will coexist on roads in the foreseeable future. To support such multiple cooperative drivings, it is critical to design an efficient message dissemination scheduling for vehicles to broadcast their kinetic status, i.e., beacon periodically. Most ongoing researches suggest designing the communication protocols via traffic and communication modeling on top of dedicated short range communications (DSRC) or cellular-based vehicle-to-vehicle (C-V2V) communications as a potential remedy. However, most of the existing researches are designed for a simple or specific traffic scenario, e.g., ignoring the impacts of the complex communication environment and emerging hybrid traffic scenarios. Moreover, some studies design beaconing strategies based on the implication of channel and traffic conditions in the beacons of other vehicles. However, the delayed perception of these information may seriously deteriorate the beaconing performance. In this paper, we take the perspective of cooperative drivings and formulate their decision-making process as a Markov game. Furthermore, we propose a multi-agent hierarchical attention reinforcement learning (MAHA) framework to solve the Markov game. More concretely, the hierarchical structure of the proposed MAHA can lead cooperative drivings to be foresightful. Hence, even without immediate incentives, the well-trained agents can still take favorable actions that benefit their long-term rewards. Besides, we integrate each hierarchical level of MAHA separately with the graph attention network (GAT) to incorporate agents' mutual influences in the decision-making process. Besides, we set up a simulator and adopt this simulator to generate dynamic traffic scenarios, which reflect the different real-world scenarios faced by cooperative drivings. We conduct extensive experiments to evaluate the proposed MAHA framework's performance. The results show that MAHA can significantly improve the beacon reception rate and guarantee low communication delay in all of these scenarios.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing. To fully utilize the widely distributed data, we concentrate on a wireless edge computing system that conducts model training using decentralized peer-to-peer (P2P) methods. However, there are two major challenges on the way towards efficient P2P model training: limited resources (e.g., network bandwidth and battery life of mobile edge devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which have received less attention in recent years. To address these two challenges, this paper adaptively constructs a dynamic and efficient P2P topology, where model aggregation occurs at the edge devices. In a nutshell, we first formulate the topology construction for P2P learning (TCPL) problem with resource constraints as an integer programming problem. Then a learning-driven method is proposed to adaptively construct a topology at each training epoch. We further give the convergence analysis on training machine learning models even with non-convex loss functions. Extensive simulation results show that our proposed method can improve the model training efficiency by about 11% with resource constraints and reduce the communication cost by about 30% under the same accuracy requirement compared to the benchmarks.

Federated learning (FL) has emerged in edge computing to address limited bandwidth and privacy concerns of traditional cloud-based centralized training. However, the existing FL mechanisms may lead to long training time and consume a tremendous amount of communication resources. In this paper, we propose an efficient FL mechanism, which divides the edge nodes into K clusters by balanced clustering. The edge nodes in one cluster forward their local updates to cluster header for aggregation by synchronous method, called cluster aggregation, while all cluster headers perform the asynchronous method for global aggregation. This processing procedure is called hierarchical aggregation. Our analysis shows that the convergence bound depends on the number of clusters and the training epochs. We formally define the resource-efficient federated learning with hierarchical aggregation (RFL-HA) problem. We propose an efficient algorithm to determine the optimal cluster structure (i.e., the optimal value of K) with resource constraints and extend it to deal with the dynamic network conditions. Extensive simulation results obtained from our study for different models and datasets show that the proposed algorithms can reduce completion time by 34.8%-70% and the communication resource by 33.8%-56.5% while achieving a similar accuracy, compared with the well-known FL mechanisms.

Quantum communication using qubits based on the principle of entangled photons is a promising solution to improve network security. However, it is difficult to successfully create an entanglement link or connection between two nodes, especially when they are far apart from each other. In addition, only one qubit can be exchanged over an established entanglement connection, resulting in a low throughput.In this paper, we propose Redundant Entanglement Pro-visioning and Selection (REPS) to maximize the throughput for multiple source-destination (SD) pairs in a circuit-switched, multi-hop quantum network. REPS has two distinct features: (i). It provisions backup resources for extra entanglement links between adjacent nodes for failure-tolerance; and (ii). It provides flexibility in selecting successfully created entanglement links to establish entanglement connections for the SD pairs to achieve network-wide optimization. Extensive analysis and simulations show that REPS can achieve optimal routing with a high probability, and improves the throughput by up to 68.35% over the highest-performing algorithms in existence. In addition, it also improves the fairness among the SD pairs in the networks.

Today, most autonomous vehicles (AVs) rely on LiDAR (Light Detection and Ranging) perception to acquire accurate information about their immediate surroundings. In LiDAR-based perception systems, semantic segmentation plays a critical role as it can divide LiDAR point clouds into meaningful regions according to human perception and provide AVs with semantic understanding of the driving environments. However, an implicit assumption for existing semantic segmentation models is that they are performed in a reliable and secure environment, which may not be true in practice. In this paper, we investigate adversarial attacks against LiDAR semantic segmentation in autonomous driving. Specifically, we propose a novel adversarial attack framework based on which the attacker can easily fool LiDAR semantic segmentation by placing some simple objects (e.g., cardboard and road signs) at some locations in the physical space. We conduct extensive real-world experiments to evaluate the performance of our proposed attack framework. The experimental results show that our attack can achieve more than 90% success rate in real-world driving environments. To the best of our knowledge, this is the first study on physically realizable adversarial attacks against LiDAR point cloud semantic segmentation with real-world evaluations.

With the wide bandwidths in millimeter wave (mmWave) frequency band that results in unprecedented accuracy, mmWave sensing has become vital for many applications, especially in autonomous vehicles (AVs). In addition, mmWave sensing has superior reliability compared to other sensing counterparts such as camera and LiDAR, which is essential for safety-critical driving. Therefore, it is critical to understand the security vulnerabilities and improve the security and reliability of mmWave sensing in AVs. To this end, we perform the end-to-end security analysis of a mmWave-based sensing system in AVs, by designing and implementing practical physical layer attack and defense strategies in a state-of-the-art mmWave testbed and an AV testbed in real-world settings. Various strategies are developed to take control of the victim AV by spoofing its mmWave sensing module, including adding fake obstacles at arbitrary locations and faking the locations of existing obstacles. Five real-world attack scenarios are constructed to spoof the victim AV and force it to make dangerous driving decisions leading to a fatal crash. Field experiments are conducted to study the impact of the various attack scenarios using a Lincoln MKZ-based AV testbed, which validate that the attacker can indeed assume control of the victim AV to compromise its security and safety. To defend the attacks, we design and implement a challenge-response authentication scheme and a RF fingerprinting scheme to reliably detect aforementioned spoofing attacks.

With the development of applications on end devices, such as cell phones and tablets, more and more passengers would like to have entertainment on these end devices when they are cruising on vehicles. Due to the limited computation ability of the end devices, some of these applications have back-end components on the edge clouds, which are realized by Service Entities (SEs). In this work, we propose a system named DSEP to Dynamically determine the SEPlacement, such that the maximum latency experienced by the passengers can be minimized. To this end, we first train two sequential neural networks to predict the position of each individual vehicle, and propose an efficient algorithm based on optimization relaxation and Lagrange decomposition to determine the SE placement. Through extensive real-data driven simulations, we find that with the two sequential neural networks proposed in this paper, there are less than 1 percent errors on estimating where the passengers will access the edge cloud system. When the computation resources in the edge cloud are limited, DSEP can reduce the response latency by up to 43 percent compared with the nearest placement scheme. Even averaging the performance improvement over all simulation settings, DSEP can reduce the response latency by 16 percent.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this article, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, and then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use real testbed experiments and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with the state-of-the-art technologies.

Spot-level parking availability information (the availability of each spot in a parking lot) is in great demand, as it can help reduce time and energy waste while searching for a parking spot. In this article, we propose a crowdsensing system called SpotE that can provide spot-level availability in a parking lot using drivers’ smartphone sensors. SpotE only requires the sensor data from drivers’ smartphones, which avoids the high cost of installing additional sensors and enables large-scale outdoor deployment. We propose a new model that can use the parking search trajectory and final destination (e.g., an exit of the parking lot) of a single driver in a parking lot to generate the probability profile that contains the probability of each spot being occupied in a parking lot. To deal with conflicting estimation results generated from different drivers, due to the variance in different drivers’ parking behaviors, a novel aggregation approach SpotE-TD is proposed. The proposed aggregation method is based on truth discovery techniques and can handle the variety in Quality of Information of different vehicles. We evaluate our proposed method through a real-life deployment study. Results show that SpotE-TD can efficiently provide spot-level parking availability information with a 20% higher accuracy than the state-of-the-art.

Fine-grained flow management is useful in many practical applications, e.g., resource allocation, anomaly detection and traffic engineering. However, it is difficult to provide fine-grained management for a large number of flows in SDNs due to switches' limited flow table capacity. While using wildcard rules can reduce the number of flow entries needed, it cannot fully ensure fine-grained management for all the flows without degrading application performance. In this article, we design and implement hybrid rule placement for fine-grained flow management (to be referred to as HiFi here after). HiFi achieves fine-grained management with a minimal number of flow entries through taking a two-step approach: wildcard entry installment and application-specific exact-match entry installment. How to optimally install wildcard and exact-match flow entries, however, is intractable. Therefore, we design approximation algorithms with bounded factors to solve these problems. We consider how to achieve network-wide load balancing via fine-grained flow management as a case study. Both experiment on a testbed built with open virtual switches and extensive simulation show that HiFi can reduce the number of required flow entries by about 45-69 percent and reduce the control overhead by about 28-50 percent compared with the state-of-the-art approaches for achieving fine-grained flow management.

In Mobile Edge Computing (MEC), many tasks require specific service support for execution and in addition, have a dependent order of execution among the tasks. However, previous works often ignore the impact of having limited services cached at the edge nodes on (dependent) task offloading, thus may lead to an infeasible offloading decision or a longer completion time. To bridge the gap, this article studies how to efficiently offload dependent tasks to edge nodes with limited (and predetermined) service caching. We formally define the problem of offloading dependent tasks with service caching (ODT-SC), and prove that there exists no algorithm with constant approximation for this hard problem. Then, we design an efficient convex programming based algorithm (CP) to solve this problem. Moreover, we study a special case with a homogeneous MEC and propose a favorite successor based algorithm (FS) to solve this special case with a competitive ratio of O(1)O(1). Extensive simulation results using Google data traces show that our proposed algorithms can significantly reduce applications' completion time by about 21-47 percent compared with other alternatives.

Recently, dynamic social network research has attracted a great amount of attention, especially in the area of anomaly analysis that analyzes the anomalous change in the evolution of dynamic social networks. However, most of the current research focused on anomaly analysis of the macro representation of dynamic social networks and failed to analyze the nodes that have anomalous structural changes at a micro level. To identify and evaluate anomalous structural change-based nodes in generalized dynamic social networks that only have limited structural information, this research considers undirected and unweighted graphs and develops a multiple-neighbor superposition similarity method ( ), which mainly consists of a multiple-neighbor range algorithm ( ) and a superposition similarity fluctuation algorithm ( ). introduces observation nodes, characterizes the structural similarities of nodes within multiple-neighbor ranges, and proposes a new multiple-neighbor similarity index on the basis of extensional similarity indices. Subsequently, maximally reflects the structural change of each node, using a new superposition similarity fluctuation index from the perspective of diverse multiple-neighbor similarities. As a result, based on and , not only identifies anomalous structural change-based nodes by detecting the anomalous structural changes of nodes but also evaluates their anomalous degrees by quantifying these changes. Results obtained by comparing with state-of-the-art methods via extensive experiments show that can accurately identify anomalous structural change-based nodes and evaluate their anomalous degrees well.

Integration of information on road transverse geometric features such as cross slope and superelevation in digital maps can widen the scope of its applications, which is primarily navigation, by enabling driving safety and efficiency applications such as Advanced Driver Assistance Systems (ADAS). The huge scale and dynamic nature of road networks make sensing such road geometric features a challenging task. Traditional methods oftentimes suffer from high cost, limited scalability and update frequency, as well as poor sensing accuracy. To overcome these problems, we propose a cost-effective and scalable road transverse slope estimation framework using sensor data from smartphones. Based on error characteristics of smartphone sensors, we intelligently combine data from accelerometer, gyroscope and GPS to estimate road transverse slope profile of a road segment. To improve accuracy and robustness of the system, the estimations of road transverse slope from multiple sources/vehicles are crowd-sourced to compensate for the effects of varying quality of sensor data from different sources. Extensive experimental evaluation on a test route of 9km demonstrates the superior performance of our proposed method, achieving 350% improvement on road transverse slope estimation accuracy over existing methods, with 90% of errors below 0.5°.

More and more applications learn from the data collected by the edge devices. Conventional learning methods, such as gathering all the raw data to train an ultimate model in a centralized way, or training a target model in a distributed manner under the parameter server framework, suffer a high communication cost. In this paper, we design Select Neighbors and Parameters (SNAP), a communication efficient distributed machine learning framework, to mitigate the communication cost. A distinct feature of SNAP is that the edge servers act as peers to each other. Specifically, in SNAP, every edge server hosts a copy of the global model, trains it with the local data, and periodically updates the local parameters based on the weighted sum of the parameters from its neighbors (i.e., peers) only (i.e., without pulling the parameters from all other edge servers). Different from most of the previous works on consensus optimization in which the weight matrix to update parameter values is predefined, we propose a scheme to optimize the weight matrix based on the network topology, and hence the convergence rate can be improved. Another key idea in SNAP is that only the parameters which have been changed significantly since the last iteration will be sent to the neighbors. Both theoretical analysis and simulations show that SNAP can achieve the same accuracy performance as the centralized training method. Compared to the state-of-the-art communication-aware distributed learning scheme TernGrad, SNAP incurs a significantly lower (99.6% lower) communication cost.

Fine-grained flow management is useful in many practical applications, e.g., resource allocation, anomaly detection and traffic engineering. However, it is difficult to provide fine-grained management for a large number of flows in SDNs due to switches' limited flow table capacity. While using wildcard rules can reduce the number of flow entries needed, it cannot fully ensure fine-grained management for all the flows without degrading application performance. In this paper, we design and implement HiFi, a system that achieves fine-grained management with a minimal number of flow entries. To this end, HiFi takes a two-step approach: wildcard entry installment and application-specific exact-match entry installment. How to optimally install wildcard and exact-match flow entries, however, is intractable. Therefore, we design approximation algorithms with bounded factors to solve these problems. We consider how to achieve network-wide load balancing via fine-grained flow management as a case study. Both experimental and simulation results show that HiFi can reduce the number of required flow entries by about 45%-69% and reduce the control overhead by 28%-50% compared with the state-of-the-art approaches for achieving fine-grained flow management.

In Mobile Edge Computing (MEC), many tasks require specific service support for execution and in addition, have a dependent order of execution among the tasks. However, previous works often ignore the impact of having limited services cached at the edge nodes on (dependent) task offloading, thus may lead to an infeasible offloading decision or a longer completion time. To bridge the gap, this paper studies how to efficiently offload dependent tasks to edge nodes with limited (and predetermined) service caching. We formally define the problem of offloading dependent tasks with service caching (ODT-SC), and prove that there exists no algorithm with constant approximation for this hard problem. Then, we design an efficient convex programming based algorithm (CP) to solve this problem. Moreover, we study a special case with a homogeneous MEC and propose a favorite successor based algorithm (FS) to solve this special case with a competitive ratio of O(1). Extensive simulation results using Google data traces show that our proposed algorithms can significantly reduce applications' completion time by about 27-51% compared with other alternatives.

Estimates of road grade/slope can add another dimension of information to existing 2D digital road maps. Integration of road grade information will widen the scope of digital map’s applications, which is primarily used for navigation, by enabling driving safety and efficiency applications such as Advanced Driver Assistance Systems (ADAS), eco-driving, etc. The huge scale and dynamic nature of road networks make sensing road grade a challenging task. Traditional methods oftentimes suffer from limited scalability and update frequency, as well as poor sensing accuracy. To overcome these problems, we propose a cost-effective and scalable road grade estimation framework using sensor data from smartphones. Based on our understanding of the error characteristics of smartphone sensors, we intelligently combine data from accelerometer, gyroscope and vehicle speed data from OBD-II/smartphone’s GPS to estimate road grade. To improve accuracy and robustness of the system, the estimations of road grade from multiple sources/vehicles are crowd-sourced to compensate for the effects of varying quality of sensor data from different sources. Extensive experimental evaluation on a test route of 9km demonstrates the superior performance of our proposed method, achieving 5× improvement on road grade estimation accuracy over baselines, with 90% of errors below 0.3°.

Recently dynamic social networks witnessed a massive surge in popularity, especially in the area of anomaly detection. Although the text-based methods have achieved impressive detection performances, their applications are limited to the social text provided by users. This research focuses on graph-based methods and proposes a universal method for generalized social networks. Different from the existing graph-based methods that summarize a number of structural features, the proposed nodes' evolution diversity inspired method (NEDM) detects anomalies in dynamic social networks from the perspective of diverse evolution mechanisms. More specifically, NEDM applies link prediction algorithms at the micro-level to fit evolution mechanisms followed by the behaviors of nodes, and designs indices to evaluate their fitting degrees in edge removal and generation processes. In addition, the behavior of a node is represented as a quantum superposition state where such behavior follows different evolution mechanisms with uncertain probabilities. We propose a quantum mechanism based particle swarm optimization algorithm (QMPSO) in NEDM. QMPSO determines the optimal observation states of the behaviors of different nodes, and maximally reflects the evolutional fluctuations in the evolution processes of social networks. As a result, NEDM can quantify the evolutional fluctuations in different periods, and detect anomalies in dynamic social networks. Comparing with art-of-the-state methods and real social data in extensive experiments on disparate real-world social networks, we verify the outstanding performance of NEDM in terms of both accuracy and universality.

Vehicular safety applications require vehicles to maintain a high awareness level of the local neighborhood through broadcasting safety beacons on the control channel. However, the existing 10-MHz control channel in the IEEE 802.11p based Dedicated Short Range Communication (DSRC) standard can be easily congested by frequent beaconing in a dense environment which therefore degrades the performance of network and safety level of vehicles. Existing congestion mitigation approaches aim to fairly distribute the channel resources based on channel load measurements, but fail to incorporate the road safety requirements of vehicles. In this paper, we model the congestion control problem of Vehicular Ad-hoc Networks (VANETs) as a utility maximization problem leveraging i) the contribution of every vehicle to channel load with respect to its location, and ii) a car-following risk factor which is defined as the rear-end crash risk perceived by each vehicle. A distributed game-theoretic rate adaptation mechanism is then proposed to address the problem. Numerical results demonstrate that the proposed scheme dominates IEEE 802.11p CSMA/CA based beaconing mechanism in terms of packet loss, packet delivery rate and aggregate throughput.

The rapid development of Autonomous Vehicle (AV) technologies provides a new opportunity to evacuate vulnerable persons from their residences to shelters when some emergency event happens. One of the most important objectives is to minimize the evacuation time, which depends on the order to evacuate persons and which shelter each person is delivered to. We first formulate this AV dispatching problem as an Integer Linear Programming (ILP) model and prove this problem is NP-hard. Due to the problem hardness, an efficient algorithm based on Dynamical Programming (DP) is proposed. Through extensive simulations, we find that our algorithm can reduce the evacuation time by 58\% compared with a greedy based algorithm, which is the common method to solve the Traveling Salesman Problem (TSP), a special case of our AV dispatching problem.

There are more and more structured traffic flows (a.k.a coflow) in today's data center networks. Completing a coflow is extremely important for various applications, e.g., MapReduce. To reduce the coflow completion time or CCT, one may increase the link capacity by applying advanced optical circuit switches in data center networks. Due to special features of optical circuit switches, both traffic scheduling and circuit scheduling will influence the CCT. However, previous solutions have some significant limitations: they consider either coflow scheduling, or circuit scheduling for only one optical circuit switch, which are both insufficient. In this paper, we study the integrated coflow and circuit scheduling (GCCS) problem with the objective to minimize the CCT, and prove its NP-hardness. We present an integrated algorithm which includes two steps, coflow scheduling and circuit scheduling, respectively. We also analyze that the proposed algorithm can achieve the approximation ratio O(h) in most practical situations, where h is the maximum number of ports among all lightpaths. Through large-scale simulations, we demonstrate that the integrated solution can significantly reduce the CCT by about 43-70 percent compared with the state-of-the-art coflow scheduler for optical networks.

With the increase of various of applications, CPU is no longer adequate for the computation tasks. Accordingly, some providers deploy accelerators in their cloud. Since not all the servers in the cloud can carry accelerators, how to schedule jobs onto accelerators and improve the system performance is an important issue. Due to the distributed computing frameworks in cloud computing systems, the jobs usually arrive in batches, and hence we try to minimize the make-span of a batch of jobs in this paper. To this end, we first formulate this problem as a mathematic programming model, and prove the NP-hardness of this problem. To solve this problem efficiently, we propose a 4- approximation algorithm. Through extensive simulations, we find that our algorithm can reduce the make-span of a batch of jobs by about 32%, and enhance the system throughput by up to 29% compared with our comparison baseline.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this paper, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use a real testbed implementation and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with state-of-the-art technologies.

The combination of Network Function Virtualization (NFV) and Software Defined Networking (SDN) possesses a great potential in accommodating dynamic network control via cloning/migration of virtualized NFs and steering of traffic flows. A great challenge is the lack of the proprietary internal NF state information to the control system (including SDN controller and NFV orchestrator), which may lead to incorrect packet/flow processing at the newly created NF instances. In this work, we design a light-weight approach which can function either independently or as a plug-in to the network control system to reveal the internal NF states. Unlike the previous work, we propose to learn the internal NF states through normal network functions instead of designing extra APIs for certain NFs. Moreover, we propose a feasible way to detect state violations and even correct them automatically. Our approach is tested by experiments, and the results confirm its efficiency and practicability.

Combining Virtual Network Functions (VNF) and Software Defined Networking (SDN) enables fine-grained traffic steering to provide required network services to flows. However, online routing calculation and flow table enforcement incurs an non-negligible overhead. In this work, we propose to design a nonblocking network with fixed routing and VNF provisioning schemes to improve the network performance (e.g. the flow completion time). We first formulate this problem as a linear programming (LP) problem with infinite number of constraints, and leverage primal-dual technology to reformulate the problem as a polynomial size LP. The LP formulation is also extended to reconfigure the network when some components become unavailable, in order to keep the network nonblocking. Since solving the LP formulation is time consuming or even impossible in large scale networks, an efficient algorithm based on optimization decomposition and column generation is proposed to find a near optimal solution quickly. Simulation results show that nonblocking networks can speed up 60% of the flows by 2x, with a small increase in the required network capacity, compared with approaches that do not use the nonblocking networks.

Network function virtualization is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named service function chain (SFC) mapping, with which network functions are deployed over virtualized and shared platforms in data centers. However, failures are quite common in data centers. Therefore, a practical and yet theoretically challenging issue in SFC mapping in such an environment is to manage the availability of the requests. In this paper, we present a framework to provision availability of SFC requests in a data center with multiple layers of connected devices, and the devices follow heterogeneous failure processes with the objective of minimizing resource usage. To expedite the process, we further propose an optimization problem of request mapping and backup estimation and solve it efficiently with an approximation algorithm. With simulations, we demonstrate the effectiveness of our proposed framework.

To better serve a diversity of flows, load balancing is crucial to ensure operational efficiency. However, previous works for load balancing have several disadvantages: 1) limited applicability with sub-flow scheduling (e.g., LetFlow); 2) hash collision (e.g., ECMP); or 3) transient network congestion due to reactive scheduling for traffic dynamics (e.g., Hedera and DevoFlow). An important reason for the above disadvantages is that it is difficult to provide fully fine-grained flow control for load balancing in an SDN as the flow table size of each SDN switch is usually limited. Inspired by the fact that a virtual switch (vswitch) has more powerful processing capacity and more flow entries compared with a physical switch, the previous work (e.g., Presto) deploys one vswitch for each ingress switch, and achieves the load balancing through efficient flow routing. However, this mechanism may lead to high cost and not well deal with topology asymmetry. Thus, this paper proposes to achieve the load balancing by incrementally deploying a certain number of vswitches in an SDN. We formulate the joint optimization of vswitch deployment and routing (JVR) problem as an integer linear program, and prove its NP-hardness. A rounding-based algorithm with bounded approximation factors is proposed to solve the JVR problem. We implement the proposed algorithm on an SDN testbed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results show high efficiency of our algorithm. For example, our proposed algorithm can reduce the link load ratio by about 41.5% compared with ECMP by deploying a small number of virtual switches.

Recent advances in connected vehicle technologies enable vehicles and signal controllers to cooperate and improve the traffic management at intersections. This paper explores the opportunity for cooperative and integrated vehicle and intersection control for energy efficiency (CIVIC-E2) to contribute to a more sustainable transportation system. We propose a two-level approach that jointly optimizes the traffic signal timing and vehicles' approach speed, with the objective being to minimize total energy consumption for all vehicles passing through an isolated intersection. More specifically, at the intersection level, a dynamic programming algorithm is designed to find the optimal signal timing by explicitly considering the arrival time and energy profile of each vehicle. At the vehicle level, a model predictive control strategy is adopted to ensure that vehicles pass through the intersection in a timely fashion. Our simulation study has shown that the proposed CIVIC-E2system can significantly improve intersection performance under various traffic conditions. Compared with conventional fixed-time and actuated signal control strategies, the proposed algorithm can reduce energy consumption and queue length by up to 31% and 95%, respectively.

Using FPGA as accelerators is gaining popularity in Cloud computing. Usually, FPGA accelerators in a datacenter are managed as a single resource pool. By issuing a request to this pool, a tenant can transparently access FPGA resources. FPGA requests usually arrive in batches. The objective of scheduling is to minimize the make-span of a given batch of requests, which is the completion time of the entire batch of jobs. As a result, either the responsiveness is improved, or the system throughput is maximized. The key technical challenge is the existence of multiple resource bottlenecks. An FPGA job can be bottlenecked by either computation (i.e., computation-intensive) or network (i.e., network-intensive), and sometimes by both. To the best of our knowledge, this is the first work that minimizes the make-span of batched requests for an FPGA accelerator pool in Cloud computing that considers multiple resource bottlenecks. In this paper, we design several scheduling algorithms to address the challenge. We implement our scheduling algorithms in an IBM Cloud system. We conduct extensive evaluations on both a small scale testbed and a large-scale simulator. Compared with the Shortest-Job-First scheduling, our algorithms can reduce the make-span by 36.25 percent, and improve the system throughput by 36.05 percent.

In the electronic system manufacturing process, the board-level functional test is recognized as the most significant step to prevent defective products from entering the market. In recent years, machine learning and data mining have proven to be efficient techniques in determining root cause from the problematic functional test result, especially when the integrated circuits (IC) are becoming increasingly highly-integrated. However, the test results are sometimes unavailable due to either abnormal ending of the test sequence or occasional system failures, which results in a decreased performance of data-driven diagnosis systems. In this paper, we propose a data imputation algorithm to predict the missing entries in the functional test result, by considering the correlation between test items with conditional specification. We evaluate our data imputation algorithm over the test results collected from three different stages of functional test on a line card used in the telecommunication system. The result shows that our proposed data imputation algorithm consistently outperforms other imputation techniques with various data-driven approaches in terms of diagnosing the root cause, increasing the diagnosis accuracy by an average of 28.13% compared to none data imputation, and 9.74% compared to the naive pass imputation.

Location information is playing a significant role in nowadays mobile applications. Performing indoor localization with existing WiFi infrastructure and smartphone motion sensor through statistical filtering has been proven to be a feasible solution. Many literature have resorted to particle filters to deal with the multi-modal and non-Gaussian problem associated with the filtering process. Although grid-based filters can approximate the true densities better compared with particle filters, their computational cost is extremely expensive, especially for large areas. In this paper, we develop a novel asymmetric grid-based filter to accommodate both high-resolution requirement and computational cost-efficiency. The evaluation over an indoor area of 3750m2has shown that our proposed method can achieve a median error of only 2.72m, which is 0.17m more accurate with only 24% of the computation cost compared to particle filters.

This paper studies how to optimize the interdependencies among the components in the interdependent Cyber-Physical Systems (CPS), in order to enhance the system robustness. In the interdependent CPS, some components may require the resources (or work conditions) provided by other components. Accordingly, small scale initial failure may incur large scale cascading failure as some of the working components may loss the resources (or work conditions) provided by the failed components. Due to this fact, we can optimize the resource allocation and change the interdependencies among components, so as to minimize the impact of cascading failure incurred by single component failure. To this end, we formulate the problem as an Integer Linear Programming (ILP) problem, and design an efficient algorithm based on progressive relaxation and rounding method to solve it. We also propose a greedy algorithm to quickly solve the problems in extreme large scale systems. In addition, we study how to allocate the redundant resources for the backup purpose and further enhance the system robustness. Simulation results show that if 1.3 times of the resources required by all the components are provided, we can eliminate the cascading failure incurred by single component failure.

Network Function Virtualization (NFV) is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named Service Function Chain (SFC) mapping, with which different network services are deployed over virtualized and shared platforms in data centers. However, such an evolution towards software-defined network functions introduces new challenges to network services which require high availability. One effective way of protecting the network services is to use sufficient redundancy. By doing so, however, the efficiency of physical resources may be greatly decreased. To address such an issue, this paper defines an optimal availability-aware SFC mapping problem and presents a novel online algorithm that can minimize the physical resources consumption while guaranteeing the required high availability within a polynomial time. Simulation results show that our proposed algorithm can significantly improve SFC mapping request acceptance ratio and reduce resource consumption.

Network Function Virtualization (NFV) is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named Service Function Chain (SFC) mapping, with which network functions (NFs) are deployed over virtualized and shared platforms in data centers. NFV typically requires a higher availability at the carrier grade than conventional cloud-based IT services, provided by native IaaS mechanism, for example. To achieve the high availability, each VNFs in an SFC can be provisioned with sufficient onsite backups. However, having too many backups may greatly decrease the resource utilization. Therefore, an open challenge is to find an effective method to allocate backup resource in order to maximize the number of SFC requests that can be served while meeting their heterogeneous availability requirements. To address this challenge, we first study how to allocate a minimum amount of backup resource for a single SFC request as an integer nonlinear program and provide an optimal solution. Based on the solution, we then propose an online heuristic algorithm for mapping multiple SFC requests with the objective of maximizing the number of SFC requests that can be served. Last but not least, we introduce a novel backup pooling mechanism to further improve the efficiency of backup resource usage. Through simulations, we show that our proposed algorithm can significantly reduce resource consumption due to backups and increase the number of co-existing SFC requests that can be served.

To take advantage of software defined networking (SDN) within a limited budget constraint, a natural strategy is to incrementally deploy a few SDN switches (and a limited amount of additional link bandwidth) into the legacy optical network. In such a hybrid optical network, operators can only change the routes of flows that traverse SDN switches. Therefore, to optimize SDN deployment, it is essential to decide the best places to deploy SDN resources (including SDN switches and link bandwidth) while taking the network traffic into consideration. In this paper, we propose a new SDN deployment scheme, called duplicated deployment, to provide a simple and efficient way for a hybrid network. Based on the proposed deployment scheme, we for the first time define the joint duplicated deployment and routing (DDR) problem for throughput maximization (or optimal deployment) with a given budget constraint on the additional SDN resource cost. Due to the NP-Hardness of the DDR problem, we then present an approximation algorithm based on the traffic mapping and randomized rounding methods, and prove that the approximation factor is (O(log n);O(log n)) in the worst case and (O(1);O(1)) under most practical situations for link capacity and flow-table size constraints, where n is the number of devices (including SDN switches and legacy routers) in the hybrid network. Through extensive simulations, we demonstrate high efficiency of our joint deployment and routing algorithm. For example, our proposed algorithm can improve the network throughput by about 26% compared with existing routing mechanisms with the same amount of extra resources.

Technological breakthroughs allow us to collect data with increasing spatio-temporal resolution from complex interaction systems. The combination of high-resolution observations, expressive dynamic models, and efficient machine learning algorithms can lead to crucial insights into complex interaction dynamics and the functions of these systems. In this paper, we formulate the dynamics of a complex interacting network as a stochastic process driven by a sequence of events, and develop expectation propagation algorithms to make inferences from noisy observations. To avoid getting stuck at a local optimum, we formulate the problem of minimizing Bethe free energy as a constrained primal problem and take advantage of the concavity of dual problem in the feasible domain of dual variables guaranteed by duality theorem. Our expectation propagation algorithms demonstrate better performance in inferring the interaction dynamics in complex transportation networks than competing models such as particle filter, extended Kalman filter, and deep neural networks.

This paper investigates a new application of vehicular sensing: detecting and reporting the slippery road conditions. We describe a system and associated algorithm to monitor vehicle skidding events using smartphones and OBD-II (On board Diagnostics) adapters. This system, which we call the VehSense, gathers data from smartphone inertial sensors and vehicle wheel speed sensors, and processes the data to monitor slippery road conditions in real-time. Specifically, two speed readings are collected: 1) ground speed, which is estimated by vehicle acceleration and rotation, and 2) wheel speed, which is retrieved from the OBD-II interface. The mismatch between these two speeds is used to infer a skidding event. Without tapping into vehicle manufactures' proprietary data (e.g., antilock braking system), VehSense is compatible with most of the passenger vehicles, and thus can be easily deployed. We evaluate our system on snow-covered roads at Buffalo, and show that it can detect vehicle skidding effectively.

Location information has become a key component of many applications in mobile and pervasive computing, and the ability to accurately predict the mobility of clients allows these applications to provide better service. However, existing location predictors rely heavily on a significant amount of empirical knowledge to function well. In this paper, we develop a novel framework to predict unknown locations when only little location information is available. Specifically, we first extract WiFi locations from WiFi scan results, then a mobility model is built based on the resulted WiFi location graph with connectivity information, finally, we make location predictions with little known location data with Gibbs sampling over the mobility model. Using a data set containing 31 fairly complete WiFi traces collected over three months as ground truth, we compare our proposed approach with other existing state-of-the-art location predictors. The experimental results show that our framework can achieve 83% location prediction accuracy with only three location samples each day, 15% better than Markov and Bayesian predictors which heavily rely on empirical knowledge.

Widely used over the Internet to encrypt traffic, HTTPS provides secure and private data communication between clients and servers. However, to cope with rapidly changing and sophisticated security attacks, network operators often deploy middleboxes to perform deep packet inspection (DPI) to detect attacks and potential security breaches, using techniques ranging from simple keyword matching to more advanced machine learning and data mining analysis. But this creates a problem: how can middleboxes, which employ DPI, work over HTTPS connections with encrypted traffic while preserving privacy? In this paper, we present SPABox, a middlebox-based system that supports both keyword-based and data analysis-based DPI functions over encrypted traffic. SPABox preserves privacy by using a novel protocol with a limited connection setup overhead. We implement SPABox on a standard server and show that SPABox is practical for both long-lived and short-lived connection. Compared with the state-of-the-art Blindbox system, SPABox is more than five orders of magnitude faster and requires seven orders of magnitude less bandwidth for connection setup while SPABox can achieve a higher security level.

Network Function Virtualization (NFV) is promising to lower the network operator's capital expenditure and operational expenditure by replacing proprietary hardware-based network equipment with software-based virtual network functions that can be consolidated into telecom clouds. In particular, NFV provides an efficient way to deploy network services using service function chains that consist of a set of virtual network functions interconnected by virtual links. A practical and yet theoretically challenging issue related to NFV Management and Orchestration is how to jointly optimize the topology design and mapping of multiple service function chains, which is called the JTDM problem. In this paper, we develop an Integer Linear Programming (ILP) model to formulate the JTDM problem with the objective of minimizing the bandwidth consumption in the physical substrate. We propose a novel heuristic algorithm, namely Closed-loop with Critical Mapping Feedback (CCMF), to efficiently address this problem. Through comprehensive simulations, we demonstrate that the CCMF algorithm is efficient in terms of the bandwidth consumption in various scenarios, and can achieve a bandwidth consumption that is close to the minimum obtained by ILP.

This paper studies how to determine an optimal order of recovering interdependent Cyber Physical Systems (CPS) after a large scale failure. In such a CPS, some failed devices must be repaired first before others can. In addition, such failed devices require a certain amount of repair resources and may take multiple stages to repair. We consider two scenarios: 1) reserved model where all the required repair resources should be prepared at the beginning of repairing a device; and 2) opportunistic model where we can partially repair a device with only part of the required resources. For each scenario, we model it using an Integer Linear Programming (ILP) and use a relaxation and rounding method to design an ILP based algorithm. In addition, we also design a Dynamic Programming (DP) based algorithm. Simulation results show that ILP based algorithm outperforms DP based algorithm by 10%-20% in systems with less than 200 failed devices, but DP based algorithm can support extreme large size systems with more than 5000 failed devices.

During the one minute it takes to read this abstract, two billion smartphones worldwide will perform billions of Wifi channel scans recording the signal strength of nearby Wifi Access Points (APs). Yet despite this ongoing planetary-scale wireless network measurement, few systematic efforts are made today to recover this potentially valuable data. In this paper we ask the question: “Are the smartphone channel scans useful in monitoring enterprise Wifi networks?” More specifically, can these client-side measurements provide new insights compared to the AP-side measurements that enterprise Wifi networks already perform? Beginning with two Wifi scan datasets collected on two large scale smartphone testbeds, we conduct case studies that show how smartphone channel scans can be used to (1) improve AP spectrum management, and (2) predict the impact of AP failure or overload. In each case, a walk on the client side yields valuable insights for network operators that are otherwise impossible to gain from AP-side measurements, and together our results demonstrate the value of smartphone channel scans.

For many emerging mobile broadband services and applications, the source and destination are located in the same local region. Consequently, it is very important to design access networks to facilitate efficient local data exchange. In the past few years, most existing studies focus on either the wired or wireless domains. In this paper, we aim to exploit both the wired and wireless domains. Specifically, we consider a Fiber-Wireless access network in which a passive optical network (PON) connects densely deployed base stations. In such a scenario, we propose a novel access scheme, namely, NCDA, where the main idea is to utilize both network coding and device association. To understand the potentials of NCDA, we first formulate a mixed integer nonlinear programming (MINLP) to minimize the weighted number of packet transmissions (WNT), which is related to both the system capacity and energy consumption. We then theoretically analyze the tight upper bounds of the minimal WNT in the PON, which helps us to approximate the original problem by a mixed integer linear programming (MILP). Next, we develop efficient algorithms based on linear programming relaxation to solve the optimal NCDA problem. To validate our design, we conduct extensive simulation experiments, which demonstrate the impact of important network parameters and the promising potentials of the proposed scheme.

It is a common view in Software Defined Network (SDN) that the flow table plays the most significant role in SDN architecture, but suffers from the limited TCAM chips. The shortage of flow table storage strongly impacts the quality of service (QoS) provided by SDN, but requires rational solutions. In this paper, we present a practical on-line approach based on the decision tree structure to solve this problem. Our performance is evaluated by the comparison with other existing technologies.

Surface transportation is of a great importance in urban life. Fueled by the promise of Smart City, it is becoming more and more common to provide WiFi services in urban Public Transportation System (PTS). In this paper, we present a practical method to make use of the WiFi service provided on buses to estimate real-time urban traffic condition. We validate the proposed method in a city district and show that it is an excellent alternative or supplement of the existing traffic condition estimation services.

Efficient wireless channel allocation is becoming a more and more important topic in wireless networking. Dynamic channel allocation is believed to be an effective way to cope with the shortage of wireless channel resource. Up to now, a number of auction mechanisms have been designed to solve the problem of dynamic channel redistribution. Such designs deal with either the problem of single channel allocation or the problem of multiple channels allocation with an assumption of the same per-channel valuation. However, considering the recent outcomes of researches on throughputs of adaptive-width channels and the needs of wireless users in practice, we need to provide buyers with a way to submit various combinatorial bids for channels. This motivates our work on designing a more practical auction mechanism to solve the problem of channel redistribution. In this paper, we propose SPECIAL, which is a Strategy-Proof and EffiCIent multi-channel Auction mechanism for wireLess networks. SPECIAL guarantees the strategy proofness of the channel auction, exploits wireless channels' spatial reusability, and achieves high channel allocation efficiency. Numerical results demonstrate that SPECIAL prevents buyers from manipulating the auction, and achieves high performance.

Relay assignment significantly affects the performance of the cooperative communication, which is an emerging technology for the future mobile system. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. However, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As the optimal solutions to the two problems are hard to find, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithms for M21-SRA-MMTcan significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTTcan achieve the close-to-optimal performance.

Network Function Virtualization (NFV) provides an effective way to reduce the network provider's cost by allowing multiple Virtual Networks (VNs) to share the underlying physical infrastructure. In the NFV environment, especially when supporting multicast service over the VNs, reliability is a critical requirement in the process of VN mapping since the failure of one virtual node can cause the malfunction of all the subsequent nodes that receive multicasting data from it. In this paper, for the first time, we study how to efficiently map VNs for reliable multicast services, while taking into consideration the max-min fairness of the reliability among distinct VNs. We propose a Mixed Integer Linear Programming (MILP) model to determine the upper bound on the max-min fairness reliability. In addition, an efficient heuristic, namely Uniform Reliability Mutation based Genetic (URMG) algorithm, is developed to address reliable multicast VN mapping with a low computational complexity. By encoding multicast tree construction and link mapping into path selection, taking into consideration the max-min reliability fairness goal, and the networking reliability factors during mutation, URMG can globally optimize the reliability and its fairness of all the multicast VN requests. Through extensive simulations, we demonstrate that URMG achieves close to the optimal reliability fairness with a much lower time complexity than the MILP and yields a significant performance improvement in terms of reliability fairness, bandwidth consumption and transmission delay comparing with other heuristic solutions.

Indoor location information plays a fundamental role in supporting various interesting location- aware indoor applications. Widely deployed WiFi networks make it feasible to perform indoor localization by first establishing a received signal strength (RSS) map covering the whole area based on a signal propagation model, then determining a location from an online RSS measurement given the RSS map. However, challenges remain in practical deployments, due to inaccurately estimated RSS values in the RSS map and insufficient number of access points (APs) in large indoor areas. To address these challenges, we develop a robust, cost-effective and scalable localization system (REAL). Our approach takes the error from the indoor radio signal propagation model into consideration. It also exploits information of unobserved APs at a given location and an optimal clustering method in the location searching phase. Our real-world experimental results demonstrate that REAL achieves considerable localization accuracy at a very low training cost even for a large indoor area. In addition, the results show that our scheme can also be effectively applied to Bluetooth networks with sparse signal coverage.

Network Function Virtualization (NFV) allows multiple Virtual Networks (VNs) to share the underlying physical infrastructure via VN mapping, thus improving the utilization of physical resources. In this paper, for the first time, we study the multicast service-oriented VN mapping that can support big data applications over Elastic Optical Networks (EONs). Since the problem of minimizing the spectrum consumption in multicast service-oriented VN mapping is NP-hard, we propose an efficient heuristic algorithm, called Integrated Genetic and Simulated Annealing (IGSA) algorithm to address the problem with low computational complexity. By encoding node mapping, multicast tree construction, link mapping and spectrum requirements in the same gene and auto-adjusted evolution, and utilizing simulated annealing to find the fittest multicast requests mapping order, IGSA can perform joint optimization for all the multicast requests in a global way. Through extensive simulations, we demonstrate that IGSA outperforms the other heuristic solutions in terms of spectrum consumption, blocking probability and normalized throughput, while achieving close to minimum spectrum consumption with a much lower time complexity than MILP.

Availability, as a part of Service Level Agreement (SLA), is a critically important issue in cloud services, as an application may not be able to run after certain server or network failures. Cloud service providers seek to not only fulfill the SLA, but also simultaneously minimize their operating costs, which are dominated by the energy consumption. In order to minimize the impact of a server/switch failure inside the datacenter on a single application, one would like to spread out the Virtual Machines (VM) for the application across different racks. However, in doing so, the power consumption may increase significantly. In this paper, we develop a variance-based metric to measure the risk of violating the availability requirement. We then propose two heuristic algorithms to place VMs in online and offline manners, respectively. These algorithms aim to strike a balance between minimizing the risk of violating the availability requirement and minimizing the energy, in order to reduce the overall cost.

Lack of an accurate and low-cost method to reconstruct indoor maps is the main reason behind the current sporadic availability of digital building floor plans. The conventional approach using professional equipment is very costly and only available in the most popular areas. In this paper, we propose and demonstrate CrowdMap, a crowd sourcing system utilizing sensor-rich video data from mobile users for indoor floor plan reconstruction with low-cost. The key idea of CrowdMap is to first jointly leverage crowd sourced sensory and video data to track user movements, then use the inferred user motion traces and context of the image to produce an accurate floor plan. In particular, we exploit the sequential relationship between each consecutive frame abstracted from the video to improve system performance. Our experiments in three college buildings show that CrowdMap achieves a precision of hallway shape around 88%, a recall around 93% and a F-measure around 90%. In addition, we achieve on average 9.8% room area error and on average 6.5% room aspect ratio error. The evaluation result demonstrates a significant improvement of accuracy compared with other crowd sourcing floor plan reconstruction systems.

Crowdsourcing is a technology with the potential to revolutionize large-scale data gathering in an extremely cost-effective manner. It provides an unprecedented means of collecting data from the physical world, particularly through the use of modern smartphones, which are equipped with high-resolution cameras and various micro-electrical sensors. In this paper, we address the critical task of reconstructing the indoor interior view of a building from crowdsourced data. We propose, design, and prototype IndoorCrowd2D, a smartphone-empowered crowdsourcing system for indoor scene reconstruction. We first formulate the problem via trackable models and then employ a divide and conquer approach to address the inherently incomplete, opportunistic, and noisy crowdsourced data. By utilizing the image information and sensory data in a coordinated way, our system demonstrates high result-accuracy, as well as allows a gradual build-up procedure of the hallway skeleton. Our evaluation result shows that IndoorCrowd2D achieves a precision around 85%, a 100% recall and a F-score around 95% for reconstructing college buildings from 1,151 datasets uploaded by 25 users. This reveals that our image and sensor hybrid method is more robust to overcome errors and outliers as compared to image-only method.

In this paper, we study the multiobjective optimization problem for green network routing. Although traditional commonly used multiobjective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one objective as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff among all objectives. Accordingly, we induce a Nash bargaining framework, which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. Finally, to evaluate the efficiency of our proposed framework, we implement it into two multiobjective optimization cases for network green routing. The first case is load balancing and energy efficiency optimization for intradomain routing, and the second one is the energy efficiency optimization of two domains for interdomain routing.

A central challenge in developing cloud datacenters Service Level Agreements is the estimation of downtime distribution of a set of provisioned servers over a service window, which is compounded by three facts. First, while steady-state probabilities have been derived for birth-death processes involving server failures and repairs, they could be highly inaccurate under transience. Furthermore, steady-state cannot be assured under typical service windows. Therefore, estimation of transient distributions is essential. Second, the processes of failures and repairs may follow any distribution and hence need to be extracted using system log data and modeled using appropriate general distributions. Third, downtime distributions over service windows depend on the number of servers and their deployment structure for a contract. We develop an efficient and generalized sample path randomization approach to precisely estimate transient probabilities under three different checkpointing strategies and three flexible failure distribution models. The estimators are unbiased, consistent, efficient and sufficient. Their asymptotic convergence is established. The estimation algorithms are computationally efficient in solving practical problems and yield rich information on transient system behaviors. The methodology is general and extensible to various server failure and repair processes characterized using birth-death modeling.

Virtual multi-input multi-output (MIMO) or vMIMO is becoming an attractive technology to achieve spatial diversity in wireless networks without using additional antennas, and to reduce power consumption by cooperation among multiple nodes. As data gathering is one of the most important operations in many sensor network applications, this paper studies energy-efficient data gathering in wireless sensor networks using vMIMO. We define the joint vMIMO and data gathering (vMDG) problem, which is NP-hard. We also propose a distributed method called D-vMDG as an approximation algorithm. This algorithm first constructs a tree-like topology by taking the unique features of vMIMO into account. Then, an energy-efficient routing protocol based on dynamic programming is proposed for each node on the constructed topology. Our theoretical analysis shows that D-vMDG can achieve an approximation ratio of O(1). Our simulations show that D-vMDG decreases the energy consumption by 81 and 36 percent compared to the well-known MDT [26] and MIMO-LEACH [19] algorithms respectively.

Multirate opportunistic routing was proposed to achieve high throughput by exploiting multi-user diversity and transmission rate diversity in wireless networks. However, the performance of multirate opportunistic routing still cannot be guaranteed when participating nodes are contributed by different parties and thus have selfish behaviors. In this paper, we present the first Cooperation-Optimal protocol for Multirate Opportunistic routing and forwarding, namely COMO, which guarantee the faithfulness of each player, and thus achieve the social efficiency and strongly Pareto efficient Nash equilibrium with the faithfulness as a given property. Here, social efficiency means that the end-to-end throughput should be maximized, while in a strongly Pareto efficient Nash equilibrium, no one can improve her utility without decreasing the utility of at least one other player. We not only rigorously prove the game-theoretic properties of our incentive protocol, but also extensively evaluate its performance on the ORBIT wireless testbed. Experiment results show that our protocol can prevent participating nodes' selfish behaviors and guarantee high performance of the multirate opportunistic routing protocol with a low communication overhead.

Recent innovations in Network Virtualization and Elastic Optical Networks (EONs) enable flexible deployment of optical networks as a service. However, one open challenge is how to embed Virtual Optical Network (VON) requests onto the physical substrate network to maximize the sharing of physical resources, which is the so called Virtual Network Embedding (VNE) problem. EONs are prone to the fragmentation of spectral resources during the process of routing and spectrum allocation. The fragmentation of spectral resources in the substrate fiber links may lead to the blocking of incoming virtual network requests. This degrades the utilization of the physical resources of the Infrastructure Providers and also, decreases the revenue of the Service Providers. In this paper, we propose a novel virtual network embedding algorithm called Alignment and Consecutiveness-aware Virtual Network Embedding (ACT-VNE), which takes into account the spectrum alignment and relative loss in spectrum consecutiveness when mapping virtual nodes/links onto the physical substrate nodes/links. We also propose a min-max reconfiguration scheme called Relative Consecutiveness Loss-aware and Misalignment-aware Virtual Network Reconfiguration (RCLM-VNR) that minimizes relative consecutiveness loss and maximizes alignment with adjacent links when reconfiguring the virtual network. Simulation results show that ACT-VNE and RCLM-VNR yield a lower blocking probability and a higher link utilization ratio, which leads to better utilization of the physical resources and increased revenue.

The hundreds of millions of deployed smartphones provide an unprecedented opportunity to collect data to monitor, debug, and continuously adapt wireless networks to improve performance. In contrast with previous mobile devices, such as laptops, smartphones are always on but mostly idle, making them available to perform measurements that help other nearby active devices make better use of available network resources. We present the design of PocketSniffer, a system delivering wireless measurements from smartphones both to network administrators for monitoring and debugging purposes and to algorithms performing realtime network adaptation. By collecting data from smartphones, PocketSniffer supports novel adaptation algorithms designed around common deployment scenarios involving both cooperative and self-interested clients and networks. We present preliminary results from a prototype and discuss challenges to realizing this vision.

Server consolidation schemes whereby each server is replaced with a virtual machine (VM) and multiple such VMs are run on a single physical server can reduce the number of physical servers needed, and in turn, both the cost and energy consumption in datacenters. However, existing schemes have not fully exploited the flexibility in the usage and allocation of virtualization resources, so as to allow one application originally deployed on a single large VM (LVM) to be split and hosted by multiple smaller VMs (SVM). Using multiple SVM instead of a LVM enables resource allocation at a smaller granularity and hence may further increase the utilization and reduce the number of physical servers. However, a major challenge to be overcome when deploying multiple SVMs for one application is to preserve the performance of the application in terms of e.g., response delay. In this paper, we show through experiment based data analysis that in order to preserve the performance of the application, one needs to allocate sufficient resources to each SVM, and the total amount of resources required by all the SVMs will exceed that required by the LVM. Nevertheless, we also show that by using the proposed heuristic algorithm called VM Splitting and Assignment (VMSA), we can substantially improve the utilization and reduce the number of physical servers.

The choice of relay nodes significantly affects the performance of wireless cooperative networks. Previous research mostly focused on dedicating one relay node to a source node in the network. However, fairness can be improved by sharing each relay node among more than one source node. This paper first defines the shared relay assignment for (max-min) fairness (SRAF) problem, and formalizes it using a mixed integer program. We then propose a heuristic algorithm (RRA) to solve this problem. The algorithm mainly uses the binary search and rounding mechanisms to implement the shared relay assignment, so that the minimum throughput of all source nodes is improved. The theoretical analysis proves that the proposed algorithm can reach the approximate performance of 2+ε, where ε is an arbitrarily small positive number. An improved version of RRA, called IRRA, can improve the minimum throughput while still preserving the worst-case performance. Our simulations show that the IRRA algorithm can achieve about 18% improvement over the best existing approach in the minimum throughout among the source nodes.

Due to lack of optical RAM buffers in fast optical switches (FOS), statistical multiplexing technologies using FOS like Optical Burst Switching (OBS) or Optical Packet Switching (OPS) are expected to have higher data losses than conventional electronic networks. Consequently, applications transferring data by means of TCP can suffer from a lower throughput. In this paper, we show that this low-throughput problem is mainly an artifact caused by the conventional TCP congestion control algorithms, and can be remedied by using a simple yet effective stop-and-wait congestion control algorithm instead, as long as the propagation delay between TCP source and TCP destination is small compared to the transmission time of an optical packet. We show that such a condition holds for a wide range of scenarios, including fat-tree-based data center networks. We also show that the throughput achieved in a FOS network using stop-and-wait can be the same as, or higher than that in an equivalent, conventional electronic network.

Relay assignment significantly affects the performance of cooperative communications. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. On the other hand, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As both of these problems are NP-hard, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithm for M21-SRA-MMT can significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTT can achieve the close-to-optimal performance.

The articles in this special issue focus on energy efficiency techniques deployed in optical fiber networking.

Network virtualization facilitates sharing and efficient utilization of computing and bandwidth resources of an underlying substrate network. As network virtualization becomes popular, it is important to efficiently map a virtual infrastructure (VI) onto a substrate network, such that the survivability of the former can be guaranteed against failures in the latter. In this paper, we study a virtualization layer approach to survivability, whereby the virtualization layer customizes a VI request with redundant nodes and links according to its reliability requirements and then passes limited information about the augmented VI to the physical layer, where the mapping of the augmented VI takes place. More specifically, we develop a flexible scheme to enhance the original VI graph with K redundant nodes, in order to fight against an arbitrary substrate node failure. In addition, a scenario-based component group (SBCG) concept is proposed to describe resource sharing of enhanced VI requests at the physical layer. We also develop an efficient heuristic that takes advantage of the limited information on SBCG to reduce costs when mapping the enhanced VI to the substrate network. The efficiency of the proposed solution is compared using extensive simulation under various performance metrics. It is shown that the K-redundant-node scheme with SBCG information is more cost efficient than the existing 1-redundant-node solution.

Different from the conventional operation mode in existing taxi dispatch systems, in this paper, we envision a new cyber-technology enabled taxi dispatch system which can efficiently provide vacant taxis with cruising route suggestions, not to respond to any specific pick-up request but instead, hoping to find prospective customers (such system is also complementary to the conventional operation mode). We address the Taxi Cruising Guidance (TCG) problem with the objective being to minimize the Global Vacant Rate (GVR), which is defined as the ratio of traveling miles with no passenger onboard, to the total traveling miles in a given time period. We propose a number of heuristic solutions and conduct comprehensive performance evaluations based on large-scale simulations. A case study is also presented by utilizing real traces collected from taxis in the city of Shanghai. As part of our research, we leverage a well-known microscopic traffic simulator (called TRANSIMS) to demonstrate that the application of TCG is also beneficial to traffic management.

Spectrum-sLICed Elastic optical path (SLICE) networks enable elastic and flexible allocation of spectral resources. SLICE networks distribute data on a number of sub-carriers overlapped in frequency domain to provide efficient sub-wavelength and super-wavelength traffic accommodation. In SLICE networks, a routing and spectrum allocation algorithm assigns a spectrum path to any demand with just enough contiguous sub-carriers while following the sub-carrier consecutiveness and spectrum-continuity constraints. In this paper, we propose novel sub-carrier allocation algorithms that employ the proposed Interference Graph technique to assign sub-carriers to a spectrum path based on the historic traffic profile. These algorithms try to achieve minimal disruptions to the live connections while minimizing the blocking probability. Simulation results show that the proposed schemes can effectively accommodate the dynamic traffic while minimizing the network reconfiguration cost in SLICE networks, with or without the traffic prediction.

We consider a promising application in Vehicular Cyber-Physical Systems (VCPS) called On-road Ad Delivery (OAD), where targeted advertisements are delivered via roadside APs to attract commuters to nearby shops. Different from most existing works on VANETs which only focused on a single technical area, this work on OAD involves technical elements from human factors, cyber systems and transportation systems since a commuter's shopping decision depends on e.g. the attractiveness of the ads, the induced detour, and traffic conditions on different routes. In this paper, we address a new optimization problem in OAD whose goal is to schedule ad messages and allocate a limited amount of AP bandwidth so as to maximize the system-wide performance in terms of total realized utilities (TRU) of the delivered ads. A number of efficient heuristics are proposed to deal with ad message scheduling and AP bandwidth allocation. Besides largescale simulations, we also present a case study in a more realistic scenario utilizing real traces collected from taxis in the city of Shanghai. In addition, we use a commercial traffic simulator (PARAMICS) to show that our proposed solutions are also useful for traffic management in terms of balancing vehicular traffic and alleviating congestion.

To protect user privacy in wireless mesh networks (WMNs), it is important to address two major challenges, namely: flow untraceability and movement untraceability, which prevent malicious attackers from deducing the flow paths and the movement tracks of mobile devices. For these two privacy requirements, most existing approaches rely on encrypting the whole packet, appending random padding, and applying random delay for each message at every intermediate node, resulting in significant computational and communication overheads. Recently, linear network coding (LNC) has been introduced as an alternative but the global encoding vectors (GEVs) of coded messages have to be encrypted so as to conceal the relationships between the incoming and outgoing messages. In this paper, we aim to explore the potential of LNC to ensure the flow untraceability and movement untraceability. Specifically, we first determine the necessary and sufficient condition, with which the two privacy requirements can be achieved without encrypting either GEVs or message contents. We then design a deterministic untraceable LNC (ULNC) scheme to provide flow untraceability and movement untraceability when the sufficient and necessary condition is satisfied. Finally, we discuss the effectiveness of the proposed ULNC scheme against traffic analysis attacks in WMNs.

Traffic grooming can effectively utilize the transmission capacity of WDM networks by properly multiplexing low-speed traffic flows onto high-capacity wavelength channels. In order to maximize the wavelength resource and cut down network costs associated with, e.g. OEO conversion for time-varying yet predictable traffic, we propose a novel predictive and incremental (PI) traffic grooming scheme, named PI-grooming. A conventional traffic grooming approach for fluctuated traffic is to run an algorithm that (re)assigns the traffic flows to as a few wavelengths as possible based only on the current traffic demands of these flows. This however will lead to a lot of OEO traffic. The proposed PI-grooming considers the existing flow assignment, the current traffic demands, and the expected traffic demands in the near future. We show that, compared with the conventional approach, PI-grooming can effectively minimize the amount of OEO traffic while still using a very small number of wavelengths.

Efficient wireless channel allocation is becoming a more and more important topic in wireless networking. Dynamic channel allocation is believed to be an effective way to cope with the shortage of wireless channel resource. In this paper, we propose SPECIAL, which is a Strategy-Proof and EffiCIent multi-channel Auction mechanism for wireLess networks. SPECIAL guarantees the strategy-proofness of the channel auction, exploits wireless channels' spatial reusability, and achieves high channel allocation efficiency.

In this paper, we study the tradeoff between two important traffic engineering objectives: load balance and energy efficiency. Although traditional commonly used multi-objective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one of the two objectives as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff between these two objectives. Accordingly, we induce a Nash bargaining framework which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed in order to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. In addition, the insights from this work are also useful for achieving a fair tradeoff in other multi-objective optimization problems.

Vehicular Cyber-Physical Systems (VCPS) provide human drivers with various services related to road safety, and on-road infotainments. Since a service (message) delivery includes service transmission, service display and driver processing, many challenges arise due to limited network resources, possible pre-emption and contention between services for the display and non-negligible driver processing delay. In this paper, we address a new Driver-centric Service Delivery Problem (DSDP) from a cross-disciplinary resource allocation standpoint. Our goal is to deliver a number of services to a set of intended drivers in a given time period so as to maximize the system-wide performance in terms of total utility income (TUI) to drivers. We show that DSDP differs from all existing problems and is NP-Complete. A number of efficient heuristics are proposed to address several issues, including wireless transmission failure as well as distributed implementation of the multi-sender systems. Utilizing real traces collected from taxis in the city of Shanghai, we also present a case study in a more realistic scenario and conduct comprehensive simulations providing numerical results.

Speeding is one of the most prevalent contributing factors in traffic crashes. The prediction of speeding is important to reduce excessive speeds and prevent speeding-related traffic accidents and injuries. Speeding (either intentional or unintentional) is a consequence of inappropriate speed control. This paper extends a previous mathematical model of driver speed control to provide quantitative predictions of intentional and unintentional speeding. These predictions consist of the time at which the driver exceeds the speed limit and the magnitude of speeding. Based on these modeling predictions, this paper develops an intelligent speeding prediction system (ISPS) to prevent the occurrence of speeding. An experimental study using a driving simulator is conducted to evaluate the ISPS. We find no significant difference between modeled predictions and experimental results in terms of the time and magnitude of intentional speeding. In addition, the ISPS can successfully predict the majority of unintentional speeding instances, with only a small portion of unnecessary speeding warnings. Applications of the ISPS to reduce driving speed and prevent the real-time occurrence of speeding and speeding-related traffic accidents are discussed.

The locator/ID separation protocol (LISP) proposed for addressing the scalability issue of the current Internet has gained much interest. LISP separates the identifier and locator roles of IP addresses by end point identifiers (EIDs) and locators, respectively. In particular, while EIDs are used in the application and transport layers for identifying nodes, locators are used in the network layer for locating nodes in the network topology. In LISP, packets are tunneled from ingress tunnel routers (ITRs) to egress tunnel routers in a map-and-encapsulation manner. For this purpose, an ITR caches on demand some mappings between EIDs and locators. Since hosts roam from place to place, however, their EID-to-locator mappings change accordingly. Thus, an ITR cannot store a mapping permanently but maintains for every mapping a timer whose default value is set to a given cache timeout. If the cache timeout for a mapping is too short, an ITR frequently queries the mapping system (control plane), resulting in a high traffic load on the control plane. On the other hand, if the cache timeout for a mapping is too long, the mapping could be outdated, resulting in packet loss and associated overheads. Therefore, it is desirable to set appropriate cache timeout for mapping items. In this paper, we analytically determine the optimal cache timeout for EID-to-locator mappings cached at ITRs to minimize the control plane load while remaining efficient for mobility. The results presented here provide valuable insights and guidelines for deploying LISP.

To cope with challenging problems faced by traditional multicast routing protocols, many branching-router (BR)-based multicast routing schemes with desirable features have been proposed. However, the current BR-based methods still lack efficient multicast management and suffer from a long join latency, leading to a disappointing mobility performance. In this paper, we propose a novel BR-based multicast architecture with a corresponding multicast routing protocol supporting multicast receiver mobility. In the proposed multicast architecture, a new management entity called multicast controller (MC) is used to handle most of the multicast management-related tasks, while other routers in the network construct a multicast tree according to the proposed Branching-Router-based Multicast routing protocol with Mobility support (BRMM). Besides, the fast handover of multicast service can be supported by BRMM through the pre-establishment of temporary multicast paths. Through extensive simulation and analysis, we show that BRMM outperforms existing protocols and has many other attractive features.

Wireless Sensor Networks (WSNs) will play a significant role at the “edge” of the future “Internet of Things.” In particular, WSNs with transmit-only nodes are attracting more attention due to their advantages in supporting applications requiring dense and long-lasting deployment at a very low cost and energy consumption. However, the lack of receivers in transmit-only nodes renders most existing MAC protocols invalid. Based on our previous study on WSNs with pure transmit-only nodes, this work proposes a simple, yet cost effective and powerful single-hop hybrid WSN cluster architecture that contains not only transmit-only nodes but also standard nodes (with transceivers). Along with the hybrid architecture, this work also proposes a new MAC layer protocol framework called Robust Asynchronous Resource Estimation (RARE) that efficiently and reliably manages the densely deployed single-hop hybrid cluster in a self-organized fashion. Through analysis and extensive simulations, the proposed framework is shown to meet or exceed the needs of most applications in terms of the data delivery probability, QoS differentiation, system capacity, energy consumption, and reliability. To the best of our knowledge, this work is the first that brings reliable scheduling to WSNs containing both nonsynchronized transmit-only nodes and standard nodes.

Opportunistic networking is an important technique to enable users to communicate in an environment where contemporaneous end-to-end paths are unavailable or unstable. To support end-to-end messaging in opportunistic networks, a number of probabilistic routing protocols have been proposed. However, when nodes are selfish, they may not have incentives to participate in probabilistic routing, and the system performance will degrade significantly. In this paper, we present novel incentive schemes for probabilistic routing that stimulates selfish nodes to participate. We not only rigorously prove the properties of our schemes, but also extensively evaluate our schemes using GloMoSim. Evaluation results show that there is an up to 75.8% gain in delivery ratio compared with a probabilistic routing protocol providing no incentive.

Virtual multi-input-multi-output (or vMIMO) communication is a promising technology to improve the spatial diversity of wireless networks. Using this mechanism, multiple single-antenna nodes can coordinate their transmissions and receptions so as to reduce power consumption. This paper studies the problem of constructing an energy-efficient topology in wireless sensor networks using vMIMO communication. We first define the problem involving joint optimization of vMIMO, partner selection and topology control. As this problem is NP-Complete, a distributed and heuristic algorithm, called vMIMO topology control (VMTC), is proposed to solve this problem. The algorithm uses an improved binary searching method to obtain an initial power assignment. A local competition method is then adopted to implement the partner selection. At last, we reduce the power consumption of each node by using efficient vMIMO modes. Our theoretical analysis show that this algorithm can achieve an approximate performance of O(1). Our simulations show that VMTC helps to decrease the power consumptions by about 32% compared to the existing algorithms.

Current transfer-incapable carpooling (TIC) scheme cannot fully utilize vehicles' available space because a carpooling passenger has to go from her origin to her destination by getting a ride from only one vehicle. This is akin to insist on delivering some packets only using one-hop communications, which usually performs worse than allowing multi-hop communications. In this paper, inspired by the “Store-and-Forward” strategy used in Delay-Tolerant Networks (DTN), we propose a new carpooling paradigm called transfer-allowed carpooling (TAC), with which each passenger can be served by more than one vehicle to go from her origin to her destination, thus increasing the carpooling performance. In particular, when given a) a number of carpooling requests (each with a maximum waiting-time and a maximum number of transfers for a passenger), and b) a list of participating vehicles (each specifying a maximum detour distance for a driver), we address a new optimization problem called Transfer-Allowed Carpooling whose objective is to maximize the successful carpooling ratio (SCR). Two effective strategies have been proposed from a driver and passenger standpoint, respectively. In addition to conducting large-scale simulations, we also present a case study in a more realistic setting by utilizing real routes collected from taxis in the city of Shanghai. Our major results are: 1) the proposed TAC approach can significantly improve SCR (by 35% to 60%), compared to the traditional TIC approach; and 2) allowing one transfer (i.e., the maximum number of transfers=1) improves the carpooling efficiency most, while allowing more than one transfer does not bring any noticeable benefits.

Opportunistic networking is an important technique to enable users to communicate in an environment where contemporaneous end-to-end paths are unavailable or unstable. To support end-to-end messaging in opportunistic networks, a number of probabilistic routing protocols have been proposed. However, when nodes are selfish, they may not have incentives to participate in probabilistic routing, and the system performance will degrade significantly. In this paper, we present a novel incentive scheme for probabilistic routing that stimulates selfish nodes to participate. We not only rigorously prove the properties of our scheme, but also extensively evaluate our scheme using GloMoSim. Evaluation results show that there is an up to 75.8% gain in delivery ratio compared with a probabilistic routing protocol providing no incentive.

Protecting networking infrastructures from malicious attacks is important as a successful attack on a high data rate link can cause the loss or delay of large amounts of data. In this paper, we consider a proactive approach where the ISPs are willing to allocate some (limited) resources to defend the networking infrastructures against the attacks. We aim to answer where and how much the defending resource should be placed so that the expected data loss can be minimized no matter where the attacker may launch the attack. We model the problem as a 2-player zero-sum game where the payoffs are measured by the maximum network flow. In order to overcome the unique challenges of such payoffs, we transform the payoffs into explicit piece-wise functions through multi-parametric linear programming (MP-LP) and divide the entire strategy space into a set of critical regions. We prove that a global Nash Equilibrium (NE) exists when there is only one critical region. However, when the number of critical regions is greater than 1, there is no global NE. We also prove that there exists one and only one local NE in each critical region. We then design a mixed-strategy solution. Our results have shown that to dedicate all defending resources to one min-cut set when there are multiple min-cut sets will not be an optimal solution, however, min-cut strategies will have higher probabilities to be selected in the mixed-strategy solution when the defending resource is limited.

With the increasingly popular virtualization of both computing and networking resources in a distributed system (called a physical substrate), multiple virtual infrastructures (VIs) can share the physical resources of the underlying substrate, and accordingly even a single failure in the substrate can affect a large number of VIs and the services they offer. Thus, the problem of efficiently mapping a VI to a substrate while guaranteeing the VI's survivability in the event of failures in the substrate becomes important. In this paper, we study the survivable VI mapping problem to protect against link failures in the substrate. We first propose a solution based on traditional shared protection (survivable virtual infrastructure mapping algorithm, P-SVIMA), and then propose a novel VI node migration protection-based algorithm (MP-SVIMA) to minimize the computing and communication resource costs. The MP-SVIMA scheme takes advantage of the flexibility in where VI nodes are mapped in the substrate by migrating a VI node from the originally mapped physical location to a different location after a physical link fails in order to recover from link failures. We compare the efficiency of our solutions using simulations under various performance metrics.

It is essential to consider drivers' perceptions and reactions when building Vehicular Cyber-Physical Systems (VCPS) since the effectiveness and efficiency of VCPS will largely depend on how drivers could benefit from such a system. This paper considers, for the first time, novel service scheduling problems from a Human Factors (HF) standpoint by taking into consideration the following fact: a driver may not be able to receive more than one service in a short period of time, even if multiple services can be transmitted to the driver from the conventional communications and networking standpoint. We study a family of the HF-aware Service Scheduling (HFSS) Problems, where the goal is to deliver up to n services, each having a time-dependent (and possibly decreasing) utility to a subset of intended drivers so as to minimize the system-wide total utility loss due to unsuccessful delivery of some services. We show that such problems are different from all existing problems. We formulate the basic HFSS problem (BHFSSP) using Integer Linear Programming (ILP) and prove its NP-Completeness. We then propose efficient heuristics for BHFSSP and its more general versions, and present numerical results from large-scale test cases. We also address several practical issues related to wireless transmission failures, distributed implementation in the multisender scenario, and other HF related considerations.

Cooperative communication is becoming an attractive technology as it can greatly improve the spatial diversity without additional antennas. This novel communication paradigm can effectively reduce power consumption via multi-node cooperation and resource allocation. This paper studies the energy-efficient node-disjoint multi-path routing for a given source-destination pair by joint route construction, relay assignment and power allocation methods. We first define a new bandwidth-power aware cooperative multi-path routing (BP-CMPR) problem, and formally prove its NP-hardness. The paper then presents a polynomial-time heuristic algorithm CMPR to solve the above problem. The algorithm adopts the Suurballe's method to find k minimal-weight node-disjoint paths from source to destination on a weighted graph. Then, dynamic programming is used to implement relay assignment and power allocation. The theoretical analysis shows that CMPR can reach approximation factors of 2 and \frac{4}{3} for BP-CMPR under the amplify-and-forward and decode-and-forward schemes respectively. The distributed version of the algorithm DCMPR is also presented for this problem. We also prove that both CMPR and DCMPR construct the same cooperative multi-path routing, and show via simulations that the performance of the proposed scheme is more than 15% better than that of a traditional multi-path routing scheme, and close to the optimal result for BP-CMPR in variety of situations.

The concept of on-road video services aims to provide infotainments to drivers/passengers during their trip. Instead of using paid services such as 3G/LTE/WiMAX communication technologies or exclusive Mobile TV Systems, free road-side APs can also be utilized to deliver videos available on the Internet to mobile users for cost saving. However, whether this approach can provide satisfactory user experience is a fundamental problem to be studied. We introduce a new performance metric called User Experience Index (UEI) for on-road video services, which takes the following into design consideration: 1) whether users can enjoy video services during their entire traveling; and 2) whether videos have been interrupted during display. With UEI, we focus on optimizing video delivery with multiple road-side APs by addressing the Joint Video Delivery Problem (JVDP) with the objective being to maximize the average UEI (AUEI) of all users through dynamic AP bandwidth allocation. To the best of our knowledge, this work is the first on improving user experience for on-road video services. Two heuristic algorithms are proposed and numerical results from large-scale simulation are also presented.

Simple yet cost effective hybrid Wireless Sensor Networks (WSN) with both standard nodes and transmit-only nodes are promising for their great potential as the "edge" of the "Internet of Things". However the lack of receivers at many transmit-only nodes in the hybrid network renders most existing MAC protocols invalid. Our previous efforts showed the benefits of this hybrid architecture for building single-hop efficient and reliable hybrid WSN cluster for QoS aware applications. This work explores the capability of building multi-hop communications in a hybrid WSN with multiple clusters (where each cluster consists of a sink as well as a certain number of standard nodes and transmit-only nodes) via a cross-layer protocol design. The proposed M-QoMoR protocol and HPAssist scheme are built based on the resource information from the underlying MAC layer. Through the analysis and extensive simulations, we showed that the hybrid WSN architecture can efficiently support multi-hop communications across multiple hybrid clusters. It also achieves certain performance boost that is not viable in the previous single hybrid WSN clusters.

This paper presents an effective solution to the known TCP incast problem in data center networks. The incast problem refers to a drastic TCP throughput drop when the number of servers synchronically sending data to the same receiver is too large. Our proposed approach utilizes the link bandwidth as fully as possible but without significant packet losses by limiting the number of concurrent senders to a reasonable value. Based on the concept of bandwidth delay product, our approach conservatively estimates the reasonable number of concurrent senders. Our approach does not modify TCP protocol itself and can thus be applied to any TCP variant, and works regardless of the type of data center network topology and throughput limitation. Analysis and simulation results show that our approach eliminates the incast problem and noticeably improves TCP throughput.

Electrical switching, when used to interconnect tens to hundreds of pods (each having a thousand of servers) in the core of a data center, incurs a high cost and power consumption and is expected to be replaced with optical switching soon. In this paper, we consider hypercube-based interconnection using optical switches in the core and study novel routing and wavelength assignment schemes for a new paradigm called Labeled Optical Burst Switching with Home Circuits (LOBS-HC). In particular, we propose a simple scheme called complementary HC assignment (CHA) for a 2-dimensional cube and ring, and extend the study to a n-cube (n >; 2) and generalized hypercube (GHC) by applying the concept of Spanning Balanced Trees (SBTs). We determine the number of wavelengths (and transceivers) needed in each case and show that it can be significantly lower than that needed with conventional wavelength routing using optical circuit switching (OCS). We also show compared the proposed solution with other proposed electronic or hybrid switching based solutions.

As network virtualization becomes popular, the problem of efficiently mapping a virtual infrastructure (VI) over a substrate network while guaranteeing its survivability in the event of failures becomes increasingly important. In this paper, we study the survivable VI mapping problem to recover from facility node failures. We develop two solutions namely the 1-redundant scheme and the K-redundant scheme for surviving facility node failures while minimizing network resource costs. We also model the two schemes as a MILP problem and propose efficient heuristics based on the MILP formulations. We compare the efficiency of our solutions using simulation under various performance metrics.

It is essential to consider drivers' perceptions and reactions when building Vehicular Cyber-Physical Systems (VCPS) since the effectiveness and efficiency of VCPS will largely depend on how drivers could benefit from such a system. This paper considers, for the first time, novel service scheduling problems from Human Factors (HF) standpoint by taking into consideration the following fact: a driver may not be able to receive more than one service in a short period of time, even if the VCPS can somehow transmit multiple services to the driver from the conventional communications and networking standpoint. We study a family of the HF-aware Service Scheduling (HFSS) Problems, where the goal is to deliver up to n services, each having a time-dependent (and non-increasing) utility to a subset of intended drivers so as to minimize the system-wide total utility loss due to unsuccessful delivery of some services. We show that such problems are different from all existing problems. We formulate the basic HFSS problem (BHFSSP) using Integer Linear Programming (ILP) and prove it and other more general problems to be NP-Complete. We also propose efficient heuristics and present numerical results from large-scale test cases.

A major disruption may affect many network components and significantly lower the capacity of a network measured in terms of the maximum total flow among a set of source-destination pairs. Since only a subset of the failed components may be repaired at a time due to e.g., limited availability of repair resources, the network capacity can only be progressively increased over time by following a recovery process that involves multiple recovery stages. Different recovery processes will restore the failed components in different orders, and accordingly, result in different amount of network capacity increase after each stage. This paper aims to investigate how to optimally recover the network capacity progressively, or in other words, to determine the optimal recovery process, subject to limited available repair resources. We formulate the optimization problem, analyze its computational complexity, devise solution schemes, and conduct numerical experiments to evaluate the algorithms. The concept of progressive network recovery proposed in this paper represents a paradigm-shift in the field of resilient and survivable networking to handle large-scale failures, and will motivate a rich body of research in network design and other applications.

In this work, we study algorithms for cooperative search and survey using a fleet of Autonomous Underwater Vehicles (AUVs). Due to the limited energy, communication range/bandwidth, and sensing range of the AUVs, underwater search and survey with multiple AUVs brings about several new challenges since a large amount of data needs to be collected by each AUV, and any AUV may fail unexpectedly. To address the challenges and meet our objectives of minimizing the total survey time and traveled distance of AUVs, we propose a cooperative rendezvous scheme called Synchronization-Based Survey (SBS) to facilitate cooperation among a large number of AUVs when surveying a large area. In SBS, AUVs form an intermittently connected network (ICN) in that they periodically meet each other for data aggregation, control signal dissemination, and AUV failure detection/recovery. Numerical analysis and simulations have been performed to compare the performance of three variants of SBS schemes, namely, Alternating Column Synchronization (ACS), Strict Line Synchronization (SLS), and X Synchronization (XS). The results show that XS can outperform other SBS schemes in terms of the survey time and the traveled distance of AUVs. We also compare XS with nonsynchronization-based survey and the lower bound on the survey time and traveled distance. The results show that XS achieves a close to optimal performance.

Stationary wireless sensor networks (WSNs) fail to scale when the area to be monitored is unbounded and the physical phenomenon to be monitored may migrate through a large region. Deploying mobile sensor networks (MSNs) alleviates this problem, as the self-configuring MSN can relocate to follow the phenomenon of interest. However, a major challenge here is to maximize the sensing coverage in an unknown, noisy, and dynamically changing environment with nodes having limited sensing range and energy, and moving under distributed control. To address these challenges, we propose a new distributed algorithm, Causataxis, which enables the MSN to relocate toward the interesting regions and adjust its shape and position as the sensing environment changes. (In Latin, causa means motive/interest. A taxis (plural taxes) is an innate behavioral response by an organism to a directional stimulus. We use Causataxis to refer to an interest driven relocation behavior.) Unlike conventional cluster-based systems with backbone networks, a unique feature of our proposed approach is its biosystem inspired growing and rotting behaviors with coordinated locomotion. We compare Causataxis with a swarm-based algorithm, which uses the concept of virtual spring forces to relocate mobile nodes based on local neighborhood information. Our simulation results show that Causataxis outperforms the swarm-based algorithm in terms of the sensing coverage, the energy consumption, and the noise tolerance with a slightly high communication overhead.

We focus on a new class of home networking applications that enable wireless communication between multimedia devices using the WiMedia MAC protocol. Applications like streaming video from DVD players to HDTVs, generate high data rates and can easily saturate the bandwidth even at the rates provided by UWB transmissions. Thus we need to enhance the MAC layer to improve bandwidth utilization and efficiently handle the requirements of such applications. In this paper, we propose a new TDMA frame structure for the WiMedia MAC protocol that uses the specific characteristics of the traffic to minimize MAC and PHY overhead while providing delay bounds within the tolerable limits of the applications. Our results show that the proposed frame structure can provide up to 10% increase in bandwidth utilization over the WiMedia frame structure and achieve a throughput gain of about 48Mbps at the highest data rate of the MB-OFDM physical layer.

As virtualization becomes more and more popular, how to guarantee survivability of a virtual infrastructure (VI) over a wide-area optical network is increasingly important. In this paper, we approach the problem of survivable VI mapping (SVIM) from a few unique perspectives. One of the most distinguishing perspectives is that a large-scale regional failure could destroy one or more facility nodes to which some VI nodes are mapped. Accordingly, redundant facility nodes at different geographical locations and redundant optical connections have to be provisioned such that the VI can still be mapped after the failure. Another distinguishing perspective is that with failure-dependent protection, the SVIM problem can be decomposed into several instances of the basic non-survivable VI mapping (NSVIM) problem, whose solution permits effective sharing of the redundant resources among all failures. In this paper, we first formulate the minimum-cost SVIM problem using mixed integer linear programming (MILP). We then propose an efficient heuristic solution to NSVIM, based on which two novel heuristic SVIM algorithms called Separate Optimization with Unconstrained Mapping (SOUM) and Incremental Optimization with Constrained Mapping (IOCM). Simulations are performed to study and compare the performance of the MILP and heuristics.

Low cost and low power Wireless Sensor Networks (WSN) with transmit-only nodes are attracting more attention due to their advantages in achieving a good balance of cost, fine-grained sensing and differentiated service for data collection applications. This work addresses the reliability and performance issues of a single-hop hybrid WSN with both transmit-only nodes and standard nodes and proposes the RH-QoMoR protocol, whose robust scheme is able to provide reliable data services and the EARE (Enhanced Automatic Resource Estimation) scheme can remove time synchronization overhead and provide more resources. The analysis and extensive simulation demonstrates its capability of providing the best possible performance to the high priority nodes under harsh environment as well as minimizing the energy consumption while maintaining QoS guarantee. The protocol can also efficiently handle dynamic network changes due to the packet loss and post-deployment adjustment.

All-optical multicast routing (AOMR) is implemented by the concept of light-tree in WDM networks. The cost-optimal multicast light-tree is NP-hard to compute, especially when taking sparse splitting into account. Thus many heuristic algorithms have been proposed. In this paper, the approximation ratios of two classical heuristic AOMR algorithms for sparse splitting WDM network are studied. Let K be the number of destinations in a multicast session, it is proved that Reroute-to-Source (R2S) algorithm achieves a tight approximation ratio equal to K in the non-equally-weighted WDM network while Member-Only (MO) algorithm approaches the optimal solution with a ratio inferior to (K2+3K)/4 for any WDM network. It is also found that if the WDM network G is unweighted, both the approximation ratios of R2S and MO are no bigger than the diameter of the network Diam(G). Simulation results illustrate that both R2S and MO obtain good performances in candidate WDM backbone NSF network, which are far from the worst cases.

Optical Burst Switching is efficient for bursty traffic but also weak in guaranteeing the delivery of real-time traffic. In this paper, we propose to enhance OBS with an OCS-like feature by providing each source-destination pair with a wavelength sharable home circuit. These wavelength sharable home circuits not only provide guaranteed bandwidth for in-profile traffic to different destinations from the same source, but also allow out-of-profile traffic between any source and destination to be statistically multiplexed. The proposed OBS enhancement approach, called Labeled OBS with Home circuits or LOBS-H, is shown, through both analysis and simulations, to require less resources (e.g., wavelengths) than OCS in order to provide the same bandwidth guarantee service, or to result in a better loss and/or delay performance with the same amount of resources.

Low cost and low power consumption are two major design criteria in wireless sensor networks (WSN). To meet the increasing demand for localized fine-grained sensing with densely deployed WSNs, this paper proposes the use of a hybrid WSN that consists of nodes with standard transceivers and nodes with only transmitters. A two-phase Constrained-Scheduling based MAC protocol is proposed, which employs the "Automatic Resource Estimation (ARE)" method. Through analysis and extensive simulations, the proposed protocol is shown to achieve a significant performance improvement in terms of data delivery probability, QoS differentiation and energy minimization over existing MAC protocols for such networks. To the best of our knowledge, this work is the first effort to bring scheduling to WSNs that contains asynchronous and uncoordinated transmit-only nodes.

Contrary to Optical Circuit Switching (OCS), Optical Burst Switching (OBS) is efficient for bursty traffic but also weak in guaranteeing the delivery of real-time traffic. We have proposed an OBS enhancement approach, called Labeled OBS with Home Circuits or LOBS-HC, which provides each source-destination pair with a wavelength sharable home circuit for the real-time traffic, so it can guarantee lossless transmission with a short delay. In previous works, we have shown that LOBS-HC requires less resources and provides a better QoS to the real-time traffic than OCS, since it does statistical multiplexing. Here, we extend the study of LOBS-HC. First, we study a few possible design choices in LOBS-HC. Then we evaluate its performance under not only real-time traffic, but also best-effort traffic. Finally, we analyze the effects of the switching speed and the burst size on the performance.

Minimizing the worst-case playback delay (WPD) in VoD services is both critical and challenging. Given a fixed amount of bandwidth for broadcasting and patching, there is no prior work on determining the minimum WPD, let alone guaranteeing it. In this work, we propose novel schemes that leverage the unique properties of a TDM-based Passive Optical Network (PON) by performing rebroadcasting and patching at its Optical Network Unit (ONUs). For a given bandwidth available for VoD services in the PON, we derive the minimum worst-case playback delay (WPD), and also design optimal patch scheduling algorithm as well as ONU rebroadcast and patching channel assignment to guarantee such minimum WPD. Numerical results confirm the superiority of the proposed schemes over the existing ones in terms of both worst-case and average performance.

In an integrated fiber and wireless access (FiWi) network, multi-path forwarding may be applied in the wireless subnetwork to improve throughput. Due to the delay difference along multiple paths, reordered packets of a flow may arrive at the Optical Line Terminal (OLT) waiting for dispatching to the Internet, which may deteriorate the TCP performance. As all traffic in a FiWi network is sent out through the OLT, the OLT serves as a convergence node which naturally makes it possible to resequence packets at the OLT before they are sent to the Internet. The fundamental difference between resequencing at the end systems and resequencing at an intermediate node (e.g., the OLT) is that very tight resequencing delay can be tolerated in the latter. Thus, resequencing at the intermediate nodes must be fast enough. In this paper, we propose an integrated flow assignment and resequencing approach which jointly determines the probability of sending packets along each path from the source and needs virtually zero resequencing delay at the OLT to reduce the out-of-order probability when packets are injected to the Internet from the access network. Simulation results validate our analysis and the effectiveness of the proposed integrated flow assignment and resequencing approach.

In this work, we envision a fully collaborative network paradigm in which both the evolved Node Bs (eNBs) and the User Equipment (UE)s collaborate between themselves to achieve the full benefits of MIMO communication. One of the major building blocks in deploying fully collaborative networks is achieving efficient UE-UE collaboration. We study various UE-UE collaboration scenarios in the context of MIMO communications and evaluate them using an enterprise grade simulator. The results show significant improvements in the UE throughputs in a realistic cellular network. The studied UE-UE collaboration schemes are also applicable to similar collaborative relationships between UEs and other elements (e.g., relay stations) of a cellular network.

Video on demand (VoD) is one of the most important services for many network operators that deploy and operate optical access networks. It is crucial to design next generation optical access networks that can guarantee a high quality VoD service. In this paper, we address this challenging issue and focus on the worst-case playback delay (WPD), which cannot be guaranteed by Internet-based video streaming, and has not been well addressed previously in optical access networks. Specifically, we first propose an integrated Gigabit Passive Optical Network (GPON) and Wavelength Division Multiplexing PON (WDM PON) architecture. With the proposed architecture, an optical line terminal (OLT) can broadcast popular videos through GPON and deliver other videos through WDM-PON, while the optical network units (ONUs) can conduct patching for their end users. We then elaborate on two minimum-WPD schemes. In the first one, we assume that the video broadcast schedule is fixed at the OLT and develop an optimal patching scheme at each ONU such that the WPD is minimized. In the second one, we consider coordinated OLT broadcast scheduling and ONU patching. A heuristic algorithm which can achieve near-optimal WPD is proposed for coordinated OLT broadcast scheduling and ONU patching. Simulation results confirm the superiority of the proposed schemes over the existing ones in terms of both worstcase and average delay performance.

Secure distance-based localization in the presence of cheating beacon (or anchor) nodes is an important problem in mobile wireless ad hoc and sensor networks. Despite significant research efforts in this direction, some fundamental questions still remain unaddressed: In the presence of cheating beacon nodes, what are the necessary and sufficient conditions to guarantee a bounded error during a two-dimensional distance-based location estimation? Under these necessary and sufficient conditions, what class of localization algorithms can provide this error bound? In this paper, we attempt to answer these and other related questions by following a careful analytical approach. Specifically, we first show that when the number of cheating beacon nodes is greater than or equal to a given threshold, there do not exist any two-dimensional distance-based localization algorithms that can guarantee a bounded error. Furthermore, when the number of cheating beacons is below this threshold, we identify a class of distance-based localization algorithms that can always guarantee a bounded localization error. Finally, we outline three novel distance-based localization algorithms that belong to this class of bounded error localization algorithms. We verify their accuracy and efficiency by means of extensive simulation experiments using both simple and practical distance estimation error models.

Channel assignment is a very important topic in wireless networks. In this paper, we study FDMA channel assignment in a noncooperative wireless network, where devices are selfish. Existing work on this problem has considered Nash Equilibrium (NE), which is not a very strong solution concept and may not guarantee a good system performance. In contrast, in this work, we introduce a payment formula to ensure the existence of a Strongly Dominant Strategy Equilibrium (SDSE), a different solution concept that gives participants much stronger incentives. We show that, when the system converges to an SDSE, it also achieves global optimality in terms of system throughput. Furthermore, we extend our work to the case in which some radios have a limited tunability. We show that in such a case, nevertheless, it is generally impossible to have a similar SDSE solution; with additional assumptions on the numbers of radios and the types of channels, etc., we can again achieve an SDSE solution that guarantees optimal system throughput. Besides this extension, we also consider other extensions of our strategic game to achieve throughput fairness and to deal with possibly inconsistent information caused by players joining and leaving. Finally, we evaluate our design with simulated experiments. Numerical results verify that the system does converge to the globally optimal channel assignment with the proposed payment formula, and that the system throughput is significantly higher than that achievable with the random-based and NE-based channel assignment schemes.

Under the emerging paradigm of federated computing services (FCS), one can create multiple virtual infrastructures (VI), one for each distributed computing application or service offering. Each VI may consist of a number of geographically distributed computing clusters that are connected with a set of dedicated circuits. In general, a VI submitted by a user to the FCS provider is unmapped at the time of the submission in that the user does not specify which computing clusters to use. The primary challenge to the FCS provider in supporting these novel applications is to establish a VI optimally over the substrate network such as a WDM network connecting many computing clusters. In this paper, we study the optimization problems of jointly allocating computing and wavelength resources for establishing Vis. First, we devise a branch and bound algorithm based on the decomposition and Lagrangian relaxation techniques to obtain the exact optimal solution with the objective being the minimization of the resource leasing cost of a VI. Second, we propose efficient heuristics to deal with a large number of online requests for Vis and compare their performance with the optimal solution.

Improving throughput and delay is an important challenge in multi-hop wireless sensor networks. In this work, we propose ABC-MC, a simple multi-channel geographic forwarding scheme. ABC-MC is based on ABC which is a lightweight and reliable routing protocol where nodes do not need to set up or maintain routing/neighbor tables. A unique feature of ABC-MC is that it uses a channel prenegotiation mechanism to reduce delay. Another unique feature of ABC-MC is that it takes account of the channel usage information within three hops in channel selection to reduce interference. Experimental results show that ABC-MC outperforms other protocols in terms of the average delay and throughput performance.

We consider a class of single hop wireless sensor networks in which the sensor nodes collect data periodically and transmit it to a sink. To reduce the complexity, cost and energy consumption of the nodes we propose the use of an asymmetric transceiver model in which the sensor nodes can transmit to the sink using standard physical layer modulation schemes that support relatively high data rates but can receive from the sink using basic modulation schemes that can only support very low data rates. The use of the transceiver module in each sensor node is thus limited to receiving simple feedback in the form of a few bytes of ACK from the sink node. In this paper we propose and study a new MAC protocol that enables effective communication between the sensor nodes and sink in such a network. We develop an analytical model to evaluate the performance of the MAC protocol and verify these results through extensive simulations. We also present results from the implementation of the protocol on a test bed consisting of XSM motes and evaluate its performance in a real world scenario.

In this paper we devise a holistic solution to the pursuer-evader tracking problem taking into account the limitations of the wireless sensor networks (WSNs) as well as the dynamics of both the pursuer and evader. More specifically, we present an optimal strategy for the pursuer to capture the evader despite the delayed and imprecise information available at the pursuer-side. In order to minimize the communication overhead while ensuring capture, we provide an optimal evader sampling scheme that adjusts the sampling frequency based on the strategies of the pursuer and evader, as well as the distance between the pursuer and evader. We support our adaptive sampling scheme with a just-in-time delivery protocol that publishes the evader's location updates directly to the pursuer, reducing the communication overhead of tracking even further. To further enhance the tracking reliability, we use a two-level design of fault tolerance: 1) a double position advertisement scheme to mask single message losses, and 2) a breadcrumbs-based backup scheme for stabilizing from desynchronization.Our simulation results show that the adaptive sampling scheme guides the pursuer to capture the evader effectively, and reduces the communication overhead significantly compared to fixed rate sampling. Our simulation results also show that our two-level fault-tolerance strategy ensures high capture rates even under consecutive message losses.

We present a practical plant-and-play wireless sensor network system for entry-exit monitoring. Our system is easily configurable and robust, making it feasible to be deployed in a wide range of entry-exit monitoring applications. At the core of our system lies a novel MAC protocol that is self-synchronizing. Notably, our MAC protocol allows the nodes to maintain a very low duty cycle (the radios are in sleep mode 100% of the time in the absence of detections), while also enabling quick synchronization of the nodes (when needed) for a consistent classification of entry or exit events. We have deployed this system for monitoring a faculty parking lot at our university and integrated it with an SMS notification system to provide information on the availability of parking spots on demand. We present the parking lot occupancy trends obtained through this deployment and discuss some of the reliability issues encountered.

This paper proposes a novel medium access control scheme for low cost, single-hop wireless networks where the source nodes have a transmitter module but no receiver module and hence they can only transmit data to a sink but cannot receive any control signals, like an ACK or NAK, from any other node. The goal of the proposed scheme is to provide QoS (in terms of packet delivery probability) to the nodes in such a network, where the existing schemes like polling or scheduled transmissions, CSMA and ARQ will be ineffective because of the unavailability of a receiver module at the nodes. The proposed scheme uses distributed control and allows the nodes to transmit each packet an optimal number of times at random instants in time within the packet generation interval. We define two optimization problems based on minimizing total network traffic and maximizing the delivery probability of the class of nodes requiring the highest QoS, respectively, and develop mathematical formulae and efficient algorithms to solve them. Numerical analysis and simulation results show that our scheme can provide high QoS to networks of different sizes.

Various wireless and optical access technologies have been developed to address different issues in access networks. By combining the complementary characteristics of wireless and optical networks, a hybrid optical-wireless access network will enable broadband, ubiquitous, and cost-effective last-mile service to the users. In this paper, a reconfigurable optical backhaul leveraging both the standard Time Division Multiplexing Passive Optical Network (TDM-PON) technology and wavelength division multiplexed (WDM) ring is proposed to achieve a higher bandwidth efficiency than simply using point-to-point backhaul links. Furthermore, an integrated routing algorithm which can adapt to the change of overall demand among different service districts by taking advantage of the proposed optical backhaul is also proposed. An experimental testbed is implemented to evaluate the reconfigurable scheme and its feasibility. Also, simulation results show that the proposed integrated routing with load balancing can improve the performance in hybrid optical and wireless networks.

Fast and energy-efficient message delivery is an ultimate goal in multi-hop wireless sensor networks. To help achieve this goal, we propose ABC, a simple geographic forwarding scheme capable of bypassing routing holes. ABC is a lightweight and reliable routing protocol in that nodes do not need to set up or maintain routing or neighbor tables; instead, ABC achieves lightweight routing via its "Angled relaying" mechanism and uses the "Backoff time and relay Cancellation" mechanism to reduce contention and the number of retransmissions. One unique feature of ABC is that a relayed message is used as an implicit ACK to a previous sender. Another unique feature of ABC is its routing hole bypassing mechanism based on reactive boundary recognition. In this paper we provide an extensive analysis of ABC in terms of average hop count and average delay per hop. Simulation results also show that ABC outperforms other protocols in terms of average delay and number of transmissions per message delivery.

Data-intensive Grid applications require huge data transferring between multiple geographically separated computing nodes where computing tasks are executed. For a future WDM network to efficiently support this type of emerging applications, traditional approaches to establishing lightpaths between given source destination pairs are not sufficient because a computing task may be executed on any one of several computing nodes having the necessary resources. Therefore, lightpath establishment has to be considered jointly with task scheduling to achieve best performance. We study the optimization problems of jointly scheduling both computing resources and network resources. We first present the formulation of two optimization problems with the objectives being the minimization of the completion time of a job and minimization of the resource usage/cost to satisfy a job with a deadline respectively. When the objective is to minimize the completion time, we devise an optimal algorithm for a special type of applications. Furthermore, we propose efficient heuristics to deal with general applications with either optimization objective and demonstrate their good performances via simulation.

Channel assignment is a very important topic in wireless networks. In this paper, we study FDMA channel assignment in a non-cooperative wireless network, where devices are selfish. Existing work on this problem has considered Nash equilibrium (NE), which is not a very strong solution concept and may not guarantee a good system-wide performance. In contrast, in this work we introduce a payment formula to ensure the existence of a strongly dominant strategy equilibrium (SDSE), a much stronger solution concept. We show that, when the system converges to a SDSE, it also achieves global optimality in terms of effective system-wide throughput. Furthermore, we extend our work to the case in which some radios have limited tunability. We show that, in this case, it is generally impossible to have a similar SDSE solution; but, with additional assumptions on the numbers of radios and the types of channels, etc., we can again achieve a SDSE solution that guarantees globally optimal effective system throughput in the entire system. Besides this extension, we also consider another extension of our strategic game, which is a repeated game that provides fairness. Finally, we evaluate our design in experiments. Our evaluations verify that the system does converge to the globally optimal channel assignment with our designed payment formula, and that the effective system- wide throughput is significantly higher than that of anarchy and Nash equilibrium (NE).

Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious beacon nodes, what are the necessary and sufficient conditions to guarantee a bounded error during 2-dimensional location estimation? Under these necessary and sufficient conditions, what class of localization algorithms can provide that error bound? In this paper, we try to answer these questions. Specifically, we show that, when the number of malicious beacons is greater than or equal to some threshold, there is no localization algorithm that can have a bounded error. Furthermore, when the number of malicious beacons is below that threshold, we identify a class of localization algorithms that can ensure that the localization error is bounded. We also outline two algorithms in this class, one of which is guaranteed to finish in polynomial time (in the number of beacons providing information) in the worst case, while the other is based on a heuristic and is practically efficient. For completeness, we also extend the above results to the 3-dimensional case. Experimental results demonstrate that our solution has very good localization accuracy and computational efficiency.

Stationary wireless sensor networks (WSNs) fail to scale when the area to be monitored is open (i.e borderless) and the physical phenomena to be monitored may migrate through a large region. Deploying mobile sensor networks (MSNs) alleviates this problem, as the self-configuring MSN can relocate to follow the phenomena of interest. However, a major challenge here is to maximize the sensing coverage in an unknown, noisy, and dynamic sensing environment while minimizing energy consumption. Another major challenge is to maintain network connectivity for each MSN node during relocations. To address these challenges, we propose a new distributed algorithm, Causataxis1, that enables the MSN to relocate toward the interesting regions and adjust its shape and position as the sensing environment changes. Causataxis achieves scalable control of the MSN via a backbone-tree infrastructure maintained over clusterhead nodes, and achieves agility via localized cluster formation and dissolution. Unlike conventional cluster-based systems with backbone networks, a unique feature of our proposed approach is its bio-system inspired growing and rotting behaviors with coordinated locomotion. We compare Causataxis with a custom tuned swarm algorithm, which uses the concept of virtual spring forces to relocate mobile nodes based on local neighborhood information. Our simulation results show that Causataxis can outperform the swarm based algorithm in terms of the sensing coverage, the energy consumption, and the noise tolerance with a slightly high communication overhead.

In triangulation-based coverage, a group of three mobile sensor nodes (MSNs) position themselves to form an equilateral triangle. A larger area is covered with many such smaller triangles as three MSNs move from one triangle to another. Such a scheme has several applications in localization, 3D imaging and coordinated search operation. In this work, we introduce an efficient mobile traversal algorithm (MTA) that provides a triangulation-based coverage of a field that can be approximated as a rectangle. We analyze the MTA in terms of the MSNs' travel distance and time taken to complete the traversal process. The bounds derived are also useful in determining the amount of energy consumption by the MSNs.

Broadcast protocols play a vital role in multihop wireless networks. Due to the broadcast nature of radio signals, a node's interference range can be larger than its transmission range, i.e., it can interfere with other node's reception even if the latter is not within its transmission range. To design an efficient broadcast protocol, both the collision and the interference among multiple transmissions must be addressed. However, most of the previous works on wireless broadcast protocols either treated interference in the same way as collision or did not consider interference at all. In this paper, we study a more general model in which interference is distinguished from collision, and propose a simple and yet efficient interference and collision free broadcast protocol. Our objective is to minimize the makespan, i.e., the earliest time such that every node receives the message. By exploiting the geometry property of the nodes that interfere with each other, we show that our algorithm is a constant approximation algorithm, it guarantees to deliver the message to all nodes within a small constant factor of the optimal makespan. We apply our algorithm under both the unit disk graph model and the more realistic radio irregularity model. The experimental results show that our algorithm consistently outperforms the previous algorithms.

Given a probabilistic graph G representing an intermittently connected network and routing algorithm A, we wish to determine a delivery subgraph G[A] of G with at most k edges, such that the probability Conn2(G[A]) that there is a path from source s to destination t (in a graph H chosen randomly from the probability space defined by G[A]) is maximized. To the best of our knowledge, this problem and its complexity has not been addressed in the literature. Also, there is the corresponding distributed version of the problem where the delivery subgraph G[A] is to be constructed distributively, yielding a routing protocol. Our proposed solution to this routing problem is multi-fold: First, we prove the hardness of our optimization problem of finding a delivery subgraph that maximizes the delivery probability and discuss the hardness of computing the objective function Conn2(G[A]); Second, we present an algorithm to approximate Conn2(G[A]) and compare it with an optimal algorithm; Third, we focus on intermittently connected networks, and model the users' mobility within them; and Fourth, we propose an edge-constrained routing protocol (EC-SOLAR-KSP) based on the insights obtained from the first step and the contact probabilities computed in the third step. We then highlight the protocol's novelty and effectiveness by comparing it with a probabilistic routing protocol, and an epidemic routing protocol proposed in literature.

In this paper, we study search algorithms for using a set of autonomous and cooperative mobile sensor nodes (MSN) with limited sensing and communication ranges to search a large area. Our objectives include minimizing the total search time and the travel distance of MSNs while enabling fault tolerance to possible MSN failures. We propose a new rendezvous scheme, namely X synchronization (XS) to facilitate the exchange of both data and control signals among the MSNs during search. We also devise a way to calculate appropriate timeout periods used to detect an MSN failure at rendezvous points and describe how surviving MSNs subsequently carry out the search mission. Numerical analysis and simulations have been performed to evaluate the performance of XS. The results show that XS can outperform other rendezvous schemes in terms of the total search time and the average travel distance of MSNs.

A triangulation-based coverage scheme using mobile sensor nodes (MSNs) has several applications in localization, 3D imaging and coordinated search operation. In this work, we introduce an efficient failure-tolerant mobile traversal algorithm (FTMTA) that provides a triangulation-based coverage of a field. FTMTA employs N MSNs such that, upto N -- 3 node failures can be tolerated to complete the coverage. FTMTA achieves three objectives: (a) as N increases, the total time to cover the field decreases in the absence of a failure; (b) each MSN travels a minimum distance; (c) upon a failure, the remaining MSNs efficiently complete the coverage of the field.

In this paper, we evaluate TCP performance in optical burst switched (OBS) networks with multiple TCP flows. Several performance metrics are studied, which include TCP throughput, fairness, retransmission ratio and stableness the OBS network with multiple TCP connections. The study is also extended to burst TCP (BTCP) proposed for OBS networks in particular. Our work provides a more comprehensive understanding of the congestion control and stableness of current existing TCP in OBS networks and sheds lights on the better TCP design for the OBS networks.

Geometric routing using source-destination locations has been widely suggested as a scalable alternative to conventional routing approaches in mobile ad hoc networks. Recently, there has been considerable attention on face routing in planar graphs constructed from overlay graphs in wireless networks. Given a plane tiled into an infinite mesh of polygons, an overlay graph is defined as one in which a graph edge is defined between two adjacent polygons if a radio link exists between any two nodes located in these polygons. We consider the problem of constructing a connected planar graph from the overlay graph, and geometric routing in such graphs. We prove a specific property of such graphs known as the redundancy property and propose a distributed routing algorithm called grid traversal algorithm (GTA) based on the redundancy property of overlay graphs. The algorithm is both localized and energy efficient, but may not guarantee connectivity in pathological cases. Simulations show that such disconnections are rare in practise and that GTA performs very well in terms of percentage of data delivered, data delay and overhead compared to GPSR, a geometric routing protocol that routes on a planar graph extracted from the unit disk graph.

In this paper, we present a new integrated optical network architecture called polymorphous, agile and transparent optical networks (PATON) which combines different resource scheduling schemes based on polymorphous optical burst switching (POBS) suitable for a variety of applications and services, and address several key technical issues related to the control and management of PATON. These issues include traffic adaptation and grooming, signaling and control packet format, polymorphic control for resource scheduling, and extentions to GMPLS. The resulting PATON compares favorably with other existing approaches presented in our related work [X. Liu et al., 2006].

Routing in Intermittently Connected Networks (ICN) is a challenging problem due to the time varying nature of network connectivity. In this work, we focus on a special class of ICN formed by mobile ad hoc users called ICMAN. A recent study of wireless users' mobility traces revealed that users usually move between a small set of socially significant places called hubs to form so-called orbits [6]. To exploit the knowledge about such mobility profiles, we propose a hub-level routing method, and two versions of user-level routing methods. We compare these approaches with Epidemic routing [21] to highlight the advantages of sociological orbit aware routing within ICMAN in terms of achieving a higher throughput and a lower overhead.

Wireless broadband networks, especially WiMAX networks, have emerged in the industry recently and many challenging research issues arise. In this paper, we proposed a heuristic clustering algorithm for minimum cost wireless broadband overlay network deployment Moreover, we also modified and implemented two heuristic algorithms based on classic linear programming based capacitated facility location algorithms. We analyzed the theoretical worst-case performance ratio of our algorithm and our numerical results showed that our algorithm performs much better in practical network settings

As more and more wireless subscribers access the Internet through cellular networks, Internet data traffic, which is known to be long range dependent (LRD), will soon dominate the conventional voice traffic. In this paper, we study the impact of such LRD data traffic on the statistical characteristics of multi-access interference (MAI) and signal to interference-plus-noise ratio (SINR) in a code division multiple access (CDMA) network. Through analysis and simulation, we show that the time-scaled MAI and SINR have slow decaying tail distributions due to the LRD data traffic. As a result, the outage probability is larger for data users than that for voice users. To improve the performance of the CDMA network in the presence of LRD data traffic, we propose a variable period prediction scheme to predict MAI or the equivalent number of active users. We show that the proposed variable period prediction is not only more accurate for data users but also less memory-consuming than existing fixed period prediction. In addition, rate control based on variable period prediction can achieve lower outage probability and higher throughput for data users than that based on fixed period prediction.

Energy conservation is important for ad hoc networks. However, little effort has been made to carefully study the energy cost metrics upon which the design of various energy efficient algorithms is based. More specifically, most existing energy consumption models only considered energy cost of exchanging data packets, although common wireless protocols also need control packets (e.g., ACK) for reliable data transmissions. Without considering the energy cost of exchanging control packets, these existing models tend to underestimate the actual energy consumption, and thus leading to suboptimal energy efficient designs. In this paper, we develop energy consumption models that take into account energy consumption due to data packets, control packets and retransmission. We verify by simulations that our models match the actual energy consumption much better than existing models. In addition, we show that a minimum energy routing protocol based on an accurate model of ours performs much better than those based on existing models

In this paper, we present our experience in implementing an experimental end-node architecture and communications middleware that enables devices to (a) create and maintain ad-hoc connectivity in the absence of infrastructure support, (b) heal IP network partitions and resume active TCP sessions during intermittent connectivity, (c) detect network infrastructure (e.g. access points) when available and use it, and (d) discover devices and services currently attached to the network. In broader terms, our communications middleware includes a connection manager (CM) that provides and maintains the link-level and IP infrastructures and heal network partitions as they occur, arid a session manager (SM), which provides end-to-end active TCP-session support against intermittent connectivity and IP address changes. Finally, we provide some experimental results from a working implementation of our communications middleware on Linux devices and results from its support, of two example distributed applications, namely a distributed file browser and a multiplayer game

In this paper, we introduce a novel concept of integrating ''macro-mobility" information obtained from the sociological movement pattern of mobile MANET users into routing. The extraction of this mobility information is based on our observation that the movement of a mobile user exhibits a partially repetitive "orbital" pattern involving a set of "hubs" in practice. This partially deterministic movement pattern is both practical and useful in locating nodes and routing packets to them without the need for constant tracking or flooding. Leveraging on this hub-based orbital pattern, we propose a sociological orbit aware location approximation and routing (SOLAR) protocol. Through extensive performance analysis we show that SOLAR significantly outperforms conventional routing protocols like dynamic source routing (DSR) and location aided routing (LAR) in terms of higher data throughput, lower control overhead, and lower end-to-end delay.

Long range dependent (LRD) traffic whose single server queue process is Weibull Bounded (WB) is first analyzed. Two upper bounds on the individual session's queue length of LRD traffic under the generalized processor sharing (GPS) scheduling discipline are then contributed. It is shown that the index parameter in the upper bound of one LRD flow, (in addition to the decay rate and the asymptotic constant), may be affected by other LRD flows. A new concept, called LRD isolation, is subsequently contributed and accompanying it, a new technique is contributed to check whether a flow, with a given GPS weight assignment, can be guaranteed to be LRD isolated. This technique is also amenable for use in an online call admission control (CAC) scenario. When existing flows have already been assigned contract weights that cannot be changed, our technique can be used to determine minimum contract weights to be assigned to a new flow in order to guarantee the flow to be LRD isolated. The results are also extended to a PGPS (packet-based GPS) scheduler and relevant numerical results are provided to show the usefulness of our bounds and LRD isolation technique.

We introduce a new protocol based on the optical-burst-switched (OBS) transport to support synchronous services such as SONET/SDH. We term this protocol synchronous optical burst switching (SOBS) and describe the problems and challenges of supporting both synchronous and asynchronous traffic with various bandwidth granularities. We discuss the problems of path signaling, periodic reservations, and burst framing. We also highlight the importance of burst-level grooming, develop related analytical formulations, and present results of various simulations.

Waveband switching (WBS) wherein wavelengths are grouped into bands and switched as a single entity can reduce cost and complexity of switching nodes by minimizing the port count. In this paper, we study the effect of wavelength conversion on the performance of WBS networks with reconfigurable multi-granular optical cross-connects (MG-OXC) to satisfy online traffic. Since wavelength conversion is still expensive and can potentially increase the number of used ports in WBS networks, efficient usage of wavelength converters is of practical interest. We propose a novel heuristic algorithm, called waveband assignment with path-graph (WAPG), which takes efficient wavebanding and efficient usage of wavelength converters into consideration when satisfying new lightpath requests. We apply the WAPG algorithm in WBS networks with full, intra-band, or limited number of wavelength converters, and compare with the FirstFit and RandomFit algorithms. Our results indicate that the proposed algorithm performs significantly better in terms of the blocking probability as well as the number of used wavelength converters.

Waveband switching (WBS) in conjunction with multigranular optical cross-connect (MG-OXC) architectures can reduce the cost and complexity of switching nodes. In this paper, we study two MG-OXC architectures: the single-layer and the multilayer MG-OXCs, and compare their performances with both off-line (static) and on-line (dynamic) traffic. In the off-line case, a near-optimal integer linear programming models (called off-ILP models) for each of the MG-OXC architectures aims to reduce the size of the MG-OXC, and compares them with the balanced path routing with heavy-traffic first waveband assignment (BPHT) heuristic developed for the multilayer MG-OXCs. The two architectures are then compared in terms of the number of wavelength a fixed number of wavelengths on each link. We also propose a novel efficient heuristic algorithm, called maximum overlap ratio (MOR) to satisfy new requests and compare it with the on-ILP, first-fit, and random-fit algorithms. We compare the two architectures in terms of the blocking probability, weighted (request) acceptance ratio, which serves as an indication of hops (WH) and MG-OXC ports required to satisfy a given set of traffic demands. In the on-line case, we develop an on-line ILP model called on-ILP, which aims to minimize the number of used ports for each of the MG-OXC architectures, given the revenue generated by satisfying the requests. Our results indicate that using WBS with either single-layer or multilayer MG-OXCs can reduce the number of ports (hence the size and cost) of the switching nodes compared to using ordinary OXCs (without waveband switching). In particular, in the off-line case, using single-layer MG-OXCs provides a greater reduction in size than multilayer MG-OXCs, while in the online case, using the multilayer MG-OXC is better.

In this paper, we characterize analytically the multiaccess interference (MAI) in wireless CDMA sensor networks with uniformly random distributed nodes and study the tradeoff between interference and connectivity. To provide a guideline for improving system behavior, three competitive deterministic topologies are evaluated along with the random topology in terms of link-level and network-level (routing) performance. The impact of the signature code length and the receiver design on network performance for different topologies is also studied.

A key problem in optical burst switching (OBS) is to schedule as many bursts as possible on wavelength channels so that the throughput is maximized and the burst loss is minimized. In this paper, we use competitive analysis to analyze the worst-case performance of a large set of scheduling algorithms, called best-effort online scheduling algorithms, for OBS networks, and establish a number of interesting upper and lower bounds on the performance of such algorithms. A surprising discovery is that the worst-case performance of any best-effort online scheduling algorithm is primarily determined by the maximum to minimum burst length ratio, followed by the range of offset time. Furthermore, if all bursts have the same burst length and offset time, all best-effort online scheduling algorithms generate the same optimal solution, regardless how different they may look like. Our analysis can also be extended to some nonbest-effort online scheduling algorithms, such as the well-known Horizon algorithm, and establish similar bounds. Based on the analytic results, we give guidelines for several widely discussed OBS problems, including burst assembly, offset time setting and scheduling algorithm design, and propose a new channel reservation protocol called VFO to improve the worst-case performance. Our simulation shows that it is quite often for an online scheduling algorithm to exhibit its (near) worst-case performance. Thus improving the worst-case performance is essential. Our simulation also suggests that VFO reduces the average burst loss rate by as much as 35%

Constructing wavelength division multiplexing (WDM) switches with cheap components and low complexity is an important problem in optical networking. Typically, there are two request models widely considered. In one model, a connection request asks to go from a wavelength on an input finer of the WDM switch to a particular wavelength on an output fiber. In the other, a connection only needs to get to a particular output fiber, irrespective of what wavelength it will be on. We give novel constructions of strictly nonblocking and rearrangeably nonblocking WDM switches for both request models using limited range wavelength converters and arrayed waveguide grating routers. We fully analyze their blocking characteristics. Our designs are all relatively simple and easy to be laid out, and are useful for both optical circuit-switching and optical packet/burst switching. As far as we know, these are the first of such constructions.

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a minmin problem. We prove that this problem is NP-complete in either single link cost (e.g. dedicated backup bandwidth) or dual link cost (e.g. shared backup bandwidth) networks. In addition, it is NP-hard to obtain a k-approximation to the optimal solution for any k>1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the min-sum problem in an undirected network with ordered dual cost links (called MSOD problem). To solve the minmin problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the minmin problem called COLE, which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing ILP based approaches but also achieves a good balance among the AP length, bandwidth efficiency and recovery time.

This paper compares Reno, new-Reno and selective acknowledgements (SACK), the three most common TCP implementations today in (future) optical burst switched (OBS) networks. In general, SACK, which considers multiple triple duplicated ACKed (TD) losses in one round, is found to perform best in OBS networks, while new-Reno, which improves Reno in packet switched networks by fast retransmission in responding to partial ACKs, may however perform worse than Reno. All three TCP implementations react to a time out (TO) loss in the same way (i.e., using slow start). In OBS networks, where a burst may contain all packets from one round, and a burst loss occurs mainly due to contention instead of buffer overflow, such a TO event may no longer imply heavy congestion, or in other words, it may he a false TO or FTO. Such FTOs, which may he common in OBS networks especially for fast TCP flows, can significantly degrade the performance of all existing TCP implementations. Accordingly, we also propose a new TCP implementation called burst TCP (BTCP) which can detect FTOs and react properly, and as a result, improve over the existing TCP implementations significantly.

Current minimum energy routing schemes in wireless networks only consider energy consumption for transmitting data packets. However most wireless devices also transmit some control packets (such as RTS and CTS in 802.11) besides data packets. Without considering the energy consumption for control packets, the existing minimum energy routing schemes tend to use more intermediate nodes, which results in more energy consumption and less throughput. We first propose more comprehensive energy consumption models that consider the energy consumption for data packets as well as control packets. Based on these models, we propose our minimum energy routing scheme. The simulation results verify that our scheme performs better than the existing minimum energy routing schemes in terms of energy consumption as well as throughput.

We have introduced a novel concept called "managed mobility", and addressed the mobility of the relaying devices called mobile ad hoc relaying stations (MARSs) in the integrated cellular and ad hoc relaying (iCAR) system. We anticipate that the idea of managed mobility proposed in this paper for the iCAR system as well as the mobility management strategies may also be applied in other ad hoc networks, such as the self-reconfigurable sensor network, to reduce additional node deployment cost and increase fault tolerance.

In this paper we investigate the relative performance of two multipath routing schemes in relatively static and highly error-prone wireless networks (e-g., sensor networks), namely, selective preferential forwarding (SPF) (or primary/secondary routing) and recently proposed selective random forwarding (SRF), in terms of their packet throughput and traffic load distribution. For meshed multipath, aiming at achieving a good performance trade-off, we introduce a novel hybrid packet forwarding scheme that takes advantage of more uniform load distribution of SRF and a higher end-to-end throughput of SPF. Our approach is guided by analytic intuition and verified by simulations.

A major challenge faced in mobile ad hoc networks (MANET) is locating the devices for communication, especially with high node mobility and sparse node density. Present solutions provided by the ad hoc routing protocols range from flooding the entire network with route requests, to deploying a separate location management scheme to maintain a device location database. In this work, we propose a novel scheme called acquaintance based soft location management (ABSLM) in MANET. In ABSLM, nodes make use of the real life concept of making acquaintances and keeping in touch with them regarding each other's current locations. ABSLM has a two-fold aim: to avoid the overhead of flooding: and to use a 'soft' location management setup that does not require a strict location management strategies and is thus computationally less expensive than the standard 'hard' location management schemes. Simulation results show that the ABSLM not only outperforms the existing flooding schemes in terms of throughput, overhead and location discovery latency, but also achieves a performance comparable to 'hard' grid based location management schemes with a much lower control overhead.

Energy conservation is a primary concern in sensor networks. Several MAC protocols have been proposed to address this concern. However, the tradeoff between power consumption and latency has not been thoroughly studied. In this paper, we propose a sensor medium access control protocol with dynamic duty cycle, DSMAC, which achieves a good tradeoff between the two performance metrics without incurring much overhead. Moreover, DSMAC is able to adjust its duty cycle with varying traffic conditions without assuming any prior knowledge of application requirements. Both analytical and simulation results have been presented in this paper.

Geography based routing in mobile ad hoc networks is an application that uses the location information of nodes in a network to route data packets. Since the amount of network state information that each node needs to maintain in order to route packets is minimal, location based routing is considered scalable compared to existing routing protocols in ad hoc networks. However, geographic routing requires location management, where the locations of destination nodes needs to be found before the actual routing can begin. Many location management schemes have been proposed in the literature, but no prior work has quantitatively compared the scalability of these protocols with respect to the increase in the number of nodes in the network. In this work, we use a theoretical framework to show the asymptotic scalability of three location management protocols. We also carry out extensive simulations to study the performance of these protocols under practical considerations. Our results indicate that all protocols perform well, with a slight performance degradation with the increasing network size. In particular, the hierarchical grid location management protocol (HGRID) performs the best for all practical purposes, and is a candidate for location management in a wireless network architecture.

In this paper, we characterize analytically the multiaccess interference in wireless code-division multiple-access sensor networks with uniformly random distributed nodes and study the tradeoff between interference and connectivity. To provide a guideline for improving system behavior, three competitive deterministic topologies are evaluated along with the random topology in terms of link-level and network-level (routing) performance. The impact of signature code length and receiver design on the network performance for different topologies is also studied.

This paper explores the feasibility of deploying optical burst switching (OBS) in metropolitan area networks (MANs) as an alternative to synchronous optical network (SONET), over wavelength-division multiplexing. We present a comparison between two OBS architectures (with centralized and distributed scheduling schemes), SONET, and next-generation SONET (NG-SONET), respectively. We quantify some of the performance metrics such as end-to-end delay and loss rate when supporting Ethernet traffic in metro ring networks. Our simulation results show that OBS offers significant performance improvement over SONET and NG-SONET. In general, the OBS architecture with distributed scheduling has a superior delay performance, whereas the OBS architecture with centralized scheduling has a better loss metric.

Traffic grooming is an important task in interworking between the wavelength-division multiplexing (WDM) optical network that supplies "pipes" at the wavelength granularity, and the attached client networks that usually require connections of subwavelength granularity. The focus of this paper is to conduct performance analysis of grooming dynamic client traffic in WDM optical networks with a mesh topology. This paper first briefly introduces the traffic grooming problem in WDM optical networks and the issues related to performance analysis. It then develops two link blocking models, an exact model based on the stochastic knapsack problem and an approximation model based on an approximate continuous time Markov chain (CTMC). The end-to-end performance analysis is conducted using the reduced load approximation. The result obtained from analysis is shown to be accurate compared with the numerical result obtained from simulation.

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet. In OBS, a key problem is to schedule bursts on wavelength channels, whose bandwidth may become fragmented with the so-called void (or idle) intervals, using both fast and bandwidth efficient algorithms so as to reduce burst loss. To date, two well-known scheduling algorithms, called Horizon and LAUC-VF, have been proposed in the literature, which trade off bandwidth efficiency for fast running time and vice versa, respectively. In this paper, we propose a set of novel burst scheduling algorithms for OBS networks with and without fiber delay lines (FDLs) utilizing the techniques from computational geometry. In networks without FDLs, our proposed minimum-starting-void (Min-SV) algorithm can schedule a burst in O(logm) time, where m is the total number of void intervals, as long as there is a suitable void interval. Simulation results suggest that our algorithm achieves a loss rate which is at least as low as LAUC-VF, but can run much faster. In fact, its speed can be almost the same as Horizon (which has a much higher loss rate). In networks with FDLs, our proposed batching FDL algorithm considers a batch of FDLs to find a suitable FDL to delay a burst which would otherwise be discarded due to contention, instead of considering the FDLs one by one. The average running time of this algorithm is therefore significantly reduced from that of the existing burst scheduling algorithms. Our algorithms can also be used as algorithmic tools to speed up the scheduling time of many other void-filling scheduling algorithms.

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet infrastructure. In OBS, a key problem is to schedule bursts on wavelength channels with both fast and bandwidth efficient algorithms so as to reduce burst loss. To date, most scheduling algorithms avoid burst contention locally (or reactively). In this paper, we propose several novel algorithms for scheduling bursts in OBS networks with and without wavelength conversion capability. Our algorithms try to proactively avoid burst contention likely to occur at downstream nodes. The basic idea is to serialize the bursts on an outgoing link to reduce the number of bursts that may arrive at downstream nodes simultaneously (and thus reducing the burst contention and burst loss probability at downstream nodes). This can be accomplished by judiciously delaying locally assembled bursts beyond a pre-determined offset time at an ingress node using the electronic memory. Compared with the existing algorithms, our proposed algorithms can significantly reduce the loss rate while ensuring that maximum delay of a burst does not exceed its prescribed limit.

Recently, a new family of protocols has been introduced for large scale ad hoc networks that makes use of the approximate location of nodes in the network for geography-based routing. Location management plays an important role in such protocols, and previous work in this area has shown that the asymptotic overhead of location management is heavily dependant on the service primitives (location registration, maintenance and discovery) supported by a location management protocol. Currently, SLALoM (C.T. Cheng et al., 2002), which is a grid-based protocol optimized for large node movements, achieves the best known upper bound on the asymptotic worst case overhead of location management. However, the location registration cost in SLALoM dominates other costs for all practical purposes, and thus novel schemes need to be designed to limit this control traffic. In this work, we use the idea of location forwarding to devise a new scheme called ELF that limits the signalling traffic, and thus enhances the scalability of location management in large ad hoc networks. We find that, while the asymptotic overhead cost by such an improvisation matches that of SLALoM, ELF outperforms SLALoM in average case scenarios.

The paper develops a theoretical performance analysis model for the online single-hop traffic grooming algorithm in the mesh topology wavelength division multiplexing (WDM) optical network. This is done by developing a link blocking model for traffic grooming based on the continuous time Markov chain and queueing theory, and by extending the Erlang fixed-point approximation for traffic grooming analysis. The results obtained from the analytic model are shown to match well with the numerical results obtained from simulations.

Optical circuit switching (OCS) is a sophisticated technology widely deployed in current optical networks, and has many advantages in the transport of stable and long-duration traffic flows. However, it is not suitable for bursty data traffic. On the other hand, an alternative technology, optical burst switching (OBS), well addresses bursty IP traffic transport, but is not suitable for stable and large flows. To transport both types of traffic effectively, a hybrid optical switching approach is proposed which combines OCS and OBS to exploit the merits of both technologies. The performance has been evaluated in terms of throughput and blocking probability.

Shared risk link group (SRLG) has been widely recognized as an important concept in survivable optical networks. The issues of avoiding the so-called "traps" in the path determination phase and maximizing bandwidth sharing are more challenging in providing shared SRLG protection than in providing shared path protection without considering SRLG. In this paper, we extend a algorithm for the scheme of protection with multiple segments (PROMISE) to provide efficient SRLG protection. The proposed algorithm uses a novel dynamic programming technology and achieves a higher bandwidth efficiency and lower request blocking probability.

As the optical network evolves from static long haul connection provider to an adaptive and "smart" backbone solution, optical burst switching (OBS) becomes an attractive scheme for its flexibility and efficiency. However, how to reduce data loss is a crucial issue in such an asynchronous and one-way reservation system. In this paper, we study one contention resolution strategy in OBS networks: deflection routing. We extend an existing work to provide approximate and accurate models for the data loss analysis of single OBS node with and without wavelength conversion capability. The accuracy of our models is evaluated by simulation results.

For reliability of communication and simplicity, often times packet are replicated along predetermined routes to the destination. Alternatively, for traffic load balancing, data traffic is distributed along disjoint or meshed multiple routes to the destination - called selective forwarding. In this paper, we study and quantify the resource usage in these schemes, namely, packet replication and selective forwarding approaches. Our evaluation shows that for successfully routing a message using forward error correction coding technique, packet replication wastes much higher network resource, such as channel bandwidth and battery power.

The integrated cellular ad hoc relaying (iCAR) system is a representative heterogeneous wireless system, proposed to address the congestion problem in the wireless networks. In this paper, we present an analytic model based on Markov chains for the queuing delay performance of iCAR. Our results show that the new call requests in iCAR have a significantly lower queuing delay than that of the conventional cellular system. The analytic model developed in this paper may serve as the guideline for the delay performance evaluation of the next generation heterogeneous wireless systems.

In this paper, a simplified analysis technique for the integrated cellular and Ad hoc relay (iCAR) systems is presented. First, a simple two-cell system is analyzed using a multi-dimensional Markov-chain. The performance metric employed is the call blocking probability of each cell in the system. To this end, first a closed-form expression for the call blocking probability in the two-cell system is provided. Then, it is shown that these closed-form expressions could be used to analyze more practical systems. The accuracy of the developed simple analytical expressions is checked and verified by comparing the results predicted by these analytical expressions with simulation results. It is shown that there is an excellent match between analytical and simulation results.

With the "bandwidth-on-demand" as a promising service provisioning model for next-generation IP over WDM optical networks, online traffic grooming emerges as a fundamental issue. This paper studies the performance analysis of the multihop online traffic grooming algorithm in mesh WDM optical networks, and develops a theoretical performance analysis model.

Wavelength band switching (WBS) has only recently attracted attention from the optical networking industry for its practical importance in reducing the control complexity and cost of optical cross-connects (OXCs). However, WBS-related problems of theoretical interest have not been addressed thoroughly by the research community, and many issues are still wide open. In particular, WBS is different from wavelength routing, and thus techniques developed for wavelength-routed networks (including e.g., those for traffic grooming) cannot be directly applied to effectively address WBS-related problems. In this paper, we first propose a new multigranular OXC (MG-OXC) architecture for WBS, which is more flexible than any existing WBS node architectures. We also adopt the most powerful waveband assignment strategy, and develop an efficient heuristic algorithm called Balanced Path routing with Heavy-Traffic first (BPHT). To verify its near-optimality, we also develop an integer linear programming (ILP) model. Both the ILP and the BPHT algorithms can handle the case with multiple fibers per link and hence are more general than our previous single-fiber solutions X. Cao et al. (2002). We conduct a comprehensive evaluation of the benefits of WBS through detailed analysis and simulations. We show that the proposed heuristic BPHT can perform much better than a heuristic which applies the optimal routing and wavelength assignment (RWA) method. We also show that WBS using BPHT is even more beneficial in multifiber networks than in single-fiber networks in terms of reducing the port count. Our analytical and simulation results also provide valuable insights into the effect of wavelength band granularity, as well as the trade-offs between the wavelength-hop and the port count required in WBS networks.

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet. In OBS, a key problem is to schedule bursts on wavelength channels whose bandwidth may become fragmented with the so-called void (or idle) intervals with both fast and bandwidth efficient algorithms so as to reduce burst loss. To date, only two scheduling algorithms, called Horizon and LAUC-VF, have been proposed, which trade off bandwidth efficiency for fast running time and vice versa, respectively. In this paper, we propose several novel algorithms for scheduling bursts in OBS networks with and without fiber delay lines (FDLs). In networks without FDLs, our proposed Min-SV algorithm can schedule a burst successfully in O(logm) time, where m is the total number of void intervals, as long as there is a suitable void interval. Simulation results suggest that our algorithm achieves a loss rate which is at least as low as the best previously known algorithm LAUC-VF, but can run much faster. In fact, its speed can be almost the same as Horizon (which has a much higher loss rate). In networks with FDLs, our proposed batching FDL algorithm considers a batch of FDLs simultaneously to find a suitable FDL to delay a burst which would otherwise be discarded due to contention, instead of considering the FDLs one by one. The average search time of this algorithm is therefore significantly reduced from that of the existing sequential search algorithms.

Recently many active queue management (AQM) algorithms have been proposed to address performance degradations of end-to-end congestion control. However, these AQM algorithms show weaknesses to detect and control congestion under dynamically changing network situations. In this paper, we propose a predictive and robust AQM algorithm, called proportional-integral-derivative (PID)-controller, using PID feedback control the incipient as well as current congestion adaptively and proactively to dynamically changing network environments. A simulation study over a wide range of IP traffic conditions shows that PID-controller outperforms other AQM algorithms such as random early detection (RED) and proportional-integral (PI) controller in terms of the queue length dynamics, the packet loss rates, and the link utilization.

Due to limited functionalities and potentially large number of sensors, conventional routing strategies proposed for distributed control applications (such as mobile ad hoc networks) are not directly applicable in wireless sensor networks. In this paper, we propose a novel mesh multipath routing (M-MPR) with selective forwarding of packets. Our evaluation shows that M-MPR achieves much improved throughput performance over conventional disjoint multipath routing, with comparable power consumption and receiver complexity. We also show that for comparable throughput, M-MPR achieves better load distribution and requires lesser route maintenance overhead with respect to packet forwarding along a preferred route.

Waveband switching (WBS) has attracted attention from the optical networking industry for its practical importance in reducing port count, the associated control complexity, and cost of optical cross-connects (OXCs). However, WBS-related problems of theoretical interest have not been addressed thoroughly by the research community and many issues are still wide open. In particular, WBS is different from wavelength routing and, thus, techniques developed for wavelength-routed networks (including for example, those for traffic grooming) cannot be directly applied to effectively address WBS-related problems. In this paper, we first develop an integer linear programming (ILP) model, which for a given set of lightpath requests, determines the routes and assigns wavelengths to the lightpaths so as to minimize the number of ports needed. Since the optimal WBS problem of minimizing the port count in WBS networks contains an instance of routing and wavelength assignment (RWA), which is NP-complete, we adopt a powerful waveband assignment strategy and develop an efficient heuristic algorithm called balanced path routing with heavy-traffic first waveband assignment (BPHT). Both the ILP and the heuristic algorithm can handle the case with multiple fibers per link. We conduct a comprehensive evaluation of the benefits of WBS through detailed analysis and simulations. For small networks, our results indicate that the performance of the BPHT heuristic is close to that achievable by using the ILP model and, hence verifying its near-optimality. We show that for larger networks, BPHT can perform better than its variation called balanced traffic routing with maximum-hop first waveband assignment and much better than another heuristic based on optimal (but waveband oblivious) RWA that minimizes wavelength resources. We also show that WBS using BPHT is even more beneficial in multifiber networks than in single-fiber networks in terms of reducing the port count. Our analytical and simulation results provide valuable insights into the effect of wavelength band granularity, as well as the tradeoffs between the wavelength-hop and the port count required in WBS networks.

The major challenges in designing survivable schemes are how to allocate a minimal amount of spare resources (e.g., bandwidth) using fast (e.g., polynomial-time) algorithms, and, in case a failure occurs, to be able to recover quickly from it. All existing approaches invariably make tradeoffs. We propose novel shared segment protection algorithms which make little or no compromise . We develop an elegant integer linear programming (ILP) model to determine an optimal set of segments to protect a given active path. Although the ILP approach is useful for a medium-size network, it is too time consuming for large networks. Accordingly, we also design a fast heuristic algorithm based on dynamic programming to obtain a near-optimal set of segments. Although the heuristic algorithm has a polynomial time complexity, it can achieve a bandwidth efficiency as high as some best-performing shared path protection schemes and, at the same time, much faster recovery than these shared path protection schemes. The proposed scheme is also applicable to a wide range of networking technologies, including Internet Protocol and wavelength-division multiplexing networks under the generalized multiprotocol label switched framework.

Abstract The performance of existing QoS routing protocols is often constrained with high control traffic and database maintenance overhead. We observe that by proper coupling of nodal mobility and location information, better QoS support can be achieved with reduced control traffic and database requirements. In this paper, we investigate the performance of a location‐aware QoS routing protocol, calledtrigger‐based distributed routing(TDR), for mobile ad hoc networks. In this protocol, the nodal database size is reduced by maintaining only local neighborhood information, and route maintenance control overhead is kept low by maintaining only one route at a time for a session. Distributed rerouting control and directed alternate route discovery help reduce the rerouting control overhead and perform quicker route repair. Moreover, rerouting based on signal degradation history makes it possible to minimize the in‐session route failure. Our evaluation shows that the TDR protocol has significantly better QoS support and reduced overhead requirements compared to the existing QoS routing protocols in ad hoc networks. Copyright © 2003 John Wiley & Sons, Ltd.

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet infrastructure. We study the performance of TCP traffic in OBS networks and in particular, the effect of assembly algorithms on TCP traffic. We describe three assembly algorithms in this paper and compare them using the same TCP traffic input. The results show that the performance of the proposed adaptive-assembly-period (AAP) algorithm is better than that of the min-burstlength-max-assembly-period (MBMAP) algorithm and the fixed-assembly-period (FAP) algorithm in terms of goodput and data loss rate. The results also indicate that burst assembly mechanisms affect the behavior of TCP in that the assembled TCP traffic becomes smoother in the short term, and more suitable for transmission in optical networks.

This paper studies loss performance of optical burst switching (OBS) with assembled burst traffic input by exploring the characteristics of assembled burst traffic. We analyze the smoothing effect of assembly algorithms, which changes the statistical properties of packet flows, and and that assembly algorithms smooth the short range burstiness in packet traffic and thus enhance the loss performance in OBS. Based on the characteristics of such assembled burst traffic, an accurate loss model for OBS is provided, which works much better than traditional loss models in packet switching networks.

The proportional service model is receiving a lot of attention a an attractive model for providing differentiated services on the Internet. In particular, this model is controllable, able to provide the "tuning knobs" for network operators to quantitatively differentiate the quality-of-service (QoS) of different classes, and lends itself naturally to simple pricing schemes. We focus on the issue of how to practically implement such a QoS differentiation scheme at high-speed routers using efficient buffer management and packet scheduling mechanisms. We first propose a uniform scheduler. Unlike previously proposed schedulers which can be used only for a single QoS metric, our scheduler is suitable for various QoS metrics. We then introduce a new packet dropping mechanism with an active counter resetting scheme that compare favorably with previous schemes. Finally, we develop an original and simple approach for the integration of absolute QoS constraints with the proportional differentiation paradigm.

Tree-shared multicasting in OBS networks can achieve bandwidth savings, less processing load, and lower burst blocking (loss) probability. In this paper, we propose several distributed shared multicast tree construction protocols, namely greedy-prune, non-member-join, all-member-join, closest-member on-tree (CMOT), and closest-node on-tree (CNOT), for tree-shared multicasting in OBS networks. For performance comparison, we also consider an optimal shared tree which is modeled as Steiner minimal tree. We evaluate the proposed protocols using simulations in terms of cost of the shared tree to the optimal shared tree. Simulations show that the CNOT and CMOT protocols outperform the other three proposed protocols in terms of the cost of the shared tree, and perform close to cost of the optimal shared tree.

We propose an agent-based traffic grooming and management mechanism for IP over wavelength division multiplexing (WDM) optical networks. The agent-based mechanism effectively manages the traffic aggregation across the optical core between the IP client networks. It offers the benefit of efficient resource usage and reduced connectivity complexity for IP over WDM optical networks. We have studied this mechanism and evaluated its performance over various traffic patterns.

For pt.I see Chunming Qiao and Dahai Xu, INFOCOM'02, p.302-11, (2002). This paper describes a novel, ultra-fast heuristic algorithm to address an NP-hard optimization problem. One of its significances is that, for the first time, it is shown that a heuristic algorithm can also have better overall performance than its time-consuming, integer linear programming (ILP) based counterparts in the online case, which is non-intuitive. The proposed heuristic algorithm is useful for developing effective shared path (mesh) protection schemes that establish survivable connections in modern networks. The advantage of our heuristic algorithm over existing algorithms for finding a pair of link (or node) disjoint paths, active path (AP) and backup path (BP), comes from the following salient feature. It uses a so-called potential backup cost (PBC) function when selecting an AP in the first phase, in order to take into consideration the backup bandwidth needed by the corresponding BP yet to be chosen in the second phase. The PBC function is derived mathematically based on a rigorous statistical analysis of experimental data. While the use of PBC only requires partial aggregate information on existing connections and distributed control, it can also be applied even more effectively when complete information is available.

This paper describes a novel framework, called distributed partial information management (or DPIM). It addresses several major challenges in achieving efficient shared path protection under distributed control with only partial information, including (1) how much partial information about existing active and backup paths (or APs and BPs respectively) is maintained and exchanged; (2) how to obtain a good estimate of the bandwidth needed by a candidate BP, called BBW, and subsequently select a pair of AP and BP for a connection establishment request so as to minimize total bandwidth consumption and/or maximize revenues; (3) how to distributively allocate minimal BBW (and deallocate maximal BBW) via distributed signaling; and (4) how to update and subsequently exchange the partial information. A DPIM-based scheme using integer linear programming is described to illustrate our approach. In addition, an ultrafast and efficient heuristic scheme is described. With about the same amount of partial information, such a heuristic-based DPIM scheme can achieve almost as a good performance as the ILP-based DPIM scheme, and a much better performance than another ILP-based scheme described by Kodialam and Lakshman (see INFOCOM'00, p.902-911, 2000). The paper also presents an elegant method to support dynamic requests for protected, unprotected, and pre-emptable connections in the unified DPIM framework.

One of the common problems faced by the wireless service providers worldwide is coping with congestion or hot spots. To handle this hot spot problem, methods that combine the existing cellular networks with ad hoc networks have been proposed. Integrated Cellular and Ad Hoc Relay (iCAR) system employs ad hoc relay stations (ARSs) within the cellular network to balance traffic loads efficiently and to share channels between cells via primary and secondary relaying. These ARSs operate in the ISM band, and therefore, do not cause interference to the cellular band. When analyzing the performance of WAR systems, there are several factors that should be taken into account These factors include the coverage area of the ARSs, the number of ARS channels, the placement of ARSs, etc. In this paper, the impact of the number of ARS channels on the performance of WAR systems is studied. To this end, a multi-dimensional Markov-chain analysis is performed for a simplified two-cell system model. Results show that, with a proper amount of ARS coverage within each cell the call blocking probabilities can be decreased significantly with a small number of channels. Results also suggest that by increasing the number of ARS channels perfect load balancing can be achieved.

In survivable WDM optical networks, one of the critical issues is route computation. Although there is a possibility to optimize the route computation (together with the wavelength assignment) for static traffic pattern, it is impossible to perform such optimization for incremental and dynamic traffic. The conventional approach first computes the working path and then computes an edge-disjoint protection path using the shared risk link groups (SRLGs) information of the working path. We propose a joint working and protection path selection approach. Our approach tries to find multiple pairs of candidate working and protection paths. Then the pair with the minimum cost sum is selected. We have evaluated the performance benefit gained from the joint path selection approach with a single service class dynamic traffic supporting 1:1 protection scheme.

We analyze the arrival process of long range dependent (LRD) traffic and demonstrate that it is a Weibull bounded burstiness (WBB) process. By decomposing a generalized processor sharing (GPS) system into isolated queues and servers, we then obtain two upper bounds on the individual session queue length, which are useful for quality of service (QoS) control. We also demonstrate that some parameters in determining the upper bound on an individual session queue, such as the index, the asymptotic constant and the decay rate may be affected by other flows existing in the GPS system. However, under certain conditions, by carefully choosing the GPS weight parameters, an individual session with LRD traffic input can be well isolated from other flows.

We study three multicast schemes, namely separate multicasting (S-MCAST), multiple uni-casting (M-UCAST), and tree-share multicasting (TS-MCAST), in optical burst-switched WDM networks taking into consideration the overheads due to control packets and guard band (GBs) of bursts on separate channels (wavelengths). In TS-MCAST, we describe four tree sharing strategies based on equal coverage (EC), super coverage (SC), overlapping coverage (OC) and overlapping coverage by maximization (OC-MAX) for deciding which multicast sessions should mix their multicast traffic, and also consider an algorithm to construct shared trees (STs). Jeong, Xiong, Cankaya, Vandenhoute and Qiao (see Proc. of IEEE ICC 2000, p.1289-91, 2000) proposed the tree sharing strategies and reported the performance of three multicast schemes for static multicast sessions and membership. In this paper, we propose efficient heuristic algorithms for managing dynamic sessions and memberships under the TS-MCAST scheme, and evaluate the efficiency of the heuristic algorithms and compare the TS-MCAST scheme with the other two schemes in terms of the bandwidth consumed and processing load assuming an unlimited bandwidth.

iCAR is a new wireless architecture based on the integration of cellular and modern ad-hoc relaying technologies. We analyze its performance and compare it with conventional cellular system. In particular, we prove that due to the ability of ad-hoc relay stations (ARS) to relay traffic from one cell to another cell dynamically. iCAR has a lower system-wide call blocking probability than any corresponding cellular system without ARS, even if traffic can be evenly distributed among cells. We also study two typical scenarios and present some numeric results.

Integrated cellular and ad hoc relaying systems (iCAR) is a new wireless system architecture based on the integration of cellular and modern ad hoc relaying technologies. It addresses the congestion problem due to unbalanced traffic in a cellular system and provides interoperability for heterogeneous networks. The iCAR system can efficiently balance traffic loads between cells by using ad hoc relaying stations (ARS) to relay traffic from one cell to another dynamically. This not only increases the system's capacity cost effectively, but also reduces the transmission power for mobile hosts and extends system coverage. We compare the performance of the iCAR system with conventional cellular systems in terms of the call blocking/dropping probability, throughput, and signaling overhead via analysis and simulation. Our results show that with a limited number of ARSs and some increase in the signaling overhead (as well as hardware complexity), the call blocking/dropping probability in a congested cell and the overall system can be reduced.

In this paper, we study several multicast schemes in optical burst-switched WDM networks taking into consideration of the overheads due to control packets and guard bands (GBs) of bursts on separate channels (wavelengths). A straightforward scheme is called separate multicasting (S-MCAST) where each source node constructs separate bursts for its multicast (per each multicast session) and unicast traffic. To reduce the overhead due to GBs (and control packets), one may piggyback the multicast traffic in bursts containing unicast traffic using a scheme called multiple unicasting (M-UCAST). The third scheme is called tree-shared multicasting (TS-MCAST) whereby multicast traffic belonging to multiple multicast sessions can be mixed together in a burst, which is delivered via a shared multicast tree. The multicast schemes (M-UCAST and TS-MCAST) are compared with S-MCAST in terms of bandwidth consumed and processing load.

We address the issue of how to provide quality of service (QoS) with limited fiber delay lines (FDLs) at the WDM layer. We propose an offset-time-based scheme, which is less complex and more scalable than existing buffer-based schemes. The proposed scheme does not mandate any buffer at the intermediate nodes, but can take advantage of FDL-based buffers, and thus is suitable for optical networks. We discuss a couple of structures of the FDL "buffers" (which differ from the conventional queues), and evaluate their effectiveness. Specifically, the offset time required for class isolation when reserving resources such as wavelengths and FDLs is quantified. The effect of having limited FDLs on the offset time-based scheme is measured in terms of the burst loss probability and queuing delay as a function of the offset time, the maximum delay time of FDLs, the number of FDLs, and the number of wavelengths.

In wavelength division multiplexed networks (WDM) with 1:1 path protection, a link-disjoint protection (backup) path is also set up at the time of setting up a working (primary) path. Hence, the failure of a single fiber-link does not cause huge data losses. This paper considers on-line routing and wavelength assignment (RWA) of protection paths in such networks. In particular, we study two strategies based on the 1:1 path protection scheme. The static strategy establishes protection paths such that once a route and wavelength have been chosen, they are not allowed to change. On the other hand, the dynamic strategy allows for re-arrangement of protection paths, that is, both the route and wavelength chosen for a protection path can change so as to accommodate a new request. With either strategy, we assume that the working paths cannot be re-arranged. This is to prevent the disruption of on-going traffic. The two strategies are compared on the basis of the number of connection requests that can be satisfied for a given number of wavelengths, assuming that the requests come one at a time, and wavelengths are assigned according to the first-fit policy. One of the results of our study is that, contrary to intuition, the static strategy performs better than the dynamic strategy.

Ever increasing data traffic and limited capacity are major causes for congestion in current cellular systems. This paper presents a new architecture for the next generation wireless systems based on the integration of the cellular infrastructure and modern ad-hoc relaying technologies. The new architecture can efficiently balance traffic loads between cells by using ad-hoc relay stations (ARS) to relay traffic from one cell to another cell dynamically. This can not only increase a system's capacity cost-effectively, but also reduce transmission power for mobile hosts, and provide services for shadow areas. In this paper, we present the architectural concept including its basic operations and principal benefits. We also propose a seed-growing approach for ARS placement, and discuss the upper bound on the number of seed ARSs needed in the system. We evaluate the performance improvement of the new architecture through analysis and simulations.

With ever increasing demands on bandwidth from emerging bandwidth-intensive applications, such as web browsing, video conferencing, E-commerce, video-on-demand services, there has been an acute need for very high bandwidth transport network facilities. Optical networks are a promising candidate for this type of applications. At the same time, many bandwidth-intensive applications require multicast services for efficiency purposes. Multicast has been extensively studied in the parallel processing and electronic networking community, and has started to receive attention in the optical network community recently. In particular, as WDM (wavelength division muitiplexing) networks emerge, supporting WDM multicast becomes increasingly attractive. In this paper, we consider efficient designs of multicast-capable WDM switching networks, which are significantly different, and hence require non-trivial extensions from their electronic counterparts. We first discuss various multicast models in WDM networks, and analyze the nonblocking multicast capacity and network cost under these models. We then propose two methods to construct nonblocking multistage WDM networks to reduce the network cost.

As WDM technology matures and multicast applications become increasingly popular, supporting multicast at the WDM layer becomes an important and yet challenging topic. In this paper, we study constrained multicast routing in WDM networks with sparse light splitting, i.e., where some switches are incapable of splitting light (or copying data in the optical domain). Specifically, we propose four WDM multicast routing algorithms, namely, Re-route-to Source, Re-route-to-Any, Member-First, and Member-Only. Given the network topology, multicast membership information, and light splitting capability of the switches, these algorithms construct a source-based multicast light-forest (consisting one or more multicast trees) for each multicast session. The performance of these algorithms are compared in terms of the average number of wavelengths used per forest (or multicast session), average number of branches involved (bandwidth) per forest as well as average number of hops encountered (delay) from a multicast source to a multicast member.

A fundamental problem in current cellular systems is limited capacity. Adding to this problem is unbalanced traffic among the cells. Given the explosion of the wireless traffic, especially wireless data traffic for Internet/Web access, and limited spectrum available for licensing, congestion will occur in some cells, resulting in blocked new calls and dropped handoffs due to the lack of available data channels (or DCHs). Since the locations of the congested cells vary from time to time (e.g. downtown on Monday morning, or amusement parks on Sunday afternoon), it's difficult to guarantee a sufficient amount of resources in each cell in a cost-effective way. In this paper, we propose to integrate the cellular infrastructure with modern wireless/mobile relaying technologies to achieve dynamic load balancing among different cells. Our basic idea is to place a number of mobile relay stations (or MRSs) within each cell to divert traffic in one (possibly congested) cell to another (non-congested) cell.

We address the issue of how to provide basic quality of service (QoS) in optical burst-switched WDM networks with limited fiber delay lines (FDLs). Unlike existing buffer-based QoS schemes, the novel offset-time-based QoS scheme we study in this paper does not mandate any buffer for traffic isolation, but nevertheless can take advantage of FDLs to improve the QoS. This makes the proposed QoS scheme suitable for the next generation optical Internet. The offset times required for class isolation when making wavelength and FDL reservations are quantified, and the upper and lower bounds on the burst loss probability are analyzed. Simulations are also conducted to evaluate the QoS performance in terms of burst loss probability and queuing delay. We show that with limited FDLs, the offset-time-based QoS scheme can be very efficient in supporting basic QoS.

In high-speed SONET rings with point-to-point WDM links, the cost of SONET add-drop multiplexers (S-ADMs) can be dominantly high. However, by grooming traffic (i.e., multiplexing lower-rate streams) appropriately and using wavelength ADMs (WADMs), the number of S-ADMs can be dramatically reduced. In this paper, we propose optimal or near-optimal algorithms for traffic grooming and wavelength assignment to reduce both the number of wavelengths and the number of S-ADMs. The algorithms proposed are generic in that they can be applied to both unidirectional and bidirectional rings having an arbitrary number of nodes under both uniform and nonuniform (i.e., arbitrary) traffic with an arbitrary grooming factor. Some lower bounds on the number of wavelengths and S-ADMs required for a given traffic pattern are derived, and used to determine the optimality of the proposed algorithms. Our study shows that using the proposed algorithms, these lower bounds can he closely approached in most cases or even achieved in some cases. In addition, even when using a minimum number of wavelengths, the savings in S-ADMs due to traffic grooming (and the use of WADMs) are significant, especially for large networks.

With ever increasing demands on bandwidth from emerging bandwidth-intensive applications, such as video conferencing, E-commerce, and video-on-demand services, there has been an acute need for very high bandwidth transport network facilities. Optical networks are a promising candidate for this type of applications. At the same time, many bandwidth-intensive applications require multicast services for efficiency purposes. Multicast has been extensively studied in the parallel processing and electronic networking community and has started to receive attention in the optical network community recently. In particular, as WDM (wavelength division multiplexing) networks emerge, supporting WDM multicast becomes increasingly attractive. In this paper, we consider efficient designs of multicast-capable WDM switching networks, which are significantly different and, hence, require nontrivial extensions from their electronic counterparts. We first discuss various multicast models in WDM networks and analyze the nonblocking multicast capacity and network cost under these models. We then propose two methods to construct nonblocking multistage WDM networks to reduce the network cost.

As WDM technology matures, IP over WDM multicast will become a challenging new topic. Supporting multicast at the WDM layer provides additional advantages, but also raises many new issues that do not exist in IP multicast. For example, the limitation on the light splitting capability of switches is one major difficulty in WDM multicast, and in addition, the limitations on both the wavelength conversion capability and optical buffer space may affect multicast routing as well. In this paper, we focus on the IP over WDM multicast routing problem, i.e. how to construct multicast trees at the WDM layer based on IP multicast routing protocols. More specifically, we study how label switched paths for optical label switching can be set up for multicast traffic. We propose two approaches, one without modification of existing IP multicast routing protocols, and the other with modification of existing IP multicast routing protocols.

Supporting WDM multicasting in an IP over WDM network poses interesting problems because some WDM switches may be incapable of switching an incoming signal to more than one output interface. An approach to WDM multicasting based on wavelength-routing, which constructs a multicast forest for each multicast session so that multicast-incapable WDM switches do not need to multicast, was proposed and evaluated previously. Such an approach requires global knowledge of the WDM layer. In this paper, we study WDM multicasting in an IP over WDM network under the framework of multiprotocol label switching (MPLS) using optical burst/label switching (OBS/OLS). We propose a protocol which modifies a multicast tree constructed by distance vector multicast routing protocol (DVMRP) into a multicast forest based on the local information only.

We study the problem of scheduling switching element (SE)-disjoint connections in banyans and dilated banyans under stage control and show how it applies to photonic cross-connect (or switch) technology. For a given set of connections (or packets), it is desirable to establish them in as few rounds as possible where the number of rounds (i.e., schedule length) corresponds to the degree at which a cross-connect may be multiplexed in time or wavelength. For a stage-controlled banyan, three scheduling algorithms are described. The first two algorithms perform well when the number of connections to be scheduled is small and large, respectively, but perform poorly otherwise. The third algorithm is optimal in that it can generate a schedule of minimum length with a polynomial time complexity. We determine the average schedule length in a banyan using these three algorithms through both analysis and simulation and extend our analysis to dilated banyans.

There are two basic approaches for establishing a connection in a reconfigurable switched optical network, whose links are multipiexed with virtual channels (e.g., wavelengths or time slots). One is called path multiplexing (PM), in which the same virtual channel has to be used on each link along a path, and the other is link multiplexing (LM), in which different virtual channels may be used. We focus on the problem of off-line permutation embedding and scheduling as a part of the comparative study of the multiplexing approaches. Specifically, we determine the minimum number of virtual channels per link needed for a given network to be rearrangeably nonblocking in PM and LM, respectively. We also examine the schedule length of a permutation in PM and LM when the network is blocking as a result of having an insufficient number of virtual channels per link. We found that PM and LM are equally effective in linear arrays, and LM is slightly more effective than PM in rings, meshes (grids), tori, and hypercubes.

We consider the problem of scheduling all-to-all personalized connections (AAPC) in WDM rings. Scheduling one connection for every source-destination pair in a network of limited connectivity provides a way to reduce routing control and guarantee throughput. For a given number of wavelengths K and a given number of transceivers per node T, we first determine the lower bound (LB) on the schedule length, which depends on both K and T. To achieve the LB, either the network bandwidth, the I/O capacity, or both should be fully utilized. This approach first constructs and then schedules circles, each of which is formed by up to four non-overlapping connections and can fully utilize the bandwidth of one wavelength. The proposed circle construction and scheduling algorithms can achieve the LB if K/spl les/T

We propose an on-line wavelength assignment algorithm for multi-fiber WDM networks, in which lightpaths are established and released dynamically. For a given number of fibers per link and number of wavelengths per fiber, the algorithm aims to minimize the blocking probability. It may also be used to reduce the number of wavelengths required for a given tolerable blocking probability. Simulation results show that our wavelength assignment algorithm performs better than other previously proposed algorithms (in the cases we studied). As the number of fibers per link increases, the benefit of having wavelength converters decreases dramatically, and the performance improvement of our algorithm over others increases. Our results also show that in case a preferred path is not available, rerouting along a node-disjoint backup path can significantly reduce the blocking probability.

One of the important considerations in designing waveguide-based photonic switching networks is to avoid crosstalk. Two approaches have been proposed which dilate a network in the space and time domains, respectively, to establish crosstalk-free connections. The space-domain dilation uses more hardware, representing cost in space, while the time-domain dilation uses more rounds (or time slots), representing cost in time. In order to evaluate the space-time tradeoffs involved in these two approaches, an analytical model is developed. We describe a recursive procedure which calculates the probability that a new connection can be established without crosstalk in a Banyan (or dilated Banyan) network by taking into consideration the dependency between traffic distributions at different stages. A Markov process based on such probabilities is then used to determine the average number of rounds needed for a set of one-to-one random connections. The model is applicable to both Banyan and dilated Banyan networks, with either stage or individual control. Simulation results are also obtained and compared to the analytic results. We show that the time-domain approach can achieve better space-time tradeoffs than the space-domain approach. One of the practical implications of this result is that a multiplane Banyan network may be more cost-effective than a dilated Banyan in avoiding crosstalk.

Path multiplexing (PM) and link multiplexing (LM) are two approaches for establishing connections (or lightpaths) in optical networks. This paper describes distributed control protocols for establishing lightpaths in WDM networks using LM and PM. We propose and evaluate the performance of two classes of protocols, namely source initiated reservation (SIR) and destination initiated reservation (DIR). It is found that DIR protocols generally perform better than SIR protocols. However, the impacts of DIR protocols on the performance of a network using LM and PM are different.

Two properties of optical transmissions, namely, unidirectional propagation and predictable propagation delay, make it possible to pipeline packet transmissions in all-optical networks. In this paper, we study the problem of scheduling all-to-all personalized communication (AAPC) in unidirectional TDM/WDM rings with pipelined transmissions, which can achieve a much higher bandwidth utilization than non-pipelined transmissions. For a given number of wavelengths, K, and number of transmitter-receiver pairs per node, T, the theoretical lower bound (TLB) on the schedule lengths is derived and scheduling methods which can achieve near optimal results are proposed for three different cases, namely, T=K, 2/spl les/T

Reducing communication latency, which is a performance bottleneck in optically interconnected multiprocessor systems, is of prominent importance. A conventional approach for establishing connections in multiplexed networks uses a set of independent time slots (or virtual channels) along a path for each connection. This approach requires the use of switching devices capable of interchanging time slots, and thus introduces latency in addition to hardware and control complexity. We propose an approach to all-optical time division multiplexed (TDM) communications in multiprocessor systems. The idea is to establish a connection along a path using a set of time slots (or virtual channels) that are dependent on each other, so that no time slot interchanging is required. We compare the proposed approach with the conventional one in terms of the overall communication latency. We found that, despite the possibility that establishing a connection may take a longer time, the proposed approach will result in lower overall communication latency as it eliminates the delays introduced by the time slot interchanging switching devices.

There are two approaches for establishing a connection in a network whose links are multiplexed with virtual channels. One is called Path Multiplexing (PM), in which the same channel has to be used on each link along a path, and the other is Link Multiplexing (LM), in which different channels may be used. We study the problem of embedding permutations in PM and LM, and in particular, determine the threshold (minimal) multiplexing degree needed for a network to be rearrangeably nonblocking. We found that PM and LM are equally effective in linear arrays, and LM is slightly more effective than PM in rings, meshes, tori and hypercubes. Our results suggest that PM may be more cost-effective in implementing networks with multiplexed optical interconnects.

A photonic switching network may be dilated in either space or time to establish crosstalk-free connections. Space-time tradeoffs are evaluated using an analytical model based on Markov process. The probability that a new connection can be established without crosstalk is calculated by taking into consideration the traffic correlations between stages. The model is applicable to both Banyan and dilated Banyan networks under either switch or stage control. Our results imply that space-time tradeoffs are improved by using Banyans instead of dilated Banyans. If hardware cost is not a concern, a multi-plane Banyan network, which is more effective than a dilated Banyan, may be used.

A procedure for diagnosing crosstalk and crosstalk-faulty switches in photonic dilated Benes networks (DBNs) is presented. It obtains the crosstalk ratios of each and every switch in an N/spl times/N DBN in 4N tests, along with O(N/spl middot/log/sup 2/N) calculations. One of its applications is to identify single or multiple switches in the DBN which are generating excessive crosstalk, or crosstalk-faulty. A recursive algorithm is used to configure the DBN for each test such that the necessary power measurements of the signals can be taken accurately. An important feature of the proposed diagnostic procedure is its suitability for automated test generation.

A physical link can be time-multiplexed to create several time slots, each of which corresponding to a virtual link. A conventional approach establishes a connection along a path using a set of independent time slots (or virtual links) and thus requires the use of switching devices capable of interchanging time slots. This paper proposes a different approach to all-optical Time Division Multiplexed (TDM) communications in multiprocessor systems. The idea is to establish a connection along a path using a set of time slots (or virtual links) that are dependent on each other, so that no time-slot interchanging is required. It is found that, despite of the possibility that establishing a connection may take a longer time, the proposed approach will result in lower overall communication latency as it eliminates the delays introduced by the time-slot interchanging switching devices.>

Time division multiplexed multistage interconnection networks (TDM-MIN's) are proposed for multiprocessor communications. Connections required by an application are partitioned into a number of subsets, called mappings, such that connections in each mapping can be established in an MIN without conflict. Switch settings for establishing connections in each mapping are determined and stored in shift registers. By repeatedly changing switch settings, connections in each mapping are established for a time slot in a round-robin fashion. Thus, all connections required by an application may be established in an MIN in a time division multiplexed way. TDM-MIN's can emulate a completely connected network using N time slots. It can also emulate regular networks such as rings, meshes, cube-connected-cycles (CCC), binary trees, and n-dimensional hypercubes using 2, 4, 3, 4, and n time slots, respectively. The problem of partitioning an arbitrary set of requests into a minimal number of mappings is NP-hard. Simple heuristic algorithms are presented and their performances are shown to be close to optimal. The flexibility of TDM-MIN's allows for the support of run-time requests through dynamic reconfigurations. The techniques are especially suitable for hybrid electro-optical systems with optical interconnects.>

An optical communication structure is proposed for multiprocessor arrays which exploits the high communication bandwidth of optical waveguides. The structure takes advantage of two properties of optical signal transmissions on waveguides, namely, unidirectional propagation and predictable propagation delays per unit length. Because of these two properties, time-division multiplexing (TDM) of messages has the same effect as message pipelining on optical waveguides. Two TDM approaches are proposed, and the combination of the two is used in the design of the optical communication structure. Analysis and simulation results are given to demonstrate the communication effectiveness of the system. A clock distribution method is proposed to address potential synchronization problems. Feasibility issues with current and future technologies are discussed.>

An optical communication structure for multipro­ ceSsor arrays that exploits the high communication bahdwidth of optical waveguides is proposed. The struc­ turle takes advantage of two properties of optical signal trqnsmissions on waveguides. Namely. unidirectional pfppagation and predictable propagation delays per unit length. Two novel time-division mUltiplexing approaches are proposed for non SIM D environments to obtain a communication bandwidth comparable to that of mes­ sage pipe lining in SIMD environments. Analysis and simulation results are given to evaluate the communica­ tion effectiveness of the system. A clock distribution method is also proposed to address potential synchroni­ zation problems. Finally. feasibility issues with current andfuture technologies are discussed.