Geometric modeling and analysis of dynamic resource allocation mechanisms
Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/8769 |
| _version_ | 1811089493856354304 |
|---|---|
| author | Secor, Matthew J. (Matthew Joelson) |
| author2 | George Verghese. |
| author_facet | George Verghese. Secor, Matthew J. (Matthew Joelson) |
| author_sort | Secor, Matthew J. (Matthew Joelson) |
| collection | MIT |
| description | Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001. |
| first_indexed | 2024-09-23T14:20:04Z |
| format | Thesis |
| id | mit-1721.1/8769 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:20:04Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/87692019-04-12T14:12:06Z Geometric modeling and analysis of dynamic resource allocation mechanisms Secor, Matthew J. (Matthew Joelson) George Verghese. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001. Includes bibliographical references (p. 159-163). The major contribution of this thesis is the investigation of a specific resource allocation optimization problem whose solution has both practical application as well as theoretical interest. It is presented as a specific case of a more general modeling framework we put forth. The underlying question asks how to partition a given resource into a fixed number of parts such that the elements of the resulting partition can be scheduled among a set of user requests to minimize the worst case difference between the schedule and the requests. This particular allocation problem has not been studied before. The general problem is difficult in part because the evaluation of the objective problem is a difficult task by itself. We present a novel algorithm for its exact solution in a constrained setting and discussion of the unconstrained setting in, followed by a number of practical applications of these solutions. The solution to the constrained optimization problem is shown to provide sizable benefits in allocation efficiency in a number of contexts at a minimal implementation cost. The specific contexts we look at include communication over a shared channel, allocation of many small channels to a few users and package delivery from a central office to a number of satellite offices. We also present a set of new fairness results for auction-based allocation mechanisms and show how these mechanisms also fall within our modeling framework. Specifically, we look at using auctions as mechanisms to allocate an indivisible shared resource fairly among a number of users. We establish that a straightforward approach as has been tried in the literature does not guarantee an fair allocation over a long time scale and provide a modified approach that does guarantee a fair allocation. We also show that by allowing users to strategize when bidding on the resource we can avoid the problem of unfairness, for some simple cases. This analysis has not been seen in existing literature. Finally, an analysis of the deterministic and stochastic stability of our class of models is presented that applies to a large subset of the models within our framework. The deterministic stability results presented establish the ultimate boundedness of the lag of deterministically stabilizable models in our framework under a wide variety of quantizer-based scheduling rules. This variety of available rules can be used to further control the behavior of the lag of a stable mechanism. We also discuss the application of existing stochastic stability theory to a large subset of the stochastic models in our framework. This is a straightforward usage of existing stability results based on verifying the satisfaction of a stochastic drift condition. by Matthew Secor. Ph.D. 2005-08-23T15:10:41Z 2005-08-23T15:10:41Z 2001 2001 Thesis http://hdl.handle.net/1721.1/8769 48125520 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 184 p. 21253199 bytes 21252957 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Secor, Matthew J. (Matthew Joelson) Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title | Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title_full | Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title_fullStr | Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title_full_unstemmed | Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title_short | Geometric modeling and analysis of dynamic resource allocation mechanisms |
| title_sort | geometric modeling and analysis of dynamic resource allocation mechanisms |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/8769 |
| work_keys_str_mv | AT secormatthewjmatthewjoelson geometricmodelingandanalysisofdynamicresourceallocationmechanisms |