9795964
On finding disjoint paths in single and dual link cost networks
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.
15302993
DEFT: Distributed Exponentially-Weighted Flow Splitting
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.
8591259
On the complexity of and algorithms for finding the shortest path with a disjoint counterpart
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 Min-Min 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 the MSOD problem). To solve the Min-Min 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 Min-Min problem called COnflicting Link Exclusion (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 integer linear programming (ILP)-based approaches but also achieves a good balance among the active path length, bandwidth efficiency, and recovery time.
196020410
Distributed Partial Information Management (DPIM) schemes for survivable networks - Part I
15521655
An ultra-fast shared path protection scheme - distributed partial information management, part II
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.
16311820
Optimal Provisioning of Elastic Service Availability
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.
9746543
Design an Interoperable Mobile Agent System Based on Predicate Transition Net Models
Mobile agents provide an effective and flexible style to develop advanced distributed systems. In order to promote interoperability and ensure the quality of mobile agent systems, it is necessary to formalize software architecture of mobile agent systems. In this paper, we not only define the software architecture of interoperable mobile agent systems using predicate transition nets, but also analyze the interoperability between agents. In addition, a formal model-driven design method to develop mobile agent systems is described with examples. Our method naturally integrates formal methods and practical approaches in the agent system design phase. The method can be used to develop other complex software systems as well.
18364869
Threat-driven modeling and verification of secure software using aspect-oriented Petri nets
Design-level vulnerabilities are a major source of security risks in software. To improve trustworthiness of software design, this paper presents a formal threat-driven approach, which explores explicit behaviors of security threats as the mediator between security goals and applications of security features. Security threats are potential attacks, i.e., misuses and anomalies that violate the security goals of systems' intended functions. Security threats suggest what, where, and how security features for threat mitigation should be applied. To specify the intended functions, security threats, and threat mitigations of a security design as a whole, we exploit aspect-oriented Petri nets as a unified formalism. Intended functions and security threats are modeled by Petri nets, whereas threat mitigations are modeled by Petri net-based aspects due to the incremental and crosscutting nature of security features. The unified formalism facilitates verifying correctness of security threats against intended functions and verifying absence of security threats from integrated functions and threat mitigations. As a result, our approach can make software design provably secured from anticipated security threats and, thus, reduce significant design-level vulnerabilities. We demonstrate our approach through a systematic case study on the threat-driven modeling and verification of a real-world shopping cart application.
5883342
Collapsar: A VM-Based Architecture for Network Attack Detention Center
The honeypot has emerged as an effective tool to provide insights into new attacks and current exploitation trends. Though effective, a single honeypot or multiple independently operated honeypots only provide a limited local view of network attacks. Deploying and managing a large number of coordinating honeypots in different network domains will not only provide a broader and more diverse view, but also create potentials in global network status inference, early network anomaly detection, and attack correlation in large scale. However, coordinated honeypot deployment and operation require close and consistent collaboration across participating network domains, in order to mitigate potential security risks associated with each honeypot and the non-uniform level of security expertise in different network domains. It is challenging, yet desirable, to provide the two conflicting features of decentralized presence and uniform management in honeypot deployment and operation. 
 
To address these challenges, this paper presents Collapsar, a virtual-machine-based architecture for network attack detention. A Collapsar center hosts and manages a large number of high-interaction virtual honeypots in a local dedicated network. These honeypots appear, to potential intruders, as typical systems in their respective production networks. Decentralized logical presence of honeypots provides a wide diverse view of network attacks, while the centralized operation enables dedicated administration and convenient event correlation, eliminating the need for honeypot experts in each production network domain. We present the design, implementation, and evaluation of a Collapsar testbed. Our experiments with several real-world attack incidences demonstrate the effectiveness and practicality of Collapsar.
14971297
Non-uniform Differential Mesh Deformation
In this paper, we propose a novel mesh deformation approach via manipulating differential properties non-uniformly. Guided by user-specified material properties, our method can deform the surface mesh in a non-uniform way while previous deformation techniques are mainly designed for uniform materials. The non-uniform deformation is achieved by material-dependent gradient field manipulation and Poisson-based reconstruction. Comparing with previous material-oblivious deformation techniques, our method supplies finer control of the deformation process and can generate more realistic results. We propose a novel detail representation that transforms geometric details between successive surface levels as a combination of dihedral angles and barycentric coordinates. This detail representation is similarity-invariant and fully compatible with material properties. Based on these two methods, we implement a multiresolution deformation tool, which allows the user to edit a mesh inside a hierarchy in a material-aware manner. We demonstrate the effectiveness and robustness of our methods by several examples with real-world data.
6904624
A threat-driven approach to modeling and verifying secure software
This paper presents a formal approach to threat-driven modeling and verification of secure software using aspect-oriented Petri nets. Based on the behavior model of intended functions, we identify and build formal models of security threats, which are potential misuses and anomalies of the intended functions that violate security goals. Threat mitigations are further modeled in an aspect-oriented paradigm. Taking Petri nets as a formal basis for modeling behaviors, threats, and mitigations as a whole, we verify properties of and consistency between behaviors and threats, and absence of identified threats from the integrated model of functions and threat mitigations. This makes it possible to achieve a design that is provably resistant to the anticipated threats and thus reduce significant design-level vulnerabilities.