Top

2006 | Book

Read chapter Read first chapter

Combinatorial and Algorithmic Aspects of Networking

Third Workshop, CAAN 2006, Chester, UK, July 2, 2006. Revised Papers

Editor: Thomas Erlebach

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Frontmatter

Invited Lecture

Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks

Abstract

Ad-hoc wireless networks have no wired infrastructure. Instead, they consist of a collection of radio stations S={1,2,...,n} deployed in a given region and connected by wireless links. Each station is assigned a transmission range, and a station t can correctly receive the transmission of another station s if and only if t is within the range of s. The overall range assignment, r: S→R ⁺, determines a (directed) transmission graph G _r. The transmission range of a station depends on the energy invested by the station. In particular, the power P _s required by a station s to correctly transmit data to another station t must satisfy the inequality \(P_s \ge {\tt dist}(s,t)^{\alpha}\), where dist(s,t) is the Euclidean distance between s and t and α≥1 is the distance-power gradient. The value of α may vary from 1 to more than 6 depending on the environment conditions at the location of the network (see [16]).

David Peleg

Contributed Papers

The Price of Anarchy in Selfish Multicast Routing

Abstract

We study the price of anarchy for selfish multicast routing games in directed multigraphs with latency functions on the edges, extending the known theory for the unicast situation, and exhibiting new phenomena not present in the unicast model. In the multicast model we have N commodities (or player classes), where for each \( i=1,\hdots,N\), a flow from a source s _i to a finite number of terminals \(t_i^1,\hdots,t_i^{k_i}\) has to be routed such that every terminal t _i ^j receives flow n _i∈ℝ_≥ 0.

One of the significant results of this paper are upper and lower bounds on the price of anarchy for edge latencies being polynomials of degree at most p with non-negative coefficients. We show an upper bound of \((p+1)\cdot\frac{\nu^{p+1}}{\nu^*}\) in some variants of multicast routing. We also prove a lower bound of ν ^p, so we have upper and lower bounds that are tight up to a factor of (p+1)ν. Here, ν and ν ^* are network and strategy dependent parameters reflecting the maximum/minimum consumption of the network. Both are 1 in the unicast case. Our lower bound of ν ^p, where in the general situation we have ν>1, shows an exponential increase compared to the Roughgarden bound of O(p/lnp) for the unicast model. This exhibits the contrast to the unicast case, where we have Roughgarden’s (2002) result that the price of anarchy is independent of the network topology. To our knowledge this paper is the first thorough study of the price of anarchy in the multicast scenario. The approach may lead to further research extending game-theoretic network analysis to models used in applications.

Andreas Baltz, Sandro Esquivel, Lasse Kliemann, Anand Srivastav

Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem

Abstract

Let a communication network be modelled by a directed graph G=(V,E) of n nodes and m edges, and assume that each edge is owned by a selfish agent, which privately holds a pair of values associated with the edge, namely its cost and its length. In this paper we analyze the problem of designing a truthful mechanism for computing a spanning arborescence of G rooted at a fixed node r ∈V having minimum cost (as computed w.r.t. the cost function) among all the spanning arborescences rooted at r which satisfy the following constraint: for each node, the distance from r (as computed w.r.t. the length function) must not exceed a fixed bound associated with the node. First, we prove that the problem is hard to approximate within better than a logarithmic factor, unless NP admits slightly superpolynomial time algorithms. Then, we provide a truthful single-minded mechanism for the problem, which guarantees an approximation factor of (1+ε)(n–1), for any ε>0.

Davide Bilò, Luciano Gualà, Guido Proietti

On the Topologies of Local Minimum Spanning Trees

Abstract

This paper is devoted to study the combinatorial properties of Local Minimum Spanning Trees (LMSTs), a geometric structure that is attracting increasing research interest in the wireless sensor networks community. Namely, we study which topologies are allowed for a sensor network that uses, for supporting connectivity, a local minimum spanning tree approach. First, we refine the current definition of LMST realizability, focusing on the role of the power of transmission (i.e., of the radius of the covered area). Second, we show simple planar, connected, and triangle-free graphs with maximum degree 3 that cannot be represented as an LMST. Third, we present several families of graphs that can be represented as LMSTs. Then, we show a relationship between planar graphs and their representability as LMSTs based on homeomorphism. Finally, we show that the general problem of determining whether a graph is LMST representable is NP-hard.

P. F. Cortese, G. Di Battista, F. Frati, L. Grilli, K. A. Lehmann, G. Liotta, M. Patrignani, I. G. Tollis, F. Trotta

Distributed Routing in Tree Networks with Few Landmarks

Abstract

We consider the problem of finding a short path between any two nodes of a network when no global information is available, nor any oracle to help in routing. A mobile agent, situated in a starting node, has to walk to a target node traversing a path of minimum length. All information about adjacencies is distributed to certain nodes called landmarks. We wish to minimize the total memory requirements as well as keep the memory requirements per landmark to reasonable levels. We propose a landmark selection and information distribution scheme with overall memory requirement linear in the number of nodes, and constant memory consumption per non-landmark node. We prove that a navigation algorithm using this scheme attains a constant stretch factor overhead in tree topologies, compared to an optimal landmark-based routing algorithm that obeys certain restrictions. The flexibility of our approach allows for various trade-offs, such as between the number of landmarks and the size of the region assigned to each landmark.

Ioannis Z. Emiris, Euripides Markou, Aris Pagourtzis

Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs

Abstract

We consider scheduling problems that are motivated by an optimization of the transmission schedule of a smart antenna. In these problems we are given a set of messages and a conflict graph that specifies which messages cannot be transmitted concurrently. In our model the conflict graph is a unit circular-arc graph.

Two variants of the problem are considered: c-mbl and nu-c-mbl. In c-mbl, the messages have unit demands, whereas in nu-c-mbl demands are arbitrary. We present an optimal algorithm for c-mbl and a 3-approximation algorithm for nu-c-mbl.

Guy Even, Shimon Shahar

On Minimizing the Number of ADMs – Tight Bounds for an Algorithm Without Preprocessing

Abstract

Minimizing the number of electronic switches in optical networks is a main research topic in recent studies. In such networks we assign colors to a given set of lightpaths. Thus the lightpaths are partitioned into cycles and paths. The switching cost is minimized when the number of paths is minimized. The problem of minimizing the switching cost is NP-hard, and approximation algorithms have been suggested for it. Many of these algoritms have a preprocessing stage, in which they first find cycles. The basic algorithm eliminates cycles of size at most l, and is known to have a performance guarantee of \(OPT+\frac{1}{2}(1+\epsilon)N\), where OPT is the cost of an optimal solution, N is the number of lightpaths, and \(0 \leq \epsilon \leq \frac{1}{l+2}\), for any given odd l. Without preprocessing phase (i.e. l=1), this reduces to \(OPT + \frac{2}{3} N\). We develop a new technique for the analysis of the upper bound and prove a tight bound of \(OPT+ \frac{3}{5}N\) for the performance of this algorithm.

Michele Flammini, Mordechai Shalom, Shmuel Zaks

Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP

Abstract

In this paper we improve the quality of a recently suggested class of construction heuristics for the Asymmetric Traveling Salesman Problem (ATSP), namely the Contract-or-Patch heuristic. Our improvement is based on replacing the selection of each path to be contracted after deleting a heaviest arc from each short cycle in an Optimal Assignment Problem Solution (OAPS) by contracting a single arc from a short cycle in an OAPS with the largest upper tolerance with respect to one of the relaxed ATSP. The improved algorithm produces higher-quality tours than all previous COP versions and is clearly outperforming all other construction heuristics on robustness.

Boris Goldengorin, Gerold Jäger, Paul Molitor

Acyclic Type-of-Relationship Problems on the Internet

Abstract

We contribute to the study of inferring commercial relationships between autonomous systems (AS relationships) from observable BGP routes. We deduce several forbidden patterns of AS relationships that impose a certain type of acyclicity on the AS graph. We investigate algorithms for solving the acyclic all-paths type-of-relationship problem, i.e., given a set of AS paths, find an orientation of the edges according to some types of AS relationships such that the oriented AS graph is acyclic (with respect to the forbidden patterns) and all AS paths are valley-free. As possible AS relationships we include customer-to-provider, peer-to-peer, and sibling-to-sibling. Moreover, we examine a number of problem versions parameterized by sets K and U where K is the set of edge types available for describing explicit pre-knowledge and U is the set of edge types available for completion of partial orientations. A complete complexity classification of all 56 cases (8 type sets for pre-knowledge and 7 type sets for completion) is given. The most relevant practical result is a linear-time algorithm for finding an acyclic and valley-free completion using customer-to-provider relations given any kind of pre-knowledge. Interestingly, if we allow sibling-to-sibling relations for completions then most of the non-trivial inference problems become NP-hard.

Sven Kosub, Moritz G. Maaß, Hanjo Täubig

Minimum-Energy Broadcasting in Wireless Networks in the d-Dimensional Euclidean Space (The α≤d Case)

Abstract

We consider the problem of minimizing the total energy assigned to nodes of wireless network so that broadcasting from the source node to all other nodes is possible. This problem has been extensively studied especially under the assumption that the nodes correspond to points in the Euclidean two- or three-dimensional space and the broadcast range of a node is proportional to at most the α root of the energy assigned to the node where α is not less than the dimension d of the space. In this paper, we study the case α≤d, providing several tight upper and lower bounds on approximation factors of known heuristics for minimum energy broadcasting in the d-dimensional Euclidean space.

Andrzej Lingas, Mia Persson, Martin Wahlen

Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks

Abstract

Gossiping is a communication primitive where each node of a network possesses a unique message that is to be communicated to all other nodes in the network. We study the gossiping problem in known topology radio networks where the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. In addition we consider the case where it is only possible to transmit a unit size message in each time step. This gives a more realistic model than if arbitrary length messages can be sent during each time step, as has been the case in most previous studies of the gossiping problem. In this paper, we propose an optimal randomized schedule that uses O(nlogn) time units to complete the gossiping task with high probability in any radio network of size n. This matches the lower bound of Ω(nlogn) by Gąsieniec and Potapov in [17] [TCS’02]. Our new gossiping schedule is based on the notion of a gathering spanning tree proposed by Gąsieniec, Peleg and Xin in [19] [PODC’05].

Fredrik Manne, Qin Xin

Backmatter

Title: Combinatorial and Algorithmic Aspects of Networking
Editor: Thomas Erlebach
Publisher: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-48824-8
Print ISBN: 978-3-540-48822-4
DOI: https://doi.org/10.1007/11922377

Springer Professional

Combinatorial and Algorithmic Aspects of Networking

Third Workshop, CAAN 2006, Chester, UK, July 2, 2006. Revised Papers

Table of Contents

Frontmatter

Invited Lecture

Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks

Contributed Papers

The Price of Anarchy in Selfish Multicast Routing

Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem

On the Topologies of Local Minimum Spanning Trees

Distributed Routing in Tree Networks with Few Landmarks

Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs

On Minimizing the Number of ADMs – Tight Bounds for an Algorithm Without Preprocessing

Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP

Acyclic Type-of-Relationship Problems on the Internet

Minimum-Energy Broadcasting in Wireless Networks in the d-Dimensional Euclidean Space (The α≤d Case)

Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks

Backmatter

Premium Partner