Fast distributed and parallel algorithms for data network control problems /
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1989.
|
| Subjects: | |
| Online Access: | ProQuest, Abstract Link to OAKTrust copy |
| Abstract: | Analysis of existing algorithms, as well as the development and analysis of new algorithms/techniques for solving network control problems are presented. First, an upper bound for the time complexity of the path formulated gradient projection algorithm (for solving the optimal routing problem in large data networks) is derived. The complexity bound is expressed in terms of the size of the network and the total amount of traffic demand. Also, a new distributed shortest path algorithm is developed for a class of hierarchically structured data networks. The time complexity of this new algorithm is generically better than any other known distributed shortest path algorithm. Next, the method of aggregation/disaggregation is applied to the gradient projection algorithm, and is shown to have the potential of speeding up the rate of convergence. Finally, a novel parallel algorithm is developed for solving the multistage optimization problem. It is shown that this new parallel algorithm achieves a better time complexity than the standard dynamic programming approach of solving the multistage optimization problem. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Electrical Engineering." |
| Physical Description: | xi, 155 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |