Abstract: In generic shortest-path routing, each node has to maintain routing information for all other nodes, thus the local routing table grows rapidly as network size increases. Compact routing can reduce the growth speed of routing table. The basic idea is to relax the constraint of shortest-path routing, i.e., non-shortest paths are permitted when forwarding packets, so that less routing information is maintained at each node, resulting in a better tradeoff between path stretch and routing table size. Thus far, many studies have proposed compact routing schemes for universal networks or networks with specific types of topology, aiming to jointly optimize routing parameters such as routing table size, path stretch and packet header length. This paper surveys the recent work on compact routing, among which classical compact routing schemes are reviewed and compared. The challenges faced by compact routing re-search and future research issues are also pointed out in the end.

Key words: compact routing, routing scheme, routing table size, stretch factor

摘要： 传统的最短路径路由策略通常需要在每个节点上维护到所有其他节点的路由信息, 路由表大小随着网络规模的增加而快速增长, 因此可扩展性不好。紧凑路由能够有效降低路由表的增长速度, 允许通过路径的小幅拉伸来大幅缩减节点的路由表, 从而在路径长度和路由表规模之间获得比最短路径路由更好的平衡。针对通用网络或特定拓扑类型的网络提出了许多紧凑路由策略, 在尽可能缩减路由表的同时优化拉伸系数和包首部长度等路由参数。对紧凑路由的研究成果进行了综述, 对提出的紧凑路由策略进行了分析和比较, 并指出了紧凑路由面临的一些问题和未来的研究方向。

关键词: 紧凑路由, 路由策略, 路由表大小, 拉伸系数