Algorithmic Issues in Communication Networks
M. Mavronicolas, A. Philippou
This component includes the fundamental study of the algorithmic properties of modern communication networks and protocols, such as the Internet and TCP/IP, respectively. Typical examples of the studied problems include flow control, routing, congestion control and buffer management in shared switches. Such problems stem from modern applications and current paradigms of network computing such as Internet computing. Unlike research carried out in the practical networking community, which often deals with loosely specified models and informal or unproven assumptions, our approach builds on the power of formal modeling and reasoning and exploits the accumulated strength of (and methods from) the theory of computing to obtain a precise understanding of the formal capabilities and limitations of modern communication networks and protocols.
A particularly appealing framework in which we are studying modern multiobjective network optimization problems, with multiple entities seeking to optimize their own payoffs in a non-cooperative network, is (non-cooperative) Game Theory. We study the Nash equilibria of such networks, which are the operating points of the network where unitateral deviation does not help users improve performance. Specifically, we study security problems for the Internet, where attack and defense entities are modeled as opponent players in a strategic game. We have studied the computation and the quality of Nash equilibria for this strategic game.
This activity is carried out in colleboration with University of Patras (Greece), Computer Technology Institute (Greece), University of Athens (Greece), University of Paderborn (Germany) and many other European institution, and it is supported financially by the European Union via the Basic Research projects DELIS (Dynamically Evolving Large Scale Information Systems) and AEOLUS (Algorithmic Principles for Building Efficient Overlay Computers).