Bertinoro Workshop on Adversarial  Modeling and Analysis of Communication Networks November 26 - December 2,  2006 University Residential Center of Bertinoro Bertinoro (Forlì), Italy

[ What the Meeting is About
| Important Dates
| Location
| How to Reach Bertinoro
| Schedule
| List of Participants
| Abstracts
| Organization and Sponsorship
| Local Weather Forecast]

What the Meeting is About

Important Dates

Location

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access.  >From the fortress you can enjoy a beautiful vista that stretches from the Tuscan Apennines to the Adriatic coast.

How to Reach Bertinoro

Tentative Schedule (liable to changes)

Notes: All breakfasts and lunches will be at Center Canteen. Dinners will be at restaurants in Bertinoro (or in Ravenna for those participating in Wednesday's excursion). 

Partial list of participants

•  Carme Alvarez, Universitat Politecnica de Catalunya 
•  Matthew Andrews,   Bell Labs
  
•  Yossi Azar,  Microsoft Research and Tel-Aviv University
  
•  Luca Becchetti,  Università di Roma "La Sapienza"
  
•  Maria Blesa,  Universitat Politecnica de Catalunya
•  Allan Borodin,   University of Toronro
•  Andrea Clementi, University of Roma II
  
•  Antonio  Fernandez,   Universidad Rey Juan Carlos
  
•  Pierre  Fraigniaud,   CNRS - LRI
  
•  David  Gamarnik,   MIT
  
•  Elias Koutsoupias, University of  Athens
•  Emmanuelle  Lebhar,   CNRS - LIAFA
  
•  Zvi Lotker,  Ben-Gurion University
  
•  Friedhelm  Meyer auf der Heide,   University of Paderborn
  
•  Boaz Patt-Shamir,   Tel-Aviv University
  
•  Pino  Persiano,   University of Salerno
  
•  Harald Raecke,  Toyota Technological Institute at Chicago
  
•  Christian Schindelhauer,  University of Freiburg
  
•  Maria Serna, Universitat Politecnica de Catalunya
•  Paul  Spirakis,   CTI
•  Rob van Stee,  University of Karlsruhe
•  Cliff Stein,   Columbia University
  
•  Prudence Wong,  University of Liverpool
•  Shmuel Zaks,   Technion
•  Lisa Zhang,   Bell Labs
  

Abstracts (in progress)

• Matthew Andrews, Bell Labs
  "Stability of the MaxWeight Routing and Scheduling Algorithm in Dynamic Graphs"

  The MaxWeight (or Load Balancing) algorithm is the most widely studied algorithm for routing and scheduling in packet switched networks. In this algorithm, each node maintains a separate queue for each possible destination. In every time step, each edge tries to move a packet between two queues for which the difference in height is maximum.

  In this talk we shall consider the case of dynamic graphs and show that the MaxWeight algorithm is stable (i.e. the queues cannot grow without bound) as long as the network is not overloaded. An important feature of our proof is that it holds even if nodes can become disconnected from the rest of the network for arbitrarily long periods.

  Time permitting we shall also briefly describe a project that is aiming to design a new MAC protocol for ad-hoc wireless networks based on the MaxWeight algorithm.

  Joint work with Kyomin Jung (MIT).

• Yossi Azar, Microsoft Research and Tel-Aviv University
  "Optimal Node Routing"

  We study route selection for packet switching in the competitive throughput model. In contrast to previous papers which considered competitive algorithms for packet scheduling, we consider the packet routing problem (specifically, output port selection in a node). We model the node routing problem as follows: a node has some number of input ports and some number of output queues. At each time unit, any number of new packets may arrive, each packet is associated with a subset of the output ports. Each output queue transmits packets in some arbitrary manner. Arrival and transmission are arbitrary and controlled by an adversary. The node routing algorithm has to route each packet to one of the allowed output ports, without exceeding the size of the queues. The goal is to maximize the number of the transmitted packets. We show that all non-refusal algorithms are 2-competitive. Our main result is an almost optimal e/(e-1} (approximately 1.58) -competitive algorithm, for a large enough queue size. For packets with arbitrary values (allowing preemption) we present a 2-competitive algorithm for any queue size.

  Joint work with Yoel Chaiutin.

• Luca Becchetti, Università di Roma "La Sapienza"
  "Adversarial Aspects of Web Spam"

  The Web is nowadays both an excellent medium for sharing information, as well as an attractive platform for delivering products and services. This platform is, to some extent, mediated by search engines in order to meet the needs of users seeking information. The Web contains numerous profit-seeking ventures that are attracted by the prospect of reaching millions of users at a very low cost. A large fraction of the visits to a Web site originate from search engines, and most of the users click on the first few results in a search engine. Therefore, there is an economic incentive for manipulating search engine's listings by creating pages that score high independently of their real merit. In practice such manipulation is widespread, and in many cases, successful. In this talk I will brielfy discuss some economic aspects of Web spamming and try to emphasize some possible directions of research in the area.

• Maria J. Blesa Aguilera, Universitat Politecnica de Catalunya
  "Stability of Communication Networks in the Presence of Adversarial Traffic and Failures: Models and Management"

  In this talk we deal with communication networks in which links or nodes may fail. We propose adversarial models for describing the traffic pattern occurring in this type of faulty systems and study properties concerning their stability (i.e., the hability of keeping the network load always bounded), specially under (non-trivial) underloaded worse-case scenarios. We show that, depending on how the system is organized and prepared to deal with failures, the dynamics of the system change and thus the conditions for stability. We propose different ways of link and node failure management and study how do they influence on the stability of faulty communication networks under the adversarial models proposed. We show that some failure managements can provoke the instability of even very simple networks.

• Andrea Clementi, University of Roma II
  "Communication in Dynamic Radio Networks"

  We study the completion time of distributed broadcasting protocols in \emph{dynamic} radio networks. The dynamic network is modelled by means of \emph{adversaries} and we consider two of them that are somewhat the extremal general cases. We first consider a favourable one, i.e., an oblivious, memoryless random adversary. At each time-slot $t$, a graph $G_t$ is selected according to the well-known random graph model $\sG(n,p)$. For any $p < 1-\epsilon$, we prove that any protocol has $\Omega(\log n)$ completion time and, for any $2/n \le p \le 1$, we derive an oblivious randomized protocol that has $O(\log n)$ completion time. This tight bound holds when the protocol knows $p$. When $p$ is unknown, we prove a lower bound $\Omega(\log^2 n /\log\log n)$ for any randomized oblivious homogeneous protocol and we provide a randomized oblivious homogeneous protocol having $O(\log^2 n)$ completion time. We observe that the above (poly)logarithmic upper bounds also hold when the random networks are with high probability sparse and disconnected.

  We then consider the deterministic (worst-case) adversary that, at each time, can make any network change. In this case, up to now, it is not even known whether finite expected completion time is achievable by randomized protocols. When the adversary is adaptive, we derive an $\Omega(n^2/\log n)$ lower bound for the completion time of any randomized broadcasting protocol. This bound is shown to be almost tight by providing a simple randomized oblivious protocol that works in $O(n^2)$ completion time. As for oblivious worst-case adversary, we prove that any oblivious randomized protocols has $\Omega(n^2/\log n)$ completion time. \noindent Our contribution provides the first strong analytical results on the broadcasting problem in fairly general models of dynamic radio networks. In particular, we note that the quadratic upper bound against this most powerful, adaptive adversary implies that no meaningful (realistic or not) dynamic adversary strategy exists yielding exponential completion time.

• Amir Epstein, Tel-Aviv University
  "A Quasi-PTAS for Unsplittable Flow on Line Graphs"

  We study the Unsplittable Flow Problem (\ufp) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for \ufp on line graphs, thereby ruling out an APX-hardness result, unless $\mathrm{NP} \ceq \mathrm{DTIME}(2^{\polylog(n)})$. Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.

  Earlier results on this problem included a polynomial time $(2+\eps)$-approximation under the assumption that no demand exceeds any edge capacity (the ``no-bottleneck assumption'') and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on \ufp, our results do not require a no-bottleneck assumption.

  Joint work with Nikhil Bansal, Amit Chakrabarti and Baruch Schieber.

• Antonio Fernandez, Universidad Rey Juan Carlos
  "A Continuous Model of Adversarial Queuing Theory"

  In this talk we generalize the Adversarial Queueing Theory
  (AQT) model to capture the dynamics of continuous scenarios in which the
  usually assumed synchronicity of the evolution is not required anymore. We
  propose model, named Continuous AQT (CAQT), in which
  packets can have arbitrary lengths, and the network links may have different
  speeds (or bandwidths) and propagation delays. We show that, in such a general
  model, having bounded queues implies bounded end-to-end packet delays and vice
  versa. From the network point of view, we show that networks with directed
  acyclic topologies are universally stable, i.e., are stable independently of the
  scheduling policies and the traffic patterns used in it, and that this even
  holds for traffic patterns that make links to be fully loaded. We also show that
  the characterization of the property of universal stability of networks is the
  same as in the AQT model and, therefore, decidable in polynomial time.
  
  Concerning packet scheduling policies, we show that the well-known LIS, SIS,
  FTG and NTS scheduling policies remain universally stable in our model.
  However, we present other scheduling policies that are unstable under the CAQT
  model, but universally stable under the AQT model. In this sense, the CAQT
  model is strictly stronger than the AQT model. Additionally, we show that the
  network features considered in the CAQT model, namely packet lengths,
  propagation delays and bandwidths, are important keynotes for the stability of
  the system.
  

• Pierre Fraigniaud, CNRS - LRI
  "Graph searching and other search games"

  This talk will survey the several variants of search games on graphs, including graph searching and cop-and-robber games. It will also present the connections between these games and graph parameters such as treewidth, pathwidth, etc.
  

• David Gamarnik, MIT
  "Undecidability results in the theory of queueing networks"

  Stability of queueing networks have been a subject of intensive research both in the computer science and operations research communities. While many special cases are known which provide sufficient or necessary conditions for stability, no sharp algorithmic characterization of stability was known for a broad class of scheduling policies. We consider the family of multiclass deterministic queueing network operating under buffer priority type scheduling policy and show that stability is an undecidable property, thus explaining the difficulty in obtaining tight characterization of stable networks. Our proof is based on a reduction from a Halting Problem of a counter machine.
  
  Joint work with Dmitriy Katz.

• David Hay, Technion
  "Packet-Mode Emulation of Output-Queued Switches"

  Most common network protocols (e.g., the Internet Protocol) work with variable size packets,
  whereas contemporary switches still operate with fixed size cells, which are easier to transmit
  and buffer. This necessitates packet segmentation and reassembly modules, resulting in
  significant computation and communication overhead that might be too costly as switches
  become faster and bigger.
  
  In this talk we consider an alternative mode of scheduling, in which packets are scheduled contiguously
  over the switch fabric. Specifically, we study such packet-mode scheduling for the combined input output
  queued (CIOQ) switch architecture and investigates its cost.
  
  We introduce frame-based schedulers that allow a packet-mode CIOQ switch with small speedup to
  mimic an ideal output-queued switch with bounded relative queuing delay. The schedulers are pipelined and
  are based on matrix decompositions.
  
  Joint work with Isaac Keslassy (EE, Technion) and Hagit Attiya (CS, Technion).

•  Elias Koutsoupias, University of Athens
  "Mechanisms for Scheduling"


• Emmanuelle Lebhar, CNRS - LIAFA
  "On augmented graphs navigability"

  This talk will survey some recent issues on small world algorihmic porperty based on the model presented by Kleinberg in 2000. Precisely, we will see several ways to augment a graph by extra edges so that greedy routing can computes polylogarithmic paths between any pair in the augmented graph, only using the original metric. For instance, the definition of the set of extra links can be inspired from an inherent hierarchical strucure of the graph, but can also be given via an embedding of the network into a metric close to Kleinberg original model. We will also see the limit of such schemes by exhibiting a graph family that cannot be augmented in such a way.

• Zvi Lotker, Ben-Gurion University
  "Instability of the FIFO protocol"

• Friedhelm Meyer auf der Heide, University of Paderborn
  "Scheduling and data management in dynamic networks"

  Dynamics in networks shows up in various ways, e.g., in mobile ad-hoc networks by the movement of the nodes or in peer-to-peer networks by inserting and removing nodes. Also "static" networks may exhibit a kind of dynamics, from the viewpoint of a user. In this lecture I will deal with modelling dynamics as on-line processes, and with developing and analysing on-line algorithms for two problems classes on dynamic networks. A main focus will be on develpoing suitable restrictions on the power of the adversary that changes the network, with the goal to forbid unrealistic dynamical behaviour and to allow on-line strategies with good competitive ratio. The two problem classes are:

  Local or Wide Areas Networks, with the Internet as a prime example, offer an enormous amount of free computing power. As this free power of the processors changes over time in an online fashion, scheduling becomes a new challenge. In this talk, I will present both experimental and theoretical analyses of strategies for scheduling processes in such a dynamic Web computing scenario, with an emphasis on modelling the dynamics of the changing free computing power.

  Page migration is a well examined, simple variant of data management in networks: An on-line stream of read requests from nodes to a data object must be processed with small costs. The read costs are proportional to the distance of the reading node to that, which holds the data object. The Paging strategy may migrate this object at a cost proportional to "size of the object" * "migration distance". Page migration on dynamic networks assumes not only the queries, but also the movement of the nodes of the network to be an on-line stream. Thus modelling and development of provably good on-line algorithms represent a particularly interesting challenge.

• Boaz Patt-Sahmir, Tel-Aviv University
  "The Greedy Algorithm for Buffer Management"

  We consider the scenario where packets arrive in an unconstrained rate to a buffer, but can be drained only at a bounded rate. In the buffer management problem, the question is which packets to discard so as to minimize the damage caused by buffer overflows. In this talk we give a selective survey of the problem in the model where each packet has a value, and review some results concerning the Greedy algorithm which discards the lowest-value packets upon overflow.

• Pino Persiano, University of Salerno
  "Mechanisms with Verification"

  A social choice function A is implementable with verification if there exists a payment scheme P such that (A,P) is a truthful mechanism for verifiable agents [Nisan and Ronen STOC 99]. In this paper we address the following questions. Given an objective function M, does there exist a social choice function that is implementable with verification and that minimizes (or maximizes) M? From a more algorithmic point of view, we ask whether there exists an {\em efficient} social choice function A that is implementable with verification and $\alpha$-approximates M.

  We give a simple sufficient condition for a social choice function to be implementable with verification for comparable types. Comparable types are a generalization of the well studied one-parameter agents. Based on this characterization, we show that a large class of objective functions M admit social choice functions that are implementable with verification and minimize (or maximize) M.

  We then focus on the well-studied case of one-parameter agents. We give a general technique for constructing efficiently computable social choice functions that minimize or approximately minimize objective functions that are non-increasing and neutral (these are functions that do not depend on the valuations of agents that have no work assigned to them).

  As a corollary we obtain efficient mechanisms with verification for some hard scheduling problems on related machines. Finally, we show that existing online algorithms for scheduling jobs to minimize the $L_p$ norm can be used to obtain online mechanisms with verification.

  Joint work with: V. Auletta, R. De Prisco, P. Penna and C. Ventre

• Harald Raecke, Toyota Technological Institute at Chicago
  "An Overview on Oblivious Routing"

  In an oblivious routing scheme the routing paths are selected independently of the traffic in the network, and therefore these schemes can be implemented very efficiently in a distributed environment. This talk gives an overview about the field starting with the early work by Valiant and Brebner who design oblivious routing schemes for the hypercube.

• Gabriel Scalosub, Technion
  "Jitter Regulation for Multiple Streams"

  For widely-used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of a traffic is typically captured by its delay jitter, i.e., the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately. This paper investigates the problem of minimizing jitter in such an environment, using a fixed-size buffer.
  
  We show that the offline version of the problem can be solved in polynomial time, by introducing an efficient offline algorithm that finds a release schedule with optimal jitter. When regulating $M$ streams in the online setting, we take a competitive analysis point of view and note that previous results by Mansour and Patt-Shamir can be extended to an online algorithm that uses a buffer of size $2MB$ and obtains the optimal jitter possible with a buffer of size $B$.
  The question arises whether such a resource augmentation is essential. We answer this question in the affirmative, by proving a lower bound that is tight up to a factor of $2$, thus showing that jitter regulation does not scale well as the number of streams increases unless the buffer is sized-up proportionally.
  
  This is joint work with David Hay.
  

• Christian Schindelhauer, University of Freiburg
  "Mobility in Ad Hoc Networks"

  We surveys mobility patterns and mobility models for wirelss networks. Mobility patterns are classified into the following types: pedestrians, vehicles, aerial, dynamic medium, robot, and outer space motion. We present the characteristics of each and shortly mention the specific problems.

  We shortly present the specifics of cellular networks, mobile ad hoc networks, and sensor networks regarding mobility. Then, we present the most important mobility models from the literature. At last we give a brief discussion about the state of research regarding mobility in wireless networks.

• Mordechai Shalom, Tel Hai Academic College
  "On minimizing the number of ADMs - improved bounds for general networks"

  A relatively new optimization criterion in studies of optical networks is that of minimizing the total number of ADMs. In these networks each given lightpath uses one ADM device at each of its two endpoints, and it is assigned a color, and one ADM can be used by two lightpaths provided they share the same color. In the talk a basic algorithm of Calinescu and Wan is investigated. This algorithm uses a preprocessing phase, where cycles that include at most a given number of lightpaths are eliminated. Optimal bounds are presented for the performance of the algorithm without its preprocessing phase, and improved bounds are presented for its performance in the general case with preprocessing. The talk is based on a work with Michele Flammini and Shmuel Zaks. The talk is self-contained, and assumes no a-priori knowledge of optical networks.

• Paul Spirakis, CTI
  "Security Network Games"

  We introduce here a model of a network under attack by a multitude of malicious, selfish entities. The defense of the network is limited and we assume the simplest possible (ie the defense of an edge). We model this as a strategic game . We study the structure and computability of its Nash Equilibria (which have to be mixed). We also introduce a new measure, the Price of Defense, that captures the effectiveness of such defense mechanisms. Our study reveals a very strong relation of the graph-theoretic structure of the network with the form of Equilibria that can be achieved.

• Cliff Stein, Columbia University
  "Bidding Strategies for Advertisers in Internet Auctions"

  Ad auctions are a major source of revenue for many internet companies. In order to participate, an advertiser submits a set of keywords, a bid on each keyword, and a budget. A large advertiser may choose tens of thousands of keywords. Although the advertiser bids on keywords, the users submit queries that may match multiple keywords. Thus, even for an advertiser who understands how his competitors are bidding, it is a challenging problem to figure out how to manage an ad campaign.

  In this talk, we study the problem of bidding from an advertiser's point of view, as someone who wants to maximize the number of clicks received, subject to a budget constraint. We first explain how to model the problem, and show that almost any reasonable model is NP-hard to optimize exactly. We then focus on simple bidding strategies. We show, perhaps surprisingly, that it is possible to get at least a 1-1/e fraction of the maximum possible number clicks by bidding only one or two distinct amounts on all keywords. In some preliminary experiments on real data, this simple strategy for bidding gets within 2% of the absolute maximum possible number of clicks.

  This talk describes work done at Google, NY jointly with Jon Feldman, S. Muthukrishnan and Martin Pal.

• Rob van Stee, University of Karlsruhe
  "Covering selfish machines"

  We consider the machine covering problem for selfish related machines. For a constant number of machines, $m$, we show a monotone polynomial time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We also present an FPTAS for the classical machine covering problem (the previous best result was a PTAS) and use this to give a monotone FPTAS.

  Additionally, we give a monotone approximation algorithm with approximation ratio $\min(m,(2+\eps)s_1/s_m)$ where $\eps>0$ can be chosen arbitrarily small and $s_i$ is the (real) speed of machine $i$. Finally we give improved results for two machines.

  Our paper presents the first results for this problem in the context of selfish machines.

• Prudence Wong, University of Liverpool
  "Atomic Selfish Routing in Parallel Link Networks"

  We consider the problem of routing a set of selfish users in a network with the objective of minimizing total latency experienced by all the users. In an environment in which each selfish user is aware of the situation facing all other users, a Nash equilibrium is a combination of choices from which no user has an incentive to unilaterally move away. Nash equilibria are known not to always optimize overall performance. The price of anarchy (PoA) is defined as the ratio between the worst possible Nash equilibrium and the social optimum.

  In this talk, we focus on atomic selfish routing in parallel link networks in which there is a finite number of users each carrying a non-negligible amount of traffic (as opposed to the more well studied case where there are infinitely many users each carrying an infinitesimal amount of traffic. We discuss how to improve the price of anarchy by using edge pricing and Stackelberg strategy.

• Shmuel Zaks, Technion
  "Minimizing the number of ADMs with and without traffic grooming: complexity and approximability"

  A relatively new optimization criterion in studies of optical networks is that of minimizing the total number of ADMs. In these networks each given lightpath uses one ADM device at each of its two endpoints, and it is assigned a color, so that at most g lightpaths of the same color can share an edge. Lightpaths of the same color that share an endpoint can use a common ADM at that endpoint. In the talk recent results concerning the complexity and approximability of this optimization problem will be discussed. Results will be presented for the basic case where traffic grooming is not allowed (g=1), and for the general case of traffic grooming (g>1). The talk is based on papers co-authored with Michele Flammini, Gianpiero Monaco, Luca Moscardelli and Mordechai Shalom. The talk is self-contained, and assumes no a-priori knowledge of optical networks.

• Lisa Zhang, Bell Labs
  "Scheduling for wireless systems"

  We consider a basestation transmitting data to a set of mobile users. At each time step the basestation receives information about the channel conditions to each user. These channel conditions are time-varying and user-dependent. The job of the scheduler is to pick a user to serve. In recent years this problem has received a great deal of attention.  In the first part of the talk we given an overview of some specific models that arise from 3rd generation wireless standards.  We summarize some of the main theoretical results and discuss the performance of scheduling algorithms that are implemented in practice.

  Time permitting, we will also consider the problem of scheduling wireless data in systems such as 802.16 (Wimax). Each scheduling decision involves constructing a frame of one or more time slots. Within each time slot multiple carriers must be assigned to users.  We present some recent results in understanding the complexity of the multi-carrier scheduling problem.

Organization and Sponsorship

Scientific Organizing Committee	Thomas Erlebach
	Adi Rosen
Local Organization
	Eleonora Campori, Ce.U.B.
Sponsored by	BICI   Bertinoro International Center for Informatics