A Survey on Compact Routing

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 research and future research issues are also pointed out in the end.