טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentLibman Lavy
SubjectNoncooperative Failure Recovery in Large-Scale Networks
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ariel Orda


Abstract

The application of game-theoretic and economic concepts, such as pricing, in networking research has become widespread in recent years. It provides a systematic framework to deal with the noncooperative nature of network users that is prevalent in modern, large-scale (and especially public) networks. Much of the work in this respect, however, deals with high-level issues, where the affected decision-makers are assumed to be the human users or the top-level applications. Among the studies that tackle the noncooperative issues in the low-layer (network and transport) protocols, the majority focus on problems arising in the flow control and routing contexts.


Our research, on the other hand, focuses on the noncooperative aspects of failure recovery mechanisms. Various types of failures, including link failures and sporadic packet losses, are common in large-scale networks, and mechanisms for overcoming them, such as packet retransmissions and reservations of backup paths, are typically integrated in the network infrastructure and protocols. We apply the noncooperative paradigm to this context and show that the selection of the failure recovery method is better considered as a tradeoff faced by the end user; this observation gives rise to an optimization problem whose solution depends on such factors as the prices charged by the network for the possible alternatives and the user's own utility.

                     

More specifically, we study several common failure recovery techniques,

including the ubiquitous ones of retransmitting packets over a different path and retransmitting after waiting for a timeout, as well as reservation of backup paths that is more specific to high-speed technologies such as all-optical networks. For each, we perform a detailed analysis of the tradeoff and the corresponding optimization problems faced by the noncooperative end user. We develop analytical and algorithmic methods for the solution of these problems, which then allows us to derive important properties of both the user's own optimal strategy and the network behavior when such strategies are employed. In particular, our results enable us to propose significant improvements to the failure-recovery facets of existing protocols.