April 2005 - tr-announce - lists.rwth-aachen.de

2005-08: A New Satisfiability Algorithm With Applications To Max-Cut
by Volker Stolz 22 Apr '05

22 Apr '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: A New Satisfiability Algorithm With Applications To Max-Cut Joachim Kneis, Peter Rossmanith AIB 2005-08 We prove an upper bound of m/5.217+3 on the treewidth of a graph with m edges. Moreover, we can always find efficiently a set of no more than m/5.217 nodes whose removal yields a very simple graph. As an application, we immediately get simple algorithms for several problems, including Max-Cut, Max-2-SAT and Max-2-XSAT. The resulting algorithms have running times of O*(2^t/5.217), where t is the number of distinct clause types. In particular, this implies a record-breaking time complexity of O*(2^m/5.217).

1 0

2005-07: Botnet Tracking: Exploring a Root-Cause Methodology to Prevent Distributed Denial-of-Service Attacks
by Volker Stolz 21 Apr '05

21 Apr '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Felix C. Freiling, Thorsten Holz, Georg Wicherski Botnet Tracking: Exploring a Root-Cause Methodology to Prevent Distributed Denial-of-Service Attacks AIB 2005-07 Abstract: Denial-of-Service (DoS) attacks pose a significant threat to the Internet today especially if they are distributed, i.e., launched simultaneously at a large number of systems. Reactive techniques that try to detect such an attack and throttle down malicious traffic prevail today but usually require an additional infrastructure to be really effective. In this paper we show that preventive mechanisms can be as effective with much less effort: We present an approach to (distributed) DoS attack prevention that is based on the observation that coordinated automated activity by many hosts needs a mechanism to remotely control them. To prevent such attacks, it is therefore possible to identify, infiltrate and analyze this remote control mechanism and to stop it in an automated fashion. We show that this method can be realized in the Internet by describing how we infiltrated and tracked IRC-based botnets which are the main DoS technology used by attackers today.

1 0

2005-06: Adaptive Routing with Stale Information
by Volker Stolz 08 Apr '05

08 Apr '05

The following technical report is available from http://aib.informatik.rwth-aachen.de/: Adaptive Routing with Stale Information Simon Fischer, Berthold Vöcking AIB 2005-06 We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided. In our theoretical model, the network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. >From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges. We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large. In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

1 0