Considerations on Novel Network Routing Mechanism

Guo Yunfei,Zhu Xuanyong,Wang Na

(Information Engineering University, Zhengzhou 450002, China)

Abstract:Routing is the cornerstone of network architecture,and a new routing mechanism is a requisite for constructing new network architecture.The current routing mechanism of the Internet layer is basically the single next-hop routing mechanism,which is the root of transmission congestion in the network.To solve this congestion problem,a fundamental measure is to change the route selection mode of current routing mechanism to allow parallel transmission over multiple routes.Currently,Border Gateway Protocol(BGP)is the only inter-domain routing protocol used in the Internet,but the routing system using BGP suffers scalability problem.To solve the scalability issue of the current inter-domain routing system,a new hierarchical routing system,i.e.Scalable Inter-Domain Routing Architecture(s-idra),is suggested.In addition to scalability,the current routing system is facing other challenges including security,Quality of Service(QoS),multicasting,mobility and dynamic network topology.Therefore,the research on routing protocols,especially the protocol for the new network architecture,is still a tough task and has a long way to go.

B eing an information network basically for“data information transmission”,the Internet was originally designed to facilitate scientific research,but now it has dramatically changes the human society in the fields of politics,economy,education,military affairs and so on.With the applications of Internet being extremely expanded,the basic functions provided by its architecture cannot meet its application requirements.Today,a common understanding among researchers has been reached:a fundamental way to solve this problem is to develop a new Internet architecture to greatly enhance its capabilities.This common understanding has become a powerful drive for research on the new architecture of information network.For example,American Global Environment for Network Innovations(GENI)［1］and NewArch［2］projects,European Union's Euro-NGI［3］project and Chinese"863"and"973"Programs are doing all-around research on the new architecture.

With respect to the new Internet architecture,some essential issues have to be carefully reviewed,including function division,protocol layer definition,transparency,robustness,and end-to-end and heterogeneous interconnection.Although no substantial breakthrough or common understanding has been made as to the form of the new Internet architecture,almost all the researchers in this field agree that the new architecture still needs the inter-networking function.That is to say,the basic function of the Internet,that is,information transmission,should still be performed by the Internet layer in the form of information forwarding.Meanwhile,within the new Internet architecture,it is required to rethink the basic problems of the Internet layer,such as information transmission mode,addressing,forwarding,routing,aggregation,and congestion control.The basic function of the Internet layer is to discover and create a transmission path between various heterogeneous networks and transmit the information among the entities involved in the communication.Obviously,routing is the required and important basic function for the Internet layer to accomplish the basic tasks of interconnection,route selection and forwarding.

1 Current Research on Internet Routing Structure

The current Internet routing system has a hierarchical structure,which,by management domain,divides the routes into two kinds:intra-domain and inter-domain.The nature of the hierarchical structure is to“separate”or“decouple”the local routing structure from the global routing structure microcosmically and macroscopically.

The“separation”not only uniforms the routing structure of the Internet layer on the whole,but also allows each individual routing structure to be most flexible and adaptive.Moreover,the“separation idea”and the two-levelrouting structure provide solid theoretical and technical foundations for the hierarchical structure to be more generalized.

The research on routing for a new Internet architecture mainly proceeds in two directions,which are based on two ideas respectively:one is to improve the current hierarchical routing structure,and the other is to develop a new routing system(e.g.,flat or solid).The authors think the routing structure of the Internet layer is likely to be developed in an“evolutionary”rather than“revolutionary”way.The Internet system is a special,complicated system.For such a complicated system,there are two different and even opposite points of view as to the development of the structure.One is evolutionary,which suggests a gradual change;and the other is revolutionary,which calls for an abrupt change.The“evolutionary”point of view emphasizes an incremental improvement of the system in terms of function and structure while the“revolutionary”one demands an all-around change.However,a considerable number of scholars who hold the“revolutionary”point of view admit that in a complicated system such as the Internet architecture,“unevenness”is always present in its structural change.For instance,the core elements of the structure would be changed relatively slowly and gently,thus being relatively stable;while other elements may be changed quickly and abruptly.The evolutions of many typical biological and physical systems follow this development mode,that is,a gradual change inthe core.The Internet layer is exactly the core of the Internet system.

From the thorough history of the Internet,it is apparent that its application demands requested externally always go far ahead of the actual development of its architecture.As a result,it is imaginable that people's“ahead-of-time”demands for Internet and the“advanced”structures they conceive thereon in any period will be valid or last only for a very limited and short time.On the contrary,it is a reasonable choice to construct a moderately advanced structure with powerful,adaptive and self-evolutionary capacities based on the idea of gradual change.This is especially the case for the Internet layer,which is the core of the Internet system.Moreover,the incrementalconstruction method can closely associate the research object with its application and development environments;thus a close,effective and healthy interaction between the application environment and the structure is likely to be achieved.

Before a new Internet architecture is determined,it is important to further study the problems existing in the routing structure of the Internet layer.This study is based on the idea of“constructing a moderately advanced structure with powerfuladaptive and self-evolutional capacities”,and it is expected to provide clear and effective solutions for exploring a more generalized hierarchicalrouting structure that will promote the development of the structure in an evolutionary way.

This paper discusses the intra-domain routes and inter-domain routes in terms of critical problems,current research and development trend.

2 Intra-domain Routing

In this section,the advantages and disadvantages of the current routing mechanism used in the Internet are analyzed.The“multiple next-hop routing”mechanism,which solves the problems of current mechanism,is also proposed and discussed.

2.1 Single Next-hop Routing Mechanism is the Root of Current Network Congestion

The current routing system of the Internet layer adopts the so-called“single next-hop routing”mechanism.In this mechanism,each router forwards all data packets that are directed to the same network exit through a single next-hop link the router specifies.The basic reason for the single next-hop routing lies in the route selection algorithm adopted in the routing protocol,which always calculates the optimal path between a pair of nodes.

This results in all packets being transmitted along the optimalpath,so the network traffic always prefers to use the nodes and links with the most powerful processing capability.Moreover,the optimal paths of different node pairs in the network are likely to overlap,and this overlapping may persist for a certain period.As a result,some nodes and links may be excessively occupied for a long time,causing the transmission over these nodes and links to be overloaded.Consequently,local network congestion occurs.In the“single next-hop routing”mechanism,the optimal path for packet transmission is found out and created,but the traffic on allnodes and links is seriously unbalanced.Some nodes and links are consecutively congested while others are left idle for a long time.

Figure 1 illustrates the packet transmission in the single next-hop routing mechanism.The number on the link indicates the transmission distance.With the routing algorithm,which always computes the shortest path between nodes for packet transmission,the optimal,single next-hop paths from other nodes to Node A(i.e.,the network exit)are created(marked with red arrows in Figure 1).By computing the shortest paths between any two nodes,it is easy to figure that they overlap the paths marked with red arrows,although their transmission directions may be different.The links marked with red arrows formthe optimal transmission paths of the entire network,and all packets of the network will be transmitted over one ore more of these links.As a result,the transmission path from E1 to B1(i.e.,E1→D1→C1→B1)or any part of the path or the node on the path is likely to be congested while the other nodes and links marked with red arrows are relatively idle because they do not forward any intermediate data;the links marked black are always idle.In short,the routing algorithm of the mechanism may bring local congestion in the network,because it makes“the optimal path is relatively stable and busy,while other links are idle”.

▲Figure 1. Transmission in single next-hop routing mechanism (the exit is Node A).

To solve the network transmission congestion problem,one fundamental measure is to change the route selection mode of the current routing mechanism to allow parallel transmission on multiple paths.That is to say,each node adopts a routing mechanism that enables multiple next hops for parallel forwarding.The purpose of adopting such a new mechanism is to even the utilities of all links in the network microcosmically,and to balance the spatial distribution of the network flow macroscopically.

2.2 Multiple Next-hop Routing is an Iimportant Aspect in Meeting the Network Design Goal of“Best Effort Service”

One design philosophy of the IPnetwork is to transmit data packets with“best effort”.In the foreseeable future,the“best effort”transmission will still be a typical network transmission mode.The current method is to select an optimal path for packet transmission based on the destination address,that is,to schedule the best resources to do one thing.However,this transmission method is far from meeting the design requirements for“best effort”,and more resources should be scheduled to do the same thing.The case in an extreme condition is that all links in the network are scheduled to transmit information packets directed to the same network exit.As for a single node,the“best effort”transmission for packets in the same exit can be implemented by dividing the link interfaces of the router into two kinds:one is for receiving the packets;and the other is for forwarding the packets to neighboring nodes.In this way,the distribution or forwarding of the packets to multiple next hops is achieved on a single router.What has to be done in the multiple next-hop routing is to determine the multiple interfaces of the destination network for forwarding packets to the next hops.In the routing table,the entry for multiple next-hop routing is displayed as each destination network corresponding to multiple next-hop interfaces.

In the network adopting single next-hop routing mechanism,the data packets with the same destination are transmitted on a single path.In the multiple next-hop routing network,each router can forward,in parallel,the packets that are directed to the same network exit to multiple next hops,and the data packets out from each hop can be transmitted in the local subnet in a distributed way until they reach the exit node.Compared to the current mechanism,the multiple next-hop routing mechanism can greatly improve the transmission efficiency,enable all resources in the network to be evenly used,and balance the entire traffic flow,thus minimizing the congestions in network transmission.

2.3 Multiple Next-hop Routing Mechanism can Improve Availability and Anti-damage Capability of the Network

In the current single next-hop routing network,when a network failure occurs,new routes have to be computed with the routing protocol.If the route has not been converged during the computing,the network cannot guarantee a reliable transmission of the data involved.In the multiple next-hop routing network,one router has several next-hop link interfaces for concurrently forwarding the packets to the same network exit.As a result,the router can quickly stop the forwarding task of an interface once the interface is found faulty.At the same time,it shields the faulty interface and forwards the data packets via other reliable interfaces.Like the single next-hop routing mechanism,the multiple next-hop routing mechanism also needs to re-compute the routes when a failure occurs,but the network services will not be interrupted during the computation.Therefore,the multiple next-hop routing mechanism can significantly improve the availability and anti-damage capability of the network.

2.4 Multiple Next-hop Routing Mechanism Provides a Reliable Cornerstone for QoS Route Selection

The route selection process for transmitting information packets in the Internet has two steps.The first step is to identify all feasible routes.With the routing protocol,this step determines which routes in the network can reach the destination network.The second step is to select the transmission route.In this step,a specific route is selected among the feasible routes identified in the first step for data packet forwarding.

In the traditional routing mechanism,i.e.,single next-hop routing mechanism,the route selection process is actually completed in one step because only one route is provided and there is no alternative route for selection in the second step.As a result,the current research on route selection based on various routing factors focuses on how to provide the best transmission route with various routing factors fully considered.

In this regard,we think all other feasible routes should be put into a set of feasible routes rather than be left aside.The various routing factors are just descriptions of route features,used to evaluate the quality of a route.They cannot deny the existence of the route.They are quantitative metrics for“transmission route selection”,but not the only criteria to determine whether a route is suitable for transmission to a network exit.In addition,the route selection process based on routing parameters should not affect the packet transmission of the network.Therefore,a separate study for the first step of the selection process,where all feasible routes are required to be provided,should be conducted.Then the route selection based on various routing factors is a task of the second step,and the selection process does not influence the transmission.The selection of a specific route thus becomes a selection of policies,which are subject to adjustment based on different requirements.

As to the Quality of Service(QoS)problem,it is basically a question on how to select“good”routes that meet QoS requirements according to various routing parameters.In the single next-hop routing mechanism,this is a problem about if Non-deterministic Polynomial(NP)time is complete.That is to say,the mechanism and the QoS requirements are contradictory.In the multiple next-hop routing mechanism,the QoSproblem is independent of the first step of the route selection process,and is only related to the second step.

The QoSroute selection is to select“good”routes that meet QoS requirements from many feasible routes.Even if several routing parameters are involved,the selection process has no impact on packet transmission,which can be proceed as usual.

3 Inter-domain Routing

The Border Gateway Protocol(BGP)［4］is currently the only protocol used in inter-domain routing.The primary function of a BGPspeaking system is to exchange the Network Layer Reachability Information(NLRI)with other BGPAutonomous Systems(ASs),and construct a global routing table to enable the data packets to reach every part of the world via the Internet.The four features of BGP(i.e.,prefix-based,path vector,policy routing and incremental update)require the globalrouting table to include all prefixes learned by the BGP speaker,for each learned prefix,to contain the complete Autonomous System Path information(i.e.,ASPATH),for each ASPATH,to store all related path attributes(e.g.,Metric and Loc Prf)for picking out an optimal path;moreover,the global routing table must store all learned routing information.

Suppose M is the memory space occupied by the globalrouting table,Nprefixis the number of reachable prefixes in the global routing table,Npathis the number of paths that can reach a prefix,and R is the memory space occupied by a reachable path and its attributes.Suppose that R is the same for every path in the routing table in the paper,the relation between them can then be expressed as the following equation:

According to the data from RouteViews［5］,in the global routing table of December 4,2007,Nprefixis 246,778,and the mathematical expectation value of Npathis 36,with a maximum value of 43 and a minimum value of 1.This means that Nprefix＞＞Npathand M is O(Nprefix).It is noteable point is that Nprefixhas increased exponentially in the last 10 years.

The contributions to the exponential growth of Nprefixare mainly multi-homing,failure to aggregate,load balancing and address fragmentation［6］.To get a better connectivity,lots of customer networks choose multiple connections to the networks of several providers.At present,the number of multi-homed ASs in the Internet has accounted for 70%of allautonomous systems［7］.As the prefixes obtained from a provider are difficult to be aggregated by the networks of other providers,the multi-homing technology often adds extra entries in the global routing table,as shown in Figure 2.Researches show that the application of multi-homing technology has brought 20%-30%of extra prefixes in the globalrouting table.Due to failures to aggregate,there are almost 15%-20%of entries in the global routing table that can be aggregated but have not been aggregated.Another reason for the prefixes originated from the same autonomous system not to be aggregated is load balancing.As shown in Figure 3,Stub_AS1 balances the input flows on Link1 and Link2 by advertising different sub-prefixes to Transit_AS1 and Transit_AS2.Currently,the load balancing technology contributes 20%-25%of the extra prefixes.The autonomous system itself may have several address fragments that cannot be aggregated,as shown in Figure 4.Noticeably,address segmentation contributes the most of the extra prefixes,near 75%.

The direct consequence from the exponential growth of Nprefixis the decrease of the network's scalability.The solutions for the scalability problem of the inter-domain routing system can be divided into the following four categories:

(1)To adopt a new inter-domain routing protocol,such as compact routing protocol［8］and Hybrid Link-state Path-vector protocol(HLP)［9］.According to Professor Krioukov from the Cooperative Association for Internet Data Analysis(CAIDA),the basic reason for poor scalability of the inter-domain routing system is that the current routing demand,i.e.,looking for the shortest path between any two points in the topology,cannot strictly guarantee the performance.This demand requires the router to obtain all topology-related knowledge,thus resulting in a huge number of information and poor scalability.Therefore,Professor Krioukov applied compact routing scheme,which aims to make a good trade-off between stretch and routing table size,to inter-domain routing and has achieved a quite good result［10］.However,the compact routing scheme cannot be directly used in inter-domain routing because the latter is a kind of policy routing and it is stillunknown whether the scalability of the routing system is good enough after policies are applied in the scheme.HLPis a new type of inter-domain routing protocol that combines link status and path vector routing algorithms.Unlike BGP,which is prefix-based,HLPis base on the autonomous system so that the scalability of the routing system using HLPis improved to some extent.

(2)To reduce Nprefix.The typical scheme for reducing Nprefixis Core Router-Integrated Overlay(CRIO)［11］.

▲Figure 2. Extra prefixes caused by multi-homing.

▲Figure 3. Extra prefixes caused by load balancing.

This scheme uses IPtunnels to shrink the global routing table size,but at the price of a longer path.It isolates the transmission network formed by tier-1 Internet Service Providers(ISPs)from customer networks,and allows the data packets to be transmitted through the transmission networks via tunnels.The customer network selects a tunnel entry based on the reachable“virtual prefixes”(e.g.,/8)advertised by tier-1 ISPs.

▲Figure 4. Extra prefixes caused by address fragmentation.

(3)To reduce Npath.The typical scheme used here is Forgetful Routing［12］.

The central idea of the scheme is to compute the set usage times of all routes,and then always evict the alternate route that will used last or furthest in the future so that the route selection process will not be affected.Since BGPspeakers only advertise their best routes to their neighbors,every alternate route is always some neighbor's best route.Therefore,when the evicted route is selected as an optimal route,the peer that originally transmits the routing information will be asked to retransmit the routing information so as to recover evicted route,The forgetful routing scheme does not require any modification of BGP.It can be incrementally deployed,which has no impact on convergence.

(4)To reduce both Nprefixand Npath.The typicalsolution is atomized routing［13］.Atomized routing collects all the prefixes with the same ASPATH to form a prefix set named“atoms”.These atoms are computed worldwide and used to route data packets.

As for the solution for the scalability problem of the inter-domain routing system,a new Scalable Inter-Domain Routing Architecture(s-idra)is proposed in this article.As shown in Figure 5,this architecture has two kinds of Autonomous Domains(ADs):origin and transit.The origin AD(i.e.,v-Origin AD)is the domain that originates and receives data packets;the transit AD(i.e.,v-Transit AD)is the domain only responsible for forwarding data packets.All v-Transit ADs form a transmission network,and the routers in v-Transit AD execute the inter-domain routing protocol to construct a v-Transit AD-based global routing table.Meanwhile,a global mapping table will be constructed based on the mapping table creation mechanism of s-idra,which includes such entries as host location identification(ID),v-Origin AD and v-Transit AD.When the border routers in v-Origin AD receives data packets which would be transferred to other domains,they first search the global mapping table,according to the destination host location ID,to find the v-Origin AD and v-Transit AD IDs of the destination host;and then,they encapsulate the data packets based on the v-Transit AD ID and forward them to the transmission network.The routers in the transmission network then forward these packets based on the v-Transit AD ID of the destination host.In s-idra,the border routers in v-Origin AD store only the global mapping table;the routers in v-Transit AD only keep the global routing table.Note that v-Origin AD and v-Transit ADare only virtual inter-domain routing entities.If an autonomous domain in real network originates and receives data packets,and also forwards the packets from other ADs,it then can be regarded as both a v-Origin AD and a v-Transit AD.

▲Figure 5. S-idra architecture.

The global routing table of s-idra is based on v-Transit AD.Take this as an example for Internet data［2］:up to December 4,2007,the Internet has 4,244 Transit ASs,which grow in a linear and quite slow way［8］.As a result,s-idra is perfectly scalable and its growth is controllable.In s-idra,the mapping table is used to replace some functions of the routing table.This simplifies the management because the distribution of the mapping table is simpler than the distribution of the routing table.The entries in the mapping table are the same at any location while the entries in the routing table vary with routers.Moreover,it is difficult to tell a given global routing table entry is correct or not because its correctness depends on the states of other routers,but the correctness of the entry in the mapping table can be easily judged.In addition,s-idra is an inter-domain routing architecture,but its transmission network is independent of any specific protocol;so,any inter-domain routing protocol can be adopted in it(e.g.,compact routing protocol).s-idra isolates the transmission network from customer networks,which accords with the development trend of Internet topology.In the SIGCOMM2007 conference,UCLA researchers Olivera et al published the latest research on the development trend of Internet topology.Their research shows the topologies of ISPnetworks and those of customer networks developing in different ways.Compared to ISPnetworks,the number of customer networks increases sharply,and its growth rate is 3.6 times of that of ISP networks.Meanwhile,the connection between ISPnetworks becomes more closely than ever.Therefore,the introduction of s-idra not only isolates the transmission network from customer networks,but also improves the stability and security of the transmission network.

4 Conclusions

Good scalability of the routing system means the entries in the routing table grow in a linear way,or in a polynomial way at most.But in reality,the entries grow exponentially due to various factors.The huge routing table and the exponential growth of table entries directly result in the significant decrease of transmission performance.After IPv6,which requires a large address space,is deployed,the routing system may face more serious scalability challenge.In addition to scalability,the routing system is challenged with other problems,such as security,QoS,multicasting,mobility and dynamic network topology.

Besides,both intra-and inter-domain routing protocols support neither dynamic network topology nor the transmission paths with asymmetric capabilities and characteristics.However,to support these are exactly what are required in the routing protocols for the wireless network that supports mobility and for the mobile network(NEMO).Therefore,the research on routing protocols,especially on the protocols for the new network architectures,is still a tough task and has a long way to go.

The information networks have facilitated the economic and social life,promoted the economic and social development,and changed the society to some extent.Looking forward to the future,it will undoubtedly play a leading role in social development.It can be foreseen that the role of the Internet will gradually evolve from the“information infrastructure”to“social infrastructure”of the world in the year 2020s.