Proof-of-stake consensus protocols often rely on distributed randomness beacons (DRBs) to generate randomness for leader selection. This work analyses the manipulability of Ethereum's DRB implementation, RANDAO, in its current consensus mechanism. Even with its efficiency, RANDAO remains vulnerable to manipulation through the deliberate omission of blocks from the canonical chain. Previous research has shown that economically rational players can withhold blocks known as a block withholding attack or selfish mixing when the manipulated RANDAO outcome yields greater financial rewards.

After successfully transitioning from proof-of-work to proof-of-stake, the Ethereum blockchain’s developer community has set an ambitious goal of achieving rapid block finalization, ideally completing it before the next block proposal, a concept known as single slot finality. Currently, block finalization on the ETH beacon chain takes ∼ 15 minutes to collect the attestation from the majority of the validators. The current protocol has several drawbacks, including slow finalization, high bandwidth usage and a rigid aggregation structure that is prone to failures. The challenge is collecting cryptographic signatures from close to a million validators distributed worldwide, connected to the network in 12 seconds without requiring high bandwidth internet connections from the peers in the network. This study presents an alternative scheme that has the potential to realize single-slot finality. Ours is a fully decentralized approach in which no node has a specific role, rendering it more robust than the current one. We simulate our heuristics on the Ethereum network topology and demonstrate that it can efficiently collect a million attestations from almost ten thousand physical nodes.

Decentralisation is one of the most important structural principles of blockchains and it should be present in all aspects of these systems. There is a growing scientific effort to develop protocols that enable the exchange of digital assets between two heterogeneous blockchains without a third-party arbitrator. We investigate the scenario where two parties wish to exchange digital tokens and run a swap protocol without the intervention of a third party. This is a complex and cooperative process for which – in a trust-less environment – atomicity and fairness must be ensured. While smart contracts provide a convenient way to achieve this, we want to ensure that the two parties leave no traceable data on the respective chains. The challenge here is that the two digital assets can reside on different chains with different signature schemes. Tackling these issues, we present a protocol description for the exchange of two arbitrary cryptocurrencies. A generic standard for atomic swap implementations in terms of the required cryptographic primitives is given. Additionally, we derive a protocol for the necessary interactions between two arbitrary chains using these primitives. To demonstrate applicability, we illustrate how this protocol can be instantiated with Schnorr and BLS signatures.

Survivable routing is crucial in backbone networks to ensure connectivity, even during failures. During network design, groups of network elements prone to potential failure events are identified. These groups are referred to asShared Risk Link Groups(SRLGs). When these SRLGs consist of a set of links intersected by a connected region of the plane, they are termed regional-SRLGs. A recent study has presented a polynomial-time algorithm for finding amaximum number of regional-SRLG-disjoint pathsbetween two given nodes in a planar topology, where the paths are node-disjoint. However, existing algorithms for this problem are not practical due to their runtime and implementation complexities. This paper investigates a more general model in two aspects. First, instead of node-disjointness, we search for non-crossing regional-SRLG-disjoint paths. Second, we show how the algorithm can be extended to solve problems in directed networks. It introduces an efficient and easily implementable algorithmic framework, leveraging an arbitrarily chosen shortest path finding subroutine for graphs with possibly negative weights. Depending on the subroutine chosen, the framework either improves the previous worst-case runtime complexity or can solve the problem with high probability (w.h.p.) in near-linear expected time. The proposed framework enables the first additive approximation for a more generalNP-hard version of the problem, where the objective is to find the maximum number of regional-SRLG-disjoint paths. We validate our findings through extensive simulations.

Fast reroute (FRR) is among the fastest survivable routing approaches in packet-switched networks, because the routers are equipped with a resilient routing table in advance such that the packets can be rerouted instantly upon failures solely relying on local information, i.e., without notification messages. However, designing the routing algorithm for FRR is challenging as the number of possible sets of failed network links can be extremely high, while the algorithm should keep track of which routers are aware of the failure. Therefore, FRR methods often rely on spanning arborescences, which provide multiple disjoint failover paths up to the global connectivity of the network. In this paper, we propose a generic algorithmic framework that theoretically increases the number of failover paths to the local connectivity between each node and the root by extending an efficient connectivity preserving operation from graph theory – called edge splitting-off – to decompose the network topology node-by-node, and use Integer Linear Programs (ILPs) on these partial subproblems to build routing arborescences in the reverse direction for the original topology. Although our practical implementation cannot reach the local connectivity in all instances, we demonstrate through simulations that it still outperforms the state-of-the-art FRR mechanisms and provides better resilience with shorter paths in the arborescences.

Payment channels are auspicious candidates in layer-2 solutions to reduce the number of on-chain transactions on traditional blockchains and increase transaction throughput. To construct payment channels, peers lock funds on 2-of-2 multisig addresses and open channels between one another to transact via instant peer-to-peer transactions. Transactions between peers without a direct channel are made possible by routing the payment over a series of adjacent channels. In certain cases, this can lead to relatively low transaction success rates and high transaction fees. In this work, we introduce pliability to constructing payment channels and graft edges with more than two endpoints into the payment graph. We refer to these constructions as hyperedges. We present hyperedge-based topologies to form hypergraphs and compare them to Bitcoin’s Lightning network and other state-of-the-art solutions. The results demonstrate that hyperedge-based implementations can both increase transaction success rate, in addition to decreasing the network cost by more than 50% compared to that of the Lightning Network.

Survivable routing is crucial in backbone networks to ensure connectivity, even during failures. At network design, groups of network elements prone to potential failure events are identified. These groups are referred to as Shared Risk Link Groups (SRLGs), and if they are a set of links intersected by a connected region of the plane, we call them regional-SRLGs. A recent study has presented a polynomial-time algorithm for finding a maximum number of regional-SRLG-disjoint paths between two given nodes in a planar topology, with the paths being nodedisjoint. However, existing algorithms for this problem are not practical due to their runtime and implementation complexities.This paper investigates a more general model, the maximum number of non-crossing, regional-SRLG-disjoint paths problem. It introduces an efficient and easily implementable algorithmic framework, leveraging an arbitrarily chosen shortest path finding subroutine for graphs with possibly negative weights. Depending on the subroutine chosen, the framework improves the previous worst-case runtime complexity, or can solve the problem w.h.p. in near-linear expected time. The proposed framework enables the first additive approximation for a more general ${\mathcal{N}}{\mathcal{P}}$ -hard version of the problem, where the objective is to find the maximum number of regional-SRLG-disjoint paths. We validate our findings through extensive simulations.

Abstract This article deals with the complexity of problems related to finding cost‐efficient, disaster‐aware cable routes. We overview various mathematical problems studied to augment a backbone network topology to make it more robust against regional failures. These problems either consider adding a single cable, multiple cables, or even nodes too. They adapt simplistic or more sophisticated regional failure models. Their objective is to identify the network's weak points or minimize the investment cost concerning the risk of a network outage. We investigate the tradeoffs in mathematical modeling for the same real‐world scenario, where more sophisticated models face more computationally challenging problems. We have seen how efficiently computational geometry algorithms can be used to solve simplified problems even for sufficiently large networks. In this article, we aim to understand why different mathematical models formulated for the same real‐world scenario can or cannot be solved efficiently. In particular, we show simplistic mathematical models that formulate NP‐hard problems.

This paper presents a novel framework called Failure-Alarm Correlation Tree based Failure Localization (FACT-FL), designed to localize failed optical layer device boards in an Optical Transport Network (OTN). Specifically, FACT-FL aims to construct a set of FACTs by correlating the failed boards and alarms, where each FACT takes one failed board and its correlated alarms as the root and leaves, respectively. Furthermore, a FACT consists of a suite of kth order Failure-Alarm Correlation Chains (k-FACCs) with different order values of k. Each k-FACC indicates the chain-like correlation established by k alarms due to one common failed board. To identify all previously undetected k-FACCs, a set of binary classifiers is trained that characterizes each k-FACC from various dimensions, including time, network topology, traffic distribution, and board/alarm attributes. Eventually, an integer linear programming (ILP) problem is formulated to extract the most likely FACT(s) from those k-FACCs. Extensive case studies demonstrate the superior results of FACT-FL in terms of metrics evaluating the identified failed boards and root alarms. We also analyze its performance under different maximum order values of k and environmental changes, including failure scenarios, network topologies, traffic distributions, and noise alarms.

Fast reroute (FRR) mechanisms that can instantly handle network failures in the data plane are gaining attention in packet-switched networks. In FRR no notification messages are required as the nodes adjacent to the failure are prepared with a routing table such that the packets are re-routed only based on local information. However, designing the routing algorithm for FRR is challenging because the number of possible sets of failed network links and nodes can be extremely high, while the algorithm should keep track of which nodes are aware of the failure. In this paper, we propose a generic algorithmic framework that combines the benefits of Integer Linear Programming (ILP) and an effective approach from graph theory related to constructive graph characterization of k-connected graphs, i.e., edge splitting-off. We illustrate these benefits through arborescence design for FRR and show that (i) due to the ILP we have great flexibility in defining the routing problem, while (ii) the problem can still be solved very fast. We demonstrate through simulations that our framework outperforms state-of-the-art FRR mechanisms andvprovides better resilience with shorter paths in the arborescences.

The current best practice in survivable routing is to compute link or node disjoint paths in the network topology graph. It can protect single-point failures; however, several failure events may cause the interruption of multiple network elements. The set of network elements subject to potential failure events is called Shared Risk Link Group (SRLG), identified during network planning. Unfortunately, for any given list of SRLGs, finding two paths that can survive a single SRLG failure is NP-Complete. In this paper, we provide a polynomial-time SRLG-disjoint routing algorithm for planar network topologies and a large set of SRLGs. Namely, we focus on regional failures, where the failed network elements must not be far from each other. We use a flexible definition of regional failure, where the only restrictions are that i) the topology is a planar graph, ii) each SRLG forms a set of connected edges in the dual of the planar graph, and iii) for each node$v$, the links incident to$v$are part of an SRLG. The proposed algorithm is based on a max-min theorem. Through extensive simulations, we show that the algorithm scales well with the network size, and one of the paths returned by the algorithm is only 4% longer than the shortest path on average.

The current best practice in survivable routing is to compute link or node disjoint paths in the network topology graph. It can protect single-point failures; however, several failure events may cause the interruption of multiple network elements. The set of network elements subject to potential failure events is called Shared Risk Link Group (SRLG), identified during network planning. Unfortunately, for any given list of SRLGs, finding two paths that can survive a single SRLG failure is NP-Complete. In this paper, we provide a polynomial-time SRLG-disjoint routing algorithm for planar network topologies and a large set of SRLGs. Namely, we focus on regional failures, where the failed network elements must not be far from each other. We use a flexible definition of regional failure, where the only restriction is that the topology is a planar graph, and the SRLGs form a set of connected edges in the dual of the planar graph. The proposed algorithm is based on a max-min theorem. Through extensive simulations, we show that the algorithm scales well with the network size, and one of the paths returned by the algorithm is only 4% longer than the shortest path on average.

Modeling and listing the joint device failures of telecommunication optical backbone networks caused by large-scale regional disasters is the aim of my dissertation [1] digested in the following. The use-cases of these failure lists include helping the operators of modern telecommunication networks to meet the predefined Quality-of-Service (QoS) conditions. Informally speaking, the task tackled is translating the composed geometric problem of protecting telecommunication networks against regional failures to small-sized purely combinatorial and probabilistic problems, respectively. The development of this translation framework relied on the following pillars: 1) constructing failure models that make the best use of the data available, 2) giving fast algorithms for determining the resulting failure lists, 3) providing a theoretical and practical analysis of the complexity of the algorithms and the properties of the failure lists. The offered failure lists can be leveraged for enhancing network preparedness against disasters.

In recent decade, the applications of the Internet of Things (IoT) have been widely spread out and the market of IoT has been rapidly growing. One of the essential elements in IoT structure is wireless sensor network (WSN) because it provides useful information anywhere and it makes IoT be more necessary technology in people’s daily life. The types of sensors in IoT are becoming more diverse beyond the conventional sensors, such as mobile phones, wearable devices, surveillance cameras, and even vehicles. Typically, in WSNs, the end users are more interested in fetching the updated sensed data no matter which node is producing that data.

Several recent studies shed light on the vulnerability of networks against regional failures, which are failures of multiple nodes and links in a physical region due to a natural disaster. The paper defines a novel design framework, called Geometric Network Augmentation (GNA), which determines a set of node pairs and the new cable routes to be deployed between each of them to make the network always remain connected when a regional failure of a given size occurs. With the proposed GNA design framework, we provide mathematical analysis and efficient heuristic algorithms that are built on the latest computational geometry tools and combinatorial optimization techniques. Through extensive simulation, we demonstrate that augmentation with just a small number of new cable routes will achieve the desired resilience against all the considered regional failures.

To evaluate the expected availability of a backbone network service, the administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single component failures is often insufficient. This paper builds a stochastic model of geographically correlated link failures caused by disasters to estimate the hazards an optical backbone network may be prone to and to understand the complex correlation between possible link failures. We first consider link failures only and later extend our model also to capture node failures. With such a model, one can quickly extract essential information such as the probability of an arbitrary set of network resources to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a disaster. Furthermore, we introduce standard data structures and a unified terminology on Probabilistic Shared Risk Link Groups (PSRLGs), along with a pre-computation process, which represents the failure probability of a set of resources succinctly. In particular, we generate a quasilinear-sized data structure in polynomial time, which allows the efficient computation of the cumulative failure probability of any set of network elements. Our evaluation is based on carefully pre-processed seismic hazard data matched to real-world optical backbone network topologies.

Bloom filters and their variants are widely used as space-efficient probabilistic data structures for representing sets and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications, a common engineering solution is to set the false positive rate very small and ignore the existence of the very unlikely false positive answers. This article is devoted to close the gap between the two design concepts ofunlikelyandnot havingfalse positives. We propose a data structure called EGH filter that supports the Bloom filter operations, and besides, it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false-positive free zone of a filter. We then generalize the filter to support the listing of the elements through the use of counters rather than bits. We detail networking applications of the filter and discuss potential generalizations. We evaluate the performance of the filter in comparison with the traditional Bloom filters. We also evaluate the price in terms of memory that needs to be paid to guarantee real false positive-free operations for having a deterministic Bloom filter-like behavior. Our data structure is based on recently developed combinatorial group testing techniques.

In this article, we propose a new protection scheme for backbone networks to guarantee high service availability. The presented scheme does not require any reconfiguration immediately after the failure (i.e., it is proactive). At the same time, it does not require any reserved backup network resources either. To achieve these seemingly contradictory goals, we utilize the recent advancements in Machine Learning (ML) to implement a network intelligence that periodically re-allocates the unused capacity as protection bandwidth to meet the service availability requirements of each connection. Our goal is achieved by two components (1) predicting the traffic for the next period on each link, and (2) intelligently selecting the best fit dedicated protection scheme for the next period depending on the estimated unused (spare) bandwidth and the previous service availability violations. Note that re-allocating protection bandwidth affects neither the operational connections nor the current best practice of operators to over-provision network bandwidth to support elephant flows. Finally, we provide a case study on the real traffic from Energy Sciences Network (ESnet), a high-speed, international scientific backbone network. The key benefit of our framework is that adaptively utilizing the over-provisioned bandwidth for spare capacity is sufficient to improve the availability from three-nines to five-nines (in ESnet for the 30 examined connections). The drawback is negligible bandwidth limitations; the user perceives a minor and very temporal bandwidth limitation in less than 0.1% of the time.

Many recent studies shed light on the vulnerability of networks against large-scale natural disasters. The corresponding network failures, called regional failures, are manifested at failing multiple network elements that are physically close to each other. The recovery mechanisms of current backbone networks protect failures listed as Shared Risk Link Groups (SRLGs). We aim to design an algorithm for the routing engines, which can generate a reasonable list of SRLGs based on the limited geometric information available. As a first step towards this direction, in this paper, we propose a limited geographic information failure model for the network topology that enables efficient algorithms to compute the set of links that are expected to be close to each other. More precisely, we work with (1) relative node positions without knowing the real distances, (2) an area in the map defines the route of each physical cable, and (3) a regional failure is a circular disk with k=0,1, ... nodes in its interior. We describe an efficient algorithm for listing SRLGs based on our limited geographic information failure model and show that under realistic assumptions, the obtained list of SRLGs is short, having approximately 1.2 n and 2.2n elements for k=0 and k=1, respectively, where n is the number of nodes of the network.

Abstract Several recent works shed light on the vulnerability of networks against regional failures, which are failures of multiple pieces of equipment in a geographical region as a result of a natural disaster. To enhance the preparedness of a given network to natural disasters, regional failures and associated Shared Risk Link Groups (SRLGs) should be first identified. For simplicity, most of the previous works assume the network is embedded on a Euclidean plane. Nevertheless, they are on the Earth's surface; this assumption causes distortion. In this work, we generalize some of the related results on the plane to the sphere. In particular, we focus on algorithms for listing SRLGs as a result of regional failures of circular or other fixed shape.

Generalized diversity coding is a promising proactive recovery scheme against single edge failures for unicast connections in transport networks. At the source node, the user data is split into two parts, and their bitwise XOR is computed as a third redundancy sub-flow. In order to guarantee instantaneous failure recovery without costly node upgrades, the network must ensure that any two of the three sub-flows reach the destination node in case of a single edge failure only by allowing flow duplication or merging identical flows, and avoiding any coding operation in the core network. In this paper, we investigate the corresponding routing problem to calculate capacity-efficient routes for these sub-flows. We propose a polynomial-time algorithm for topologies without capacity constraints on the links and without capability limitations of the nodes. We show that with node limitations the presented algorithm (as well as a minimum cost disjoint path-pair) provides a 4/3-approximation for the routing problem. Furthermore, we formulate an integer linear program to provide a minimum cost solution with arbitrary constraints in general graphs and we propose a polynomial-time algorithm in directed acyclic graphs. Our simulation results suggest that with upgrading only a small set of core network nodes with flow duplication and merging capabilities most of the benefits of generalized diversity coding can be achieved.

At backbone network planning, an important task is to identify the failures to get prepared for. Technically, a list of link sets, called Shared Risk Link Groups (SRLG), is defined. The observed reliability of network services strongly depends on how carefully this list was selected and whether it contains every high-risk failure event. Regional failures often cause the breakdown of multiple elements of the network, which are physically close to each other. In this article, we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give an approach to generate the list of SRLGs that hit every possible circular disk shaped disaster of a given radius r. We show that this list has O((n + x)ρr) SRLGs, where n is the number of nodes in the network and x is the number of link crossings, and ρ, is the maximal number of links that could be hit by a circular disaster of radius r. We give a fast polynomial algorithm to enumerate the list of SRLGs and show that its worst-case time complexity is asymptotically optimal under some practical restrictions. Finally, through extensive simulations, we show that this list in practice has a size of ≈ 1.2n.

Nowadays, a majority of the Internet service providers are either piloting or migrating to software-defined networking (SDN) in their networks. In an SDN architecture a central network controller has a top-down view of the network and can directly configure each of their physical switches. It opens up several fundamental unsolved challenges, such as deploying efficient multipath routing that can provide disjoint end-to-end paths, each one satisfying specific operational goals (e.g., shortest possible), without overwhelming the data plane with a prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest (node- or edge-) disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the complexity of the underlying mathematical problem is NP-complete and we present fast heuristic algorithms. By extensive simulations, we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1%-5%), eventually opening the door for wide-scale multipath routing deployments. Finally, we show that even if a primary tree is already given it remains NP-complete to find a minimum length secondary tree concerning this primary tree.

Bloom filters and their variants are widely used as space efficient probabilistic data structures for representing set systems and are very popular in networking applications. They support fast element insertion and deletion, along with membership queries with the drawback of false positives. Bloom filters can be designed to match the false positive rates that are acceptable for the application domain. However, in many applications a common engineering solution is to set the false positive rate very small, and ignore the existence of the very unlikely false positive answers. This paper is devoted to close the gap between the two design concepts of unlikely and not having false positives. We propose a data structure, called EGH filter, that supports the Bloom filter operations and besides it can guarantee false positive free operations for a finite universe and a restricted number of elements stored in the filter. We refer to the limited universe and filter size as the false positive free zone of the filter. We describe necessary conditions for the false positive free zone of a filter and generalize the filter to support listing of the elements. We evaluate the performance of the filter in comparison with the traditional Bloom filters. Our data structure is based on recently developed combinatorial group testing techniques.

In order to evaluate the expected availability of a service, a network administrator should consider all possible failure scenarios under the specific service availability model stipulated in the corresponding service-level agreement. Given the increase in natural disasters and malicious attacks with geographically extensive impact, considering only independent single link failures is often insufficient. In this paper, we build a stochastic model of geographically correlated link failures caused by disasters, in order to estimate the hazards a network may be prone to, and to understand the complex correlation between possible link failures. With such a model, one can quickly extract information, such as the probability of an arbitrary set of links to fail simultaneously, the probability of two nodes to be disconnected, the probability of a path to survive a failure, etc. Furthermore, we introduce a pre-computation process, which enables us to succinctly represent the joint probability distribution of link failures. In particular, we generate, in polynomial time, a quasilinear-sized data structure, with which the joint failure probability of any set of links can be computed efficiently.

IT and telco providers are preparing for the era of 5G; in terms of technology, the driving force is virtualization, both for computing and networking. The 5G services will be superior than today's online services not only in technological aspects, but also from an economic and business perspective: fast service creation, effective utilization of resources, dynamic adaption to actual demand are all direct benefits of the virtualized infrastructure. In this paper we study the economic interactions between 5G resource providers and customers: we formalize how resources should be priced and selected for being booked. In particular we show that usage-based pricing is an income-maximizing scheme for providers, and we derive the problem the customers need to solve for cost-optimizing service deployment.

Shared Risk Link Group (SRLG) is a failure the network is prepared for, which contains a set of links subject to a common risk of single failure. During planning a backbone network, the list of SRLGs must be defined very carefully, because leaving out one likely failure event will significantly degrade the observed reliability of the network. Regional failures are manifested at multiple locations of the network, which are physically close to each other. In this paper we show that operators should prepare a network for only a small number of possible regional failure events. In particular, we give a fast systematic approach to generate the list of SRLGs that cover every possible circular disk failure of a given radius r. We show that this list has O((n + x)σr) SRLGs, where n is the number of nodes in the network, x is the number of link crossings, and σris the maximal number of links that could be hit by a disk failure of radius r. Finally through extensive simulations we show that this list in practice has size of ≈ 1.2 n.

Internet of Things (IoT) systems produce great amount of data, but usually have insufficient resources to process them in the edge. Several time-critical IoT scenarios have emerged and created a challenge of supporting low latency applications. At the same time cloud computing became a success in delivering computing as a service at affordable price with great scalability and high reliability. We propose an intelligent resource allocation system that optimally selects the important IoT data streams to transfer to the cloud for processing. The optimization runs on utility functions computed by predictor algorithms that forecast future events with some probabilistic confidence based on a dynamically recalculated data model. We investigate ways of reducing specifically the upload bandwidth of IoT video streams and propose techniques to compute the corresponding utility functions. We built a prototype for a smart squash court and simulated multiple courts to measure the efficiency of dynamic allocation of network and cloud resources for event detection during squash games. By continuously adapting to the observed system state and maximizing the expected quality of detection within the resource constraints our system can save up to 70% of the resources compared to the naive solution.

Instant and precise localization of a mobile user is fundamental for supporting various sophisticated indoor location-aware services. This paper focuses on achieving unambiguous user positioning using practical Bluetooth low energy (BLE) beacons with multiple discrete power levels. By receiving the beacon coverage status from a user's device, the cloud server can unambiguously pinpoint the user's location and react correspondingly. We first define the problem of beacon deployment for positioning (BDP) and provide several theoretic bounds on the number of required beacons to gain sufficient understanding on its performance behavior. The BDP problem is further formulated into an integer linear program (ILP) and solved in extensive case studies. We claim that this is the first systematic and in-depth research on beacon deployment for unambiguous user positioning. Our analysis and experiments show that the proposed solution takes O(√N) to O(N/2) beacons for N test positions, which is 2-8 times less beacons compared to that by the naive approach, while the analytical bounds are tight with the ILP results with 20% of gap.

In this article, we investigate the Advanced Global Neighborhood Failure Localization (AG‐NFL) monitoring trail (m‐trail) approach, which provides ultra‐fast all‐optical restoration for any shared protection scheme. In contrast with its previous counterparts, AG‐NFL separates the management tasks of protection switching and link maintenance, and focuses on the identification of the proper switching actions in a timely manner rather than unambiguously localizing link failures. We form switching link groups at each node, that is, links whose failures do not have to be distinguished from each other, for example, because their corresponding switching actions can be performed at the same time. Forbidden link‐pairs are introduced to identify the minimal set of conflicting switching actions, which minimizes the number of switching link groups. Furthermore, in order to minimize the number of m‐trail reconfigurations upon dynamic traffic, we analyze the AG‐NFL performance in four different m‐trail design scenarios with decreasing dependency on the data plane. We prove that AG‐NFL is NP‐complete, and we propose an efficient heuristic to solve it. We demonstrate through simulations that unambiguous localization of switching link groups instead of single link failures leads to a significantly improved m‐trail performance both in wavelength resources and the number of required transponders, while signaling‐free restoration is still provided. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 327–341 2017

In this paper, we propose a new proactive recovery scheme against single edge failures for unicast connections in transport networks. The new scheme is a generalization of diversity coding where the source data AB are split into two parts A and B and three data flows A, B, and their exclusive OR (XOR) A⊕B are sent along the network between the source and the destination node of the connection. By ensuring that two data flows out of the three always operate even if a single edge fails, the source data can be instantaneously recovered at the destination node. In contrast with diversity coding, we do not require the three data flows to be routed along three disjoint paths; however, in our scheme, a data flow is allowed to split into two parallel segments and later merge back. Thus, our generalized diversity coding (GDC) scheme can be used in sparse but still two-connected network topologies. Our proof improves an earlier result of network coding, by using purely graph theoretical tool set instead of algebraic argument. In particular, we show that when the source data are divided into two parts, robust intra-session network coding against single edge failures is always possible without any in-network algebraic operation. We present linear-time robust code construction algorithms for this practical special case in minimal coding graphs. We further characterize this question, and show that by increasing the number of edge failures and source data parts, we lose these desired properties.

Packet classification is a building block in many network services, such as routing, monitoring, and policy enforcement. In commodity switches, classification is often performed by memory components of various rule matching patterns (longest prefix match, ternary matches, exact match, and so on). The memory components are fast but expensive and power-hungry with power consumption proportional to their size. In this paper, we study the applicability of rule caching and lossy compression to create packet classifiers requiring much less memory than the theoretical size limits of the semantically-equivalent representations, enabling significant reduction in their cost and power consumption. This paper focuses on the longest prefix matching. Our objective is to find a limited-size longest prefix match classifier that can correctly classify a high portion of the traffic, so that it can be implemented in commodity switches with classification modules of restricted size. While for the lossy compression scheme a small amount of traffic might observe classification errors, a special indication is returned for traffic that cannot be classified in the rule caching scheme. We develop optimal dynamic-programming algorithms for both problems and describe how to treat the small amount of traffic that cannot be classified. We generalize our solutions for a wide range of classifiers with different similarity metrics. We evaluate their performance on real classifiers and traffic traces and show that in some cases we can reduce a classifier size by orders of magnitude while still classifying almost all traffic correctly.

Network-wide local unambiguous failure localization (NL-UFL) has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.

We present a new set of solutions for topology verification and failure localization in Software Defined Networks (SDNs). Our solutions are targeted towards offloading the control plane as much as possible and bringing more resilience against congestion or partitioning in the control plane. The core idea is to define control flows for network diagnosis and utilize a fraction of the forwarding table rules on the switches to serve these control flows. For topology verification, we present provably optimal or order-optimal solutions in total number of static forwarding rules and control messages. For single link failure localization, we present a solution that requires at least 3 |E| but at most 6 |E| forwarding rules using at most 1+log2 |E| control messages, where |E| denotes the number of bidirectional links in the forwarding plane. We analyze the latency vs. rule and control message optimality trade-offs showing that sub-second failure localization is possible even in data center scale networks without significant additional overhead in the number of static rules and control messages. We further simulate the performance of failure localization in identifying multiple link failures.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state of the art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we redesign the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode an FIB comprising more than 440 K prefixes to just about 100-400 kB of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

Packet classification is a building block in many network services such as routing, filtering, intrusion detection, accounting, monitoring, load-balancing and policy enforcement. Compression has gained attention recently as a way to deal with the expected increase of classifiers size. Typically, compression schemes try to reduce a classifier size while keeping it semantically-equivalent to its original form. Inspired by the advantages of popular compression schemes (e.g. JPEG and MPEG), we study in this paper the applicability of lossy compression to create packet classifiers requiring less memory than optimal semantically-equivalent representations. Our objective is to find a limited-size classifier that can correctly classify a high portion of the traffic so that it can be implemented in commodity switches with classification modules of a given size. We develop optimal dynamic programming based algorithms for several versions of the problem and describe how a small amount of traffic that cannot be classified can be easily treated, especially in software-defined networks. We generalize our solutions for a wide range of classifiers with different similarity metrics. We evaluate their performance on real classifiers and traffic traces and show that in some cases we can reduce a classifier size by orders of magnitude while still classifying almost all traffic correctly.

This paper deals with fast node failure localization in optical networks with monitoring trails (m-trails). It is based on Network-wide local unambiguous failure localization, which enables every node to autonomously localize any single node failure in the network in a distributed and all-optical manner by inspecting the m-trails traversing through the node. A new and innovative heuristic algorithm is presented which is based on recursion and constrained matching algorithms in general graphs. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length to achieve NL-UFL. In our experiments the new heuristic can reduce the computation time by 1000-10000 times compared to prior art.

Linear error correction is widely implemented in millions of telecommunication devices to cope with unreliable or noisy communication channels. A common error in linear encoders is when some bits that are originally one in the generator matrix get erased and become zero - usually due to a soft error becoming a hard error or simply a physical impact on the device. The need to deal with this phenomenon has been recognized in the literature, although to the best of our knowledge no one has ever tried to diagnose erasure-type faults in an encoder. In this paper we focus on the situation when the linear encoder hardware unit becomes faulty and propose a novel combinatorial fault detection scheme based on group testing to diagnose its state with great efficiency in a quick manner. Furthermore we touch upon some solutions to compensate for at both the sender and the receiver side.

A fundamental unsolved challenge in multipath routing is to provide disjoint end-to-end paths, each one satisfying certain operational goals (e.g., shortest possible), without overwhelming the data plane with prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the underlying mathematical problem is NP-complete and we present heuristic algorithms that improve the known complexity bounds from cubic to the order of a single shortest path search. Finally, by extensive simulations we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1 -- 5%), eventually opening the door for wide-scale multipath routing deployments.

Survivable routing methods have been thoroughly investigated in the past decades in transport networks. However, the proposed approaches suffered either from slow recovery time, poor bandwidth utilization, high computational or operational complexity, and could not really provide an alternative to the widely deployed single edge failure resilient dedicated 1 + 1 protection approach. Diversity coding is a candidate to overcome these difficulties with a relatively simple technique: dividing the connection data into two parts, and adding some redundancy at the source node. However, a missing link to make diversity coding a real alternative to 1+1 in transport networks is finding its minimum cost survivable routing, even in sparse topologies, where previous approaches may fail. In this paper we propose a polynomial-time algorithm with O(|V||E| log |V|) complexity for this routing problem. On the other hand, we show that the same routing problem turns to be NP-hard as soon as we limit the forwarding capabilities of some nodes and the capacities of some links of the network.

This article explores a recently introduced novel technique called the nested monitoring trail (m‐trail) method in all‐optical mesh networks for failure localization of any shared risk link group (SRLG) with up to undirected links. The nested m‐trail method decomposes each network topology that is at least ‐connected into virtual cycles and trails, in which sets of m‐trails that traverse through a common monitoring node (MN) can be obtained. The nested m‐trails are used in the monitoring burst (m‐burst) framework, in which the MN can localize any SRLG failure by inspecting the optical bursts traversing through it. An integer linear program (ILP) and a heuristic are proposed for the network decomposition, which are further verified by numerical experiments. We show that the proposed method significantly reduces the required fault localization latency compared with the existing methods. Finally, we demonstrate that nested m‐trails can also be used in adaptive probing to find SRLG faults in all‐optical networks. The nested m‐trail based probing method needs a significantly reduced number of sequential probes. Thus, the method overcomes one of the important hurdles to deploy adaptive probing in all‐optical networks: the large number of sequential probes needed to localize SRLG faults. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 347–363 2015

Large-scale information dissemination in multicast communications has been increasingly attracting attention, be it through uptake in new services or through recent research efforts. In these, the core issues are supporting increased forwarding speed, avoiding state in the forwarding elements, and scaling in terms of the multicast tree size. This paper addresses all these challenges-which are crucial for any scalable multicast scheme to be successful-by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept, we build our Bloom filter by enclosing limited information about the structure of the tree. Analytical investigation is conducted and approximation formulas are provided for optimal-length Bloom filters, in which we got rid of typical Bloom filter illnesses such as false-positive forwarding. These filters can be used in several multicast implementations, which are demonstrated through a prototype. Thorough simulations are conducted to demonstrate the scalability of the proposed Bloom filters compared to its counterparts.

Shared protection, such as failure-dependent protection (FDP), is well recognized for its outstanding capacity efficiency in all-optical mesh networks, at the expense of lengthy restoration time due to multihop signaling mechanisms for failure localization, notification, and device configuration. This paper investigates a novel monitoring trail (m-trail) scenario, called Global Neighborhood Failure Localization (G-NFL), that aims to enable any shared protection scheme, including FDP, for achieving all-optical and ultra-fast failure restoration. We first define the neighborhood of a node, which is a set of links whose failure states should be known to the node in restoration of the corresponding working lightpaths (W-LPs). By assuming every node can obtain the on-off status of traversing m-trails and W-LPs via lambda monitoring, the proposed G-NFL problem routes a set of m-trails such that each node can localize any failure in its neighborhood. Bound analysis is performed on the minimum bandwidth required for m-trails under the proposed G-NFL problem. Then, a simple yet efficient heuristic approach is presented. Extensive simulation is conducted to verify the proposed G-NFL scenario under a number of different definitions of nodal neighborhood that concern the extent of dependency between the monitoring plane and data plane. The effect of reusing the spare capacity by FDP for supporting m-trails is examined. We conclude that the proposed G-NFL scenario enables a general shared protection scheme, toward signaling-free and ultra-fast failure restoration like p-Cycle, while achieving optimal capacity efficiency as FDP.

Many of our computer networks, not the least of which the Internet, are built upon hop-by-hop routing. At the moment, it is not clear whether we will be able to scale these networks into the future economically. In this paper, we propose a new information-theoretic model to study routing scalability, we present preliminary analysis suggesting that hop-by-hop routing tolerates network growth surprisingly efficiently, and we sketch the scalability map of the Internet which we then use to make some bold predictions.

The Internet routing ecosystem is facing compelling scalability challenges, manifested primarily in the rapid growth of IP packet forwarding tables. The forwarding table, implemented at the data plane fast path of Internet routers to drive the packet forwarding process, currently contains about half a million entries and counting. Meanwhile, it needs to support millions of complex queries and updates per second. In this paper, we make the curious observation that the entropy of IP forwarding tables is very small and, what is more, seems to increase at a lower pace than the size of the network. This suggests that a sophisticated compression scheme may effectively and persistently reduce the memory footprint of IP forwarding tables, shielding operators from scalability matters at least temporarily. Our main contribution is such a compression scheme which, for the first time, admits both the required information-theoretical size bounds and attains fast lookups, thanks to aggressive level compression. Although we find the underlying optimization problem NP-complete, we can still give a lightweight heuristic algorithm with firm approximation guarantees. This allows us to squeeze real IP forwarding tables, comprising almost 500, 000 prefixes, to just about 140-200 KBytes of memory within a factor of 2-3 of the entropy bound, so that forwarding decisions take only 8-10 memory accesses on average and updates are supported efficiently. Our compression scheme may be of more general interest, as it is applicable to essentially any prefix tree.

Network-wide local unambiguous failure localization (NL-UFL) [1] has been demonstrated as an interesting scenario of monitoring trails (m-trails). It attempts to enable every node to autonomously localize any failure event in the network in a distributed and all-optical manner by inspecting a set of m-trails traversing through the node. This paper investigates the m-trail allocation problem under the NL-UFL scenario by taking each link and node failure event into consideration. Bound analysis is performed using combinatorial group testing (CGT) theory and this is followed by the introduction of a novel heuristic on general topologies. Extensive simulation is conducted to examine the proposed heuristic in terms of the required cover length and the number of m-trails to achieve NL-UFL.

In this paper we close the gap between end-to-end diversity coding and intra-session network coding for unicast connections resilient against single link failures. In particular, we show that coding operations are sufficient to perform at the source and receiver if the user data can be split into at most two parts over the filed GF(2). Our proof is purely combinatorial and based on standard graph and network flow techniques. It is a linear time construction that defines the route of subflows A, B and A ⊕ B between the source and destination nodes. The proposed resilient flow decomposition method generalizes the 1+1 protection and the end-to-end diversity coding approaches while keeping both of their benefits. It provides a simple yet resource efficient protection method feasible in 2-connected backbone topologies. Since the core switches do not need to be modified, this result can bring benefits to current transport networks.

Failure dependent protection (FDP) is known to achieve optimal capacity efficiency among all types of protection, at the expense of longer recovery time and more complicated signaling overhead. This particularly hinders the usage of FDP in all-optical mesh networks. As a remedy, this paper investigates a new restoration framework that enables all-optical fault management and device configuration via state-of-the-art failure localization techniques, such as the FDP restoration process. It can be implemented without relying on any control plane signaling. With the proposed restoration framework, a novel spare capacity allocation problem is defined and is further analyzed on circulant topologies for any single link failure, aiming to gain a solid understanding of the problem. By allowing reuse of monitoring resources for restoration capacity, we are particularly interested in the monitoring resource hidden property, where less or even no monitoring resources are consumed as more working traffic is in place. To deal with general topologies, we introduce a novel heuristic approach to the proposed spare capacity allocation problem, which comprises a generic FDP survivable routing scheme followed by a novel monitoring resource allocation method. Extensive simulation is conducted to examine the proposed scheme and verify the proposed restoration framework.

This paper investigates monitoring burst (m-burst), an interesting framework of all-optical failure localization technique reported in [2], in all-optical networks with multi-link SRLGs up to d links. We introduce a novel m-trail allocation method for achieving local unambiguous failure localization (L-UFL), where a single monitoring node (MN) can localize any SRLG failure by inspecting the optical bursts traversing through it. In specific, the proposed m-trail method ensures that (d + 1) link-disjoint m-trails originating from the MN will traverse each link, such that any healthy link is traversed by at least one uninterrupted m-trail during an SRLG failure. As a proof of concept, we formulate two integer linear programs (ILPs) and implement the method for SRLGs with d up to 3. Numerical results show that the scheme takes very short fault localization latency, while achieving the best performance.

Conventional all-optical restoration strategies like p-cycle achieve very fast restoration with high spare capacity consumption. In contrast, failure dependent protection (FDP) can achieve near-optimal capacity efficiency at the cost of high signaling/control complexity (so as for long restoration time). In this paper, we investigate a previously reported all-optical restoration framework that aims to yield a restoration speed similar to p-cycle while achieving near optimal resource consumption as FDP. In particular, we propose a simple yet efficient heuristic for joint allocation of monitoring trails and protection lightpaths, which serves as the key to enable the all-optical restoration. The resultant all-optical restoration framework is further examined by extensive simulations regarding the network resource consumption, number of transmitters, monitoring requirement, and running time.

Information-centric networking (ICN)1is a new communication paradigm, which has been increasingly attracting attention in the wider research community. Its focus on information provides an alternative to the endpoint-centric model of today's Internet. While architectural foundations for ICN have been laid out in many ongoing efforts, solutions to forwarding information in such new networking environment still remain a challenge. Our criteria for a solution to this challenge are efficiency in terms of achievable link speed and scalability in terms of supported sizes of the network, while supporting multicast as a native operation. Our solution in this paper provides scalability through an extensible addressing format while keeping the forwarding operation efficient in terms of required state as well as forwarding performance.

The paper investigates a novel monitoring trail (m-trail) scenario that can enable any shared protection scheme for achieving all-optical and ultra-fast failure restoration. Given a set of working (W-LPs) and protection (P-LPs) lightpaths, we firstly define the neighborhood of a node, which is a set of links whose failure states should be known to the node in restoration of the corresponding W-LPs. A set of m-trails is routed such that each node can localize any failure in its neighborhood according to the ON-OFF status of the traversing m-trails. Bound analysis is performed on the minimum bandwidth required for the m-trails. Extensive simulation is conducted to verify the proposed scheme.

IP-level failure protection based on the IP Fast ReRoute/Loop-Free Alternates (LFA) specification has become industrial requirement recently. The success of LFA lies in its inherent simplicity, but this comes at the expense of letting certain failure scenarios go unprotected. Realizing full failure coverage with LFA so far has only been possible through completely reengineering the network around LFA-compliant design patterns. In this paper, we show that attaining high LFA coverage is possible without any alteration to the installed IP infrastructure, by introducing a carefully designed virtual overlay on top of the physical network that provides LFAs to otherwise unprotected routers. We study the problem of how to provision the overlay to maximize LFA coverage, we find that this problem is NPcomplete, and we give Integer Linear Programs to solve it. We also propose novel methods to work-around the limitations of current LFA implementations concerning Shared Risk Link Groups (SRLGs), which might be of independent interest. Our numerical evaluations suggest that router virtualization is an efficient tool for improving LFA-based resilience in real topologies.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community, by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state-of-the-art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we re-design the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode a FIB comprising more than 440K prefixes to just about 100--400 KBytes of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

In this comment, we present some remarks on the availability evaluation of overlap dedicated segment protection (o-DSP) method in Tornatore et al., 2010, ãAvailability Formulations for Segment Protection" . We show how to correctly apply the pivotal decomposition availability-evaluation method in directed graphs (which was claimed to inapplicable in ), such that it gives the same (exact) connection availability value as the generating function method proposed in the original paper.

The paper considers the problem of single-link failure localization in all-optical mesh networks. Our study follows a generic monitoring approach using supervisory lightpaths (S-LPs), in which a set of bi-directional monitoring trails (bm-trails) are defined and closely monitored, such that the network controller can achieve unambiguous failure localization (UFL) for any single link by collecting the flooded alarms from the affected bm-trails. With a target of minimizing the number of bm-trails (or the length of alarm codes) required for single-link UFL, the paper provides optimal (or essentially optimal) solutions to the bm-trail allocation problem on a number of well known topologies. First we demonstrate that the theoretical lower bound of [log2(|E|+1)] bm-trails can be achieved in any 2 · [{ log2{(|E|+1)} }] connected graph, where |E| is the number of links. Next, we prove an essentially optimal solution for 1-by-N grid topologies (also known as chocolate bar graphs), where [{0.42+ log2{(|E|+2)}}] bm-trails can be achieved. Based on the solution for chocolate bars, we further investigate bm-trail solutions to general 2-dimensional (2D) grid topologies, and the developed solution requires no more than 3+[ log2(|E|+1)] bm-trails for UFL. Such an optimal (or essentially optimal) logarithmic behavior, although has been well observed in general topologies in our previous studies , is formalized for the first time in this paper via a suite of polynomial-time deterministic constructions that consume less than a few seconds of running time in topologies of thousands of nodes.

Large-scale information distribution has been increasingly attracting attention, be it through uptake in new services or through recent research efforts in fields like information-centric networking. The core issue to be addressed is the more efficient distribution of information to a large set of receivers. Avoiding state in the forwarding elements is crucial for any scheme to be successful. This paper addresses this challenge by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept which represent the trees flatly as sets, we build our filter by enclosing limited information about the structure of the tree, namely its stage decomposition, which helps to get rid of typical Bloom filter illnesses as infinite loops and false positive forwarding. Our analytical and simulation results show that by using this information we obtain more succinct tree representation while still maintaining forwarding efficiency.

About what is the smallest size we can compress an IP Forwarding Information Base (FIB) down to, while still guaranteeing fast lookup? Is there some notion of FIB entropy that could serve as a compressibility metric? As an initial step in answering these questions, we present a FIB data structure, called Multibit Burrows-Wheeler transform (MBW), that is fundamentally pointerless, can be built in linear time, guarantees theoretically optimal longest prefix match, and compresses to higher-order entropy. Measurements on a Linux prototype provide a first glimpse of the applicability of MBW.

Survivable routing serves as a key role in connection-oriented communication networks for achieving desired service availability for each connection. This is particularly critical for the success of all-optical mesh networks where each lightpath carries a huge amount of data. Currently, 1+1 dedicated path protection appears to be the most widely deployed network resilience mechanism because it offers instantaneous recovery from network failures. However, 1+1 protection consumes almost twice as much capacity as required, which imposes a stringent constraint on network resource utilization. In addition, finding an SRLG-disjoint path is essential for 1+1 protection, which is nonetheless subject to non-trivial computation complexity and may fail in some SRLG scenarios. To address these problems, we introduce a novel framework of 1+1 protection, called Generalized Dedicated Protection (GDP), for achieving instantaneous recovery from any SRLG failure event. It is demonstrated, that finding a non-bifurcated optimal solution for GDP is NP-complete. Thus, the paper presents a novel scheme applying Generalized Dedicated Protection and Network Coding (GDP-NC) to ensure both optimal resource utilization among dedicated protection approaches and instantaneous recovery for single unicast flows, which can be split into multiple parts in all-optical networks. We demonstrate that the proposed GDP-NC survivable routing problem is polynomial-time solvable, owing to the ability to bifurcate flows. This flexibility comes at the expense of additional hardware for linear combination operations for the optical flows.

Communication networks have to provide a high level of resilience in order to ensure sufficient Quality of Service for mission-critical services. Currently, dedicated 1+1 path protection is implemented in backbone networks to provide the necessary resilience. On the other hand, there are several possible realization strategies for 1+1 path protection functionality (1PPF), utilizing both diversity- and network coding. In this paper we consider the cost aspects of the different realization strategies. We evaluate the cost of providing 1PPF both analytically and empirically in realistic network topologies. Our results show that both diversity and network coding can provide 1PPF with reduced cost compared to traditional 1+1 path protection, even in case of short paths and strict coding restrictions. Specifically, the network coding scheme could be used as a cost-efficient and potentially all-optical realization of 1PPF.

Monitoring trail (m-trail) has been proposed as an effective approach for link failure localization in all-optical wavelength division multiplexing (WDM) mesh networks. Previous studies in failure localization rely on alarm dissemination via control plane signaling such that the network controller can collect the flooded alarms to form an alarm code for failure identification. Such cross-layer signaling effort obviously leads to additional control complexity. This paper investigates a novel m-trail failure localization scenario, called network-wide local unambiguous failure localization (NWL-UFL), where each node can perform UFL based on locally available on–off state of traversing m-trails, such that alarm dissemination in the control plane can be completely avoided. The paper first defines and formulates the m-trail allocation problem under NWL-UFL and conducts a series of bound analysis on the cover length required for localizing any single-link failure. This is the first study on monitoring trail allocation problem that aims to gain understanding on the consumed cover length via analytical approaches due to the special feature of the NWL-UFL scenario. A novel heuristic algorithm based on random spanning tree assignment (RSTA) and greedy link swapping (GLS) is developed for solving the formulated problem. Extensive simulation on thousands of randomly generated network topologies is conducted to verify the proposed scheme by comparing it to a naive counterpart and with the derived lower bounds. We also demonstrate the impact of topology diversity on the performance of the proposed scheme as well as its scalability regarding network sizes.

Monitoring trail (m-trail) provides an efficient way to achieve fast and unambiguous failure localization (UFL) in all-optical networks. To remove electronic alarm dissemination, the extended m-trail concept allows trail status checking at each on-trail node. Each monitoring node can localize any failure using its locally available on-off status of the traversing m-trails. In this paper, we introduce a novel algorithm to unambiguously localize any SRLG failure locally at any MN. The proposed algorithm is characterized by a signalling-free alarm collection mechanism which can completely be realized in the optical domain. We will show that in the course of minimizing the number of m-trails, the consumed monitoring resources in terms of cover length can also be effectively reduced. Simulation is conducted to verify the proposed algorithm with respect to the number of m-trails, resource consumption, and running time.

IP Fast ReRoute (IPFRR) is the IETF standard for providing fast failure protection in IP and MPLS/LDP networks and Loop Free Alternates (LFA) is a basic specification for implementing it. Even though LFA is simple and unobtrusive, it has a significant drawback: it does not guarantee protection for all possible failure cases. Consequently, many IPFRR proposals have appeared lately, promising full failure coverage at the price of added complexity and non-trivial modifications to IP hardware and software. Meanwhile, LFA remains the only commercially available, and therefore, the only deployable IPFRR solution. Deployment, however, crucially depends on the extent to which LFA can protect failures in operational networks. In this paper, therefore, we revisit LFA in order to give theoretical insights and practical hints to LFA failure coverage analysis. First, we identify the topological properties a network must possess to profit from good failure coverage. Then, we study how coverage varies as new links are added to a network, we show how to do this optimally and, through extensive simulations, we arrive to the conclusion that cleverly adding just a couple of new links can improve the quality of LFA protection drastically.

Being reported as the most general monitoring structure for out-of-band failure localization approach, the monitoring trail (m-trail) framework has been witnessed with great efficiency and promises to serve in the future Internet backbone with all-optical mesh wavelength division multiplex (WDM) networks. Motivated by its potential and significance, this paper investigates failure localization in all-optical mesh networks using m-trails. By considering shared risk link groups (SRLGs) with up to all adjacent links of any node in the network, a novel algorithm of m-trail allocation for achieving unambiguous failure localization (UFL) of any single SRLG failure is developed. The proposed algorithm aims to minimize the number of required m-trails and can achieve superb performance with respect to the computation efficiency. We claim that among all the previously reported counterparts, this paper has considered one of the most applicable scenarios to the design of network backbone, and the proposed method can be easily extended to the case of node failure localization. Extensive simulation is conducted to verify the proposed algorithm in comparison to its existing counterparts.

Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. Monitoring trail (m-trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localization (UFL) of any single link failure while effectively reducing the amount of alarm signals flooding the networks. However, it is critical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the total bandwidth consumed, which ubiquitously determines the length of the alarm code and bandwidth overhead for the m-trail deployment, respectively. In this paper, the m-trail design problem is investigated. To gain a deeper understanding of the problem, we first conduct a bound analysis on the minimum length of alarm code of each link required for UFL on the most sparse (i.e., ring) and dense (i.e., fully meshed) topologies. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm is verified by comparison to an integer linear program (ILP) approach, and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consumption while achieving significant reduction in computation time. To investigate the impact of topology diversity, extensive simulation is conducted on thousands of random network topologies with systematically increased network density.

We study SRLG (Shared Risk Link Group) failure monitoring and localization in all-optical WDM (Wavelength Division Multiplexing) networks. All links in each SRLG are logically grouped as a whole, and they fail at the same time when the SRLG failure event occurs. To achieve fast SRLG failure localization, monitoring is carried out at the optical layer using the recently proposed monitoring trail (m-trail) structure. By formulating an ILP (Integer Linear Program), we optimally solve the m-trail allocation problem to achieve unambiguous SRLG failure localization with the minimum monitoring cost. We claim that our work provides the first study in optimally allocating free-routed m-trails for achieving fast and unambiguous SRLG failure localization, with flexible tradeoff between the monitor cost and the bandwidth cost (i.e., supervisory wavelength-links).

Achieving fast, precise, and scalable fault localization has long been a highly desired feature in all-optical mesh networks. Monitoring tree (m-tree) is an interesting method that has been introduced as the most general monitoring structure for achieving unambiguous failure localization (UFL). Ideally, with J m-trees one can monitor up to 2J-1 links when a single failure has to be located. Such a logarithmic behavior has also been observed in numerous case studies of real life network topologies. It is expected that the m-tree framework will lead to a highly scalable link failure monitoring mechanism for not only all-optical mesh networks, but any possible future information system with mesh topologies, such as all-optical mesh networks, touch panels, quantum computing, and VLSI. It is an important task to investigate the extent such an optimal logarithmic behavior may hold, in particular in practically relevant network topologies. As an endeavor toward this goal, the paper investigates the problem by identifying essentially tight logarithmic bounds for two dimensional lattice networks. Experiments are conducted to show the feasibility and performance of the proposed constructions.

To satisfy the stringent requirement of capacity enhancement in wireless networks, cooperative relaying is envisioned as one of the most effective solutions. In this paper, we study the capacity enhancement problem by way of Relay Stations (RSs) placement to achieve an efficient and scalable design in broadband wireless access networks. To fully exploit the performance benefits of cooperative relaying, we develop an optimization framework to maximize the capacity as well as to meet the minimal traffic demand by each Subscriber Station (SS). In specific, the problem of joint RS placement and bandwidth allocation is formulated into a mixed-integer nonlinear program. We reformulate it into an integer linear program which is solvable by CPLEX. To avoid exponential computation time, a heuristic algorithm is proposed to efficiently solve the formulated problem. Numerical analysis is conducted through case studies to demonstrate the performance gain of cooperative relaying and the comparison between the proposed heuristic algorithm against the optimal solutions.

Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. M-trail (monitoring trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localization (UFL) of any single link failure while effectively reducing the amount of alarm signals flooded in the networks. However, it is critical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the totally consumed bandwidth, which ubiquitously determines the length of alarm code and bandwidth overhead for the M-trail deployment, respectively. In this paper, the m-trail design problem is investigated. To gain deeper understanding of the problem, we firstly conduct a bound analysis on the minimum length of alarm code required for UFL. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm prototype can be found in. The algorithm is verified by comparing with an integer linear program (ILP), and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consumption while achieving significant reduction in computation time. To investigate the impact of topology diversity, extensive simulation is conducted on thousands of random network topologies with systematically increased network connectivity. Lastly, we provide abundant discussions and interesting conclusive remarks that position our discoveries.

We introduce Cooperative Fast Protection (CFP) as a novel protection scheme in WDM networks. CFP achieves capacity-efficient fast protection with the features of node-autonomy and failure-independency. It differs from p-cycle by reusing the released working capacity of the disrupted lightpaths (i.e. stubs) in a cooperative manner. This is achieved by allowing all the failure-aware nodes to switch the traffic, such that the disrupted lightpaths can be protected even if the end nodes of the failed link are not on the protecting cycles. CFP also differs from FIPP p-cycle by not requiring the source node of the disrupted lightpath on the protecting cycle. By jointly optimizing both working and spare capacity placement, we formulate an ILP for CFP design. Numerical results show that CFP significantly outperforms p-cycle by achieving faster protection with much higher capacity efficiency.

In this paper, a novel approximate link-state dissemination framework, called TROP, is proposed for shared backup path protection (SBPP) in multiprotocol label switching (MPLS) networks. While performing dynamic explicit survivable routing in a distributed environment, link-state dissemination may cause a nontrivial signaling overhead in the process of exploring spare resource sharing among individual backup label switched paths (LSPs). Several previously reported studies have tackled this problem by initiating a compromise between the amount of dissemination and the achievable extent of resource sharing. The paper first summarizes the previously reported schemes into a compact and general link-state dissemination framework by way of singular value decomposition (SVD). To improve the accuracy of the matrix reconstruction and to eliminate the overestimation of the sharable spare capacity along each link, a novel SVD approach based on the min-plus algebra (also called tropical semirings) is introduced. Simulation results show that the proposed schemes can achieve a lower blocking probability than that by all the other counterpart schemes while taking the same complexity of link-state dissemination. This great advantage is gained at the expense of a longer computation time for solving a linear program (LP) in each dissemination cycle at the core nodes. We also consider the stale link-state phenomena that may cause imprecision in the routing information at the ingress nodes due to the delay in the periodic/event-driven link-state update message advertisement.

Spare capacity allocation serves as one of the most critical tasks in dynamic GMPLS networks to meet the stringent network availability constraint stipulated in the SLA of each connection. In this paper, an availability-aware spare capacity reconfiguration scheme based on shared backup path protection (SBPP) is proposed, aiming to guarantee the E2E availability of each LSP. We first provide an E2E availability model for a SBPP connection that is composed of a working and a SRG-disjoint shared backup LSP pair in the presence of all possible single, and dual simultaneous failures. Partial restoration is identified to further improve the capacity efficiency, and achieve finer service differentiation. For this purpose, restoration attempt is defined as a parameter for each connection that can be manipulated at the source node when the spare capacity of each link is scheduled. Based on the developed model, a linear program (LP) is formulated to perform inter-arrival spare capacity reconfiguration along each pre-determined shared backup LSP to meet the availability constraint of each connection. Simulation is conducted to verify the derived formulation, and to demonstrate the benefits gained in terms of the spare capacity saving ratio, where the conventional SBPP scheme that achieves 100% restorability for any single failure is taken as a benchmark. We will show that the simulation results validate the proposed E2E availability model, where a significant reduction on the required redundancy can be achieved in the effort of meeting a specific availability constraint for each SBPP connection.

Shared segment protection (SSP), compared with shared path protection (SPP), and shared link protection (SLP), provides an optimal protection configuration due to the ability of maximizing spare capacity sharing, and reducing the restoration time in cases of a single link failure. This paper provides a thorough study on SSP under the GMPLS-based recovery framework, where an effective survivable routing algorithm for SSP is proposed. The tradeoff between the price (i.e., cost representing the amount of resources, and the blocking probability), and the restoration time is extensively studied by simulations on three networks with highly dynamic traffic. We demonstrate that the proposed survivable routing algorithm can be a powerful solution for meeting stringent delay upper bounds for achieving high restorability of transport services. This can significantly improve the network reliability, and enable more advanced, mission critical services in the networks. The comparison among the three protection types further verifies that the proposed scheme can yield significant advantages over shared path protection, and shared link protection.

As for today, radio spectrum resource is rigidly partitioned for dedicated purposes. The exclusive license of fixed size spectrum blocks separated by guard bands easily solves the interference problems; however, the rigid allocation of spectrum is clearly inadequate for providing optimal spectrum efficiency for spatially and temporarily varying loads. Dynamic spectrum allocation (DSA) is a new and promising alternative where the assigned spectrum blocks may vary in time and space, too. In this paper we describe a spatio-temporal DSA model that splits the complex problem into temporal and spatial dynamic spectrum allocation. In our architecture the spectrum is allocated by regional spectrum brokers (RSB) that also coordinate spectrum access between regions. The problem of interference between different regions and providers is handled by a flexible description using the proposed geographical and radio technology coupling parameters. We also show how the optimal allocation can be found by giving the ILP solution to the problem. To evaluate the efficiency of the proposed DSA method, different gains are defined from the regulator's point of view. The performance evaluation is carried out using computer simulations, and the results are compared with the cases where either there is no interference allowed at all, or interference does not occur between regions.

This paper introduces a new dynamic availability-aware survivable routing scheme under the framework of generalized multi-protocol label switching (GMPLS)-based recovery, which aims to achieve the best generality for the network operation in meeting the end-to-end (E2E) availability requirement of each connection. The paper first defines the partial restorability, justifies the feasibility of equipping a connection with partial restorability under the GMPLS control plane, and highlights the approach of evaluating the E2E availability for a pair of working and partially restorative SRG (shared risk group)-disjoint shared backup label switched paths (LSPs). A compact matrix expression is developed for modeling the minimum spare capacity along each link and the cost function for solving both of the paths. Based on the developed cost function, a novel integer linear program (ILP) is formulated to dynamically determine the working and backup LSPs of the corresponding connection request with the least amount of total capacity while the E2E availability requirement of the connection is met. We demonstrate that the model is general to the traffic uniformity, connection indivisibility, and working bandwidth restorability compared with the previous studies. Simulation is conducted to verify the proposed ILP model by making a comparison with a number of legacy schemes that achieve 100% restorability in facing a specific number of simultaneous failures, such as shared path protection (SPP), 1+1 protection, and dual-failure protection. In the case study, we have seen merits in the proposed algorithm by significantly reducing the required redundancy in the effort of achieving the given availability constraint for each connection request.

A new concept Quality of Resilience (QoR) presented in this paper is based on the distinction in the reliability-related Quality of Service (QoS) parameters of the short-term quality factors and the long-term quality factors. The former parameters are called availability parameters and the latter are called QoR parameters. In one hand by dividing the service duration time into intervals, the service is considered available during a time interval, if the Service Level Agreement (SLA) between the user and the network operator is satisfied. In the other hand the long-term characteristics of the service are derived from the service downtime distribution. With the downtime histograms the asymptotic characteristics of the service can be represented both at the transport and service layers. Since the resilience mechanism implemented into the network match the transport layer downtime histograms, this new characterization of the QoS helps to measure the impacts of a given recovery scheme on the next generation services.

It is observed that the singular value decomposition (SVD) transformation based on min-plus algebra (or called tropical semi-rings) leads to a very good characteristic in zero underestimating the reconstructed matrix. This paper introduces a novel distributed control framework for shared protection in optical networks with reduced routing information based on the tropical semi-rings technique, called sharing with reduced information with tropical semi-rings (SRI-TROP). The design of the proposed framework aims to initiate a compromise between the amount of link-state dissemination and the performance impairment due to the incompleteness of routing information, such that the precision in the link-state matrix reconstruction can efficiently map to the reduction in blocking probability. Based on the framework, a series of novel schemes are proposed, which are verified and compared with the reported counterparts in a simulation. The simulation results show that the performance in terms of the precision in the reconstructed link-state and the resultant blocking probability can be significantly improved.

Shared segment protection (SSP), compared to shared path protection (SPP) or shared link protection (SLP), provides an optimal protection configuration, since SSP can increase the number of connections sharing the same protection segments and can reduce the restoration time in case of single link failure. This paper provides a thorough study on SSP under the GMPLS-based recovery framework, where an effective survivable routing algorithm for SSP is proposed, called shared segment protection (SSP) algorithm. The main advantage of the SSP algorithm is to reduce the high computation complexity in solving the ILP formulation first introduced in P-H. Ho et al., (2004). With an efficient iterative approach the design space is significantly reduced by excluding all the links that result intolerably long routes. The tradeoff between the price (i.e., cost representing the amount of resources, and the blocking probability) and the restoration time is extensively studied by simulations on three networks with highly dynamic traffic. It is demonstrated that the SSP algorithm can be a powerful solution in the GMPLS-based recovery with a stringent delay upper bound for achieving high availability and restorability of the transport services. The comparison among the three protection types further verifies that SSP can yield significant advantages over SPP and SLP.

The paper proposes a novel distributed control architecture for shared protection with reduced complete routing information, which aims to initiate a graceful compromise between the amount of link-state dissemination and the performance impairment due to the incompleteness of routing information. We first give explicit and comprehensive descriptions on a number of reported routing information dissemination scenarios for shared protection. A novel framework of link-state dissemination for facilitating shared protection, called reduced complete routing scenario, is introduced, in which the singular value decomposition (SVD) transformation is adopted to deal with the information reduction. We show, through simulation, that the proposed scheme can achieve a higher throughput and a better estimation in reconstruction of the spare provision matrix than the other schemes taking the same complexity of link-state dissemination.

This paper investigates the problem of optimal diverse routing for shared path-based protection in the complete routing information scenario on mesh optical networks, where a novel Integer Linear Programming (ILP) formulation is introduced such that the least-cost link-disjoint working and protection path-pair can be derived in a single step. The proposed ILP formulation is characterized by the facts that it is solvable with the commercially available Linear Programming (LP) solvers and that it can deal with the dependency between working and spare capacity in the network, which is a step ahead of the most state-of-the-art techniques in the design of diverse routing algorithms for shared protection. To verify the proposed ILP, an experiment is conducted to compare it with four reported schemes for end-to-end shared protection on two network topologies, namely APFPBC, MLR, ITSA, and ILP-2S, where blocking probability is taken as the performance metric with connection requests being dynamically launched into the networks. The simulation results show that the ILP formulation yields the best performance while the ILP-2S scheme investigating less network states yields the worst. We also use the results by the proposed ILP to evaluate the four heuristic-based schemes adopted in the simulation in terms of two performance indexes – the percentage of optimality (denoted as %opti) and the offset of optimality (denoted as Q).

This paper focuses on the problem of dynamic survivable routing for segment shared protection (SSP) in mesh communication networks provisioning bandwidth guaranteed tunnels. With SSP, a connection is settled by concatenating a series of protection domains, each of which contains a working and protection segment pair behaving as a self-healing unit for performing local restoration whenever the working segment is subject to any unexpected interruption. We first discuss the advantages of using SSP-the ability to shorten the restoration time as well as achieve a higher throughput by saving spare capacity required for 100% restorability; then the survivable routing problem is formulated into an Integer Linear Programming (ILP), where the switching/merging node pair of each protection domain along with the corresponding least-cost working and protection segment pair can be jointly determined for a dynamically arrived connection request. A novel approach of arc-reversal transformation is devised to deal with the situation that the working segments of two neighbor protection domains may overlap with each other by more than a single node. Due to a very high computation complexity induced in solving the ILP, a novel heuristic algorithm is proposed, named Cascaded Diverse Routing (CDR), to allocate protection domains for a connection request by performing diverse routing across a set of predefined candidate switching/merging node pairs. Experiments are conducted on five two-connected network topologies to verify the ILP and the CDR algorithm. We first determine the best diameter of protection domains for the CDR scheme in each network topology. Using the results of best diameters, CDR is compared with two reported schemes, namely PROMISE and OPDA. We demonstrate in the simulation results that the path-shared protection schemes are outperformed by the SSP schemes in terms of blocking probability under all possible arrangements in the experiment and that CDR yields better performance than PROMISE and OPDA due to the extra efforts in manipulating the location of working segments at the expense of longer computation time.

This paper proposes a suite of approaches to solve the survivable routing problem with shared protection. We first define in mathematics the maximum extent of resource sharing for a protection path given the corresponding working path according to the current network link-state. Then the problem of solving the least-cost working & protection path-pair (in terms of the sum of the cost) is formulated into an Integer Linear Programming process. Due to the dependency of the protection path on its working path, however, the formulation is not scalable with the network size, and takes an extra effort to solve. Therefore, we introduce two heuristic algorithms, called Iterative Two-Step-Approach (ITSA) & Maximum Likelihood Relaxation (MLR), which aim to explore the approximating optimal solutions with less computation time. We evaluate the performance of the proposed schemes, and make a comparison with some reported counterparts. The simulation results show that the ITSA scheme, with a properly defined tolerance to optimality, can achieve the best performance at the expense of more computation time. On the other hand, MLR delivers a compromise between computation efficiency & performance.

This paper provides a suite of approaches to solving the survivable routing problem with shared protection. The problem diverse solving the least-cost working and protection path-pair (in terms of the sum of the cost) is formulated into integer linear programming. We also introduce two heuristic algorithms, called iterative two-step-approach (ITSA) and maximum likelihood relaxation (MLR), which aim to finding the approximating optimal solution within a limited amount of computation time. We examine the performance of the proposed schemes and make a comparison with some reported counterparts. It is observed that the ITSA scheme with a properly defined tolerance to the optimality can achieve the best performance at the expense of much longer computation time. MLR can provide an ultra-fast path selection process, which behaves as a good tradeoff between computation efficiency and performance.