Compressing Two-Dimensional Routing Tables |
| |
Authors: | Subhash Suri Tuomas Sandholm and Priyank Warkhede |
| |
Affiliation: | (1) Department of Computer Science, University of California, Santa Barbara, CA 93106, USA. suri@cs.ucsb.edu., US;(2) Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. sandholm@cs.cmu.edu., US;(3) Cisco Systems, 170 West Tasman Drive, San Jose, CA 95134, USA., US |
| |
Abstract: | We consider an algorithmic problem that arises in the context of routing tables used by Internet routers. The Internet addressing
scheme is hierarchical, where a group of hosts are identified by a prefix that is common to all the hosts in that group. Each
host machine has a unique 32-bit address. Thus, all traffic between a source group s and a destination group d can be routed along a particular route c by maintaining a routing entry (s, d, c) at all intermediate routers, where s and d are binary bit strings. Many different routing tables can achieve the same routing behavior. In this paper we show how to
compute the most compact routing table. In particular, we consider the following optimization problem: given a routing table
D with N entries of the form (s, d, c) , determine a conflict-free routing table with fewest entries that has the same routing behavior as D. If the source and destination fields have up to w bits, and there are at most K different route values, then our algorithm runs in worst-case time O( NK w
2
) . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|