CN1207878C

CN1207878C - Routing table compression method

Info

Publication number: CN1207878C
Application number: CNB021314489A
Authority: CN
Inventors: 龚志波
Original assignee: Harbour Networks Holdings Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2002-10-14
Filing date: 2002-10-14
Publication date: 2005-06-22
Anticipated expiration: 2022-10-14
Also published as: CN1402488A

Abstract

The invention relates to an optimization method of an Internet protocol network unicast routing table. In a device that needs to use a large-capacity routing table to implement packet forwarding, this method can generate an equivalent aggregated route to reduce the number of routes used for forwarding, thereby adapting to the continuous increase in the number of network routes with a small system resource overhead. The method can be applied to forwarding devices such as routers or IP switches.

Description

A kind of routing table compression method

Affiliated field:

The present invention relates to the optimization method of a kind of Internet protocol (IP) network unicast routing table, belong to the computer network communication technology field.

Background technology:

In IP network, IP forwarding units such as router and three-tier switch use IP route table control message forwarding.Along with the high speed development of IP network, in large-scale IP network, especially in the internet, the sustainable growth of route quantity has reached the order of magnitude of hundreds of thousands bar route in the internet.Big capacity routing table is brought bigger overhead for the IP forwarding unit, as takies a large amount of internal memories, inquiry and maintenance efficiency reduction etc.

In present IP forwarding unit, high layer software is submitted to the IP forwarding engine with the effective route in the routing table, is kept in the converting route, and forwarding engine is pressed the indication of converting route, specifically carries out the high speed forwarding capability of message.Forwarding engine can be realized by software or hardware, but use hardware to realize in the high speed forwarding unit usually.The flexibility of Hardware Forwarding Engine is lower, and the capacity of converting route is had fixing restriction usually.And the effective route in the present routing table must all be submitted in the converting route, can correctly implement message and transmit to guarantee forwarding engine.Routing Protocol and the forwarding engine relation in equipment is referring to Fig. 1: wherein arrow represents that route submits direction among the figure, (1) is physical interface, (2) be link layer protocol, (3) be the IP forwarding engine, (4) be the IP layer, (5) are the TCP/UDP protocol layers, and (6) are the unicast routing protocol layers, (7) be unicast routing table, (8) are that singlecast router is transmitted.

Chinese patent 00804339.6 has proposed a kind of implementation method of high efficiency converting route, and purpose is to realize the high efficiency retrieval of transmitting, and " compression " wherein is meant the minimizing in route forwarding table committed memory space.And the purpose of this method is the route quantity that is submitted to converting route in order to reduce, it is a kind of optimization method of before route is added converting route, being taked, " compression " wherein is meant the minimizing of route quantity in the converting route, and this and concrete converting route implementation are irrelevant.

Goal of the invention:

The present invention is directed to big capacity IP forwarding unit and propose a kind of compression method of converting route, reduce route quantity in the converting route, guarantee not influence simultaneously correctly to carry out forwarding capability by creating the polymerization route.

The technical scheme of invention:

Although the route quantity in the large-scale IP network is very big, but the neighbouring device of each IP forwarding unit can be not a lot, usually between several to dozens of, the purpose of forwarding unit only is that packet is forwarded in this a small amount of neighbouring device one, this just for the compression of route provides may.

The principle of IP route table is to use the longest matching process, when promptly using a purpose IP address search converting route, selection is routed that the network segment comprises and the route of network segment scope minimum (mask-length is the longest), then message is forwarded to the neighbouring device of route appointment.The IP address of neighbouring device is called next hop address in routing table.For the identical route of a plurality of next hop address, can replace with the short route of a mask, be called the polymerization route.Transmit for IP, it is identical adopting the forwarding effect of polymerization routing address, and therefore the route quantity in the converting route can reduce.Certainly, the route polymerization simply that not all next hop address is identical needs certain scheme of design to obtain correct polymerization route.

This method adopts specified scheme to calculate the polymerization route based on current routing table; Submit polymerization route and the route that can not be aggregated to converting route, the route that is aggregated the route covering is not submitted converting route to; Replace original route by the polymerization route, do not influence and correctly carry out forwarding capability, simultaneously converting route is compressed.

Structure routing table data structure commonly used is y-bend Ji Shu (Radix Tree), and Ji Shu is present widely used method.Ji Shu is made of tree node.Have route data on the tree node, also may not have route data.Do not have the tree node of route data to be called the sky node, have the tree node of route data to be called physical node.Empty node must have two child nodes, and physical node can have zero to two child nodes.In the base tree, each node will comprise an elevation information at least, and the position of physical node highly is the mask-length of route.Two brotghers of node are exactly the position height of their father node from first different position (bit) that a high position begins, and two child nodes this be 0 be left child node, be 1 be right child node.Two physical nodes have relationship between superior and subordinate, and then these two routes have inclusion relation, and one section identical destination address prefix is promptly arranged, but the mask-length difference.Provided the example of a y-bend Ji Shu in Fig. 2, wherein nodes such as a, b, d are empty node, and nodes such as c, e, f are physical node, comprise routing iinformation.

In the base tree, a continuous empty node region is for can optimize the interval.Be only to comprise the sky node in this zone, and the parent pointer of these sky nodes by binary tree directly is connected with left and right sides child pointers.In the example of Fig. 3, there are 3 can optimize the interval, be respectively { a, b, d}, { i, m}, { j}.Except the father node that can optimize interval root node, other are optimizable object with optimizing interval direct-connected physical node.Interval interior optimization process can be optimized and only these physical nodes need be considered.For example first object optimized that can optimize in the interval is among Fig. 3: e, f, g, c.Can optimize the interval interior object optimized for second is: l, n, o.Discontinuous optimization do not have relative influence between the interval, polymerization is calculated and can be carried out respectively.In whole routing table, do optimization respectively as long as can optimize the interval to each.In the base tree, only needing increases the polymerization route on empty node, just can reach sufficient polymerization effect.So calculate the process of polymerization route, next jumping of whether need on each empty node just considering to increase polymerization route, polymerization route is taken as the process of what value.

The present invention proposes four levels and else optimizes compression method:

1) utilize in the routing table polymerization of nature, covered by higher level's route and also next to jump identical route not selected, do not submit to converting route.For example in Fig. 4, node h and p, q are for can omit route, and they are jumped identical father node h by next and j covers, needn't be to transmitting submission.

2) to an optimizable interval, only when the route in a whole interval or a subinterval all have identical next just generate a polymerization route when jumping, can not cover whole interval.For example in Fig. 5, increased the polymerization route on node b and the j newly, they make that nodes such as e, f, g, h, p, q needn't be to transmitting submission, thereby have compressed the size of transmitting.

3) to an optimizable interval, next jumping of getting interval interior quantity maximum generates a polymerization route, covers whole interval.For example in Fig. 6, increased the polymerization route on the node a newly, it makes that nodes such as f, g, h, l, o needn't be to transmitting submission, thereby has compressed the size of transmitting.

4) to an optimizable interval, take all factors into consideration and generate a plurality of polymerization routes, what reach whole interval chooses route quantity minimum.For example in Fig. 7, increased the polymerization route on node a and the j newly, they make that nodes such as f, g, h, l, p, q needn't be to transmitting submission, thereby have compressed the size of transmitting.

In these four ranks, rank one is the basis.Other three levels are after other optimizes, and all will use the principle of rank one to select the route that submit to, ignore the route that needn't submit to.When it uses separately, distribute, the size of transmitting is descended to some extent for normal route.But because the route that provides of Routing Protocol is not overlapping usually, so that rank 1 is optimized effect when using separately is not too obvious.The optimization effect of rank 2 and rank 3 is apparent in view, but is not best practice.Rank 4 is best practice, but the scheme complexity, computing cost is big, and practicality is not strong.Therefore rank 2 and rank 3 can be combined, form the less and effect of a kind of computation complexity practical optimization method preferably.

Beneficial effect:

This method replaces a large amount of route datas by adopting the polymerization route, has reduced the route quantity in the converting route, thereby can reduce the capacity pressure of forwarding engine, reduces space expense, reduces cost, and improves the route carrying capacity of equipment.This method can be applied to the IPV4 and the IPV6 network equipment, and applicable equipment comprises the various forwarding units in the IP network, as router, three-tier switch, IP gateway etc.

The Figure of description explanation:

Fig. 1 singlecast router structure chart

Fig. 2 y-bend base tree schematic diagram

Fig. 3 can optimize area schematic

Fig. 4 rank 1 is optimized schematic diagram

Fig. 5 rank 2 is optimized schematic diagram

Fig. 6 rank 3 is optimized schematic diagram

Fig. 7 rank 4 is optimized schematic diagram

(in Fig. 2 to Fig. 7, the empty node of circular representative, square representative physical node, the polymerization route that the star representative increases.Lowercase representation node numbering, capitalization is represented next jumping of route.)

Embodiment:

Operating process is as follows in the enforcement:

1) unicast routing protocol generates route or deletion route, is submitted to routing table

2) routing table maintenance module adopts following proposal to do computation optimization

3) if computation optimization obtains the new route of choosing, then be submitted to route forwarding table

4) if computation optimization makes and originally chooses route to become not choose, then from the routing forwarding list deletion wherein the idiographic flow of computation optimization 3 schemes are arranged, correspond to 3 ranks that preamble is narrated respectively.The concrete processing procedure of rank 1 is as follows:

Adition process:

1) route R adds routing table entry;

2) if next jumping of the father node of R is identical with R, R is labeled as does not choose.

3) otherwise R be labeled as and choose, and check the subtree of R, run into physical node and then recall.

4) if the subtree of R has next to jump the AR identical with R, then deletion.

5) if the subtree of R has next jumping common route identical with R and chooses, then change into and not choosing.

6) if the subtree of R has next jumping common route different with R and do not choose, then change into and choosing.

Delete procedure:

1) the directly deletion if R does not choose.

2) subtree of inspection R runs into physical node and then recalls.

3) if the subtree of R has next to jump the AR identical with the father node of R, then deletion.

4) if the subtree of R has next jumping common route identical with the father node of R and chooses, then change into and not choosing.

5) if the subtree of R has next jumping common route different with the father node of R and do not choose, then change into and choosing.

6) route R deletes from routing table;

The concrete processing procedure of rank 2 is as follows:

Adition process:

1) route R adds routing table entry;

2), then finish if next jumping of the father node of R is identical with R.

3) if the father node of R is AR, then delete father node AR, and recomputate AR for another branch of father node.

4) upwards progressively check fraternal subtree from R, run into physical node and then recall.Find and comprise R's and next jumps all identical with R maximum subtree.

5) root node in maximum subtree increases an AR.Next jumping is exactly next jumping of R.

6) each deletion route that adds all uses the method for rank 1 to adjust adjacent AR.

Delete procedure:

1) if the father node of R is AR, then deletes father node AR.

2) find the brotgher of node B of R.

3) deletion route R.

4) with the adition process treatments B node of rank 2, rebulid this regional AR.

5) each deletion route that adds all uses the method for rank 1 to adjust adjacent AR.

The concrete processing procedure of rank 3 is as follows:

Adition process:

1) route R adds routing table entry;

2) find first non-NULL father node of R top.

3), then finish if next jumping of father node is identical with R

4) father node is AR else if, deletes this AR

5) if father node is not AR, check the direct report non-NULL child node under the father node, if next jumping is all identical with R, then below father node, increase AR.

6) left and right sides subtree of R is respectively got a direct report non-NULL child node, repeat above the processing.

7) each deletion route that adds all uses the method for rank 1 to adjust adjacent AR.

Delete procedure:

1) finds first non-NULL father node of R top.

2) if father node is not AR, then directly delete R, finish.

3) if the left and right sides child node of R is AR, delete these AR.

4) get the direct report non-NULL child node of R, handle it, rebulid this regional AR with the adition process of rank 3.

Claims

1. A routing table compression method of a network data forwarding device, adopting a binary base tree data structure to construct a routing table, submitting effective routes in the routing table to an IP forwarding engine, storing in the forwarding routing table, and forwarding the engine according to the forwarding route The specific instruction content of the table is to perform the forwarding function of the message; for the routes with the same next-hop address in the IP routing table, replace them with a route with a shorter mask, which is called aggregated route, and is characterized in that:

Based on the routing table of the forwarding device, calculate the aggregated route;

Submit aggregated routes and routes that cannot be aggregated to the forwarding routing table, and routes covered by aggregated routes will not be submitted to the forwarding routing table;

The original route is replaced by the aggregated route, and the forwarding routing table is compressed; the method for calculating the aggregated route is:

(1) The continuous empty node area in the base tree is an optimizable interval, and the real subnodes directly connected to the nodes in the optimizable interval are optimizable objects;

(2) Increase and calculate the aggregate route on the optimized empty node;

(3) There is no correlation between discontinuous optimizable intervals, and aggregation calculations are performed separately.

2. routing table compression method according to claim 1, it is characterized in that increasing and calculating the operation of aggregation route is: utilize the natural aggregation in routing table, be covered by superior route and the same route of next hop is not selected, does not Submit to the forwarding routing table.

3. The routing table compression method according to claim 1, characterized in that the operation of increasing and calculating aggregated routes is: for an optimizable interval, only when the routing of the entire interval or a sub-interval has the same next hop Only when a summary route is generated, it may not cover the entire interval.

4. The routing table compression method according to claim 1, wherein the operation of increasing and calculating aggregated routes is: for an optimizable interval, get the next hop with the largest number in the interval to generate an aggregated route, covering the entire interval .