| Abstract |
The demand for bandwidth contracts over networks has recently been growing very rapidly. However, traditional, long-term, static bandwidth contracts are no longer popular. Users now demand short-term, customized and affordable contracts. To this end, auctions appear to be the proper trading mechanism. Indeed, when appropriately designed, auctions can provide fast, simple and fair trading of bandwidth to populations of highly scattered and heterogeneous users (such as Internet-connected users) whose demand is not accurately known, thus resulting in transparent setting of prices and good revenues for the seller. When purchasing bandwidth over a path, it is only meaningful for a user to reserve the same amount in all links. One approach to guarantee this is to perform a combinatorial auction. However, it is well known that winner determination in this case can be complicated and possibly NP-complete. In the present thesis, a simple, yet efficient auction mechanism for allocating bandwidth on a network basis has been designed, implemented and evaluated. This mechanism consists of a set of simultaneous multi-unit Dutch (descending-price) auctions, one per link of the network. In order for a user to win bandwidth over a certain path, it suffices to simultaneously bid for the quantity desired at all relevant auctions. Thus, instant allocation is attained. The user then pays for each unit of bandwidth the sum of prices over the links of the path at the instant where the bid was submitted. User strategies can be based on the price per unit of bandwidth and the spare capacity of the various links, which are sent as feedback to users. An important feature of this approach is that prices at the various links drop at different rates, following rules specified so that prices reflect the demand exhibited so far for each link. Thus, more popular links are in general more expensive, which is fair from an economic point of view and may lead to improved social welfare. Three price-dropping policies have been developed, implemented and evaluated experimentally, in terms of the social welfare associated with the resulting allocation. It is argued, both theoretically and by means of experiments, that it is indeed efficient to introduce such rules rather than drop all prices at the same rate. Finally, the issue of incentive compatible pricing is addressed, by introducing a Vickrey-type pricing rule, which is incentive compatible in certain interesting cases. Besides the theoretical part of this thesis, special software has been developed that implements the mechanism designed and encapsulates some other popular auction mechanisms. These implementations have required certain modifications of the mechanisms as prescribed in theory, which were performed so that theoretical soundness of the mechanism is maintained.
|
Ένας μηχανισμός δημοπρασίας για δέσμευση εύρους ζώνης σε μονοπάτια ενός δικτύου
