紧凑路由研究

计算机科学与探索 ›› 2011, Vol. 5 ›› Issue (3): 193-207.

紧凑路由研究

唐明董^1,2, 刘建勋¹, 张国清²

1. 湖南科技大学知识处理与网络化制造湖南省教育厅重点实验室, 湖南湘潭 411201
2. 中国科学院计算技术研究所, 北京 100190

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-03-01 发布日期:2011-03-01

A Survey on Compact Routing

TANG Mingdong^1,2, LIU Jianxun¹, ZHANG Guoqing²

1. Key Laboratory of Knowledge Processing & Networked Manufacturing, Hunan University of Science and Tech-nology, Xiangtan, Hunan 411201, China
2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Received:1900-01-01 Revised:1900-01-01 Online:2011-03-01 Published:2011-03-01

摘要/Abstract

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

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

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

唐明董1,2 , 刘建勋1 , 张国清2 . 紧凑路由研究[J]. 计算机科学与探索, 2011, 5(3): 193-207.

TANG Mingdong^1,2, LIU Jianxun¹, ZHANG Guoqing². A Survey on Compact Routing[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(3): 193-207.