Recent advances in space quantum communications envision Low Earth Orbit (LEO) satellites for global entanglement distribution. Entanglement distribution in such a network requires considerations such as satellite mobility, ground station mobility due to the Earth’s rotation, inter-satellite links, and multiple orbital shells, all of which have not been thoroughly studied in the networking literature. We ameliorate this deficit by defining a system model which accounts for all of the aforementioned factors. Using this system model, we formulate the dynamic optimal entanglement distribution (DOED) problem. We convert the DOED problem in a dynamic physical network to an instance of the problem in a static logical graph, the latter of which can be used to solve the former. We obtain a reduced logical graph from a logical graph, which can be used to reduce the complexity of solving the DOED problem. We propose two polynomial-time greedy algorithms for computing entanglement paths, as well as an integer linear programming (ILP)-based algorithm as a benchmark. We present evaluation results to demonstrate the advantages of our model and algorithms.

As LEO/VLEO satellites offer many attractive features, such as low transmission delay, they are expected to be an integral part of 6G. Global entanglement distribution over LEO and VLEO satellite network must reckon with satellite movement over time. Current studies do not fully capture the dynamic nature of satellite constellations. We model a dynamic LEO/VLEO satellite network as a time-varying graph and construct a sequence of static graphs to represent a dynamic network. We study the entanglement distribution problem between a set of source-destination node pairs in this dynamic network utilizing Multi-commodity Flow (MCF). Solving MCF over a sequence of graphs independently for each graph may produce a completely different set of paths. Changing the set of paths every time the graph topology changes may involve a significant amount of overhead, as an established set of paths must be taken down and a new set of paths established. We propose a technique that will avoid this overhead by computing only one set of paths P to be used over all the graphs in the sequence. The degraded performance offered by$P$may be viewed as the cost of using P. The benefit of using$P$is the overhead cost of path switching that can be avoided. We provide a cost-benefit analysis in a LEO/VLEO constellation for entanglement distribution between multiple source-destination pairs. Our extensive experimentation shows that a significant amount of savings in overhead can be achieved if one is willing to accept a slightly degraded performance.

In a smart grid environment, communication network plays an important role as it must deliver data from the Phasor Measurement Units (PMUs) in the Substations (SSs) to the Control Center(s) (CCs) in real time. Accordingly, communication network design has received considerable attention from smart grid researchers in the last few years. In a recent paper, we studied this problem where all the substations were sending data to a single CC and formalized it as the Rooted Delay Constrained Minimum Spanning Tree problem. As the number of substations in a geographic area is often large, PMU data from the substations do not directly go to the Control Center (CC) and instead goes to multiple Local Controls Centers (LCC) within a specified delay threshold. The aggregated data from the LCCs is then sent to the CC. In this paper, we extend our earlier results by considering Multiple Local Control Centers (MLCCs) where the PMU data must arrive from the SSs to a LCC within a specified delay threshold. This gives rise to a new problem, where we need to create a Delay Constrained Spanning Forest instead of a Delay Constrained Spanning Tree as in earlier studies. We provide (i) an optimal solution for the problem using Integer Linear Programming, (ii) a Lagrangian Relaxation, and (iii) a Heuristic solution. Finally, we evaluate the performance of our solution techniques with real substation location data of Arizona.

This work proposes a robust Partial Domain Adap-tation (PDA) framework that mitigates the negative transfer problem by incorporating a robust target-supervision strategy. It leverages ensemble learning and includes diverse, complementary label feedback, alleviating the effect of incorrect feedback and promoting pseudo-label refinement. Rather than relying exclusively on first-order moments for distribution alignment, our approach offers explicit objectives to optimize intra-class compactness and inter-class separation with the inferred source prototypes and highly-confident target samples in a domain-invariant fashion. Notably, we ensure source data privacy by eliminating the need to access the source data during the adaptation phase through a priori inference of source prototypes. We conducted a series of comprehensive experiments, including an ablation analysis, covering a range of partial domain adaptation tasks. Comprehensive evaluations on benchmark datasets corroborate our framework's enhanced robustness and generalization, demonstrating its superiority over existing state-of-the-art PDA approaches.

An important problem in network science is finding an optimal placement of sensors in nodes in order to uniquely detect failures in the network. This problem can be modelled as an identifying code set (ICS) problem, introduced by Karpovsky et al. in 1998. The ICS problem aims to find a cover of a set S, such that the elements in the cover define a unique signature for each of the elements of S, and to minimise the cover’s cardinality. In this work, we study a generalised identifying code set (GICS) problem, where a unique signature must be found for each subset of S that has a cardinality of at most k (instead of just each element of S). The concept of an independent support of a Boolean formula was introduced by Chakraborty et al. in 2014 to speed up propositional model counting, by identifying a subset of variables whose truth assignments uniquely define those of the other variables. In this work, we introduce an extended version of independent support, grouped independent support (GIS), and show how to reduce the GICS problem to the GIS problem. We then propose a new solving method for finding a GICS, based on finding a GIS. We show that the prior state-of-the-art approaches yield integer-linear programming (ILP) models whose sizes grow exponentially with the problem size and k, while our GIS encoding only grows polynomially with the problem size and k. While the ILP approach can solve the GICS problem on networks of at most 494 nodes, the GIS-based method can handle networks of up to 21 363 nodes; a ∼40× improvement. The GIS-based method shows up to a 520× improvement on the ILP-based method in terms of median solving time. For the majority of the instances that can be encoded and solved by both methods, the cardinality of the solution returned by the GIS-based method is less than 10% larger than the cardinality of the solution found by the ILP method.

We study geometric variations of the discriminating code problem. In the \emph{discrete version} of the problem, a finite set of points $P$ and a finite set of objects $S$ are given in $\mathbb{R}^d$. The objective is to choose a subset $S^* \subseteq S$ of minimum cardinality such that for each point $p_i \in P$, the subset $S_i^* \subseteq S^*$ covering $p_i$ satisfies $S_i^*\neq \emptyset$, and each pair $p_i,p_j \in P$, $i \neq j$, we have $S_i^* \neq S_j^*$. In the \emph{continuous version} of the problem, the solution set $S^*$ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ($d=1$), the points in $P$ are placed on a horizontal line $L$, and the objects in $S$ are finite-length line segments aligned with $L$ (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. Still, for the 1-dimensional discrete version, we design a polynomial-time $2$-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ($d=2$) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce $(16\cdot OPT+1)$-approximate and $(64\cdot OPT+1)$-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. We show that the identifying code problem for axis-parallel unit square intersection graphs (in $d=2$) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects.

Communication network topology design problem in a smart grid environment has received considerable attention in recent times, because in this environment, power transmission control data, generated by Phasor Measurement Units (PMUs), needs to be exchanged between Substations (SS) and Controls Centers (CC) in real time. In this paper, we formalize this design problem studied in a previous paper as the Rooted Delay Constrained Minimum Spanning Tree (RDCMST) problem. While other researchers have studied the RDCMST problem in a topological setting, we study it in a geometric setting. We provide a modified version of the well-known Prim's algorithm for construction of a Minimum Spanning Tree of a graph to solve the RDCMST problem. We (i) establish the necessary and sufficient condition for the existence of a solution for the RDCMST problem, (ii) demonstrate that our algorithm may fail to find the optimal solution for some problem instances, (iii) characterize conditions on the input data which will ensure that our algorithm will find the optimal solution, and (iv) demonstrate that under some pathological condition, the ratio between our algorithm and the optimal solution can be arbitrarily large. We provide an Integer Linear Programming formulation for the problem for computation of the optimal solution. We evaluate the performance of our algorithm with real substation location data of Arizona. In our experiments, our algorithm always produced either optimal or near optimal solutions.

We study two geometric variations of the discriminating code problem. In the discrete version, a finite set of points P and a finite set of objects S are given in ℝ^d. The objective is to choose a subset S^* ⊆ S of minimum cardinality such that the subsets S_i^* ⊆ S^* covering p_i, satisfy S_i^* ≠ ∅ for each i = 1,2,…, n, and S_i^* ≠ S_j^* for each pair (i,j), i ≠ j. In the continuous version, the solution set S^* can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case (d = 1), the points are placed on some fixed-line L, and the objects in S are finite segments of L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in 1D. We then design a polynomial-time 2-approximation algorithm for the 1-dimensional discrete case. We also design a PTAS for both discrete and continuous cases when the intervals are all required to have the same length. We then study the 2-dimensional case (d = 2) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-hard, and design polynomial-time approximation algorithms with factors 4+ε and 32+ε, respectively (for every fixed ε > 0).

The United Nations, in their annual World Drug Report in 2018, reported that the production of Opium, Cocaine, Cannabis, etc. all observed record highs, which indicates the ever-growing demand of these drugs. Social networks of individuals associated with Drug Trafficking Organizations (DTO) have been created and studied by various research groups to capture key individuals, in order to disrupt operations of a DTO. With drug offenses increasing globally, the list of suspect individuals has also been growing over the past decade. As it takes significant amount of technical and human resources to monitor a suspect, an increasing list entails higher resource requirements on the part of law enforcement agencies. Monitoring all the suspects soon becomes an impossible task. In this paper, we present a novel methodology which ensures reduction in resources on the part of law enforcement authorities, without compromising the ability to uniquely identify a suspect, when they become "active" in drug related activities. Our approach utilizes the mathematical notion of Identifying Codes, which generates unique identification for all the nodes in a network. We find that just monitoring important individuals in the network leads to a wastage in resources and show how our approach overcomes this shortcoming. Finally, we evaluate the efficacy of our approach on real world datasets.

A staggering 450,000 people died due to drug consumption in 2015, out of which, a third of the deaths were a direct result of drug overdosing. Illicit manufacturing of Cocaine, Heroin, Cannabis, etc., by Drug Trafficking Organizations (DTOs), all peaked recently, which is a major indication of their worldwide demand. With drug offenses increasing globally, the list of suspect individuals, associated with drug trafficking organizations, has also been growing over the past few decades. As it takes significant amount of technical and human resources to monitor a suspect, an increasing list entails greater resource requirements on the part of law enforcement agencies. Soon, monitoring all the suspects on the list becomes an impossible task. In this paper, we present a novel methodology called Augmented Identifying Codes (AIC), an extension of the mathematical notion of Identifying Codes. We show that our method requires significantly lesser resources, on the part of the law enforcement agencies, when compared to strategies adopting standard network centrality measures, for monitoring of individuals associated with drug trafficking organizations. Finally, we evaluate the efficacy of our approach on real world datasets.

The studies in fault-tolerance in networks mostly focus on the connectivity of the graph as the metric of fault-tolerance. If the underlying graph is k-connected, it can tolerate up to k -1 failures. This metric in various forms, has been used extensively for robust design of communication networks, which may be viewed as a single layer network. In the last few years, there is an increasing awareness in the research community that critical infrastructure networks, such as the power grid and the communication network arehighlyinterdependent. This inter-dependency has become critical in a smart-grid environment, where the electric power transmission/distribution network is highly integrated with the communication network. This dependency realization has led to a fairly large number of studies on robustness and resiliency of interdependent multi-layer networks. Unfortunately, many of the proposed models of inter-dependency that appeared in the literature in the last few years fail to capture the complex inter-dependency that exists between entities of power grid and communication networks, involving a complex combination of conjunctive and disjunctive relations. The Boolean logic based model of inter-dependency proposed in [1] overcomes this limitation. Using this dependency model, in this paper we explore ''connectivity'' of a two-layer interdependent network and formally define a new metric,Two-Layeredconnectivity(TL-connectivity),that is a counterpart of the traditional connectivity metric for a single-layer network(SL-connectivity).We provide an algorithm for computation of TL-connectivity. The problem can be solved in polynomial time in some special cases, whereas for some others, the problem is NP-complete. Finally, we evaluate the technique with a specific case study.

A cellular network is often modeled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Cellular graphs are used to model hexagonal cell structure of a cellular network. Assuming a 2-band buffering system where the interference does not extend beyond two cells away from the call originating cell, we study a version of the channel assignment problem in cellular graphs that been studied only minimally. In this version, each node has a fixed set of frequency channels where only a subset of which may be available at a given time for communication (as other channels may be busy). Assuming that only a subset of frequency channels are available for communication at each node, we try to determine the size of the smallest set of free channels in a node that will guarantee that each node of the cellular graph can be assigned a channel (from its own set of free channels) that will be interference free in a two band buffering system. The mathematical abstraction of this problem is known as the Choice Number computation problem and is closely related to the List Coloring problem in Graph Theory. In this paper we establish a lower and an upper bound of the distance-2 Choice Number of cellular graphs. In addition we also conduct extensive experimentation to study the impact of the availability of the number of free channels in a node to the percentage of the total number of nodes in the network that can be assigned an interference free channel in a two band buffering system.

Distributed storage of data files in different nodes of a network enhances its fault tolerance capability by offering protection against node and link failures. Reliability is often achieved through redundancy in one of the following two ways: (i) storage of multiple copies of the entire file at different locations (nodes) or (ii) storage of file segments (not entire files) at different node locations. In the file distribution scheme, file segments from a file are created in such a way that it is possible to reconstruct the entire file, just by accessing any segments. For the reconstruction scheme to work, it is essential that the segments of the file are stored in nodes that are connected in the network. However, in the event of node/link failures, the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially correlated or region based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The first goal of this research is to design a least cost file storage scheme to ensure that no matter which region is destroyed; resulting in fragmentation of the network, a largest connected component of the residual network will have enough file segments with which to reconstruct the entire file. In case the least cost to ensure this objective is within the allocated budget, the storage design will be all region fault‐tolerant (ARFT). In case the least cost exceeds the allocated budget, design of an ARFT file storage system design is impossible. The second goal of this research is to design file storage schemes that will be maximum region fault‐tolerant within the allocated budget. The third goal of this research is to investigate the impact of the coding parameters and on storage requirements for ensuring all region or \textit{maximum region} fault‐tolerant design. We provide maximum region fault‐tolerant design. We provide approximation algorithms for the problems and evaluate their performance through simulation using two real networks and compare their results to the optimal solutions obtained using Integer Linear Program. The simulation results demonstrate that the approximation algorithms almost always produce near optimal results in a fraction of the time needed to find the optimal solution. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 380–395 2015

Fiber-Wireless (FiWi) networks have received considerable attention in the research community in the last few years as they offer an attractive way of integrating optical and wireless technology. As in every other type of networks, routing plays a major role in FiWi networks. Accordingly, a number of routing algorithms for FiWi networks have been proposed. Most of the routing algorithms attempt to find the “shortest path” from the source to the destination. A recent paper proposed a novel path length metric, where the contribution of a link towards path length computation depends not only on that link but also every other link that constitutes the path from the source to the destination. In this paper we address the problem of computing the shortest path using this path length metric. Moreover, we consider a variation of the metric and also provide an algorithm to compute the shortest path using this variation. As multipath routing provides a number of advantages over single path routing, we consider disjoint path routing with the new path length metric. We show that while the single path computation problem can be solved in polynomial time in both the cases, the disjoint path computation problem is NP-complete. We provide optimal solution for the NP-complete problem using integer linear programming and also provide two approximation algorithms with a performance bound of 4 and 2 respectively. The experimental evaluation of the approximation algorithms produced a near optimal solution in a fraction of a second.

The orthogonal frequency division multiplexing (OFDM) technology provides an opportunity for efficient resource utilization in optical networks. It allows allocation of multiple sub-carriers to meet traffic demands of varying size. Utilizing OFDM technology, a spectrum efficient and scalable optical transport network called SLICE was proposed recently. The SLICE architecture enables sub-wavelength, super-wavelength resource allocation and multiple rate data traffic that results in efficient use of spectrum. However, the benefit is accompanied by additional complexities in resource allocation. In SLICE architecture, in order to minimize utilized spectrum, one has to solve the routing and spectrum allocation (RSA) problem, a generalization of the routing and wavelength allocation (RWA) problem. In this paper, we focus our attention to the on-line version of RSA problem and provide an algorithm for the ring network with a competitive ratio of min{O(log(dmax)), O(log(k))} where k is the total number of requests and dmaxis the maximum demand in terms of the number of sub-carriers. Moreover, we provide a heuristic for the network with arbitrary topology and measure the effectiveness of the heuristic with extensive simulation.

The orthogonal frequency division multiplexing (OFDM) technology provides an opportunity for efficient resource utilization in optical networks. It allows allocation of multiple sub-carriers to meet traffic demands of varying size. Utilizing OFDM technology, a spectrum efficient and scalable optical transport network called SLICE was proposed recently. The SLICE architecture enables sub-wavelength, super-wavelength resource allocation and multiple rate data traffic that results in efficient use of spectrum. However, the benefit is accompanied by additional complexities in resource allocation. In SLICE architecture, in order to minimize the utilized spectrum, one has to solve the routing and spectrum allocation problem (RSA). In this paper, we focus our attention to RSA and (i) prove that RSA is NP-complete even when the optical network topology is as simple as a chain or a ring, (ii) provide approximation algorithms for RSA when the network topology is a binary tree or a ring, (iii) provide a heuristic for the network with arbitrary topology and measure the effectiveness of the heuristic with extensive simulation. Simulation results demonstrate that our heuristic significantly outperforms several other heuristics proposed recently for RSA.

It has been observed that individuals' decisions to adopt a product or innovation are often influenced by the recommendations of their friends and acquaintances. Motivated by this observation, the last few years have seen a number of studies on influence maximization in social networks. The primary goal of these studies is identification of k most influential nodes in a network. A major limitation of these studies is that they focus on a non-adversarial environment, where only one player is engaged in influencing the nodes. However, in a realistic scenario multiple players attempt to influence the nodes in a competitive fashion. The proposed model considers a competitive environment where a node that has not yet adopted an innovation, can adopt only one of the several competing innovations and once it adopts an innovation, it does not switch. The paper studies the scenario where the first player has already chosen a set of k nodes and the second player, with the knowledge of the choice of the first, attempts to identify a smallest set of nodes (excluding the ones already chosen by the first) so that when the influence propagation process ends, the number of nodes influenced by the second player is larger than the number of nodes influenced by the first.

Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.

Robustness or fault-tolerance capability of a network is an important design parameter in both wired and wireless networks. Connectivity of a network is traditionally considered to be the primary metric for evaluation of its fault-tolerance capability. However, connectivity κ(G) (for random faults) or region-based connectivity κR(G) (for spatially correlated or region-based faults, where the faults are confined to a region R) of a network G, does not provide any information about the network state, (i.e., whether the network is connected or not) once the number of faults exceeds κ(G) or κR(G). If the number of faults exceeds κ(G) or κR(G), one would like to know, (i) the number of connected components into which G decomposes, (ii) the size of the largest connected component, (iii) the size of the smallest connected component. In this paper, we introduce a set of new metrics that computes these values. We focus on one particular metric called region-based component decomposition number (RBCDN), that measures the number of connected components in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBCDN of a network. In addition, we study the problem of least cost design of a network with a target value of RBCDN. We show that the optimal design problem is NP-complete and present an approximation algorithm with a performance bound of O(log K + 4log n), where n denotes the number of nodes in the graph and K denotes a target value of RBCDN. We evaluate the performance of our algorithm by comparing it with the performance of the optimal solution. Experimental results demonstrate that our algorithm produces near optimal solution in a fraction of time needed to find an optimal solution.

The traditional studies on fault-tolerance in networks assume that the faults are random in nature, i.e., the probability of a node failing is independent of its location in the deployment area. However, this assumption is no longer valid if the faults are spatially correlated. In this paper we focus on the study of the impact of region-based faults on wireless networks. Most of the studies on connectivity of wireless networks assume a unit disk graph model, i.e., links exist between two nodes if they are within a circular transmission range of one another. However, the unit disk graph model does not capture wireless communication environment accurately. The log-normal shadow fading model for communication was introduced to overcome the limitations of the unit disk graph model. In this paper we investigate connectivity issues of wireless networks in a log-normal shadow fading environment where the faults are spatially correlated. If dmin(G) denotes the minimum node degree of the network, we provide the analytical expression and method for computing P(dmin(G) ≥ 1) in a region-based fault scenario, where P(dmin(G) ≥ 1) denotes the probability of the minimum node degree being at least 1. Through extensive simulation, we find (P(κG) ≥ 1), where κ(G) represents the connectivity of the graph G formed by the distribution of nodes on a 2D plane and examine the relationship between P(dmin(G) ≥ 1) and P(κ(G) ≥ 1).

Connectivity k(G) of a network G is traditionally considered to be the primary metric for evaluation of its fault tolerance capability. However, connectivity as a metric has several limitations - e.g., it has no mechanism to distinguish between localized and random faults. Also it does not provide any information about the network state, if number of failures exceed k(G). The network state information that might be of interest in such a scenario is the size of the largest connected component. In this paper, we address both these limitations and introduce a new metric called region-based largest component size (RBLCS), that provides the largest size of the component in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBLCS for a given network. In addition, we study the problem of least cost design of a network with a target value of RBLCS. We prove that the optimal design problem is NP-complete and present a heuristic to solve the problem. We evaluate our heuristic by comparing its solutions with the optimal solutions. Experimental results demonstrate that our heuristic produces near optimal solution in a fraction of time needed to find the optimal.

Power consumption can be significantly reduced in Systems-on-Chip (SoC) by scaling down the voltage levels of the Processing Elements (PEs). The power efficiency of this Voltage Islanding technique comes at the cost of energy and area overhead due to the level shifters between voltage islands. Moreover, from the physical design perspective it is not desirable to have an excessive number of voltage islands on the chip. Considering voltage islanding at an early phase of design as during floorplanning of the PEs can address various of these issues. In this paper, we propose a new cost function for the floorplanning objective different from the traditional floorplanning objective. The new cost function not only includes the overall area requirement, but also incorporates the overall power consumption and the design constraint imposed on the maximum number of voltage islands. We propose a greedy heuristic based on the proposed cost function for the floorplanning of the PEs with several voltage islands. Experimental results using benchmark data study the effect of several parameters on the outcome of the heuristic. It is evident from the results that power consumption can be significantly reduced using our algorithm without significant area overhead. The area obtained from the heuristic is also compared with the optimal, and found to be within 4% of the optimal on average, when area minimization is given the priority.

Optical reach is defined as the distance optical signal can traverse before its quality degrades to a level that necessitates regeneration. It typically ranges from 500 to 2000 miles, and as a consequence, regeneration of optical signal becomes essential in order to establish a lightpath between a source-destination node pair whose distance exceeds the limit. In a translucent optical network, the optical signal is regenerated at selected nodes of the network before the signal quality degrades below the acceptable 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 between them. In this paper, we study the regenerator placement problem and present complexity result for that.

Sensing and transmission phenomena of an implanted sensor dissipates energy which results in rise in temperature of its surroundings. Simultaneous operation of such multiple active sensors increases the temperature of the surrounding environment causing hotspots. Such hotspots are highly undesirable as they may cause damage to the environment as well as to the sensor network, posing a challenge for deployment of sensors. The problem is further enhanced for a temperature sensitive environment, as the allowable threshold temperature for such environments is less. Here we investigate the formation of hotspots in such temperature sensitive environments due to the heat dissipation of multiple active sensors and try to achieve a maximum coverage of such networks avoiding hotspots. We formulate this as a variation of the maximum independent set problem for hypergraphs. We devise an Integer Linear Program to achieve the optimal solution for the problem. We also provide a greedy heuristic solution for the problem. For a special case of this problem, where the hotspots are formed due to pairs of sensors only, we prove a 5-approximation bound for the greedy solution. Experimental results show that our algorithm achieves near-optimal solutions in almost all the test cases.

OSCI's TLM-2.0 standard enables the simulation of functionality and timing of a system by defining two coding styles namely Loosely-timed (LT) and approximately timed (AT). Without dynamic switching between the two modes, a user interested in performance analysis is forced to execute the model in AT mode for the entire duration of simulation. A run-time switching mechanism enables user to execute uninteresting simulation portions (e.g. operating system boot) in the high speed LT mode and switch to detailed AT model only when one needs to carry out detailed micro-architectural analysis (e.g. benchmark execution). In this paper, we introduce a comprehensive switching mechanism that addresses all the potential issues during LT-to-AT and AT-to-LT transitions. We test this switching methodology on one Intel proprietary Interconnect Bus model and demonstrate a 24X speedup over AT-only simulations.

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.

The temporal fluctuations in quality exhibited by the wireless links act as a major challenge in the design of efficient routing protocols in real-world Mobile Ad hoc Networks (MANETs). None of the existing link metrics fully account for the characteristics of data loss and delay on the links of a MANET. This paper provides the design of a novel delay-based link quality metric that uses realtime statistics from the wireless driver to take into account wireless contention, congestion, channel loss and mobility. The proposed delay metric is additive, does not introduce much additional overhead and is reflective of the varying wireless link quality. We design an efficient Link Delay- aware Routing (LDAR) protocol based on the proposed link metric. The proposed protocol has been implemented on a MANET test bed consisting of 5 laptop nodes. The evaluation of our protocol performed through extensive experimentation on the 5-node multi-hop MANET testbed and network simulator NS-2 demonstrate the superior benefits of the new protocol.

An efficient technique for mapping application tasks to heterogeneous processing elements (PEs) on a network-on-chip (NoC) platform, operating at multiple voltage levels, is presented in this paper. The goal of the mapping is to minimize energy consumption subject to the performance constraints. Such a mapping involves solving several subproblems. Most of the research effort in this area often address these subproblems in a sequential fashion or a subset of them. We take a unified approach to the problem without compromising the solution time and provide techniques for optimal and heuristic solutions. We prove that the voltage assignment component of the problem itself is NP-hard and is in approximable within any constant factor. Our optimal solution utilizes a mixed integer linear program (MILP) formulation of the problem. The heuristic utilizes MILP relaxation and randomized rounding. Experimental results based on E3S benchmark applications and a few real applications show that our heuristic produces near-optimal solution in a fraction of time needed to find the optimal.

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.

Service Overlay Network (SON) was proposed to alleviate the difficulties encountered in providing end-to-end Quality of Service (QoS) guarantees. SON is able to provide QoS guarantees by purchasing bandwidth from individual network domains and building a logical end-to-end data delivery infrastructure on top of the existing Internet. We focus on SON topology design problems under a generalized cost model. Earlier research in this topic considered two distinct cost models - fixed (leased) cost model and variable (usage-based) cost model. However in most applications, the costs of both nodes and links have a fixed component as well as a variable component that often depends on usage. Our generalized cost model takes this fact into account and our topology design algorithm uses this cost model to And the optimal topology. Since the SON topology design problem is NP-complete, we provide approximation algorithm with guaranteed performance bound. We validate the effectiveness of our algorithm through extensive simulation.

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.

Multichannel communication in a wireless mesh network with routers having multiple radio interfaces significantly enhances the network capacity. Efficient channel assignment and routing is critical for realization of optimal throughput in such networks. In this paper, we investigate the problem of finding the largest number of links that can be activated simultaneously in a wireless mesh network subject to interference, radio and connectivity constraints. Our goal is to activate all such links and we present an interference aware channel assignment algorithm that realizes this goal. We show that the Link Interference Graph created by utilizing a frequently used interference model gives rise to a special class of graphs, known as overlapping double-disk (ODD) graphs. We prove that the Maximum Independent Set computation problem is NP-complete for this special class of graphs. We provide a Polynomial Time Approximation Scheme (PTAS) for computation of the Maximum Independent Set of an ODD graph. We use this PTAS to develop a channel assignment algorithm for a multiradio multichannel Wireless Mesh Network. We evaluate the performance of our channel assignment algorithm by comparing it with the optimal solution obtained by solving an integer linear program. Experimental results demonstrate that our channel assignment algorithm produces near optimal solution in almost all instances of the problem.

Tracking mobile targets is an important application of wireless sensor networks. However, mobility of the target brings new challenges to designing energy-efficient and scalable data collection schemes. A novel dynamic grid-based tracking (DGT) scheme for tracking mobile target is proposed in this paper. This scheme is distributed in nature, and can be adaptive to the mobility of the target. The underlying idea of embedding a virtual grid structure and restricting mobility-related choices to grid nodes can be generally applied to other wireless sensor networks applications, where mobility is an important consideration during protocol design

Task to resource mapping problems are encountered during (i) hardware-software co-design and (ii) performance optimization of Network Processor systems. The goal of the first problem is to find the task to resource mapping that minimizes the design cost subject to all design constraints. The goal of the second problem is to find the mapping that maximizes the performance, subject to all architectural constraints. To meet the design goals in performance, it may be necessary to allow multiple packets to be inside the system at any given instance of time and this may give rise to the resource contention between packets. In this paper, a Randomized Rounding (RR) based solution is presented for the task to resource mapping and scheduling problem. We also proposed two techniques to detect and eliminate the resource contention. We evaluate the efficacy of our RR approach through extensive simulation. The simulation results demonstrate that this approach produces near optimal solutions in almost all instances of the problem in a fraction of time needed to find the optimal solution. The quality of the solution produced by this approach is also better than often used list scheduling algorithm for task to resource mapping problem. Finally, we demonstrate with a case study, the results of a Network Processor design and scheduling problem using our techniques.

Efficient transfer of bulk data requires routing that minimizes the net transfer time instead of providing flow level bandwidth guarantees. In this work, we consider a realistic scenario where available bandwidth for each link in a given network is time varying. In such a network and for a given file size, we provide an optimal algorithm that minimizes the total time required to transfer the file from source to destination. We further consider the problem where path shifting is allowed to increase the net throughput for bulk data transfer. For this problem, we provide a dynamic programming based optimal algorithm that minimizes the number of path shifts required to transfer the file in the specified time. Solution to the above problems addresses both the performance and scalability issues that arise in large bulk data transfer for long duration of time.

In a WDM optical network, each fiber link can carry a certain set of wavelengths /spl Lambda/= {/spl lambda//sub 1/,/spl lambda//sub 2/,...,/spl lambda//sub W/}. One scheme for tolerating a single link failure (or node failure) in the network is the path protection scheme, which establishes an active path and a link-disjoint (or node-disjoint) backup path, so that in the event of a link failure (node failure) on the active path, data can be quickly re-routed through the backup path. We consider a dynamic scenario, where requests to establish active-backup paths between a specified source-destination node pair arrive sequentially. If a link-disjoint (node-disjoint) active-backup path pair is found at the time of the request, the paths are established; otherwise, the request is blocked. In this scenario, at the time a request arrives, not every fiber link will have all W wavelengths available for new call establishment, as some of the wavelengths may already have been allocated to earlier requests and communication through these paths may still be in progress. We assume that the network nodes do not have any wavelength converters. This paper studies the existence of a pair of link-disjoint (node-disjoint) active-backup paths satisfying the wavelength continuity constraint between a specified source-destination node pair. First we prove that both the link-disjoint and node-disjoint versions of the problem are NP-complete. Then we focus on the link-disjoint version and present an approximation algorithm and an exact algorithm for the problem. Finally, through our experimental evaluations, we demonstrate that our approximation algorithm produces near-optimal solutions in almost all of the instances of the problem in a fraction of the time required by the exact algorithm.

Faults in some sensor networks are likely to be localized. The conventional metric of fault-tolerance - connectivity of the network graph - fails to capture any notion of locality. This research introduces a new metric - region-based connectivity - that incorporates the notion of locality.

The paper presents the design and evaluation of a highly scalable, decentralized and self-organizing peer-to-peer network architecture based on multi-mesh topology. Our network automatically adapts to dynamic node arrivals, departures and failures. Each node maintains a fixed set of neighbor connections, regardless of the size of the network. This demonstrates the scalability of the network. Our network is close in spirit to the content-addressable network. While the content-addressable network uses torus as the underlying network topology, our network uses multi-mesh. Multi-mesh has some unique advantages over torus and this is reflected in the evaluations of our network against the content-addressable network.

We present a new memory-efficient scheme for address lookup that exploits the caching support provided by general-purpose processors. We propose compact prefix tries, in which prefixes occurring at multiple levels of a subtrie are compressed into a single node that fits in a single cache line. The scheme performs well in compressing dense as well as sparse tries. For an IP core router (Mae-West) database with 93354 prefixes, the simulation results for compact prefix tries show up to 70% improvement in lookup performance and up to 33% reduction in memory when compared with LC-tries. In fact, the entire forwarding table for Mae-West required only 829 KB space. Measurements for compact prefix tries, when compared with most existing schemes, show better results in terms of memory usage as well as lookup speeds. Moreover, as the memory usage is significantly less and sparse tries with long paths can be compressed into only a few nodes, this scheme is particularly attractive for IPv6.

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.

A fundamental problem in QoS routing is to find a path between a specified source-destination node pair that satisfies a set of end-to-end quality of service constraints. We study this problem in a communication system where there are multiple additive quality of service parameters associated with each link. It is well-known that the multi-constrained path selection problem (MCPS) is NP-complete. In this paper, we present a fully polynomial time approximation scheme for an optimization version of the MCPS problem. This means that for any given /spl epsi/ > 0, we can compute, in time bounded by a polynomial of the input size of the problem and in 1//spl epsi/, a solution whose cost is at most (1 + /spl epsi/) of that of the optimal solution.

We consider the problem of routing the lightpaths of a logical topology of a WDM network on an arbitrary physical topology, such that the logical topology remains,connected even after the failure of a physical link. We focus our attention on the ring interconnection as the logical topology because it is widely used in many protection schemes. We first establish the necessary and sufficient condition for a ring logical topology to withstand failure of a single physical link. Next we show that the testing of this necessary and sufficient condition is an NP-complete problem. Finally, we give an algorithm for testing the necessary and sufficient condition and demonstrate the execution of the algorithm with the help of an example.

We consider the problem of routing the lightpaths of a logical topology of a WDM network on an arbitrary physical topology, such that the logical topology remains connected even after the failure of a physical link. In a previous paper Modiano et. al. (see Proc. IEEE INFOCOM'01, 2001) introduced the notion of survivable routing and established a necessary and sufficient condition for the existence survivable routes of a logical topology in a physical topology. In this paper we show that the problem of determining whether survivable routing is possible for a logical topology in a given physical topology is an NP-complete problem. Moreover we show that the problem remains NP-complete, even when the logical topology is restricted to be a ring with a specific ordering of the nodes.

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.

This paper presents a performance-driven I/O pin routing algorithm with special consideration of wire uniformity. First, a topological routing based on a min-cost max-flow algorithm is proposed. In this phase, an exponential weight function is used to guide the flow distribution which is very helpful in distributing wires, globally and uniformly, on the whole routing area. Then a physical routing phase is applied to implement one-to-one connection between chip pads and I/O pins, which focuses on the wire uniformity of the fanout area nearby the periphery of chip pads. Finally, a balanced position based wire polishing approach is proposed to further improve the local wire uniformity which tries to modify each wire into a smooth curve instead of broken line while satisfying the specified design rules such as wire-wire pitch and wire-pin pitch. A routing cost function is adequately defined to guide the whole routing process which leads to a good trade-off between wire uniformity and wire length. The algorithm has been implemented and tested on up to 10-ring 600-pin PGA and the experimental results are very promising.

A cellular network is often modelled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Sen et al. (1998) introduced the notion of cellular graphs that models the hexagonal cell structure of a cellular network. Assuming a k-band buffering system where the interference does not extend beyond k cells away from the call originating cell, we provided two different formulations of the channel assignment problem: distance-k chromatic number problem and k-band chromatic bandwidth problem. The channel assignment algorithms presented in Sen et al. were non-optimal. In this paper we provide: (i) a new algorithm for the distance-k chromatic number problem that is optimal and (ii) a near optimal algorithm for the 2-band chromatic bandwidth problem that has a performance bound of 4/3. The complexity of the algorithms is O(p), where p is the number of cells.

A cellular network is often modelled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. We introduce the notion of cellular graphs that models the hexagonal cell structures of a cellular network. Exploiting the regular structure of the cellular graphs we compute the upper and the lower bounds for a class of channel assignment problems. Assuming a k-band buffering system where the interference does not extend beyond k cells away from the call originating cell, we provide two different formulations of the channel assignment problem-distance-k chromatic number problem and k-band chromatic bandwidth problem. We give one algorithm for the first problem and two for the second, with all three algorithms assigning channels to the cells. The complexity of the algorithm for the first problem is O(p), where p is the number of cells. For the second problem, the complexity of the first algorithm is O(p) and the complexity of the second algorithm is O(k/sup 5/log k). All the algorithms are asymptotically optimal, in the sense that the order of the upper bound of the number of channels required is the same as the order of the lower bound.

Packet radio networks are modeled as arbitrary graphs by most researchers. We show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. We study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(nlogn) algorithm when all the transceivers are located on a line. We restrict our attention to static allocation in general and TDMA in particular. However, it may be noted that the results presented are also valid for other static allocation schemes.

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.

A new routing algorithm is proposed in this correspondence for the network architecture developed in [1]. It has been shown that this algorithm gives the shortest path between the source to destination, when all the processors and the communication links of the network are non- faulty. For the situation when some of the processors are faulty, a heuristic function is given, which if used in the routing algorithm will give shortest path from the source to destination, if such a path exists.

The problem of diagnosability of a system with three-valued test outcomes was considered in earlier works [1]-[3]. However all these works assume the system to be modeled as in [4]. In this correspondence, we consider a more general model of the system and study the diagnosability criteria in presence of three-valued test outcomes. In this model, each unit is tested jointly by a number of other units of the system as opposed to each test being carried out by a single unit of the system as in [4]. Necessary and sufficient conditions for the diagnosability of a system under this general model have been presented in this correspondence. Throughout the correspondence, diagnosability without repair has been considered.

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].