Network flow optimization and distributed control algorithms

dc.contributor.advisorBaras, John Sen_US
dc.contributor.authorChen, Huigangen_US
dc.contributor.departmentElectrical Engineeringen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2007-02-01T20:21:42Z
dc.date.available2007-02-01T20:21:42Z
dc.date.issued2006-11-21en_US
dc.description.abstractThis thesis concerns the problem of designing distributed algorithms for achieving efficient and fair bandwidth allocations in a resource constrained network. This problem is fundamental to the design of transmission protocols for communication networks, since the fluid models of popular protocols such as TCP and Proportional Fair Controller can be viewed as distributed algorithms which solve the network flow optimization problems corresponding to some fairness criteria. Because of the convexity of the optimization problem as well as its decoupling structure, there exist classical dual algorithm and primal/dual algorithm which are both distributed. However, the main difficulty is the possible instability of the dynamics of these algorithms caused by transmission delays. We use customized Lyapunov-Krasovskii functionals to obtain the stability conditions for these algorithms in networks with heterogeneous time-varying delays. There are two main features of our results. The first is that these stability conditions can be enforced by a small amount of information exchange among relevant users and links. The second is that these stability conditions only depend on the upper bound of delays, not on the rate of delay variations. We further our discussion on scalable algorithms with minimum information to maintain stability. We present a design methodology for such algorithms and prove the global stability of our scalable controllers by the use of Zames-Falb multipliers. Next we extend this method to design the first scalable and globally stable algorithm for the joint multipath routing and flow optimization problem. We achieve this by adding additional delays to different paths for all users. Lastly we discuss the joint single path routing and flow optimization problem, which is a NP hard problem. We show bounded price of anarchy for combined flow and routing game for simple networks and show for many-user networks, simple Nash algorithm leads to approximate optimum of the problem.en_US
dc.format.extent789209 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4121
dc.language.isoen_US
dc.subject.pqcontrolledEngineering, Electronics and Electricalen_US
dc.subject.pquncontrolledNetworken_US
dc.subject.pquncontrolledOptimizationen_US
dc.subject.pquncontrolledDistributed algorithmsen_US
dc.subject.pquncontrolledStabilityen_US
dc.titleNetwork flow optimization and distributed control algorithmsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
umi-umd-3912.pdf
Size:
770.71 KB
Format:
Adobe Portable Document Format