Guohua Zhang

Graduation Semester and Year

2008

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Science

Department

Computer Science and Engineering

First Advisor

Yonghe Liu

Abstract

Congestion occurs when resource demands exceed the capacity of a network. The goal of congestion control is to use the network as efficiently as possible. While extensive efforts have been devoted to providing optimization based, distributed congestion control schemes for efficient bandwidth utilization and fair allocation in the Internet and wireless networks, little consideration was given to congestion control for networks in challenged environments, specifically for networks with time-varying link capacities and networks that intermittently communicate. In this dissertation, we explore optimal congestion control strategies for such networks based on optimization techniques and repeated game theory. For networks with time varying link capacities, we explicitly model link capacities to be time varying and investigate the corresponding optimal congestion control strategies. In particular we propose a primal-dual congestion control algorithm which is proved to be trajectory stable in the absence of feedback delay. Different from system stability around a single equilibrium point, trajectory stability guarantees the system is stable around a time varying reference trajectory. Moreover, we obtain sufficient conditions for the scheme to be locally stable in the presence of delay. The key technique is to model time variations of capacities as perturbations to a constant link. Furthermore, to study the robustness of the algorithm against capacity variations, we investigate the sensitivity of the control scheme and through simulations study the tradeoff between stability and sensitivity. For a set of challenged networks that continuous end-to-end connectivity may not exist, network nodes may only communicate during opportunistic contacts (they are often referred as delay tolerant networks or opportunistic networks). While custody transfer can provide certain reliability in delay these networks, a custodian node cannot discard the message unless its life time expires or the custody is transferred to another node after a commitment. This creates a challenging decision making problem at a node in determining whether to accept a custody transfer: on one hand, it is beneficial to accept a large number of messages as it can potentially advance the messages toward their ultimate destinations and network utilization can be maximized; on the other hand, if the receiving node over-commits itself by accepting too many messages, it may find itself setting aside an excessive amount of storage and thereby preventing itself from receiving further potentially important, high yield (in terms of network utilization) messages. To solve this congestion control problem, we apply the concepts of revenue management, and employ dynamic programming to develop congestion control strategies. For a class of network utility functions, we show that our solution is optimal. More importantly, our solution is distributed in nature where only the local information such as available buffer of a node is required. This is particularly important given the nature of delay tolerant networks where global information is often not available and the network is inherently dynamic. Our simulation results show that the proposed congestion management scheme is effective in avoiding congestion and balancing network load among the nodes. In the above scheme, we have assumed that the time horizon is finite in making the decision of resource allocation. However, in practice, in certain situations, it might be difficult or impossible to predict when the dynamic behavior will stop. This will render the proposed dynamic programming based control strategy not directly applicable. As an alternative solution, we also employ repeated game theory to model the decision making for custody transfer and propose a new congestion control strategy. The repeated game based approach is particularly suitable for the situations where a node cannot be certain that when a contact will occur and when the dynamic behavior is going to stop. Our simulation results show that the control strategy based on repeated game theory is effective in avoiding congestion and balancing network load.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS