Onsite Registration: Sunday(10/25) to Wednesday(10/28), from 8am to 3pm.
Continental Breakfast: Monday (10/26) to Wednesday (10/28), 8am-9am
Sunday, Oct 25
9:00 AM - 12:30 PM
TS 01: Tutorial-1
Room: Banneker
- Tutorial: Networking Protocols Defensive Against Malicious Failures of Trusted Components
- Radia Perlman (Sun Microsystems Laboratories, USA)
A network is a collection of components cooperating to move data. In traditional networks, any malicious component can do much damage. For instance, a malicious router can lie about its connections, flood the network with data, or do the routing protocol correctly, but then fail to forward data properly, perhaps forwarding for some sources and not for others. This tutorial will cover failure modes of traditional forms of networks (spanning tree, distance vector, link state, path vector), and designs of more resilient networks, ranging from self-stabilizing networks to networks that will continue to work even when some of the trusted components have been arbitrarily compromised ("Byzantine failures"). It also covers techniques to minimize the need for configuration, and limit damage due to misconfiguration.
TS 02: Tutorial-2
Room: Wright
- Tutorial: Resilient and Survivable Networks
- James P. G. Sterbenz (University of Kansas & Lancaster University (UK), USA)
This tutorial provides a broad overview of the emerging field of resilient, survivable, disruption-tolerant, and challenged networks. These networks aim to remain operational and provide an acceptable level of service in the face of a number of challenges including: natural faults of network components; failures due to misconfiguration or operational errors; malicious attacks against the network hardware, software, or protocol infrastructure; large-scale natural disasters; unpredictably long delay paths either due to length (e.g. satellite and interplanetary) or as a result of episodic connectivity; weak and episodic connectivity and asymmetry of wireless channels; high- mobility of nodes and subnetworks; and unusual traffic load, legitimate (e.g. flash crowds) and DDoS attacks. The sub-disciplines of resilience will be described, including: survivability and fault- tolerance; energy-challenged, disruption- and delay-tolerant networks (DTNs); dependability, reliability, and availability; the role of security; performability (QoS); and robustness (in the control- theoretic sense). Key case studies will be presented. The fault - error - failure chain will presented, as well as the D^2R^2+DR resilience strategy: defend, detect, remediate, recover real-time control loop and diagnose, refine background control loop. Finally, multi-level techniques and mechanisms that span all protocol layers, planes, and parts of the network will be systemically and systematically covered.
2:00 PM - 3:30 PM
TS 03: Mini-Tutorial-1
Room: Banneker
- Tutorial: OD Cycles for a Wide Variety of Survivability Policies in Converged Networks
- Meir Herzberg (ECI Telecom, Israel)
Tutorial Abstract: The establishment of converged telecommunication networks, that simultaneously accommodate a growing variety of services through a common supporting network infrastructure, is a general trend, aimed at significantly reducing network expenditures. This trend has encouraged the development of a unified network paradigm capable of supplying a wide variety of cost-effective recovery solutions, each of which may cope differently with fiber cuts and equipment failures at the network nodes in order to satisfy service-dependent requirements. Expansion of the Origin-Destination (OD) Cycles approach to encompass high-order values applied to failure-independent and dependent path-recovery cases is used to meet that challenge by offering a sample of ten different policies for survivability and their relative performance measures in terms of consumption of network resources and the resulting times of recovery. For practical purposes the scope of failure scenarios is limited to single and double point of network failures only, even though the approach suggested is generic and can basically address even more complex events. Several test networks are extensively analyzed to demonstrate results of the paradigm developed and to present some useful observations about the relative positioning of the policies considered for survivability.
TS 04: Mini-Tutorial-2
Room: Wright
- Tutorial: Large Scale Optimization in Survivable WDM Mesh Networks
- Brigitte Jaumard (Concordia University, Canada); Samir Sebbah (Concordia University, Canada); Caroline Rocha (Université de Montréal, Canada)
Design and planning of survivable WDM networks involve different decision and optimization problems under network, traffic, and cost constraints. The high bandwidth brought by WDM access technology has incited network operators to extensive deployment of WDM in both access and backbone networks. Edges of networks have been pushed and transport capacity significantly increased, making the design and planning tasks harder. Consequently, efficient and scalable tools are, more than ever, needed to help network designers. Most of the design and planning problems arising in survivable optical WDM network are large scale optimization and hard combinatorial ones that cannot be tackled efficiently with the classical Integer Linear Programming (ILP) approaches. The Column Generation (CG) technique is an efficient optimization tool which has been shown to be very effective for solving particular classes of large scale systems. Indeed, combined with classical ILP tools, the CG technique offers a valuable tool for the design of highly efficient global search heuristics with an indication on the distance to the globally optimal solution when exact solution is not possible. However, it requires special care at the mathematical modeling step. The objective of this tutorial is to provide in-depth learning on the use of CG and ILP tools throughout different network design examples arising in survivable WDM networks, showing that such tools are highly efficient and scalable.
4:00 PM - 5:30 PM
TS 05: Mini-Tutorial-3
Room: Banneker
- Tutorial: Reliable Carrier Ethernet Transport
- Michael S. Berger (Technical University of Denmark, Denmark); Henrik Wessing (Technical University of Denmark, Denmark); Sarah Ruepp (Technical University of Denmark, Denmark)
This tutorial addresses how Carrier Ethernet technologies can be used in the transport network to provide resilience to the packet layer. Carrier Ethernet networks based on PBB-TE and T-MPLS/MPLS-TP are strong candidates for reliable transport of triple-play services. These technologies offer Operation, Administration and Management (OAM) functionalities and support for Quality of Service (QoS), required to obtain carrier grade quality. This tutorial provides an overview of the current level of standardization followed by an exhaustive survey of Carrier Ethernet reliability. A number of enhancements are still required to make Carrier Ethernet ready for large scale deployments of reliable point-to-multipoint services. The tutorial highlights the necessary enhancements and shows possible solutions and directions towards reliable multicast. Explicit focus is on OAM for multicast, where the signalling to identify faults is described. Finally, best practises from a Danish National project are shown.
TS 06: Mini-Tutorial-4
Room: Wright
- Tutorial: Nature Inspired Optimization for Network Reliability and Resilience
- Abdullah Konak (Penn State University, USA); Alice Smith (Auburn University, USA)
This tutorial focuses on designing reliable and resilient networks using meta-heuristics inspired by nature. The tutorial covers three new meta-heuristics, namely Ant Colony Optimization, Particle Swarm Optimization, Artificial Immune Systems, with their applications to network reliability problems. Ant Colony Optimization is inspired by the behavior of real ants while searching for food. Artificial immune systems (AIS) mimic functions of the biological immune system to solve computational problems. ACO and AIS are introduced with their applications to the service deployment problem in telecommunication systems. The service deployment problem concerns with allocation of network services over a network with unreliable components in order to maximize service availability. A Monte Carlo (MC) simulation is used to evaluate solutions created by the ACO and AIS algorithms. These meta-heuristics and the MC simulation are integrated in a novel way to minimize the computational effort to evaluate solutions. Particle swarm optimization (PSO) is a population based optimization tool which emulates the social behavior of species that live in the form of swarms in nature. PSO is demonstrated on a novel connectivity management system for ad-hoc wireless networks. The objective of the connectivity management system is to improve overall network connectivity by strategically positioning special nodes called agents. A PSO algorithm is used to dynamically determine the best possible positions of agents to improve network performance.
5:30 PM - 6:30 PM
Welcome Reception
Room: Edison EF
Monday, Oct 26
8:45 AM - 9:00 AM
Opening Remark
Room: Edison AB
9:00 AM - 10:00 AM
KS 01: Keynote by Chuck Kalmanek (Vice-President, AT&T Labs-Research)
Room: Edison AB
- Darkstar: Using Exploratory Data Mining to Raise the Bar on Network Reliability and Performance
- Charles R. Kalmanek (AT&T Labs - Research, USA); Jennifer Yates (AT&T Labs - Research, USA)
Networks have become a critical infrastructure, and performance requirements for network-based applications are becoming increasingly stringent. This trend challenges service providers to raise the bar on the performance and reliability of network services. To achieve this, new network and service management systems are needed that enable providers to continually improve performance, identify issues that are flying under the radar of network operations, and troubleshoot complex issues. This paper presents the Darkstar system, which allows analysts to address these challenges using exploratory data mining and sophisticated correlation tools. We present an overview of key applications that are built on top of the Darkstar system to illustrate the power of the approach.
10:30 AM - 12:30 PM
PS 01: Plenary Session-1
Room: Edison AB Chair: Arun Somani (Iowa State University, USA)
- 10:30 Whole Fiber Switched p-Cycles
- Diane P. Onguetou (TRLabs and University of Alberta, Canada); Wayne Grover (University of Alberta, Canada)
In the design of survivable optical networks, the cost and complexity of wavelength assignment and conversion and wavelength-selective switching is always a dominant consideration. And yet, while nodes and single DWDM channels may fail, a pre-dominant source of unavailability is physical damage to optical cables. Thus, we have considered: If it is ultimately glass that fails, what if we just replace the glass directly? More specifically, what if p-cycles were used to rapidly, simply and efficiently provide for the direct replacement of failed fiber sections with whole replacement fibers? As long as the loss budgets are adequate, entire DWDM wavebands could be restored with no switching or manipulation of individual lightpaths. Following a substitution transient, the DWDM layer would never know the break happened. In environments where fiber switching devices are low cost, and ducts are full of dark fiber, this could provide a very low cost alternative to protect an entire DWDM transport layer (or working capacity envelope) against the single largest cause of outage. Here, we make a first proposal of considering this approach. A main motivation is to remove the complexity due to wavelength assignment and wavelength continuity constraints when configuring p-cycles in a fully transparent network context. Another objective is the overall real CAPEX and OPEX cost reductions.
- 11:00 Improved Availability Models for p-Cycle-Based Network Design
- Mohammad Seyed Kiaei (Concordia University, Canada); Amin Ranjbar (McGill University, Canada); Caroline Rocha (Université de Montréal, Canada); Brigitte Jaumard (Concordia University, Canada); Chadi Assi (Concordia University, Canada)
Dual-failures are considered as the main contributors to service unavailability in p-cycle based mesh networks that are designed to withstand single failures. Methods such as post-failure reconfiguration and pre-failure provisioning of additional protection capacity have been considered to add another level of protection against dual-failures. In this paper, we present availability-aware service provisioning method in networks designed to only withstand single failures. The approach we discuss builds upon previous work and uses the concept of “cutsets method" to categorize failures that cause overall service outage; we discuss some subtle issues which make existing methods inaccurate. We then develop an improved non-joint optimization ILP model for solving the service provisioning problem under the assumption of fully loaded straddling spans in p-cycles. We also address the scalability issue by introducing several techniques to speed up the run time of the model. We evaluate the resources of inaccuracy in different scenarios. Our results indicate that the ILP solutions of our models outperform the prior work in terms of estimating service path unavailability in all considered network and traffic scenarios.
- 11:30 CAPEX and Availability Tradeoffs of Homing Architectures in Multi-Layer Networks
- Eleni Palkopoulou (Chemnitz University of Technology, Germany); Dominic A. Schupke (Nokia Siemens Networks, Germany); Thomas Bauschert (Chemnitz University of Technology, Germany)
A generic multi-layer model and a linear programming (LP) formulation are developed enabling the calculation of the optimal solution in terms of network equipment capital expenditures (CAPEX) in multi-homing design. Alternative homing architectures to traditional dual homing are studied not only with respect to network equipment costs but also regarding the achieved availability gain. Case study results show that significant cost savings can be obtained by deploying a shared router strategy, which are independent from the traffic demand and deployed equipment.
- 12:00 Survivable Design of Reconfigurable MPLS VPN Networks
- Robert Cotter (University of Missouri-Kansas City, USA); Deep Medhi (University of Missouri-Kansas City, USA)
MPLS has become an increasingly common technology for guaranteed transport services for carrying customer traffic. We consider the survivable design problem from the perspective of an MPLS VPN network provider where the data rate required is dynamically configurable based on customers' traffic demands. Network optimization formulations for global design and end-to-end fast reroute design are presented. For the global design model, we present two variations: global sequential redesign and selective sequential redesign. Through computational work, we observe that as networks get larger, the relative cost of making that network survivable goes down. Furthermore, as a network of a given number of nodes increases its connectivity, the cost of survivability goes down. Finally, the global sequential redesign and selective sequential redesign methods produce survivable design costs that are comparable, while they are approximately 28% less expensive than the end-to-end fast reroute design approach for survivability.
12:30 PM - 2:00 PM
Lunch-Mon
Room: Edison EF
2:00 PM - 3:00 PM
IS 01: Invited Session-1: (a) Radia Perlman (Sun), (b) Arun Somani (Iowa State University)
Room: Edison AB Chair: James P. G. Sterbenz (University of Kansas & Lancaster University (UK), USA)
- 14:00 Folklore of Robust Network Routing
- Radia Perlman (Sun Microsystems Laboratories, USA)
This paper describes various types of fragility that can occur in networks, along with various types of defenses that can mitigate these issues. Although some of the techniques suggested in this paper are novel, most of them are “known”, but only as folklore, instead of being written down. Because these issues are not well-documented, many protocols do not implement these well-known techniques. We include technologies that are considered “layer 2” as well as “layer 3”, because we use the term “routing” to include any technology in which paths are dynamically computed and packets are forwarded.
- 14:30 Autonomous Aero-Visual and Sensor Based Inspection Network for Asset Monitoring
- Arun Somani (Iowa State University, USA); Koray Celic (Iowa State University, USA)
This article introduces a theoretical and experimental program to develop the inspection and fault detection technology needed to integrate MAVs for persistent intelligence, reconnaissance, maintenance and surveillance for obscured or logistically challenging assets in non-urban environments. The design is explained using a context of heterogeneous deployment of wireless sensors for real-time asset monitoring by anticipating exceptional conditions and building the system to cope with them. The system converges towards an error-free state with self-stabilization, the ability to fall back to a safe mode in a financially feasible manner. This sophisticated mechanism requires a real-time capacity estimation capability to sustain the quality-of-service, which can be achieved by a distributed sensor network. We discuss issues in design and information propagation in such sensor clustered topology, optimization for power-aware networking, and link and node capacity assignment to achieve the desired goals.
3:30 PM - 5:20 PM
FP 01: Multilayer Survivability
Room: Edison AB Chair: Suku Nair (Southern Methodist University, USA)
- 15:30 Survivable IP Link Topology Design in an IP-over-WDM Architecture
- John G. Klincewicz (AT&T Labs, USA); Gagan Choudhury (AT&T Labs - Research, USA)
The design of an IP link topology (i.e., deciding which set of router-to-router communication links to establish) is an important factor in determining both the cost and performance of an IP network. In an IP-over-WDM architecture, these router-to-router links consist of wavelengths carried over an optical network. Each physical link in the optical network can carry multiple router-to-router wavelengths. The IP network must be designed for survivability in the event of an optical network failure (i.e., the loss of any given physical link or optical switch). Therefore, if there are particular physical links that carry an inordinate number of router-to-router wavelengths, a substantial amount of capacity may be required elsewhere in the IP network in order to assure survivability. In this paper, we describe a heuristic for designing an IP link topology in an IP-over-WDM architecture. In choosing which IP links to establish, the heuristic explicitly considers which router-to-router wavelengths that would be carried over each physical link and the various failure scenarios that could result. It is particularly targeted toward large, sparse networks. Some computational comparisons are included.
- 15:52 Diverse Routing Based on Shared Risk Link Groups
- Moritz B Kiese (TU München, Germany); Velislava Marcheva (O2 GmbH, Germany); Joerg Eberspaecher (Technische Universität München, Germany); Dominic A. Schupke (Nokia Siemens Networks, Germany)
This paper investigates the diverse routing problem in the presence of Shared Risk Link Groups (SRLGs) and proposes two ILP models for partial SRLG-disjoint protection based on grouping of the individual SRLGs in classes. We demonstrate our approach with SRLGs constructed from seismic maps, hence reducing the likelihood of a single earthquake affecting large portions of the network. Compared with the traditional diverse routing, our two models provide higher survivability with no increase in the overall routing cost, measured in terms of the total number of edges used.
- 16:14 A Multi-layer Recovery Strategy in FAN over WDM Architectures
- Jerzy Domzal (AGH University of Science and Technology, Poland); Robert Wójcik (AGH University of Science and Technology, Poland); Krzysztof Wajda (AGH University of Science and Technology, Poland); Andrzej Jajszczyk (AGH University of Science and Technology, Poland); Victor Lopez (Universidad Autonoma de Madrid, Spain); José Alberto Hernández (Universidad Autonoma de Madrid, Spain); Javier Aracil (Universidad Autonoma de Madrid, Spain); César Cárdenas (École Nationale Supérieure des Télécommunications, France); Maurice Gagnaire (Ecole Nationale Superieure des Telecommunications, France)
Network operators are migrating towards IP over WDM architectures. In such multi-layer networks, it is necessary to efficiently use the resources available from both layers in order to provide coordinated recovery strategies. Thanks to the development of the control plane (GMPLS and ASON), it is feasible to set up and tear down lightpaths automatically, so the WDM layer itself can support failure recovery. This paper describes a multi-layer recovery strategy in a FAN/WDM (Flow- Aware Networking/Wavelength Division Multiplexing) architecture. We propose using the EHOT (Enhanced Hold-Off Timer) algorithm to control network operation after link or node failure. Although FAN operates only on the IP level, the presented analysis shows that it is possible to ensure sufficiently low (less than 50 ms) recovery times in FAN working over an intelligent optical layer. Additionally, the paper shows the motivation for FAN networks and presents the results of carefully selected simulation experiments which allow for evaluating the duration of outages in data transmission under various conditions.
- 16:36 Crosslayer Survivable Mapping in Overlay-IP-WDM Networks
- Peera Pacharintanakul (University of Pittsburgh, USA); David Tipper (University of Pittsburgh, USA)
Survivability is a critical requirement for reliable services in any network. As the Internet moves towards a three layer architecture consisting of Overlay on top of IP on top of WDM-based networks incorporating the interaction between and among network layers is crucial for efficient and effective implementation of survivability. This paper highlights the challenges of providing survivability in three-layer networks and develops a novel approach crosslayer survivable mapping to offer such survivability in an efficient way. We investigate the impacts of overlay network dependency on lower layer network layout in terms of the capacity allocated to overlay paths. The results demonstrate the impact due to layer dependency that it is more severe than initially anticipated making it clear that single layer network design is inadequate to assure service guarantees and efficient capacity allocation.
- 16:58 Service Overlay Network Design with Reliability Constraints
- Ngok Lam (McGill University, Canada); Lorne Mason (McGill University, Canada); Zbigniew Dziong (École de technologie supérieure, University of Quebec, Canada)
We studied a class of Service Overlay Network (SON) capacity allocation problem with reliability constraints. It is assumed that a SON network could enter an inadmissible status for two reasons; first when there is insufficient resource to accommodate new connections, second when some hardware devices malfunction. The design problem is usually formulated as either a Maximum Profit (MP) constrained optimization problem or a Minimum Cost (MC) constrained optimization problem. In this article we investigate the relationship between the MP and MC formulations in the context of ensuring system operability. By using the set of Lagrange multipliers from the MC formulation as a tool, we show the general condition that the MP and MC give exactly the same reliable network designs. The key contribution of this paper is the provision of insight into the solution nature of the MP and the MC formulations in designing a reliable overlay network, thereby giving guidelines to the proper formulation the network designers may consider in designing a reliable yet economically optimal SON network.
FP 02: Wireless Networking
Room: Edison C Chair: Yi Qian (University of Nebraska–Lincoln, USA)
- 15:30 An End-to-End Solution for Secure and Survivable Routing in MANETs
- Stephen Dabideen (University of California,Santa Cruz, USA); Brad Smith (University of California, Santa Cruz, USA); JJ Garcia-Luna-Aceves (University of California at Santa Cruz, USA)
Security is a necessary requirement for the future of mobile ad-hoc networks. For a routing protocol to be considered secure, in the most general sense, uncorrupted data packets must be delivered to the destination. To achieve this, it is necessary to secure both the control plane (ensuring path discovery) and the data plane of the protocol. Survivability deals with the network remaining connected after node and link failures. In both cases, paths between from the source to the destination becomes unusable, either because of malicious behavior or lack of connectivity. A solution to both problems lie in path diversity. The availability of alternate paths, for which the performance have been verified, can be used to avoid malicious nodes or simply used to recovery from failures in the network. In this paper we focus on the need for path diversity for secure routing since its roll in the survivability of the network is inarguable.
- 15:52 Improving the Topological Resilience of Mobile Ad Hoc Networks
- Tae-Hoon Kim (University of Pittsburgh, USA); David Tipper (University of Pittsburgh, USA); Prashant Krishnamurthy (University of Pittsburgh, USA); Lee Swindlehurst (University of California at Irvine, USA)
In order to effectively deploy survivability techniques to improve the resilience of mobile ad hoc networks, one must be able to identify all the weak points of the network topology. The weak or critical points of the topology are those links and nodes whose failure results in partitioning of the network. Here we propose a new algorithm based on results from algebraic graph theory, that can find the critical points in the network for single and multiple failure cases. Utilizing this algorithm we present numerical results that examine how the number of critical points varies with nodal density. Secondly, we propose three localized topological control schemes to improve the network connectivity around critical points to lessen their importance and improve the network resilience. Numerical studies to evaluate the proposed schemes under node and link failure network conditions are presented.
- 16:14 Performance of a Cognitive Radio Network with Tolerable Service Degradation
- Shensheng Tang (Missouri Western State University, USA); Brian Mark (George Mason University, USA)
We analyze the performance of a cognitive radio wireless network, where secondary users opportunistically share the radio spectrum with primary users through spectrum sensing and may cause service degradation to the primary users due to unreliable spectrum sensing. When a secondary user occupying a channel detects the presence of a primary call arriving to the channel, it switches from its current channel to another channel, if one is available, to continue its service; however, if the secondary user fails to detect presence of the primary call, it remains on the channel and both calls will receive degraded service. Based on a queueing network model, we derive closed-form solutions for the equilibrium state probabilities and derive several performance metrics of interest. In particular, we introduce the system supportability metric to evaluate the extent to which the system can support secondary users and the interference factor to evaluate the degree of service degradation imposed on primary users by the secondary users. Numerical results are presented to show the impact of system parameters on the derived performance metrics.
- 16:36 Lightweight Scheme for Generating Stealthy Probes
- Shriram Ganesh (University of Delaware, USA); Adarshpal Sethi (University of Delaware, USA); Rommie Hardy (US Army Research Laboratory, USA)
Probing based approaches have been effectively used for network monitoring in the past. Probes such as ICMP pings provide an effective tool for detecting compromised nodes which try to delay or drop traffic. But an intelligent attacker may evade detection by giving preferential treatment to probe traffic. This is usually possible because probe packets have a different format from regular application packets and are easily distinguishable. The solution to this problem is to create stealthy probes which are indistinguishable from normal application traffic. In this paper, we build upon our earlier work on the design approaches for stealthy probing, and we propose a lightweight and effective scheme for generating stealthy probes.
- 16:58 Providing Survivability against Jamming Attack via Joint Dynamic Routing and Channel Assignment
- Shanshan Jiang (Vanderbilt University, USA); Yuan Xue (Vanderbilt University, USA)
Built upon a shared wireless medium, wireless network is particularly vulnerable to jamming attacks. The ability to recover from attacks and maintain an acceptable level of service degradation is a crucial aspect in the design of a wireless network. To address this issue, this paper investigates the network restoration solutions via the joint design of traffic rerouting, channel re-assignment, and scheduling. Efficient routing and channel assignment schemes can relieve the interference caused by both the normal network nodes and the jamming nodes. Therefore, based on the necessary conditions of schedulability, we first formulate the optimal network restoration problem as linear programming problem, which gives an upper bound on the achievable network throughput. After we solve the LP problems, we have a set of flows assigned to edges that have been assigned to different channels. And based on the LP solutions, we provide a greedy scheduling algorithm using dynamic channel assignment, which schedules both the network traffic and the jamming traffic. In particular, we consider two strategies, namely {\em global restoration} and {\em local restoration}, which can support a range of tradeoffs between the restoration latency and network throughput after restoration. To quantitatively evaluate the impact of jamming attacks during and after restoration, we define two performance degradation indices, {\em transient disruption index (TDI)} and {\em throughput degradation index (THI)}. Finally, extensive performance evaluations are performed to study the impact of various jamming scenarios in a multi-hop multi-channel wireless network.
6:30 PM - 8:30 PM
Banquet
Joe Theisman's restaurant is 0.4 mile or 8 minutes walk from Westin Alexandria. We will form a group at the lobby, leave on 6:15pm.
Room: Joe Theismann's
Tuesday, Oct 27
9:00 AM - 10:00 AM
KS 02: Keynote by Kishor Trivedi (Hudson Professor, Duke University)
Room: Edison AB
- Dependability and Security Models
- Kishor S. Trivedi (Duke University, USA); Dong Seong Kim (Duke University, USA); Arpan Roy (Duke University, USA); Deep Medhi (University of Missouri-Kansas City, USA)
There is a need to quantify system properties methodically. Dependability and security models have evolved nearly independently. Therefore, it is crucial to develop a classification of dependability and security models which can meet the requirement of professionals in both fault-tolerant computing and security community. In this paper, we present a new classification of dependability and security models. First we present the classification of threats and mitigations in systems and networks. And then we present several individual model types such as availability, confidentiality, integrity, performance, reliability, survivability, safety and maintainability. Finally we show that each model type can be combined and represented by one of the model representation techniques: combinatorial (such as reliability block diagrams (RBD), reliability graphs, fault trees, attack trees), state-space (continuous time Markov chains, stochastic Petri nets, fluid stochastic Petri nets, etc) and hierarchical (e.g., fault trees in the upper level and Markov chains in the lower level). We show case studies for each individual model types as well as composite model types.
10:30 AM - 12:30 PM
PS 02: Plenary Session-2
Room: Edison AB Chair: Brunilde Sanso (Ecole Polytechnique de Montreal, Canada)
- 10:30 Analysis of Virus Spread in Wireless Sensor Networks: An Epidemic Model
- Shensheng Tang (Missouri Western State University, USA); Brian Mark (George Mason University, USA)
We study the potential threat for virus spread in wireless sensor networks WSNs). Using the epidemic theory, we proposed a new model, called Susceptible-Infective-Recovered with Maintenance (SIR-M), to characterize the dynamics of the virus spread process from a single node to the entire network. By introducing a maintenance mechanism in the sleep mode of WSNs, the SIR-M model can improve the network anti-virus capability and enable the network adapt flexibly to different types of viruses, without incurring additional computational or signaling overhead. The proposed model can capture both the patial and temporal dynamics of the virus spread process. We derive explicit analytical solutions for the model and discuss some practical applications of interest. Extensive numerical results are presented to validate our analysis. The proposed model is applicable to the design and analysis of information propagation mechanisms in communication networks.
- 11:00 Survivability of P2P Multicasting
- Krzysztof Walkowiak (Wroclaw University of Technology, Poland)
At the present time there are many Peer-to-Peer (P2P) multicasting systems supporting live streaming, i.e. real-time dissemination of various content issued at a source node towards a set of receivers. The objective of content distributing can be twofold: maximization of the system throughput (i.e. the streaming rate) and minimization of the streaming cost while guaranteeing the particular streaming rate. In this we paper we focus on P2P multicasting applied for delivering very important content, which need delivery guarantees, e.g. weather forecast, hurricane warnings, distribution of security updates, stock exchange data, etc. To protect the system against failures several (at least two) multicasting trees are established. We tackle the question of how additional survivability constraints guaranteeing failure-disjoint trees influence the cost and throughput of the P2P multicasting system. We consider failure the following network element: overlay link, upstream node and ISP link. To investigate the problem we use both simulations and offline optimization methods. According to our results, the additional requirements necessary for protection do not have a substantial impact on the P2P multicasting system performance.
- 11:30 Exploiting Relocation to Reduce Network Dimensions of Resilient Optical Grids
- Jens Buysse (Ghent University, Belgium); Marc De Leenheer (Ghent University, Belgium); Chris Develder (Ghent University, Belgium); Bart Dhoedt (Ghent University, Belgium)
Optical Grids are widely deployed to solve complex problems we are facing today. An important aspect of the supporting network is resiliency i.e. the ability to overcome network failures. In contrast to classical network protection schemes, we will not necessarily provide a back-up path between the source and the original destination. Instead, we will try to relocate the job to another server location if this means that we can provide a backup path which comprises less wavelengths than the one the traditional scheme would suggest. This relocation can be backed up by the Grid specific anycast principle: a user generally does not care where his job is executed and is only interested in its results. We present ILP formulations for both resilience schemes and we will evaluate them in a case study on a European network topology.
- 12:00 Multiterminal Measures for Network Reliability and Resilience
- Toni Farley (Arizona State University, USA); Charles Colbourn (Arizona State University, USA)
Network reliability, specifically k-terminal reliability, gives the probability that k specified nodes in a network are connected. Multi-terminal network resilience measures the average k-terminal reliability over all node sets of size k. This is the expectation that a randomly chosen set of k nodes is connected. One may also ask for the probability that any k nodes are connected. This leads to three ways to require a set of k nodes be connected: the nodes are provided as input to the problem (as in reliability), they are randomly chosen (as in resilience), or they can be any k nodes. Certain problems may require a set constructed by some combination of the three. We introduce new measures to cover these possibilities, and reduce all measures to two general expressions that capture them. These expressions permit the consideration of decades of work on reliability to solve them. Additionally, we introduce six component-based network measures, and demonstrate how they can be solved alongside reliability and resilience. The component based measures admit even more variability in problem definition. In the end, we have thirteen distinct measures, and solve them simultaneously. An algorithm and example results are provided.
12:30 PM - 2:00 PM
Lunch-Tue
Pasara Thai restaurant is on the north side of Westin Alexandria across the street, at 2051 Jamieson Ave, Alexandria, VA 22314.
Room: Pasara Thai
2:00 PM - 3:00 PM
IS 02: Invited Session-2: (a) Eytan Modiano (MIT), (b) Robert Doverspike (AT&T Labs-Research)
Room: Edison AB Chair: Michal P. Pioro (Warsaw University of Technology, Poland)
- 14:00 Lightpath Routing and Capacity Assignment for Survivable IP-over-WDM Networks
- Aradhana Narula-Tam (MIT Lincoln Laboratory, USA); Eytan Modiano (MIT, USA)
In IP-over-WDM networks the logical topology consists of a set of lightpaths that are routed on top of the physical fiber topology. Hence a single fiber cut can lead to multiple logical link failures. We study the impact of lightpath routing on network survivability and spare capacity requirements. We show that poor routings can lead to significant increase in spare capacity requirements and develop new metrics for assessing the survivability of different lightpath routings. Finally, we use these metrics to develop joint lightpath routing and capacity assignment algorithms that significantly reduce the spare capacity requirements of IP-over-WDM networks.
- 14:30 Restoration in Carrier Networks
- Robert Doverspike (AT&T Labs - Research, USA); Bruce Cortez (AT&T, USA)
Quality of Service (QoS) is an important objective of large telecommunications carriers. Network restoration is the prime capability needed to achieve this objective. While a large body of publications study and propose different restoration methods and network optimization algorithms, very few have actually been implemented. To address this, we present background on how today’s large carrier terrestrial networks are constructed and operated. In particular we describe their segmentation, layering, and where, how and why network restoration is selectively implemented. We conclude with some observations where restoration research has the greatest need.
3:30 PM - 5:20 PM
FP 03: Survivable Design-I
Room: Edison AB Chair: Joerg Eberspaecher (Technische Universität München, Germany)
- 15:30 DSP Network Design with Availability Considerations
- Brody Todd (University of Alberta, Canada); John Doucette (University of Alberta, Canada)
This paper expands on the demand-wise shared protection model in order to capacitate a network that reaches given minimum availability requirements. By enabling DSP to take into consideration minimum availability, a network can be capacitated to meet user’s requirements of the network. This provides a way to customize the level of protection throughout the network that matches the needs of those using the network.
- 15:52 Optimization of p-Cycles for Survivable Anycasting Streaming
- Adam Smutnicki (Wroclaw University of Technology, Poland); Krzysztof Walkowiak (Wroclaw University of Technology, Poland)
Intensive and extensive development of computer networks generates the problem of ensuring suitable high level of network survivability. A lot of research have been done in this area in past years, including those associated with the use of p-cycles. p-Cycles provide very good level of protection with low cost. Up to now, p-cycles have been widely used for protection of unicast and multicast traffic. In this paper we consider the use of p-cycles in the context of protecting anycast traffic. We propose the new approach, which joins protection on physical link level with protection on the flow level. What is more, we introduce new properties and formulate an algorithm for minimising the total cost of protection. Obtained numerical results show that the proposed methodology outperforms existing approaches.
- 16:14 Availability Target Redefinition for Dynamic Connections in WDM Networks with Shared Path Protection
- Diego Lucerna (Politecnico di Milano, Italy); Massimo Tornatore (University of California, Davis, USA); Biswanath Mukherjee (Dept. of Computer Science - University of California Davis, USA); Achille Pattavina (Politecnico di Milano, Italy)
Recently, new solutions for automatized management in optical networks promise to allow customers to specify on-demand the terms of the Service Level Agreement(SLA) to be guaranteed by the Service Provider (SP). For a WDM mesh network that provides shared-path-protection we exploit the knowledge, among the other Service Level Specifications (SLS), of the connection holding time to dynamically manage the availability provided by the network to the connection during its lifetime. We monitor the actual availability provided to the connection, considering, e.g., the actual downtime experienced by the connection, and, every time the network status changes (typically, for a fault occurrence, or a connection departure or arrival), we evaluate the the maximal availability that can be provided to the connection based on our knowledge of all the predictable network state changes, i.e., the future connection departures. Since some of the connection will be ahead of their stipulated availability (credit), while other connections will be behind their availability requirements (debit), we propose a mechanism that allows to "trade'' availability "credits'' and "debits'', by increasing or decreasing the shareability level of the backup capacity. So, we introduce an holding-time-aware approach which permits to manage in a more flexible manner the availability provided during the connection lifetimes. For a typical wavelength-convertible US nationwide network, our approach obtains significative savings on Blocking Probability (BP), while reducing the penalties due to SLA violations.
- 16:36 Near-Optimal FIPP p-Cycle Network Designs using General Path-Protecting p-Cycles and Combined GA-ILP Methods
- Diane P. Onguetou (TRLabs and University of Alberta, Canada); Dimitri Baloukov (TRLabs, Canada); Wayne Grover (University of Alberta, Canada)
Recent work on failure independent path-protecting p-cycles (FIPP) has revealed some new, relatively simple and possibly cost-effective approaches for FIPP p-cycle network design. The first step of the proposed strategy consists of solving a more general path-protecting p-cycle (GPP) problem in which the constraint of failure independence is relaxed. The second step consists of imposing the failure independence constraint onto the GPP solution and identifying the working paths that become unprotected as a result. A FIPP p-cycle solution is extracted by capacitating additional cycles to protect these paths, the number of which the results revealed to never exceed three. Another contribution of this work is the adaptation of the novel combination of genetic algorithms with integer linear programming (GA-ILP) to the GPP concept, which allowed us to solve large GPP problem instances. GA-ILP solutions were typically within 1% of optimality for smaller networks for which the exact solutions were known. The GPP and FIPP solutions obtained with the assistance of GA-ILP were considerably better (by as much as 23%) than those obtained by the FIPP disjoint route set (DRS) method. Furthermore, the results obtained in this paper also showed that relaxing the disjoint route set constraint in FIPP p-cycle networks can result in as much as 9% decrease in spare capacity cost. Also in this paper, we ventured to provide a true comparison of span-protecting p-cycles with FIPP p-cycles, from the capacity efficiency perspective.
- 16:58 Static Lightpath Establishment with Transmission Impairments Consideration in WDM All-Optical Networks
- Maroua Bakri (Ecole Nationale d'Ingénieurs de Tunis, Tunisia); Mohamed Koubaa (Ecole Nationale d'Ingénieurs de Tunis, Tunisia); Mourad Menif (École Supérieure des Communications de Tunis, Tunisia); Imen Ouarda (Ecole Supérieure des Communications de Tunis, Tunisia)
Providing ultra high-speed end-to-end connectivity in core optical networks while satisfying the requirements for quality of service is a topic of intense research. In an optical network, a connection is set up to carry a data signal via an all-optical channel (lightpath) from its source to destination nodes. The analog nature of the signal transmission through the network links and nodes leads to signal quality degradation due to impairments accumulation. Such degradation should be taken into account when considering the Routing and Wavelength Assignment (RWA) problem. Most of preceding studies carried out on RWA neglect the impact of the physical layer impairments. In this paper, three physical layer impairment aware RWA algorithms are developed. We explicitly consider the effect of four physical layer impairments namely Chromatic Dispersion (CD), Polarization Mode Dispersion (PMD), Optical Signal to Noise Ratio (OSNR) and Nonlinear Phase Shift (φNL). Taking into account physical impairments when solving the RWA problem intuitively should affect the computed solution: the selection of a suitable path and suitable wavelength may fail to meet the minimum transmission requirement. To the best of our knowledge, this is the first attempt to include, simultaneously, the four aforementioned transmission impairments when dealing with the RWA problem. The performance of the proposed algorithms is demonstrated to be promising through illustrative numerical examples.
FP 04: Traffic Engineering & Resiliency
Room: Edison C Chair: John G. Klincewicz (AT&T Labs, USA)
- 15:30 On Reliability, Performance and Internet Power Consumption
- Brunilde Sanso (Ecole Polytechnique de Montreal, Canada); Hakim Mellah (GERAD and École Polytechnique de Montréal, Canada)
With the increasing concern for global warming, the impact of Internet power consumption is gaining interest. In this paper, we explore, for the first time, the relationship between network robustness, performance and Internet power consumption. We first discuss such a relationship based on data collected from Internet sources. Next, we propose a modeling framework to size that relationship. It is shown that when designing networks based on power consumption, careful attention should be paid to the trade-off between energy consumption and network performance since doing otherwise would lead to unreliable networks.
- 15:52 Differentiated Reliability in Traffic Engineered MPLS and DiffServ-aware Next Generation Networks
- Christian Awad (École Polytechnique of Montreal, Canada); Brunilde Sanso (Ecole Polytechnique de Montreal, Canada); Andre Girard (INRS-EMT and GERAD, Canada)
Positioned between the IP service and optical transport planes, DiffServ-aware MPLS-TE (MPLS-DS-TE) combines the advantages of Multi-Protocol Label Switching (MPLS), Differentiated Services (DiffServ) and Traffic Engineering (TE) to provide high performance and quality of service guarantees in next generation multimedia networks. However, there is no clear indication on how to ensure QoS control and provide differentiated reliability in case of failures. In previous work, we proposed the DiffServ* and the DiffProtect architectures to provide differentiated protection for IP services for which more reliability is needed. In this article, we review the key features of these architectures and explain how DiffServ* can be easily implemented using the new MPLS-DS-TE framework and discuss, with the support of simulation results, how DiffServ* improves MPLS-DS-TE's bandwidth management and QoS control capabilities in the event of failures.
- 16:14 Primary and Backup Paths Optimal Design for Traffic Engineering in Hybrid IGP/MPLS Networks
- Anna Mereu (University of Cagliari, Italy); Davide Cherubini (Alcatel-Lucent, Ireland); Alessandra Fanni (University of Cagliari, Italy); Antonio Frangioni (University of Pisa, Italy)
The paper describes an optimization model which aims at minimizing the maximum link utilization of IP telecommunication networks under the joint use of the traditional IGP protocols and the more sophisticated MPLS-TE technology. The survivability of the network is taken into account in the optimization process implementing the path restoration scheme. This scheme benefits of the Fast Re-Route (FRR) capability allowing service providers to offer high availability and high revenue SLAs (Service Level Agreements). The hybrid IGP/MPLS approach relies on the formulation of an innovative Linear Programming mathematical model that, while optimizing the network utilization, provides optimal user performance, efficient use of network resources, and 100\% survivability in case of single link failure. The possibility of performing an optimal exploitation of the network resources throughout the joint use of the IGP and MPLS protocols provides a flexible tool for the ISP (Internet Service Provider) networks traffic engineers. The efficiency of the proposed approach is validated by a wide experimentation performed on synthetic and real networks. The obtained results show that a limited number of LSP tunnels have to be set up in order to significantly reduce the congestion level of the network while at the same time guaranteeing the survivability of the network.
- 16:36 Cooperative Multi-Provider Routing Optimization and Income Distribution
- Mariusz Mycek (Warsaw University of Technology, Poland); Stefano Secci (Telecom ParisTech, France); Michal P. Pioro (Warsaw University of Technology, Poland); Jean-Louis Rougier (TELECOM ParisTech, France); Artur Tomaszewski (Warsaw University of Technology, Poland); Achille Pattavina (Politecnico di Milano, Italy)
We consider the problem of cooperative distributed routing optimization in multi-domain (and multi-provider) networks. The main area of our interest are ASON/G-MPLS transport networks, still the results of our investigations could be extended to any multi-domain network, where particular domains have limited mutual visibility of intra-domain resources. This paper refines a distributed decomposition mechanism for reliable cooperative optimization of flow reservation levels (introduced in [1]), by considering the fundamental issue of fair income distribution. The proposed idea of income distribution mechanism has been adopted from the theory of cooperative games (Shapley value). We show the benefits in adopting the proposed income distribution scheme by numerical simulations.
- 16:58 Objective Functions for Optimization of Resilient and Non-Resilient IP Routing
- Matthias Hartmann (University of Wuerzburg, Germany); David Hock (University of Wuerzburg, Germany); Michael Menth (University of Wuerzburg, Germany); Christian Schwartz (University of Wuerzburg, Germany)
Intradomain routing in IP networks follows least-cost paths according to administrative link costs. Routing optimization modifies these values to minimize an objective function for a network with given link capacities and traffic matrix. An example for an objective function is the maximum utilization of all links under failure-free conditions or also after rerouting in case of network failures. Many papers have provided heuristic algorithms for routing optimization using different objective functions, but the investigation and comparison of various objective functions has not attracted much attention so far. In this work we present several objective functions for resilient IP routing. We also propose a new combined optimization approach which can simultaneously optimize different objective functions with almost no additional computation effort and describe new techniques to minimize overall computation time. The different objective functions and combinations thereof are then analyzed and compared experimentally.
Wednesday, Oct 28
8:45 AM - 9:45 AM
KS 03: Keynote by Jon Peha (Chief Technologist, Federal Communication Commission)
Room: Edison AB
10:00 AM - 12:00 PM
PS 03: Plenary Session-3
Room: Edison AB Chair: Dominic A. Schupke (Nokia Siemens Networks & Research, Technology and Platforms, Germany)
- 10:00 Optimizing the IP router update process with traffic-driven updates
- Wouter Tavernier (Ghent University - IBBT, Belgium); Dimitri Papadimitriou (Alcatel-Lucent Bell, Belgium); Didier Colle (IBBT - Ghent University, Belgium); Mario Pickavet (Ghent University, Belgium); Piet Demeester (Ghent University, Belgium)
The update process in an IP router after a failure is detected, is a complex process involving more than just recalculating shortest paths. When statistics related to forwarded traffic are not taken into account, which is generally the case, we show that packet loss can be significantly higher than is strictly needed. In this paper we present a combined control and traffic-driven routing table update scheme which minimizes the packet loss during the switchover, based on an efficient use and planning of the central router process quantum. We discuss the parameters of the algorithm and show its value in a simulation environment.
- 10:30 Robust Routing vs Dynamic Load-Balancing A Comprehensive Study and New Directions
- Pedro Casas (Telecom Bretagne, France); Federico Larroca (TELECOM ParisTech, France); Jean-Louis Rougier (TELECOM ParisTech, France); Sandrine Vaton (Telecom Bretagne, France)
Traffic Engineering (TE) has become a challenging task for network management and resources optimization due to traffic uncertainty and to the difficulty to predict traffic variations. To address this uncertainty in a robust and efficient way, two almost antagonist approaches have emerged during the last years: Robust Routing and Dynamic Load-Balancing. The former copes with traffic uncertainty in an off-line preemptive fashion, computing a stable routing configuration that is optimized for a large set of possible traffic demands. The latter balances traffic among multiple paths in an on-line reactive fashion, adapting to traffic variations in order to optimize a certain cost-function. Much has been said and discussed about the advantages and drawbacks of each approach, but very few works have tried to compare the performance of both mechanisms, particularly in the same network and traffic scenarios. This paper brings insight into several Robust Routing and Dynamic Load-Balancing algorithms, evaluating their virtues and shortcomings and presenting new mechanisms to improve previous proposals. Among others, such a study intends to help network operators in choosing an adequate mechanism to cope with traffic uncertainty.
- 11:00 Utility of Algebraic Connectivity Metric in Topology Design of Survivable Networks
- William Liu (University of Canterbury, New Zealand); Harsha Sirisena (University of Canterbury, New Zealand); Krzysztof Pawlikowski (University of Canterbury, New Zealand); Allan McInnes (University of Canterbury, New Zealand)
In studies of survivable networks, it is important to be able to differentiate network topologies by means of a robust numerical measure that indicates the levels of immunity of these topologies to failures of their nodes and links. Ideally, such a measure should be sensitive to the existence of nodes or links which are more important than others, for example, if their failures cause the network’s disintegration. In this paper, we suggest using an algebraic connectivity metric, adopted from spectral graph theory, namely the 2nd smallest eigenvalue of the Laplacian matrix of the network topology, instead of the average nodal degree that is usually used to characterize network connectivity in studies of the spare capacity allocation problem. Extensive simulation studies confirm that this metric is a more informative and more accurate parameter than the average nodal degree for characterizing network topologies in survivability studies.
- 11:30 On Robust Network Planning
- Ali Tizghadam (University of Toronto, Canada); Alberto Leon-Garcia (University of Toronto, Canada)
One of the important properties of a reliable communication network is the robustness to the environmental changes. This paper looks at the design of robust networks from a new perspective. A graph-theoretical metric, betweenness, in combination with network weight matrix is used to define a global quantity, network criticality, to characterize the robustness of a network. We show that network criticality is a monotone decreasing function of weight matrix. Furthermore, it is shown that network criticality is a strictly convex function of network weight matrix. This leads to a well-defined convex optimization problem to find the optimal weight matrix assignment to minimize network criticality.
12:30 PM - 2:00 PM
Lunch-Wed
Room: Edison EF
1:30 PM - 3:20 PM
FP 05: Survivable Design-II
Room: Edison AB Chair: Didier Colle (IBBT - Ghent University, Belgium)
- 13:30 Protection for MPLS-TP Multicast Services
- Jiang Zhang (Technical University of Denmark, Denmark); Sarah Ruepp (Technical University of Denmark, Denmark); Michael S. Berger (Technical University of Denmark, Denmark); Henrik Wessing (Technical University of Denmark, Denmark)
This paper proposes three innovative point-to-multipoint protection schemes to provide efficient and reliable MPLS Transport Profile multicast services, which is particularly relevant for the fast growing IPTV broadcast service. The three proposed protection schemes are all based on the interconnected rings structure, which is a widely deployed topology of legacy networks and has the natural ability to support resiliency. The first protection scheme extends the protection methods defined in the latest IETF draft standard to the interconnected rings structure. The second protection scheme introduces an adapted OAM function, which has the ability to monitor the multicast service’s status, such as configuration failures, software failures and performance degradation, to ensure the reliability of the whole branches and leaves of the multicast service. Furthermore, the interconnecting nodes of the rings make the protection switching decision, which releases the work to upgrade every node on the existing ring and thereby eases the MPLS Transport Profile network deployment. Instead of having one working path in one direction and the other direction being used as protection path, in the third protection scheme, the paths in both directions are used as working paths. When there is a failure, the two working paths protect each other, which increases the efficiency of the network resources. The traffic distribution on the ring is divided by these two separated working paths, which lowers the amount of affected entities when a failure occurs.
- 13:52 Efficient Ethernet Multi-Ring Protection System
- Doojeong Lee (KAIST, Korea); June-Koo Kevin Rhee (KAIST, Korea); Kyusang Lee (KAIST, Korea); Peter Cho (Actus Networks, Korea)
Ethernet ring protection (ERP) introduced by ITU-T G.8032 Recommendation is a new class of packet switched network protection technology that can provide ring automatic protection switch for nested multiple Ethernet rings. An ERP system is required to provide network protection against link and node failures within 50ms. Whenever the protection scheme switches the ring to have a new topology, the standard requires all nodes to flush their filtering data base (FDB) resulting in congestion in the access networks. In this paper we evaluate the protection performance of the current G.8032 scheme and introduce additional novel schemes for performance enhancements in nested multi ring networks.
- 14:14 Scalable Backup Configurations Creation for IP Fast Reroute
- Shohei Kamamura (NTT, Japan); Takashi Miyamura (NTT, Japan); Cristel Pelsser (IIJ, Japan); Ichiro Inoue (NTT, Japan); Kohei Shiomoto (NTT, Japan)
IP Fast Reroute techniques have been proposed to achieve fast failure recovery in just a few milliseconds. The basic idea of IP Fast Reroute is to reduce recovery time after failure by precomputing backup routes. A multiple routing configurations (MRC) algorithm has been proposed for obtaining IP Fast Reroute. MRC prepares backup configurations, which are used for finding a detour route after failures. However, this current algorithm requires too many backup configurations to recover from failures. We propose a new backup configuration computation algorithm for reducing configurations as much as possible. The basic idea is to construct a spanning tree excluding failure links in each backup configuration. We show that the effectiveness of our algorithm is especially high in large-scale power-law networks.
- 14:36 A Wavelength Sharing and Assignment Heuristic to Minimize the Number of Wavelength Converters in Resilient WDM Networks
- Shreejith Billenahalli (University of Texas at Dallas, USA); Miguel Razo (University of Texas at Dallas, USA); Wanjun Huang (University of Texas at Dallas, USA); Arularasi Sivasankaran (University of Texas at Dallas, USA); Limin Tang (University of Texas at Dallas, USA); Hars Vardhan (University of Texas at Dallas, USA); Paolo Monti (The Royal Institute of Technology (KTH), Sweden); Marco Tacca (University of Texas at Dallas, USA); Andrea Fumagalli (UTD, USA)
With the successful introduction of reconfigurable optical add-drop multiplexers (ROADMs) and related technologies, WDM networks are now growing in the number of optical nodes, wavelengths, and lambda services supported. In addition, shared path protection mechanisms — whereby lambda services are allowed to share protection wavelength channels — are possible at the optical (WDM) layer. Efficient strategies must be devised to both determine the set of services that must share a common protection wavelength channel and assign wavelengths to every service. One objective of these strategies is to minimize the total number of wavelength converters (WCs), which are required every time the wavelength continuity constraint cannot be met. This paper presents a scalable and efficient heuristic, whose goal is to minimize the number of WCs in resilient WDM networks supporting static sets of shared path protection lambda services. The heuristic comprises a set of polynomial algorithms that are executed sequentially to obtain a sub-optimal solution. In small size instances of the problem, the heuristic is compared against the optimal solution obtained from ILP formulation. For large size instances — tens of thousands of lambda services and hundreds of nodes — the heuristic yields an average number of WCs that is close to be linear in the number of services, despite the fact that the wavelength sharing factor increases.
- 14:58 Designing Backbone Networks using the Generalized Steiner Problem
- Franco Robledo Amoza (Facultad de Ingeniería, Universidad de la República, Uruguay); Eduardo Canale (Facultad de Ingeniería, Universidad de la República, Uruguay)
In the design of metropolitan optical fiber networks, a commonly applied requirement is to ensure the existence node-disjoint-paths between pairs of distinguished nodes of the network. In this way, when a failure occurs in some component (link or node), the network will remain connected, a basic requisite for maintaining an operational state. In this work, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) for designing a survivable backbone. The algorithm builds topologies which comply with heterogeneous node-connectivity requirements. The method is applied to a set of problem instances with different connectivity requirements, obtaining results which appear promising.
FP 06: Diversity Coding
Room: Edison C Chair: Yu Liu (Juniper Networks, USA)
- 13:30 Continuity-based Resilient Communication
- Piotr Cholda (AGH University of Science and Technology, Poland); Anders Mykkeltveit (Norwegian University of Science and Technology, Norway); Bjarne E. Helvik (Norwegian University of Science and Technology, Norway); Andrzej Jajszczyk (AGH University of Science and Technology, Poland)
The paper advocates that in some communication service providing settings, it is more appropriate to focus on the continuity of a connection as the prime reliability attribute for defining requirements and establishing Service Level Agreements, rather than the traditionally used availability. The justification for this approach and types of services where continuity is relevant are given. For illustration, a transport network with an optical control plane for a utility grid along with some theoretical background is studied.
- 13:52 Path Diversification: A Multipath Resilience Mechanism
- Justin P Rohrer (The University of Kansas, USA); Abdul Jabbar (The University of Kansas, USA); James P. G. Sterbenz (University of Kansas & Lancaster University (UK), USA)
We present Path Diversification, a new mechanism that can be used to select multiple paths between a given ingress and egress node pair using a quantified diversity measure to achieve maximum flow reliability. The path diversification mechanism is targeted at the end-to-end layer, but can be applied at any level for which a path discovery service is available, e.g. intra-realm routing, inter-realm routing. Path diversification also takes into account higher level requirements for low-latency or maximal reliability in selecting appropriate paths. Using this mechanism will allow future internetworking architectures to exploit naturally rich physical topologies to a far greater extent than is possible with shortest-path routing and/or equal-cost load balancing. In this paper we describe the path diversity metric and its application at various aggregation levels. We then apply this metric in the path diversification process in the context of several real-world network graphs to asses the gain in flow reliability due to path diversification.
- 14:14 Network Coding for Resilient Peer-to-Peer Networks
- Dingyong Hu (University of Electronic Science and Technology of China, Hong Kong); Morris Wang (The Hong Kong Polytechnic University, Hong Kong); Francis C.M. Lau (Hong Kong Polytechnic University, Hong Kong); Qicong Peng (University of Electronic Science and Technology of China, P.R. China)
Peer dynamics (departure or failure) in peer-to-peer (P2P) networks disrupts the downloading process to the peers. Previous works on fault resilience include peer selection and overlay topology organization. Random network coding based on the generation concept is a practical approach to implement network coding for data networks in general. If we model the generations as blocks distributed by a “seed” in a P2P network and the disruptions caused by peer dynamics as packet losses, random network coding can be applied in P2P networks. In this paper, we propose a network coding scheme using a concept we call “generation crossing”. We also introduce a full cardinality precode, which enables a peer to reconstruct the original data file when only a subset of data blocks is received. We show that the success rate for the whole file to be delivered to peers increases remarkably with a small number of overlapped packets between successive generations.
- 14:36 Two-Stage Decomposition of SNORT Rules towards Efficient Hardware Implementation
- Hao Chen (State University of New York - Binghamton, USA); Douglas Summerville (State University of New York at Binghamton, USA); Yu Chen (State University of New York - Binghamton, USA)
The performance gap between the execution speed of security software and the amount of data to be processed is ever widening. A common solution is to close the performance gap through hardware implementation of security functions. However, continuously expanding signature databases have become a major impediment to achieving scalable hardware based pattern matching. Additionally, evolutionary rule databases have necessitated real time online updating for reconfigurable hardware implementations. Based on the observation that signature patterns are constructed from combinations of a limited number of primary patterns, we propose to decompose the Snort signature patterns. These smaller primary pattern sets can be stored along with their associations to allow dynamic signature pattern reconstruction. Not only does the matching operation potentially become more scalable, but the real time online updating task is simplified. The approach is verified with patterns from the latest version of the Snort rule database. The experimental results show that after decomposition, a reduction in size of over 77% can be achieved on Snort signature patterns.
- 14:58 Model based Evaluation of Policies for End-Node Driven Fault Recovery
- Jesper Grønbæk (Aalborg University, Denmark); Hans-Peter Schwefel (Aalborg University, Denmark); Thomas S. Toftegaard (Århus University, Denmark)
Abstract—In evolving ubiquitous networking environments some end-nodes will rely on highly critical end-user services in infrastructure and ad-hoc networks. As future networks will be dominated by mobility and unreliable wireless links, providing such critical end-user services is a challenge. In this work we target the problem of managing faults in such networking systems by fault management driven by the end-node. We introduce a system model to evaluate recovery decision policies based on fault diagnosis capabilities. The model method is applied in a scenario of hand-over between wireless access points. Evaluated policies are (1) no fail-over, (2) fail-over at fault diagnosis and (3) time restricted fail-over. Comparison to detailed simulations show that the developed Markov model is suitable to maximize end-user service reliability - in this case for the example of an SCTP file transfer. The numerical results from the model allow to determine the best strategy and its parameters depending on properties of the fault-diagnosis component.
3:30 PM - 4:30 PM
CP: Closing Panel: "Does Reliability Matter in Future Networks?"
Room: Edison AB
Announcing best paper award.
Panelist: Dominic Schupke, Nokia Siemens; Roy Pinchot, Telecontinuity; James Sterbenz, Kansas University; John Doucette, U. Alberta; David Tipper, U. Pittsburgh
Printer-friendly version
Send to friend
