Distributed Control Approaches to Network Optimization
Abstract
The objective of this research is to develop distributed approaches to optimizing network traffic. Two problems are studied, which include exploiting social networks in routing packets (coupons) to desired network nodes (users in the social network), and developing a rate based transport protocol, which will guarantee that all the flows in a network (e.g. Internet) meet a delay constraint per packet. Firstly, we will study social networks as a means of obtaining information about a system. They are increasingly seen as a means of obtaining awareness of user preferences. Such awareness could be used to target goods and services at them. We consider a general user model, wherein users could buy different numbers of goods at a marked and at a discounted price. Our first objective is to learn which users would be interested in a particular good. Second, we would like to know how much to discount these users such that the entire demand is realized, but not so much that profits are decreased. We develop algorithms for multihop forwarding of such discount coupons over an online social network, in which users forward coupons to each other in return for a reward. Coupling this idea with the implicit learning associated with backpressure routing (originally developed for multihop wireless networks), we would like to demonstrate how to realize optimal revenue. We will then propose a simpler heuristic algorithm and try to show, using simulations, that its performance approaches that of backpressure routing. As the second problem, we look at the traditional formulation of the total value of information transfer, which is a multi-commodity flow problem. Here, each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. This problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. However, this idea of value does not capture the fact that flows might associate value, not just with throughput, but with link-quality metrics such as packet delay, jitter and so on. The traditional congestion control problem is redefined to include individual source preferences. It is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the quality degradation seen by each source is bounded by a value that it declares. Decoupling source-dissatisfaction and link-degradation through an ?effective capacity? variable, a distributed and provably optimal resource allocation algorithm is designed, to maximize system utility subject to these quality constraints. The applicability of our controller in different situations is illustrated, and results are supported through numerical examples.