Optimization and Non-Cooperative Issues in Communication Networks.

PHD ThesisCommunication networks and more in general distributed systems are undergoing rapid advancements. The last few years have experienced a steep growth in research on different related aspects. However, although the great promise for our future communication capabilities, several challenges need still to be addressed. A crucial ingredient for the successful development end employment of the corresponding arising technologies is the design of networks better suited for the management of large bandwidth and high quality services, as required by the emerging tasks, such as on-demand-video, multimedia and data integrated networks, seamless and ubiquitous access to system resources in mobile environments, secure on-demand data, and so forth. In this thesis we focus on the analysis of the performance and complexity of distributed systems such as optical networks (representing the main contribution of the thesis) and wireless networks. More specifically, we consider classical combinatorial optimization problems arising in communication networks from two different perspectives. In the first part we consider the design of classical centralized polynomial time (approximation or exact) algorithms. Such an investigation is conducted under a traditional computational complexity setting in which time constraints must be taking into account for tractability and efficiency matters. The above perspective implicitly or explicitly assumes that the resources of the system are directly accessible and controllable by a centralized authority, but this assumption in highly distributed systems might be too strong or unrealistic. Therefore, in the second part of the thesis we consider communication problems arising in networks with autonomous or non-cooperative users. In such a scenario users pursue an own often selfish strategy and the system evolves as a consequence of the interactions among them. The interesting arising scenario is thus characterized by the conflicting needs of the users aiming to maximize their personal profit and of the system wishing to compute a socially efficient solution. Algorithmic Game theory is considered the most powerful tool dealing with such non-cooperative environments in which the lack of coordination yields inefficiencies. In such a scenario we consider the pure Nash equilibrium as the outcome of the game and in turn as the concept capturing the notion of stable solution of the system. Under the above perspectives, the thesis makes different progresses on the understanding of a variety of problems in communication networks. Our results include: polynomial time algorithms, NP-complete results, approximation algorithms and inapproximability results; analysis of performances, convergence and existence of Nash equilibria in selfish scenarios