2University of Maryland
3U.S. Army Research Laboratory
Routing in communication networks, both wireline and wireless, has been a subject of extensive and in-depth study over the last few decades. It is a subject that is fairly well understood. Its state-of-the-art status can be summarized as follows: If a well-defined performance measure can be translated to a link metric, then there are low-complexity, efficient, robust, fast-converging, and often distributed algorithms for finding the optimal routes. Note the important distinction regarding the possibility of mapping the performance measure to a link metric. For example, on the Internet, if end-to-end latency is the performance measure, then the link metric is delay over the link. Bellman-Ford types of algorithms then perform very well and quickly discover the best routes . By contrast, on the traditional circuit-switched voice telephone network, where the performance measure is blocking probability, there is no known link metric that captures the performance measure and, hence, up to this day we only have heuristic routing algorithms for assigning routes to accepted calls.
At this point it is also important to note that the routing problem, being basically a discrete optimization ...