Chinese Journal of Computers   Full Text
Title	Hidra: A Hierarchical Inter-Domain Routing Architecture
Authors	WANG Na1),2) MA Hai-Long2) CHENG Dong-Nian2) WANG Bin-Qiang2)
Address	1)(College of Electronic Technology, PLA Information Engineering University, Zhengzhou 450004) 2)(College of Information Engineering, PLA Information Engineering University, Zhengzhou 450002)
Year	2009
Issue	No.3(377—390)
Abstract &   Background	Abstract The Internet inter-domain routing system is facing serious scalability challenge, which represents super-linear growth of the global routing table and increasingly frequent routing updates. The root cause that contributes to the rapid routing table growth is that number of IP prefix identifying location of autonomous system is uncontrollable; the root reason that leads to increasingly frequent routing updates is the flat inter-domain routing architecture. To address these limitations, this paper proposes a Hierarchical Inter-domain Routing Architecture(Hidra). The basic idea of Hidra is to separate edge networks from the core: “relatively stable” core networks lie in a high-rank routing layer, and a high-rank inter-domain routing protocol is operated among routers in core networks to maintain reachability to all other core networks; in the “relatively queasy” edge, a low-rank mapping layer along with a corresponding mapping service is introduced to keep the reachability between the edge and core. Because being separated from unstable edge networks, core networks have the enhanced routing stability. Hidra introduces an inter-domain routing identity RID(Routing Idengity) to identify the location of transit autonomous system, which is only defined by transit autonomous system and its provider autonomous system. As a result, scale of global routing table is observably reduced. Keywords inter-domain routing; BGP; scalability; mapping service Background Many studies reveal that Internet inter-domain routing system is facing a scaling challenge. The current global routing table has been growing at an alarming rate over the recent years. With the wide IPv6 deployment, the routing table size in the default free zone(DFZ) is growing dramatically. This routing scalability concern is exacerbated by an increase in users’ requests for provider-independent addresses. At the same time, the need for effective traffic engineering at both edge networks and ISPs also add potential scaling challenges to the global routing table by techniques such as announcing more specific prefixes. Overall, the Internet community is presented with a challenge to keep the global routing table scalable in face of an expected growth in the address space, an increased allocation of provider-independent address prefixes, and a demand for effective traffic engineering. Another major factor regarding routing scalability is the amount of update messages routers must process in real time. Because of the flat nature of the Internet routing, a routing flap to any destination can trigger routing updates to be propagated through the entire Internet. Research results have shown that the overwhelming majority of BGP updates are generated by a very small number of sources, most of them being small edge networks. Several efforts have point out that the routing scaling problem necessitates architectural changes and now is an important crossroad when changes can and must be made. The main contribution of the paper is to propose a new inter-domain routing architecture, Hidra(Hierarchical inter-domain routing architecture). The paper found that the root cause that contributes to the rapid routing table growth is that number of IP prefix identifying location of autonomous system is uncontrollable; the root reason that leads to increasingly frequent routing updates is the flat inter-domain routing architecture. As a result, Hidra divides the inter-domain routing into two layers: a low-rank mapping layer and a high-rank routing layer. The low-rank mapping layer is used to maintain the reachability between stub and transit autonomous systems; the high-rank routing layer is used to maintain the reachability between transit autonomous systems. Hidra consists of mapping table establishment and management protocol, routing table distribution protocol, high-rank inter-domain routing protocol and path maintenance protocol. For separating network edge and core, evaluation results indicate that in Hidra network, high-rank inter-domain routing updates are observably decreased, the stability of core network routing is enhanced. Hidra introduces an inter-domain routing identifier—RID(Routing Identifier)—to identify transit autonomous system’s location. RID comprises autonomous system number and a locator. The locator is uniquely determined by transit autonomous system and its provider autonomous system. The RID address format brings about number of RID correlating with number of the transit autonomous system’s providers. Evaluation results indicate that in Hidra network, global routing table is observably reduced, grows linearly and controllably.