Today's communication networks (such as the Internet) have seen tremendous growth both in terms of network capacity and in the number of elements (e.g., end-users, routers and hosts) it supports. As the size of these networks continue to grow, it is becoming increasingly difficult to efficiently control network resources and satisfy the diverse service requirements of the various users. Solutions that once worked well for small networks may no longer be appropriate for large-scale and high-bandwidth networks. Thus, there is a pressing need to carefully understand how to appropriately design and control these large-scale systems.
One of the main objective of my research has been to understand how to model large networks and to develop simple and efficient mechanisms to control these networks. Somewhat surprisingly, we have found that largeness, which is a source of complexity, can often be exploited to simplify network control. To illustrate the type of simplicity that arises when networks are large, we have modeled the network control problem as a pricing problem. The price affects the users' interest to join the network (e.g., the arrival rate of the user is a function of the price), and thus can be viewed as a feedback signal that the network uses for control. The network's objective is to maximize some overall revenue or utility by appropriately choosing the price. The network has many choices in setting up the price. It could use a dynamic pricing scheme, where the price changes frequently over time. In the extreme case, the price can change whenever the state of the network (e.g., the current number of users in the system) changes. Dynamic schemes can obviously achieve the highest possible revenue. However, the optimal dynamic price is in general infeasible to obtain. For small and Markovian systems, one may use Dynamic Programming (e.g., MDP) techniques to compute the optimal dynamic price. However, for large (or even moderate) systems, the complexity of such an approach grows exponentially with the size of the network.
Interestingly , it turns out that when the capacity of the network is large, simple static pricing schemes, where the price is constant or changes relatively slowly over time, can asymptotically achieve the same revenue as the optimal dynamic pricing scheme. Further, the near-optimal static price can be determined from a simple non-linear programming problem. We have established this result under very general network settings, first for a non-Markovian network with fixed topology and routing, then in the case when the network supports dynamic routing, and also in the case where the topology of the network becomes increasingly complex as its capacity grows. Hence, our result indicates that significant simplicity in control can indeed be achieved in large networks.
For large networks, it is also imperative that the control algorithm can be implemented on-line in a distributive fashion. Although the above result indicates that a form of simple control suffices for large networks, it still requires solving a global optimization problem in order to obtain the control parameters (such as the static price). Our follow-up work develops decentralized control algorithms based on these simple static control policies. For an example of how such an approach significantly reduces the computation complexity and control overhead, see our work on Quality-of-Service (QoS) routing for high-bandwidth networks. For another example of simplicity of network dynamics in large wireless networks, see our work on the capacity-delay tradeoff in large mobile wireless networks.
Selected publications: