Start · Persons · Teaching · Research · Conferences · Guests · Contact

Algorithmics of Large and Complex Networks

Subprojects SR 7/9: Overview

3rd Phase (2005-2007): Game-Theoretic Equilibria in Unicast and Multicast Networks

Researchers

Non-Cooperative Multicast Routing

Multicast means sending information from one sender (called source) to several receivers (called terminals) at the same time through a communication network. Transfer through a link of the network takes time, depending on the total amount of data which is sent down the link (we speak of latency here). If there are several users sharing the network, we have a competitive situation.

Game-theoretic approaches try to analyze such situations and to make predictions about the performance of the system. Of special interest are optimal routings and Nash equilibria. The former are routings which minimize some global objective function, typically the total latency experienced by all the users. This function is called the social cost function. Nash equilibria on the other hand are routings in which no individual user has an incentive to deviate from the current routing decision (given that all other users keep theirs). We assume that users do not care about the social cost, but just about their individual costs.

As a game-theoretic framework, we use the Wardrop model, which assumes an infinite number of users each of them controlling a negligible amount of traffic. The Wardrop model has been used for the unicast case (i.e., where we only have one terminal for each source) before, and extensive studies have been done. However, the multicast case exhibits new phenomena, which makes further research necessary. We are specially interested in:

Example: Data has to be routed from the one node at the bottom to all the upper nodes at the top simultaneously. The horizontal links are very fast compared to the bottom-up links. This simple network exhibits a very high coordination ratio, i.e., its performance is far away from the optimum when shared by non-cooperative users.

An example network

Characterizing Worst-Case Equilibria in the KP Model

The KP model (introduced by Koutsoupias and Papadimitriou) deals with much simpler networks than we use for our multicast studies. It considers only one source and one terminal and a number of parallel links in between. However, in contrast to the Wardrop model, the number of users is finite. Probabilistic issues are also introduced, as we allow mixed strategies, i.e., the routing decisions of the users are deferred, and they only have to specify how likely it is that they will choose a certain routing. Flow is unsplittable in this model. Hence, the routing decision of a single user consists simply of naming one of the links.

Some terminology: Possible routing decisions of a single user are also called strategies. A strategy profile is a vector of strategies: one for each user. A mixed strategy (for a certain user) is a probability distribution on the strategies from which this user can choose. A mixed strategy profile is a vector of mixed strategies, one for each user. Individual and social costs are measured in terms of expectation. A Nash equilibrium is a mixed strategy profile, in which no user has an incentive to deviate from his own mixed strategy (given the mixed strategies of all other users).

In this setting, there can be several Nash equilibria with different social costs. It is still an open problem to charaterize worst-case equilibria in this model.

Correlated Equilibria and Maximum Latencies

As in the KP model, we consider a finite number of users. A correlated strategy is a probability distribution on the set of all strategy profiles. Mixed strategy profiles hence are special cases of correlated strategies. By allowing correlated strategies, we can model coalition aspects of routing games.

Work has already been done in this model for certain conceptions of social costs (see, e.g., Christodoulou and Koutsoupias). One of the probabilistically most challenging conception of social cost is the maximum over the individual costs of all users. In this project, we develop and apply appropriate probabilistic tools (concentration results, etc.) to tackle this maximum social cost.

Computation of Nash Equilibria

In the unicast case, Nash equilibria can be computed rather easily by solving a convex optimization problem. The multicast situation, however, seems to escape this approach and to require a different treatment. We aim at the developement of efficient algorithms for this problem. In addition, we are implementing and extending existing algorithms for the unicast case with the aim of creating a programming library with a documented interface.

2nd Phase (2003-2005): Design of Efficient Architectures and Algorithms for Multicast Networks

Researchers

General Packing Problems and Block Solvers

We developed an approximation algorithm for a general packing problem including the multicast problem. The algorithm is based on methods of convex optimization. The considered packing problem is of the form

$\displaystyle \begin{array}{lc} (P) & \lambda^* ~=~ \min \{ \lambda ~\vert~ f(x) \le \lambda e\}, \end{array} $

where $f : B o \mathbf{Z}^M$ is a vector of $M$ non-negative convex functions, $B$ is a non-empty convex set and $e$ is the vector with all components equal to 1. Grigoriadis and Khachiyan have given a $(1+\epsilon)$ approximation for this problem, provided that the optimization problem $\Lambda(p) = \min_{x \in B} p^T f(x)$ is approximable within $1 + \varepsilon/6$. We generalized their method for the case of approximablity within $c \ge 1$. We have shown that $O(M ( \epsilon^{-2}\ln \varepsilon^{-1} +ln M))$ calls to the block solver are sufficient to guarantee an approximation ratio of $c (1 + \epsilon)$. This result can be directly applied to the multicast congestion problem, where the block problem is the classical Steiner tree problem.

Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods

We improved the explicit construction developed in the 1st Phase by means of a new number theoretic approach: a generalization of the Erdos-Heilbronn conjecture on the size of restricted sums implies that $N \lceil \sqrt{3n/4} ceil + 2n \lceil \sqrt{3n/4} ceil \lceil \sqrt{N} ceil$ edges suffice for arbitrary choices of $n$ and $N$. Recently, Ahlswede and Aydinian gave an explicit construction based on the theorem of Kruskal and Katona using only $(1 + o(1)) \cdot N \log_2(N)$ edges in case $n < N ^ {1/\sqrt{\log_2 N}}$.

It is remarkable that Ahlswede/Aydinian's as well as our constructions are premised on combinatorial methods. This underlines the fact that direct methods for the design of expanders and communication networks are sometimes superior to eigenvalue based methods (e.g. Ramanujan graphs), as observed by Wigderson and Zuckerman in 1993.

1st Phase (2001-2003): Design of Efficient Architectures and Algorithms for Multicast Networks

Researchers

Task Formulation

Internet communication keeps growing tremendously. The increasing demand of bandwidth for data transfer enhances the requirements concerning network topology and, in particular, electrical and optical switches. To minimize data delay and to avoid blocking of flows, fast intelligent routing algorithms are needed. New communication services, such as teleconferencing and video-on-demand, rely on stable non-blocking point to multipoint connections (multicast). However, conventional switches are either designed for symmetrical point to point (unicast) communication (e.g. Banyan switches) or their crosspoint complexity grows quadratically with their number of ports. While many aspects of the unicast switch design are well-studied, the design of efficient multicast switches requires new methodical efforts.

Routing under Congestion Minimization

A communication network can be modelled as an undirected graph $G=(V,E)$, $\vert V\vert=n$, $\vert E\vert=m$, where each node represents a computer that is able to receive, copy and send packets of data. In multicast traffic, several nodes have a simultaneous demand to receive a copy of a single packet. These nodes together with the packet's source specify a multicast request $S$. Meeting the request means to establish a connection represented by a Steiner tree with terminal set $S$, i.e., a subtree of $G$ containing $S$ and having no leaf in $V\setminus S$. Given $G$ and a set of multicast requests it is natural to ask about Steiner trees such that the maximum edge congestion, i.e., the maximum number of trees sharing an edge is as small as possible.

Problem: Given $S_1,...,S_k \subseteq V$. Find Steiner trees $T_1,...,T_k$ where $S_i \subseteq V(T_i)$, such that the maximum edge congestion

\begin{displaymath}\max_{e\in E}\vert\{T\in\{T_1,\ldots,T_k\}~\vert~e\in E(T)\}\vert\end{displaymath}

is minimum.

This NP hard problem can be formulated as an integer linear program. In previous work it was shown that the corresponding LP relaxation can be solved in polynomial time with the Ellipsoid method. Randomized rounding yields an integral solution that approximates the optimum within a factor of $O(\log n)$. However, there is no practically efficient implementation of the ellipsoid method. We generalized the combinatorial multicommodity flow algorithm of Garg and Könemann to obtain a considerably faster algorithm for approximating the integer optimum within $O(OPT+\log n)$. Several variants of the algorithm have been implemented and tested against a fast heuristic.

Design of Sparse Asymmetric Connectors

Asymmetric connectors play an important role for constructing switches in multicast communication networks. Their task is to connect $n$ inputs to $N$ outputs, $n<N$, such that all inputs can send data to arbitrary outputs simultaneously. The conventional solution is a crossbar, i.e., the complete bipartite graph $K_{n,N}$ with $n\cdot N$ edges. Known theoretical solutions with $O(N+n \log n)$ edges use $\Omega$ ($\log N$) intermediate stages, which is not acceptable for fast routing. We study the problem of constructing sparse asymmetric connectors in the following formulation:

Problem: Sparse $(n,N)$ connectors of depth $k$ Given $n, N, k \in\mathbf{N}$ with $n<N$. Construct a graph $G=(V,E)$ (where the set of nodes $V$ is partitioned into the set $I$ of $n$ inputs, the set $L$ of intermediate nodes, and the set $O$ of $N$ outputs) such that for any injective mapping $f: I o O$ there are $n$ vertex disjoint paths of length $k$ connecting each $i\in I$ to $f(i)$.

Of special interest is the case $k=2$ and $n<\sqrt{N}$. For this, we consider connectors with the following general structure: $I$ and $L$ are completely connected (due to $\vert I\vert=n<\sqrt{N}$, this is efficient as long as $\vert L\vert=O(n)$); $L$ and $O$ are connected by a minimum number of edges such that Hall's condition, $\vert\Gamma(S)\vert\ge\vert S\vert$ for all $S\subseteq O$ with $\vert S\vert\le n$, is satisfied (this is equivalent to the existence of a perfect matching between each $n$-element subset of $O$ and some $n$-element subset of $L$).

We found two different explicit constructions for $(n,N)$ connectors of depth 2 with $(1+o(1))\cdot(N\sqrt{n}+n\sqrt{Nn})$ edges. For $n\le N^{\frac{1}{2}-\varepsilon}$ the existence of $(n,N)$ connectors of depth 2 with $O(N)$ edges can be shown by a simple probabilistic analysis (due to Amnon Ta-Shma).

Selected Publications from the 1st and 2nd Phase

last modified on Fri Nov 11 15:15:43 2011, Lasse Kliemann
Valid XHTML 1.0   Valid XHTML 1.0 Strict   Valid CSS!