Cloud computing depends critically on large data centers connected by a high-speed optical network. A fault-tolerant communication scheme to handle requests for communication in such a system is essential. In this paper we have proposed an optimal approach to the problem of developing a path-protection scheme to handle communication requests in data center (DC) networks. We have formulated our problem as an Integer Linear Program (ILP). We have studied our approach using simulations, varying parameters, such as the number of DCs, and the number of disasters. Our simulations show that considering additional disasters do not add significantly to the cost of the solution, which means significant resource savings while supporting users' demands.

This paper addresses the regenerator placement problem (RPP) when designing resilient, impairment aware WDM optical networks. For the RPP, we have proposed two solutions; an optimal solution for small networks (less than 10 nodes) and a near-optimal heuristic solution for practical-sized networks. The optimal solution uses an Integer Linear Program which can be implemented by any solver for mathematical programming. The heuristic makes use of an approach, proposed in a recent paper, that requires a formulation involving an exponential number of constraints. It was shown in that paper that this formulation can be solved very efficiently using a branch-and-cut algorithm and that the approach may be used to design resilient networks which guarantees restoration. In this paper we have shown that this branch-and-cut approach may be used as a part of a highly efficient heuristic which gave optimal results in an overwhelming number of cases that we tested.

The distance an optical signal can travel before the signal quality degrades to a level that necessitates regeneration is called the optical reach. To establish a lightpath of length greater than the optical reach, it is necessary to regenerate optical signals at one or more nodes. In this paper we have proposed routing and wavelength assignment algorithms for translucent networks. For each request for a lightpath, the objective is to find a route from the source to the destination of the request, so that a translucent lightpath may be established that requires the fewest possible stages of regeneration. We have proposed an Integer Linear Programming (ILP) formulation that gives the optimum solutions for small networks. For larger networks, we have proposed an efficient heuristic. We have shown that the heuristic produces close-to-optimal solutions in a fraction of the time needed for the optimal solutions.

The standard approach of using multi-commodity network flow (MCNF) techniques for designing optimal WDM networks often lead to computationally difficult Mixed Integer Linear Programs (MILP) which work only on small networks. Modern Operations Research (OR) techniques may be helpful when developing efficient algorithms for large WDM networks. This paper explores the Branch, Price and Cut techniques for designing optimal WDM optical networks. We have studied a well-known problem in WDM networks - non-bifurcated traffic grooming over a specified logical topology. The standard way to solve this problem is to view it as a MCNF problem and solve the resulting MILP using a commercial MILP solver package, such as the ILOG CPLEX to give us an optimum traffic grooming strategy. The number of binary variables and the number of constraints of the MCNF problems increases with the network size and tools such as the CPLEX solver takes increasingly longer time. We have shown how we can take advantage of the structural properties of this problem and solve it efficiently using modern Operations Research techniques.

In hierarchical sensor networks, higher powered relay nodes can be deployed to act as cluster heads. The lifetime of such a network is primarily determined by the lifetime of the relay nodes. Recently, it has been shown that the use of a Mobile Data Collector (MDC), which moves through the sensor network to collect data, can improve the performance of the network in a number of ways. We propose a model for hierarchical networks using a MDC, where the MDC travels along a pre-determined trajectory at a known speed, and collects data from each relay node. In this model, the relay nodes need to buffer their data until they can be uploaded to the MDC. To reduce the buffer size, as well as the delay for the data communication, it is desirable to minimize the length of the trajectory. In our model the MDC "visits" a relay node, to collect data, at any point within the permitted transmission distance of the relay node. There is a trade-off in this approach, as a large permitted transmission distance means that the relay node will expend higher energy, and hence, have a reduced lifetime. In this paper, we present two formulations for computing the minimal trajectory of the MDC. Our approaches allow us to control the transmission distances of the relay nodes and hence, achieve the lifetime objectives. Minimizing the length of the trajectory reduces the buffer size requirements at each node as well as the delay between successive visits.

The optical reach (the distance an optical signal can travel before the signal quality degrades to a level that necessitates regeneration) ranges from 500 to 2000 miles. To establish a lightpath of length greater than the optical reach, it is necessary to regenerate optical signals. In a translucent optical network, there are regeneration points, where the signal undergoes Optical-Electronic-Optical (O-E-O) conversion. In this paper we have proposed routing algorithms for translucent networks in a dynamic lightpath allocation environment in which requests for communication arrive continuously. In response to each request for communication, the objective is to establish, if possible, a path, from the source to the destination of the request for communication, so that a lightpath may be established, using the path that requires the fewest stages of regeneration. In practical transparent networks, a lightpath must satisfy the wavelength continuity constraint. However, in a translucent network, this constraint can be relaxed at the regeneration points. We have proposed an Integer Linear Program, to give the optimum results for small networks, as well as an efficient heuristic for this problem that works for larger networks. We have evaluated the heuristic through extensive simulations to establish that the heuristic produces close-to-optimal solutions in a fraction of the time needed for the optimal solutions. Our extensive evaluations demonstrate the relative impact of a set of network resources, such as (i) the number of regenerators, (ii) the optical reach of the regenerators and (iii) the number of wavelengths, on the network performance, measured in terms of the call blocking probability. To the best of our knowledge this is the first study that undertakes such an evaluation for translucent networks.

Two-tiered sensor networks, where higher-powered relay nodes are used as cluster heads, have been proposed recently for designing sensor networks. Assigning sensor nodes to clusters, in an energy efficient way, is known to improve the lifetime of such networks. In this paper we have proposed an efficient distributed algorithm for assigning sensor nodes to clusters in two-tiered networks, using both single-hop and multi- hop routing schemes. Our distributed clustering strategy allocates sensor nodes to clusters, based on limited local information only. However, the solutions generated are shown to be comparable to optimal solutions obtained using an ILP formulation. We have also compared our approach to a number of existing heuristics recently proposed in the literature and have shown, through simulations, that our approach consistently outperforms current heuristics. In summary, the quality of the solutions obtained using our approach is comparable to those obtained using an ILP formulation, but the solutions can be generated very quickly, making it suitable for practical-sized networks with hundreds of sensor nodes.

Abstract In hierarchical sensor networks using relay nodes, sensor nodes are arranged in clusters and higher poweredrelay nodescan be used as cluster heads. The lifetime of such a network is determined primarily by the lifetime of the relay nodes. In this paper, we propose two new integer linear programs (ILPs) formulations for optimal data gathering, which maximize the lifetime of the upper tier relay node network. Unlike most previous approaches considered in the literature, our formulations can generate optimal solutions under thenon‐flow‐splitting model. Experimental results demonstrate that our approach can significantly extend network lifetime, compared to traditional routing schemes, for the non‐flow‐splitting model. The lifetime can be further enhanced by periodic updates of the routing strategy based on the residual energy at each relay node. The proposed rescheduling scheme can be used to handle single or multiple relay node failures. We have also presented a very simple and straightforward algorithm for the placement of relay nodes. The placement algorithm guarantees that all the sensor nodes can communicate with at least one relay node and that the relay node network is at least 2‐connected. This means that failure of a single relay node will not disconnect the network, and data may be routed around the failed node. The worst case performance of the placement algorithm is bounded by a constant with respect to any optimum placement algorithm. Copyright © 2008 John Wiley & Sons, Ltd.

Component failure in a WDM network is a serious problem that has attracted considerable attention in recent times. In a standard protection (or restoration) scheme the objective is to preserve the logical topology by switching over to back-up paths (or by setting up new lightpaths) after a fault occurs. In this paper we have proposed a new scheme where we handle a fault simply by modifying the traffic routing scheme to avoid the fault. We show that it is possible to guarantee that a significantly high number of requests for communication can be handled using this scheme, irrespective of the location of the fault. Two new integer linear program formulations have been presented using this approach. The first formulation assumes a fixed RWA, while the second finds the optimal RWA for maximizing guaranteed throughput. A large number simulation experiments demonstrate that, in the vast majority of cases, an optimal solution obtained using our second formulation not only generates a survivable routing but handles all the requests that the original fault-free logical topology was designed to handle.

Traffic grooming techniques in optical networks are attracting increasing research attention in order to handle the huge bandwidth mismatch between high capacity lightpaths and low-rate individual traffic requests. It is important to have guaranteed survivability of all user connections in such networks. Path protection has emerged as a widely accepted technique for survivable WDM network design. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable traffic grooming in WDM networks, under specified resource constraints. Our approach addresses the complete design problem including logical topology design, RWA, and routing of (subwavelength) requests over the logical topology. We further ensure that the resultant logical topology is able to handle the entire traffic request after any single link failure. We first present two ILP formulations for optimally designing a survivable logical topology, and then propose a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection.

Since the optical reach (the distance an optical signal can travel before its quality degrades to a level that necessitates regeneration) ranges from 500 to 2000 miles, regeneration of optical signals is essential to establish lightpaths of lengths greater than the optical reach. In a translucent optical network, the optical signal is regenerated at selected nodes of the network before the signal quality degrades below a threshold. Given the optical reach of the signal, to minimize the overall network design cost, the goal of the regenerator placement problem is to find the minimum number of regenerators necessary in the network, so that every pair of nodes is able to establish a lightpath (either transparent or translucent) between them. In this paper, we study the regenerator placement problem and prove that the problem is NP-complete. We formulate the regenerator placement problem as a connected dominating set problem in a labeled graph (LCDS) and provide a procedure for computing it. We evaluate the effectiveness of our approach using a number of networks.

In a recent paper, Kim and Lumetta [6] proposed a capacity efficient protection scheme that provides fast recovery in WDM mesh networks. They introduced the notion of a stream that is utilized for this purpose. In this paper, we introduce the concept of gStream, which is a more generalized form of stream and develop efficient algorithms for maximizing capacity utilization without sacrificing the benefit of fast recovery. We show that the problem of finding the set of gStreams that maximizes capacity utilization is NP-complete. We present (i) an optimal solution for formation of streams and gStreams and (ii) a heuristic solution. The results of our experimental evaluation show that our heuristic provides near optimal solution to almost all instances of the problem in a fraction of the time needed for finding the optimal solution.

Traffic grooming techniques are used to combine low-speed data streams onto high-speed lightpaths with the objective of minimizing the network cost, or maximizing the network throughput. In this paper, we first present an efficient integer linear program (ILP) formulation for traffic grooming on mesh WDM networks. Our formulation can be easily modified to implement different objective functions. Unlike previous formulations, our ILP formulation can be used for practical sized networks with several hundred requests. We then propose a second ILP for traffic grooming, with the simplifying assumption that RWA is not an issue. This second formulation is able to generate, in a reasonable time, grooming strategies, for networks with over 30 nodes, with hundreds and even thousands of low-speed data streams. Finally, we introduce a set of ILP formulations for traffic grooming, where the logical topology is specified. We have studied, using simulation, the time needed to determine grooming strategies, using the different ILP formulations.

Nodes in sensor networks are often prone to failure, particularly when deployed in hostile territories, where chances of damage/destruction are significantly higher. There is also the possibility for the loss of connectivity between nodes due to the inherent limitations of the wireless communication medium. Therefore, a sensor network should be designed in such a way that the network is able to continue to operate, even if some of the nodes/links in the network fail. The scalability and the lifetime of sensor networks are affected by the limited transmission range and the battery power of sensor nodes. Recently, relay nodes have been proposed for balanced data gathering, reduction of transmission range, connectivity and fault tolerance. In hierarchical sensor networks using relay nodes, sensor nodes are arranged in clusters and higher-powered relay nodes can be used as cluster heads. Finding the minimum number of such relay nodes, along with their locations, so that each sensor node can communicate with at least ks(ks= 1,2...) relay nodes and the relay node network is kr-connected (kr= 1,2...), is known to be a difficult problem. Some recent works in this area have proposed heuristic solutions for the the special cases of ks= 1 or 2 and kr= 1 or 2. In this paper, we have presented a generalized integer linear program (ILP) formulation capable of generating exact solutions for arbitrary values of ksand kr.

In hierarchical sensor networks, sensor nodes are arranged in clusters, and higher-powered relay nodes can be used as cluster heads. The scalability and the lifetime of sensor networks are affected by the limited transmission range and battery power of the nodes. Proper techniques for assigning sensor nodes to clusters have been shown to improve the lifetime of the network. Previous approaches to clustering focus on different heuristics to achieve load balancing. In this paper, we have proposed two fast and efficient integer linear program (ILP) formulations for assigning sensor nodes to clusters in a two-tiered network, where the relay nodes are used as cluster heads. The first is for single hop routing and the second is a generalized formulation that can be used with any multi-hop routing strategy. The objective, in both cases, is to maximize the lifetime of the relay node network. We have tested our formulations with a number of different routing strategies, and for each case, we have compared our formulation to several existing heuristics for clustering. The results demonstrate that our ILP's consistently outperform the heuristics and are fast enough to be used for practical networks with hundreds of sensor nodes.

Survivable routing of a logical topology ensures that the lightpaths are routed in such a way that a single link failure does not disconnect the network. However, even if the network remains connected after a failure, there is no guarantee that the resulting logical topology will be able to support the required traffic. In this paper, we introduce a new approach that integrates the logical topology design and survivable routing problems. When a topology is generated using our approach, it is guaranteed to have a survivable routing. We further ensure that the topology is able to handle the entire traffic demand, for any single link failure. We have formulated an ILP that optimally designs a survivable logical topology, and also proposed a fast heuristic which can be used for large networks.

One major objective in WDM network design is to develop a logical topology and a routing that minimizes the congestion of the network. A standard approach is to decouple the problem of logical topology design and the problem of routing on this logical topology. Heuristics for finding the logical topology exist and a straight-forward linear program (LP), based on the node-arc formulation is normally used to solve the routing problem over a given logical topology. We have found that such LP formulations become computationally intractable for large networks. In this paper, we have introduced a novel approach for routing traffic over a given logical topology, using the concept of approximation algorithms. This technique allows us to efficiently route traffic for practical sized networks and obtain solutions, which are guaranteed to be within a specified bound of the optimal solution. Simulation results from different networks demonstrate that approximation algorithms can be used to quickly generate "near-optimal" solutions to the traffic routing problem in WDM networks.

A large optical network may carry multiple traffic classes with different priorities and fault-tolerance requirement. Higher priority traffic may require having a back-up path so that the traffic can be switched quickly to this path in case of a failure in the primary path. The lower priority traffic classes may not have any such requirement. In the path protection schemes currently in use for the WDM networks, a backup path is computed for all traffic, whenever a primary path is established between a source-destination pair. The resource needed for communication using the backup path are reserved (or set aside) for data communication between a source-destination pair, and are utilized only when the primary path is unavailable due to a failure in the network. The traffic carrying capacity of a network can be increased, if the resources set aside for the backup paths are utilized for data communication. In this paper we propose a path protection scheme for networks with multiple classes of traffic. The key features of our scheme are (i) not all traffic classes have backup paths - only higher priority classes have backup paths, (ii) primary paths of lower priority share wavelengths with secondary paths of higher priority traffic, and (iii) lower priority traffic can be preempted by higher priority traffic in case of a failure. The sharing of a wavelength between a primary path of a lower priority communication with the secondary path of a higher priority communication allows the network to satisfy more call requests, thereby reducing the call blocking probability. We provide a mathematical programming formulation for computing the primary and backup paths for call requests in a dynamic environment. We also compute the call blocking probability of our scheme and compare it with the call blocking probability of the conventional scheme through simulation. Our experimental results show significant gain by the proposed scheme over the conventional scheme.

Over the years several queuing policies have been proposed to ensure fairness between competing requests at a service point. The fair queuing (FQ) algorithm due to Demers, Keshav and Shenkar (1990) is a queuing technique that attains near perfect fairness, where perfect fairness is considered to be the one attained by a fluid flow model. In a data network, the head of the line processor sharing (PS) is considered to be the most fair algorithm. It has been shown that the difference in throughput at any time, in any queue, for any arrival pattern between the FQ and the PS discipline will never exceed MAX, where MAX is the maximum packet size. This difference in throughput is taken as a metric for fairness measure of a queuing algorithm. The drawback of the FQ algorithm is its high packet processing overhead (O (log N)), where N is the number of active flows. To alleviate this problem of high computational complexity, Shreedhar and Varghese (1996) proposed a fair queuing algorithm based on the idea of deficit round robin (DRR). Although DRR reduces the packet processing overhead to O(1), its fairness measure is considerably worse (3MAX) than that of FQ (MAX). In this paper, we present a new round robin based fair queuing algorithm (FQRR) whose packet processing overhead is O(1) and fairness measure is 2MAX.

Commercially available fiber-optic cables allow limited numbers of wavelengths on a single fiber. In this paper we have developed a pragmatic method of implementing all-optical wavelength routed networks using bundles of fibers to realize each communication link. We have explored some interesting features of this approach for dynamic lightpath assignment. We have shown that our approach allows virtual wavelength translation where we may derive some benefits of partial wavelength translation without actually having to change the carrier frequency. This design also allows us to have bundles of varying sizes to accommodate anticipated differences in traffic through different communication links of the network. Finally, we have presented a simple dynamic scheme, based on local information alone, for allocating lightpaths.

It is desirable to have low diameter logical topologies for multihop lightwave networks. Researchers have investigated regular topologies for such networks. Only a few of these (e.g., GEMNET) are scalable to allow the addition of new nodes to an existing network. Adding new nodes to such networks requires a major change in routing scheme. For example, in a multistar implementation a large number of retuning of transmitters and receivers anti/or renumbering nodes are needed for GEMNET. We present a scalable logical topology which is not regular but it has a low diameter. This topology is interesting since it allows the network to be expanded indefinitely and new nodes can be added with a relatively small change to the network. We present the new topology, an algorithm to add nodes to the network and two routing schemes.

This paper presents a new testable design scheme appli- cable to any arbitrary 1-dimensional bilateral systolic array. The hardware overhead is a global control he and a small amount of additional logic per cell . The proposed design ensures that all cells in the array can simultaneously be set to any state in constant steps after initialization, regardless of the size of the array. The design also supports propaga- tion of test outcomes to observable exiremitles so that the where IVI is the number of states per cell and N is the number

A synthesis approach to the design of a class of regular networks which provide optimal fault tolerance and are of small diameter is presented. The approach makes it possible to design a regular network in the form of a directed graph when the number of nodes n and the number of connections per node d are given, for any n and d. The designed graph will have node connectivity d and a diameter proportional to (og/sub d/ n).>

The problem of integrating testability issues into the synthesis process of programmable-logic-array (PLA-)based VLSI logic design is investigated. Based on the insight gained from prior work on algorithmic and heuristic test generation for PLAs, a systematic methodology for synthesizing easily testable PLAs from high-level (Boolean) specifications is developed. Experimental results are presented to illustrate how adaptive heuristics aid in reducing the complexity of the synthesis-for-testability problem.>

This correspondence presents a class of optimally fault tolerant multiprocessor network architecture, based on the networks proposed earlier by Pradhan [71, where the networks are represented by regular digraphs. Because of optimal fault tolerapce, the number of connections per node is precisely related to the degree of fault tolerance the network is designed to provide. The routing of messgges in presence Qf faults is adaptive and unless the number of faults is equal to the degree of fault tolerance the increase in routing delay in presence of faults is minimal.

This correspondence deals with the problem of testing the diagnosmbllity of a system in presence of hybrid faults (that is, when some of the units of the system have failed intermittently and some have failed permanently). Presence of intermittent faults can lead to incomplete diagnosis and usually complicates the diagnosis problem in comparison to permanent fault situation. Alternative characterizations for hybrid fault diagnosability of a system to those originally presented in [3] are derived in this paper. It is shown that these conditions lead to the testing of the hybrid diagnosability of a system with fewer computations than that in [3].

This correspondence suggests an improved characterization of Boolean functions based on parameters, for unate cascade (UC) realizability. Using this characterization, UC realizability can be readily tested and arrays of UC's can be synthesized to realize arbitrary Boolean functions.

In this paper the problems associated with the minimal realization of synchronous sequential machines by unate cellular cascades have been studied. Given the sequential machine in the form of a flow table, a systematic procedure is followed to generate all the selectable sets. Compatible sets consisting of these selectable sets are next determined and the different secondary variables are assigned. The nested functional forms of the next-state expressions for these variables are finally established. The proposed method is very systematic and perfectly suited for machine processing.

A simple method for the implementation of Booth's algorithm for multiplication of signed binary numbers has been presented. It has been shown that for large word lengths, a significant economy has been achieved compared to Majithia and Kitai's method.

A permuter network is used to arbitrarily change the ordering of the variables of a switching function. A new scheme for permuter arrays is discussed in this note whereby the variables are selected sequentially by a number of "selector cells" according to the required output ordering. A cellular realization of the selector cell is suggested.

A simple algorithm for testing the 2-summability of Boolean functions is presented in this note. The concept of asummobility has been extended and the idea of "mutual 2-asummability" has been introduced. The authors show how mutual 2-asummobility can be utilized for the testing of isobaricity of threshold functions containing no more than seven variables.