Sensor fusion plays an increasingly important role in real-time traffic perception using roadside sensing devices because the use of single type of sensors often fail to deliver satisfactory performance in certain harsh environment. This paper investigates asynchronous data fusion for lane-level vehicle tracking with randomly delayed measurements and inaccurate detections from millimeter wave (MMW) radars and magnetic sensors in tunnels, where vehicle tracking with single type of sensors can not meet the requirements of reliable and accurate lane-level tracking due to inaccurate radar detections at far distances, noisy radar detections in tunnel environment, and missed or false vehicle detections by magnetic sensors. A multisensor data association algorithm is first designed to assign the measurements of MMW radar and magnetic sensors to a particular vehicle. A multi-lane estimation model is then developed, which employs Bayesian weight mixture filtering to fuse MMW radar and magnetic sensor measurements and to estimate the lane in which a vehicle is located. Finally, the proposed algorithm is implemented in a real environment - the Xianfengding Tunnel located in Jiangxi Province, China. Experiments are conducted to validate the accuracy of the proposed method using real data. The proposed method and the collected data are further integrated to establish a real-time digital twin system aimed at supporting advanced traffic management. The fusion results and the real radar measurement dataset of the tunnel are made available athttps://github.com/futianxuan/data.

Presents corrections to the paper, “Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering,” (Xu, D., et al)IEEE/ACM Trans. Netw., vol. 19, no. 6, pp. 1717–1730, Dec. 2011).

Current intra-domain routing protocols like OSPF and IS-IS use link-state routing algorithms with hop-by-hop forwarding that sacrifice traffic engineering performance for ease of implementation and management. Though optimal traffic engineering algorithms exist, they tend to be either not link-state algorithms or to require source routing - characteristics that make them difficult to implement. As the focus of this paper, we introduce HALO, the first optimal link-state routing algorithm with hop-by-hop forwarding, where link weights can be calculated locally. Furthermore, our solution can adapt to changing traffic patterns automatically. The optimality of the algorithm is proved theoretically and also verified numerically.

The rapid advancement of smartphones has instigated tremendous data applications for cell phones. Supporting simultaneous voice and data services in a cellular network is not only desirable but also becoming indispensable. However, if the voice and data are serviced through the same antenna (like the 3G UMTS network), a voice call with data sessions requires better radio connection than a voice-only call. In this paper, we systematically study the coordination between the voice and data transmissions in UMTS networks. From analyzing a large carrier's UMTS network recording data, we first identify the most relevant network measurements/features indicating a potential call drop, then propose a drop-call predictor based on AdaBoost. Moreover, we develop an intelligent call management strategy to voluntarily block data sessions when the voice is predicted to be dropped. Our analysis utilizing real service provider's data sets shows that our proposed scheme can not only predict drop calls with a very high accuracy but also achieve the highest user satisfaction compared to the other existing call management strategies.

Today's networks typically handle traffic engineering (e.g., tuning the routing-protocol parameters to optimize the flow of traffic) and failure recovery (e.g., pre-installed backup paths) independently. In this paper, we propose a unified way to balance load efficiently under a wide range of failure scenarios. Our architecture supports flexible splitting of traffic over multiple precomputed paths, with efficient path-level failure detection and automatic load balancing over the remaining paths. We propose two candidate solutions that differ in how the routers rebalance the load after a failure, leading to a trade-off between router complexity and load-balancing performance. We present and solve the optimization problems that compute the configuration state for each router. Our experiments with traffic measurements and topology data (including shared risks in the underlying transport network) from a large ISP identify a "sweet spot" that achieves near-optimal load balancing under a variety of failure scenarios, with a relatively small amount of state in the routers. We believe that our solution for joint traffic engineering and failure recovery will appeal to Internet Service Providers as well as the operators of data-center networks.

This paper settles an open question with a positive answer: Optimal traffic engineering (or optimal multicommodity flow) can be realized using just link-state routing protocols with hop-by-hop forwarding. Today's typical versions of these protocols, Open Shortest Path First (OSPF) and Intermediate System-Intermediate System (IS-IS), split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF/IS-IS to the offered traffic is a well-known NP-hard problem, and even the best setting of the weights can deviate significantly from an optimal distribution of the traffic. In this paper, we propose a new link-state routing protocol, PEFT, that splits traffic over multiple paths with an exponential penalty on longer paths. Unlike its predecessor, DEFT, our new protocol provably achieves optimal traffic engineering while retaining the simplicity of hop-by-hop forwarding. The new protocol also leads to a significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a conceptual framework, called Network Entropy Maximization, that is used to identify the traffic distributions that are not only optimal, but also realizable by link-state routing.

With the explosive deployment of "triple play" (voice, video and data services) over the same access network, guaranteeing a certain-level of survivability for the access network is becoming critical for service providers. The problem of economically provisioning survivable access networks has given rise to a new class of network design problems, including the so-called survivable multi-level fat tree problem (SMFT). We show that two special cases of SMFT are polynomial- time solvable, and present two approximation algorithms for the general case. The first is a combinatorial algorithm with approximation ratio min{[~L/2] + 1, 2log2n} where L is the longest Steiner path length between two terminals, and n is the number of nodes. The second is a primal-dual (2Deltas+ 2)- approximation algorithm where Deltasis the maximum Sterner degree of terminals in the access network. We then show that approximating SMFT to within a certain constant c > 1 is NP- hard, even when all edge-weights of G are 1, L les 10, and Deltasles 3. Finally, we experimentally show that the approximation algorithms perform extremely well on random instances of the problem.

With economic constraints and limited routing capability, the structure of an access network is typically a "fat tree", where the terminal has to relay the traffic from another terminal of the same or higher level. New graph theory problems naturally arise from such features of access network models, different from those targeted towards survivable backbone (mesh) networks. We model the important problem of provisioning survivability to an existing single-level fat tree through two graph theory problem formulations: the Terminal Backup problem and the simplex cover problem, which we show to be equivalent. We then develop two polynomial-time approaches, indirect and direct, for the simplex cover problem. The indirect approach of solving the matching version of simplex cover is convenient in proving polynomial-time solvability though it is prohibitively slow in practice. In contrast, leveraging the special properties of simplex cover itself, we demonstrate that the direct approach can solve the simplex cover problem very efficiently even for large networks. Extensive numerical results of applying our algorithms are also reported for designing survivable access networks over different types of topologies.

Link-state routing with hop-by-hop forwarding is widely used in the Internet today. The current versions of these protocols, like OSPF, split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF to the offered traffic is an NP-hard problem, and even the best setting of the weights can deviate significantly from an optimal distribution of the traffic. In this paper, we propose a new link-state routing protocol, PEFT, that splits traffic over multiple paths with an exponential penalty on longer paths. Unlike its predecessor, DEFT, our new protocol provably achieves optimal traffic engineering while retaining the simplicity of hop-by-hop forwarding. A gain of 15 % in capacity utilization over OSPF is demonstrated using the Abilene topology and traffic traces. The new protocol also leads to significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a new conceptual framework, called network entropy maximization, which is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.

Service availability is one of the most closely scrutinized metrics in offering network services. It is important to cost- effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In particular, demands for availability may be elastic and such elasticity can be leveraged to improve cost-effectiveness. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting Quality of Protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. This investigation quantifies several engineering implications. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

In lightweight mobile ad hoc networks, both probabilistic and deterministic key management schemes are fragile to node fabrication attacks. Our simulation results show that the Successful Attack Probability (SAP) can be as high as 42.6% with the fabrication of only 6 copies from captured nodes comprising only 3% of all nodes. In this paper, we propose two low-cost secure-architecture-based techniques to improve the security against such node fabrication attacks. Our new architectures, specifically targeted at the sensor-node platform, protect long-term keys using a root of trust embedded in the hardware System-on-a-Chip (SoC). This prevents an adversary from extracting these protected long-term keys from a captured node to fabricate new nodes. The extensive simulation results show that the proposed architecture can significantly decrease the SAP and increase the security level of key management for mobile ad hoc networks.

This is an overview of the ongoing FAST Copper project, which is aimed at substantial improvements in rate, reach, reliability, and quality in copper-last-mile broadband access through fiber/DSL deployment, engineering innovations, and fundamental research. The project is funded by NSF, and is currently pursued jointly by Princeton University, Stanford University, and Fraser Research Lab. In this article, we outline the motivations, challenges, and research issues associated with the project, and report some of the recent results by the Princeton team in each of the four dimensions: frequency, amplitude, space, and time.

Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and ISIS use to compute shortest paths. The resulting optimization problem -to find the best link weights for a given topology and traffic matrix -is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, we propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a two-stage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.

Service availability is one of the most closely scrutinized metrics in offering network services. The network vendor can earn more revenue from the customers by guaranteeing higher service availability at the cost of higher operational expense. It is important to cost-effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting quality of protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. Several quantitative observations are made from this investigation. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

It is widely believed that although being more complex, a probabilistic key predistribution scheme is much more resilient against node capture than a deterministic one in lightweight wireless ad hoc networks. Backed up by the surprisingly large successful attack probabilities computed in this paper, we show that the probabilistic approaches have only limited performance advantages over deterministic approaches. We first consider a static network scenario as originally considered in the seminal paper by Eschenauer and Gligor [1], where any node capture happens after the establishment of all pairwise links, and show that the deterministic approach can achieve a performance as good as the probabilistic one. Furthermore in a mobile network, the probabilistic key management as described in [1] can lead to a successful attack probability of one order of magnitude larger than the one in a static network.

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.

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%

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.

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.

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.

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.