Ph.D Thesis

Ph.D StudentMenache Ishai
SubjectCompetitive Resource Allocation in Communication Networks
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


Modern, large-scale communication networks are shared by end-users with diverse characteristics and performance objectives. Selfish user behavior is to be expected in these networks, considering their distributed nature and the scarce resources available. The objective of this research is to establish a better understanding of networks with self-interested users, with implications on desirable management architectures.

We first tackle the challenging problem of how to allocate capacity in a wireline network shared by heterogeneous and selfish users. Inspired by the DiffServ standard, we propose a scalable architecture that offers a small number of service classes, where dynamic capacity management is applied for maintaining pre-defined ratios between the relevant congestion measures. Starting with a detailed analysis for the single hop model, we demonstrate the existence and uniqueness of the equilibrium in which the required ratios are maintained. We further provide dynamic schemes for capacity adjustment, and consider the incorporation of pricing and congestion control to enforce absolute performance bounds on top of the proportional ones. Our basic results are then extended to networks with general topology.

Perhaps the most lucid example for the consequences of selfish behavior in wireless networks is the case where a mobile captures a shared collision channel by continuously transmitting packets, hence nullifying other users’ throughput. In the second part of the thesis, we show that this undesired scenario can be avoided under a natural power-throughput tradeoff assumption, where each user minimizes its average transmission rate (proportional to power investment) subject to minimum-throughput demand. We consider the so-called fading channel model, where the channel quality of each user is time-varying and available to the user prior to the transmission decisions. Our equilibrium analysis reveals that there are at most two Nash equilibrium points where all users obtain their demands, with one strictly better than the other in terms of power investment for all users. Furthermore, we suggest a fully distributed mechanism that leads to the better equilibrium.

The above model is then extended in several respects. We consider general reception models, and also investigate the consequences of distributed power control. As in the collision channel case, we demonstrate the existence of a power-superior equilibrium point. On the negative side, however, we point to the possibility of a partial-equilibrium with starvation, where stronger users prevent weaker ones from obtaining their respective throughput demands. Braess-like paradoxes are reported as well, where addition of system resources can lead to reduced performance.