Structural Information and Communication Complexity

We consider the traffic grooming problem in passive WDM star networks. Traffic grooming is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. We first prove that the traffic grooming problem in star networks is NP-hard for a more restricted case than the one considered in [2]. Then, we propose a polynomial time algorithm for the special case where there are two wavelengths per fiber using matching techniques. Furthermore, we propose two reductions of our problem to two combinatorial optimization problems, the constrained multiset multicover problem [3], and the demand matching problem [4] allowing us to obtain a polynomial time H _2C (resp. \(2+\frac{4}{5}\)) approximation algorithm for the minimization (resp. maximization) version of the problem, where C is the capacity of each wavelength.

In this paper we consider all-optical networks in which a service provider has to satisfy a given set of communication requests. Each request is charged a cost depending on its wavelength and on the wavelengths of the other requests met along its path in the network. Under the assumption that each request is issued by a selfish agent, we seek for payment strategies which can guarantee the existence of a pure Nash equilibrium, that is an assignment of paths to the requests so that no request can lower its cost by choosing a different path in the network. For such strategies, we bound the loss of performance of the network (price of anarchy) by comparing the number of wavelengths used by the worst pure Nash equilibrium with that of a centralized optimal solution.

An important technique for discovering routes between two nodes in an ad-hoc network involves applying the face routing algorithm on a planar spanner of the network. Face routing guarantees message delivery in networks that contains large holes, where greedy algorithms fail. Existing techniques for constructing a suitable planar subgraph involve local tests that eliminate crossings between existing links by deleting some links. They do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, some of the routes found in face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph. The test is relatively simple, requires low overhead and does not eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead associated with multiple hops.

Path Layout is a fundamental graph problem in label switching protocols. This problem is raised in various protocols such as the traditional ATM protocol and MPLS which is a new label switching protocol standardized recently by the IETF. Path layout is essentially the problem of reducing the size of the label-table in a router. The size is equivalent to the number of different paths that pass through the router, or start from it. A reduction in the size can be achieved by choosing a relatively small number of paths, from which a larger set is composed using concatenation.

We obtain slightly improved upper bounds on efficient approximability of the Maximum Independent Set problem in graphs of maximum degree at most B (shortly, B-MaxIS), for small B≥ 3. The degree-three case plays a role of the central problem, as many of the results for the other problems use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-MaxIS shows that one can achieve approximation ratio arbitrarily close to \(3-\frac{\sqrt{13}}{2}\). Improvements of an approximation ratio below \(\frac65\) for this case translate to improvements below \(\frac{B+3}{5}\) of approximation factors for B-MaxIS for all odd B. Consequently, for any odd B≥ 3, polynomial time algorithms for B-MaxIS exist with approximation ratios arbitrarily close to \(\frac{B+3}5-\frac{4(5\sqrt{13}-18)}5\frac{(B-2)!!}{(B+1)!!}\). This is currently the best upper bound for B-MaxIS for any odd B, 3≤ B<613.

We study asynchronous packet radio networks in which transmissions among nodes may be delayed. We consider the task of broadcasting a message generated by the source node. The timing of arrivals of messages is controlled by adversaries. We consider three different adversaries. The edge adversary can have a transmitted message delivered at different times to different recipients. The crash adversary is the edge one augmented by the ability to crash nodes. The node adversary can have a message received at arbitrary times, but simultaneously by all the recipients. A protocol specifies for each node how many times the message is retransmitted by this node, after it has been received. The total number of transmissions of nodes is defined to be a measure of performance of a broadcast protocol, and is called its work. The radio network is modeled as a graph and is given as input to a centralized algorithm. An aim of the algorithm could be either to find a broadcast protocol, possibly with additional properties, or to verify correctness of a given protocol. We give an algorithm to find a protocol correct against the edge adversary. The obtained protocol is work-exponential in general. This is an inherent property of the problem, as is justified by a lower bound. We develop a polynomial algorithm to verify correctness of a given protocol for a given network against the edge adversary. We show that a problem to decide if there exists a protocol, for a given network and of a specified work performance, is NP-hard. We extend some of these results to the remaining two adversaries.

We consider the problem of D-hop virtual path layout in ATM (Asynchronous Transfer Mode) networks. Given a physical network and an all-to-all traffic pattern, the problem consists of designing a virtual network with a given diameter D, which can be embedded in the physical one with a minimum congestion (the congestion is the maximum load of a physical link). Here we propose a method to solve this problem when the diameter is 2. We use this method to give an asymptotically optimal solution for the 2-hop virtual path layout problem for all-to-all traffic when the physical network is a mesh, a torus or a chordal ring.

We propose a family of novel schemes based on Chord retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to improve on the maximum/average number of hops for lookups and the routing table size per node.

We consider a 2-edge connected, undirected graph G=(V,E), with n nodes and m non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog² n) time and linear space algorithm to find a best swap edge for every edge of T, thus improving for \(m = o \left( n^2/\log^2 n \right)\) the previously known O(n ²) time and space complexity algorithm.

A black hole is a harmful host that destroys incoming agents without leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the location of the black hole. A team of agents, provided with a network map and executing the same protocol, solves the problem if at least one agent survives and, within finite time, knows the location of the black hole.

It is known that a team must have at least two agents. Interestingly, two agents with a map of the network can locate the black hole with O(n) moves in many highly regular networks; however the protocols used apply only to a narrow class of networks. On the other hand, any universal solution protocol must use Ω(n log n) moves in the worst case, regardless of the size of the team.

A universal solution protocol has been recently presented that uses a team of just two agents with a map of the network, and locates a black hole in at most O(n log n) moves. Thus, this protocol has both optimal size and worst-case-optimal cost. We show that this result, far from closing the research quest, can be significantly improved.

In this paper we present a universal protocol that allows a team of two agents with a network map to locate the black hole using at most O(n + d log d) moves, where d is the diameter of the network. This means that, without losing its universality and without violating the worst-case Ω(n log n) lower bound, this algorithm allows two agents to locate a black hole with Θ(n) cost in a very large class of (possibly unstructured) networks.

This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most δ, i.e., the tree-length δ graphs. For such graphs we construct additive 2δ-spanners with O(δnlog n) edges, and additive 4δ-spanners with O(δn) edges. This provides new upper bounds for chordal graphs for which δ=1. We also show a lower bound, and prove that there are graphs of tree-length δ for which every multiplicative δ-spanner (and thus every additive (δ–1)-spanner) requires Ω(n ^{1 + 1/Θ(δ)}) edges.

In this paper, we address a particular case of the general problem of λ labellings, concerning frequency assignment for telecommunication networks. In this model, stations within a given radius r must use frequencies that differ at least by a value p, while stations that are within a larger radius r′>r must use frequencies that differ by at least another value q. The aim is to minimize the span of frequencies used in the network. This can be modelled by a graph labelling problem, called the L(p,q) labelling, where one wants to label vertices of the graph G modelling the network by integers in the range [0;M], while minimizing the value of M. M is then called the λ number of G, and is denoted by λ \(_{q}^{p}\) (G).

Another parameter that sometimes needs to be optimized is the fact that all the possible frequencies (i.e., all the possible values in the span) are used. In this paper, we focus on this problem. More precisely, we want that: (1) all the frequencies are used and (2) condition (1) being satisfied, the span must be minimum. We call this the no-holeL(p,q) labelling problem for G. Let [0;M′] be this new span and call the ν number of G the value M′, and denote it by ν \(^{p}_{q}\)(G).

In this paper, we study a special case of no-hole L(p,q) labelling, namely where q=0. We also focus on some specific topologies: cycles, hypercubes, 2-dimensional grids and 2-dimensional tori. For each of the mentioned topologies cited above, we give bounds on the ν \(_{\rm 0}^{p}\) number and show optimality in some cases. The paper is concluded by giving new results concerning the (general, i.e. not necessarily no-hole) L(p,q) labelling of hypercubes.

The problem of routing traffic through a congested network is studied. The framework is that introduced by Koutsoupias and Papadimitriou where the network is constituted by m parallel links, each having a finite capacity, and there are n selfish (noncooperative) agents wishing to route their traffic through one of these links: thus the problem sets naturally in the context of noncooperative games. Given the lack of coordination among the agents in large networks, much effort has been lavished in the framework of mixed Nash equilibria where the agent’s routing choices are regulated by probability distributions, one for each agent, which let the system reach thus a stochastic steady state from which no agent is willing to unilaterally deviate. Recently Mavronicolas and Spirakis have investigated fully mixed equilibria, where agents have all non zero probabilities to route their traffics on the links. In this work we concentrate on constrained situations where some agents are forbidden (have probability zero) to route their traffic on some links: in this case we show that at most one Nash equilibrium may exist and we give necessary and sufficient conditions on its existence; the conditions relating the traffic load of the agents. We also study a dynamic behaviour of the network, establishing under which conditions the network is still in equilibrium when some of the constraints are removed. Although this paper covers only some specific subclasses of the general problem, the conditions found are all effective in the sense that given a set of yes/no routing constraints on each link for each agent, we provide the probability distributions that achieve the unique Nash equilibrium associated to the constraints (if it exists).

The mobile agent rendezvous problem consists of k ≥ 2 mobile agents trying to rendezvous or meet in a minimum amount of time on an n node ring network. Tokens and markers have been used successfully to achieve rendezvous when the problem is symmetric, e.g., the network is an anonymous ring and the mobile agents are identical and run the same deterministic algorithm. In this paper, we explore how token failure affects the time required for mobile agent rendezvous under symmetric conditions with different types of knowledge. Our results suggest that knowledge of n is better than knowledge of k in terms of achieving rendezvous as quickly as possible in the faulty token setting.

We study here the gossiping problem (all-to-all communication) in known radio networks, i.e., when all nodes are aware of the network topology. We start our presentation with a deterministic algorithm for the gossiping problem that works in at most n units of time in any radio network of size n. This is an optimal algorithm in the sense that there exist radio network topologies, such as: a line, a star and a complete graph in which the radio gossiping cannot be completed in less then n units of time. Furthermore, we show that there isn’t any radio network topology in which the gossiping task can be solved in time \(<\lfloor\log(n-1)\rfloor+2.\) We show also that this lower bound can be matched from above for a fraction of all possible integer values of n; and for all other values of n we propose a solution admitting gossiping in time ⌈log(n − 1)⌉ + 2. Finally we study asymptotically optimal O(D)-time gossiping (where D is a diameter of the network) in graphs with max-degree \(\Delta=O(\frac{D^{1-1/(i+1)}}{\log^{i} n}),\) for any integer constant i≥ 0 and D large enough.

Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. However, combining linearizability with efficiency in practical algorithms is difficult. A reconfigurable linearizable data service, called Rambo, was developed by Lynch and Shvartsman. This service guarantees consistency under dynamic conditions involving asynchrony, message loss, node crashes, and new node arrivals. The specification of the original algorithm is given at an abstract level aimed at concise presentation and formal reasoning about correctness. The algorithm propagates information by means of gossip messages. If the service is in use for a long time, the size and the number of gossip messages may grow without bound. This paper presents a consistent data service for long-lived objects that improves on Rambo in two ways: it includes an incremental communication protocol and a leave service. The new protocol takes advantage of the local knowledge, and carefully manages the size of messages by removing redundant information, while the leave service allows the nodes to leave the system gracefully. The new algorithm is formally proved correct by forward simulation using levels of abstraction. An experimental implementation of the system was developed for networks-of-workstations. The paper also includes analytical and preliminary empirical results that illustrate the advantages of the new algorithm.

We study the problem of designing fault tolerant routings in complete and complete bipartite optical networks. We show that this problem has strong connections to various fundamental problems in design theory. Using design theory approach, we find optimal f-tolerant arc-forwarding indexes for complete networks of a prime power order, and all complete bipartite networks. Similarly, we find almost exact values for f-tolerant optical indexes for these networks. Our work motivates an interesting relaxation of an extensively studied problem on mutually orthogonal Latin squares.

In this paper we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is \({\cal NP}\)-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. We improve the upper bounds of [11] both for the two-dimensional mesh of trees, and for the pyramid networks. We also present upper and lower bounds for other topologies: the higher-dimensional meshes of trees, and the trees of meshes networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, the presented upper bound almost matches the lower bound of [11].

Load balancing on a multi-processor system consists of redistributing tasks among processors so that all processors end up with roughly the same amount of work to perform. The token distribution problem is a variant of the load balancing problem where each task has unit-size and it represents an atomic element of work. We present an algorithm for computing a perfect token distribution (each processor has either ⌈ T/N ⌉ or \(\lfloor T/N \rfloor\) tasks, where N is the number of processors and T is the number of tasks scattered among processors) on distributed tree-connected networks having worst-case running time O(TD) (D denotes the diameter of the tree). The number of token exchanges exceeds the optimum by at most O(D min {T,N}).

In order to compute a perfect token distribution each node v must be able to store Θ(d _v (log T+log N)) bits, where d _v is the degree (number of adjacent nodes) of v. This is the first fully decentralized algorithm for computing perfect token distributions on arbitrary tree-connected networks which does not receive as input any kind of aggregate information about the network (e.g., number of nodes or total number of tokens).

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user has to follow a path leading to it from the root node. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment problem involves finding a set of hotlinks maximizing the gain in the expected cost. The paper addresses this problem in the more realistic greedy user model recently introduced in [3], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on trees.

We investigate the problem of sharing the cost of a multicast transmission in a wireless network where each node (radio station) of the network corresponds to (a set of) user(s) potentially interested in receiving the transmission. As in the model considered by Feigenbaum et al [2001], users may act selfishly and report a false ”level of interest” in receiving the transmission trying to be charged less by the system. We consider the issue of designing a so called truthful mechanisms for the problem of maximizing the net worth (i.e., the overall ”happiness” of the users minus the cost of the transmission) for the case of wireless networks. Intuitively, truthful mechanism guarantee that no user has an incentive in reporting a false valuation of the transmission. Unlike the ”wired” network case, here the cost of a set of connections implementing a multicast tree is not the sum of the single edge costs, thus introducing a complicating factor in the problem. We provide both positive and negative results on the existence of optimal algorithms for the problem and their use to obtain VCG truthful mechanisms achieving the same performances.

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k≥ 1. We investigate the time complexity of devising minimal-space all-shortest-path k-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k≥ 3, as well as whether a graph admits an all-shortest-path k-strict IRS, for every integer k≥ 4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case.

We study an on-line parallel job scheduling problem, where jobs arrive over list. A parallel job may require a number of machines for its processing at the same time. Upon arrival of a job, its processing time and the number of requested machines become known, and it must be scheduled immediately without any knowledge of future jobs. We present a 8-competitive on-line algorithm, which improves the previous upper bound of 12 by Johannes [8]. Furthermore, we investigate two special cases in which jobs arrive in non-increasing order of processing times or jobs arrive in non-increasing order of sizes. Better bounds are shown.

In this paper we study the range assignment problem in static ad-hoc networks on metric spaces. We consider the h-strong connectivity and h-broadcast problems on trees, high dimensional Euclidean spaces and general finite metric spaces. Both homogeneous and non-homogeneous cases are explored. We show that the h-broadcast problem is polynomial solvable on trees and present an O(n ²)-approximation algorithm for the h-strong connectivity problem on trees, where n is the number of stations. Furthermore, we propose a probabilistic O(log n loglog n)-approximation algorithm for the h-broadcast problem and a probabilistic O(n ² log n loglog n)-approximation algorithm for the h-strong connectivity problem on high dimensional Euclidean spaces and general metric spaces. In the case of high dimensional real normed spaces, if the distance-power gradient α≤ 1+O(logloglog n/loglog n), an O(log ^α n)-approximation algorithm and an O(n ² log ^α n)-approximation algorithm are developed for the h-broadcast problem and the h-strong connectivity problem, respectively. They are the first algorithms for the range assignment problem in static ad-hoc networks on general metric spaces. And the approximation ratio of O(log n loglog n) for the h-broadcast problem on general metric spaces is close to the known lower bound O(log n) [19].