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:
Traditional Quality-of-Service (QoS) routing proposals compute ``best'' paths based on the current snapshop of the network configuration. Such a myopic approach suffers from significant computation and communication overhead, as paths need to be recomputed every time a new flow enters the network. Further, it can lead to sub-optimal behaviour for the entire system. When one attempts to reduce the computation and communication overhead (e.g., by reducing the frequency of path-computation and link-state updates), the routing accuracy degrades. Hence, there is a fundamental tradeoff between the accuracy of the QoS routing decisions and the computation/communication overhead.
Using the idea of simplicity in large systems, we have developed a novel approach for QoS routing in high-bandwidth networks that can substantially alleviate the computation and communication overhead of QoS routing without sacrificing the performance. The new approach (which we refer to as an ``optimization-based'' approach to QoS routing) is based on the idea that when the capacity of the network is large, simple proportional routing scheme can approach the performance of the optimal dynamic routing schemes. In a proportional routing scheme, calls are routed to alternate paths based on pre-determined probabilities. The right routing probabilities can be derived from the solution of a simple optimization problem that depends only on the average demand and capacity of the network.
We then develop an online, distributed algorithm that can efficiently solve the optimal routing probabilities. We rigorously established the convergence of the algorithm to the optimal control parameters, and provided guidelines on how to choose the parameters of the algorithm to ensure efficient control. Our optimization-based approach to QoS routing has the following advantages:
In wireless ad hoc and sensor networks, it is the number of nodes that is large. We have shown that this type of largeness can also lead to simple and critical insights in control. In particular, we study the problem of the fundamental capacity-delay tradeoff in large mobile ad hoc networks. Note that although it is well known that mobility can improve network capacity, it remained a challenging problem as to what is the maximum capacity under a given delay constraint, and how to achieve this maximum capacity. We have developed a systematic methodology both for finding the optimal capacity-delay tradeoff and for designing the capacity-achieving scheme. Our methodology can be applied to a number of mobility models, such as the i.i.d. mobility model, the random way-point mobility model, and the Brownian motion mobility model. In each case, we have identified the limitations of existing works, obtained sharper results under more general settings, and provided new insights on the fundamental capacity-delay tradeoffs. In particular, under the i.i.d. mobility model, our study allows us to develop a scheme that can exploit mobility and achieve a provably larger per-node capacity than that of the static networks even with delay that does not grow with the number of nodes. This is the first such result of its kind in the literature. Our methodology can also be extended to incorporate additional scheduling constraints in the system, and be used to find optimal scheduling schemes in a variety of network settings.
Selected publications:
Many researchers have adopted a cross-layer approach to solving wireless network problems. However, there have been arguments for and against cross-delay design in wireless networks. A fundamental problem in cross-layer design is the tradeoff between efficiency and modularity. In cross-layer control solutions, although the performance of the system can be optimized, the tight interaction between the layers could make the overall system highly sensitive to changes in each layer. A main objective of our work is to understand whether we can design cross-layer control solutions that only require a loose coupling between the layers. By loose coupling, we mean that the cross-layer solution should be robust to imperfect information or imperfect actions taken at various layers. If this is true, we then have the best of both worlds, i.e, we achieve both efficiency and modularity.
We have demonstrated this kind of loose coupling in certain cross-layer control problems. In particular, we have formulated and solved a cross-layer control problem that jointly allocates the end-to-end data rate to each user (i.e., the congestion-control problem) and computes the schedule and power/rate assignment for each link (which we will referred to as the scheduling problem). In the optimal solution, the congestion-control component and the scheduling component can be decomposed: they both act independently on the queue lengths of the system. The two components are then coupled by the update of the queue length at each link. Further, if one replaces the scheduling component by an imperfect scheduling policy that only computes suboptimal schedules at each time, we can still quantify the impact on the overall system performance fairly easily for a large class of imperfect scheduling policies.
It is usually preferable that the control algorithms can be implemented in a distributed fashion. This is particularly important for ad hoc and sensor networks. However, distributed algorithms add complexity to the cross-layer design. The reason is that distributed algorithms are unlikely to achieve optimality, hence the interaction between the layers become much harder to predict and control. Nonetheless, our work on cross-layer control with loose coupling provides us with some hope because it indicates that these imperfect distributed algorithms may still suffice. In fact, for certain simple interference models, we have already obtained fully distributed algorithms for cross-layer congestion-control and scheduling problems.
Our future work will extend this loose-coupling concept to other classes of cross-layer control problems. Some of the on-going directions that we are pursuing include: incorporating the routing layer into the cross-layer control framework; studying the interaction with MAC layers that use random access; studying the interaction with coding and modulation schemes at the physical layer; and dealing with delay sensitive applications.
Selected publications: