Constrained Optimization Routing and Its Applications

Zhanfeng Jia
(Professor Pravin P. Varaiya)
(DARPA) IPTO N66001-00-C-8062

The study of the constraint optimization routing (COR) problem is motivated by recent research efforts on the QoS routing problem of the communication network. QoS routing leads to a series of problems including link state advertisement, path selection, admission control, path setup, and path maintenance. The COR problem focuses on finding a path through the network that satisfies the QoS requirements. Conventional routing protocols characterize network links by a single metric, such as hop count. Routing protocols like RIP or OSPF find the shortest path based on this metric. For routing that supports QoS requirements, the link model must include multiple parameters such as bandwidth, cost, delay, delay jitter, loss probability, and so on. Routing protocols then become more complicated because they must find paths that satisfy multiple constraints.

The COR problem has many applications in a variety of areas such as management of transportation systems, decision-making, and mission planning. For example, in the Mixed Initiative Control for Automa-teams (MICA) Project, the unmanned aerial vehicles, or UAVs, want to destroy valuable targets subject to possible attacks from these targets, limited fuel, and other obstacles. This path planning problem can be easily abstracted as a COR problem with constraints of hazard, path length, etc.

A latest research effort is to build a dynamic routing algorithm with traffic engineering (DRATE) framework under the structure of the COR problem. In this framework, flows come and are routed one by one with specific link metric sets. These link metric sets are calculated based on dynamic flow information in real time, such that traffic engineering objectives are achieved. The key techniques are (1) to map the traffic engineering objectives appropriately into link metric sets, and (2) to integrate multiple objectives and fit the COR structure.


Send mail to the author : (jia@eecs.berkeley.edu)


Edit this abstract