Auction-based resource allocation in selfish networks

Abstract

Networks function properly only when nodes cooperate to provide service. In many networks, such as ad hoc and interdomain networks, network devices are deployed by different owners. Due to limited communication resources, nodes in such networks may behave selfishly. That is, they are only interested in maximizing their own utilities, leading to selfish networks. Incentives are required in such networks to stimulate cooperation. In wired selfish networks, existing work mainly focuses on traffic assignment among predetermined available paths for one source and destination pair. In wireless selfish networks, available bandwidth is assumed to be fixed and predetermined, and the interferences among flows are ignored. Resource allocation in selfish networks needs to be developed under more general models. This dissertation has devised general analytical models for bandwidth allocation in wired and wireless selfish networks. Based on the analogy between resource allocation in selfish networks and auction, auction theory has been adopted in the design and analysis of resource allocation schemes. With incentives introduced in the schemes, selfish nodes will follow the prescribed algorithm and report their information truthfully so that the system cost is minimized. I firstly propose a general model for bandwidth allocation in wired selfish networks. Bandwidth requirements of call routing requests in a given period are allocated as a batch and satisfied at the end of the period. Then, a centralized mechanism is designed to allocate bandwidth and determine payments with different sequencing strategies. Some properties of the mechanism such as individual rationality and incentive-compatibility are studied. I go on to develop the distributed algorithm in wired selfish networks. Available paths are no longer assumed to be fixed and predetermined. Destination nodes conduct the sub-auctions in a certain order for bandwidth allocation and determine payments in a distributed manner. Truthfulness of the distributed mechanism is guaranteed under Nash equilibrium. This distributed mechanism, as a more scalable solution to allocate bandwidth in wired selfish networks, can still guarantee the performance achieved by existing work.