Der Kalender liegt auch im csv-Format (z.B. für Microsoft Outlook) und im ics/iCal-Format vor.
Zeit: 23.02.2012, 14:00 Uhr
Ort: Informatik-Zentrum, Raum 5056, Ahornstr. 55
Referent: Dipl. Inform. Stefan Götz, Informatik IV, RWTH Aachen
Thema: Supporting Diversity and Evolvability in Communication Protocols
Abstract:
Internet communication has become very heterogeneous: typical use cases include web browsing, mobile communication, cloud and data-center networking, and sensor networks. However, today's communication protocols are still developed with significant manual effort for supposedly generic or average use cases. As a result, protocols are not custom-tailored to the requirements of users, applications, or services and are not as fast, flexible, secure, or reliable as they could be. Also, advances in protocol engineering and research are adopted only very slowly.
This talk presents an evolvable protocol platform, EPP, which illustrates a step in this direction of greater flexibility. It aims at assembling protocol stacks semi-automatically from software components, so that they can adapt gracefully to the constant evolution of communication protocols and their usage scenarios.
At its core, EPP describes the functionality of and interaction between individual software components. It then composes them into complete protocol stacks by evaluating these descriptions along with a set of communication requirements, as specified by the network, device, application, and user.
The main contributions of our approach consist of a concise protocol component meta-model, a composition algorithm for protocols, and an efficient ranking method where a single protocol stack needs to be selected from multiple alternatives. Together, these mechanisms can contribute to adapting protocols automatically to the increasing heterogeneity of communication scenarios and challenges.
07.02.2012, sts
Zeit: 24.02.2012, 14:00 Uhr
Ort: Informatik-Zentrum, AH 1, Ahornstr. 55
Referent: Dipl.-Inform. Frank Radmacher, Informatik 7, RWTH Aachen
Thema: Games on Dynamic Networks: Routing and Connectivity
Abstract:
In this talk we present three models of two-player games that capture the behavior of dynamic networks, in particular routing and connectivity problems.
In the first part we study 'sabotage games' (van Benthem, 2002), where a 'Runner' traverses a graph towards a given target, while a 'Blocker' removes edges. In the second part we present a new 'routing game' in which a 'routing agent' has to deliver packets to their destinations, while a 'demand agent' generates packets and moreover blocks connections for a certain amount of time. In the third part we discuss a 'connectivity game' between a 'Constructor' and a 'Destructor'. While Destructor deletes nodes, Constructor can restore or even create new nodes under certain conditions. Constructor either has a reachability or a safety objective, i.e., Constructor has to either establish a connected network or guarantee that the network always stays connected.
For the solvability of these games we obtain results on (un-)decidability as well as computational complexity bounds. In some cases also routing algorithms can be generated by computing winning strategies.
17.02.2012, sts
Zeit: 27.02.2012, 11:15 Uhr
Ort: Informatik-Zentrum, AH1, Ahornstr. 55
Referent: Dipl.-Inform. Martin Zimmermann, RWTH Aachen
Thema: Solving Infinite Games with Bounds
Abstract:
We investigate the existence and the complexity of computing and implementing optimal winning strategies for graph games of infinite duration.
Parameterized linear temporal logics are extensions of Linear Temporal Logic (LTL) by temporal operators equipped with variables for time bounds. In model-checking, such specifications were introduced as "PLTL" by Alur et al. and as "PROMPT-LTL" by Kupferman et al. We show how to determine in doubly-exponential time, whether a player wins a game with PLTL winning condition with respect to some, infinitely many, or all variable valuations. Hence, these problems are not harder than solving LTL games. Furthermore, we present an algorithm with triply-exponential running time to determine optimal variable valuations that allow a player to win a game. Finally, we give doubly-exponential upper and lower bounds on the values of optimal variable valuations.
In Muller games, we measure the quality of a winning strategy using McNaughton's scoring functions. We construct winning strategies that bound the losing player's scores by two and show this to be optimal. This improves the previous best upper bound of n! in a game with n vertices, obtained by McNaughton. Using these strategies, we show how to transform a Muller game into a safety game whose solution allows to determine the winning regions of the Muller game and to compute a finite-state winning strategy for one player. This yields a novel antichain-based memory structure and the first definition of permissive strategies for Muller games. Moreover, we generalize our construction by presenting a new type of game reduction from infinite games to safety games and show its applicability to several other winning conditions.
26.01.2012, sts
Zeit: 07.03.2012, 9:00 Uhr
Ort: Informatik-Zentrum, Raum 5056, Ahornstr. 55
Referent: MSC. CS, Muhammad Hamad Alizai
Thema: Exploiting Wireless Link Dynamics
Abstract:
We address the challenge of link estimation and routing over highly dynamic and bursty wireless links that rapidly shift between reliable and unreliable periods of transmission. To this end, we propose unconventional yet efficient approaches of link estimation, routing and addressing in multi-hop wireless networks to exploit wireless link dynamics instead of bypassing them for the sake of stability and reliability. The goal is to maximize routing performance parameters, such as transmission counts and throughput, by exploiting the burstiness of wireless links while, at the same time, preserving the stability and reliability of the existing mechanisms.
The contributions of this work are as follows:
Firstly, we develop relevant link estimation metrics to estimate link burstiness and identify intermediate links that can enhance the routing progress of a packet at each hop. Secondly, we propose adaptive routing extensions that enable the inclusion of such long-range intermediate links into the routing process. Thirdly, we devise a resilient addressing scheme to assign stable locations to nodes in challenging network conditions. Our evaluation highlights the key achievements of this work when compared to the state-of-the-art: The proposed metrics identify bursty links in the network with high accuracy, the routing extensions reduce the transmission count in the network by up to 40%, and the addressing scheme achieves 3-7 times more stable addressing even under challenging network conditions.
14.02.2012, sts
Zeit: 08.03.2012, 10:00 Uhr
Ort: Informatik-Zentrum, Raum 5052, Ahornstr. 55
Referent: Dipl.-Inform. Alexander Zimmermann
Thema: Das Transmission Control Protocol - Neue Wege einer modernen Loss Recovery
Abstract:
Mehr als drei Jahrzehnte nach seiner Standardisierung ist das Transmission Control Protocol (TCP) nach wie vor das am häufigsten eingesetzte Transportprotokoll im Internet. Kernpunkt der TCP-Spezifikation ist die Congestion Control, die es ermöglicht, die Senderate entsprechend der im Netzwerk wahrgenommenen Überlast anzupassen. Mangels eines expliziten Feedbacks durch das Netzwerk wertet TCP traditionell den Verlust von Segmenten als implizites Anzeichen einer Überlast. Eine der Möglichkeiten für TCP, den Verlust von Segmenten festzustellen, ist der Empfang von Duplicate Acknowledgments. Leider liefert diese Heuristik nicht immer korrekte Resultate, insbesondere dann nicht, wenn Segmente in einer anderen Reihenfolge empfangen werden als sie gesendet wurden: das Problem des Packet Reordering. Motiviert durch die negativen Auswirkungen des Reordering auf TCP, wird mit TCP-aNCR ein senderseitiger Algorithmus vorgestellt, der die TCP-Spezifikation standardkonform erweitert. Auf Basis einer Erkennungs- und Quantifizierungskomponente werden TCP's Congestion Control und Loss Recovery adaptiv an das im Netzwerk präsente Reordering angepasst, so dass sich das Standardverhalten des Protokolls nicht ändern, falls kein Reordering im Netzwerk vorkommt.
13.02.2012, sts