CN101515899B - Route generation method and device - Google Patents

Abstract

The embodiment of the present invention provides a route generation method and device. The embodiment of the present invention provides a route generation method, comprising: receiving an update message sent by a neighbor node; comparing the optimal route information of the current node with the neighbor node, and updating the optimal route information of the current node; determining the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table items of each node; and obtaining at least one next-hop route information of the IP address reaching the same destination network according to the upstream and downstream relationship of each node.

Description

A method and device for generating a route

technical field

The present invention relates to the field of network technology, and more specifically, to a route generation method and device.

Background technique

With the development of science and technology, the Internet is becoming more and more popular, and the connection of various networks mainly depends on routers. Routers are the hub of the Internet, and routers determine data forwarding through routing. Routing is the activity of moving information from a source location to a destination location through an interconnected network. Generally speaking, in the routing process, information will pass through at least one or more intermediate nodes. As the hub of interconnection between different networks, the router system constitutes the main context of the TCP/IP-based international interconnection network Internet. It can also be said that the router constitutes the skeleton of the Internet. Its processing speed is one of the main bottlenecks of network communication, and its reliability directly affects the quality of network interconnection. Therefore, in the field of campus network, regional network, and even the entire Internet research, router technology has always been at the core, and its development history and direction have become a microcosm of the entire Internet research.

Among the existing relatively mature routing protocols, whether it is the RIP (Routing Information Protocol, Routing Information Protocol) protocol based on the distance vector algorithm, or the OSPF (OpenShortest Path First, open shortest path first) protocol based on the link state, all belong to the Single next hop routing protocol. In the process of data transmission using the single-next-hop routing protocol method, although the best path for packet forwarding can be found and established, when a link failure occurs, the transmitted data cannot be switched to other routes for transmission, resulting in data The packet loss rate is relatively high during transmission.

Contents of the invention

Embodiments of the present invention provide a method and device for generating a route to solve the problem that in the prior art, when a link failure occurs in a single-next-hop route, the transmitted data cannot be switched to other routes for transmission, resulting in data loss during data transmission. The problem of relatively high packet rate.

An embodiment of the present invention provides a method for generating a route, including:

Receive update messages sent by neighbor nodes;

Comparing the optimal routing information of the current node with the neighbor node, updating the optimal routing information of the current node;

Determine the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node;

Obtain at least one next-hop routing information to the IP address of the same destination network according to the upstream and downstream relationship of each node;

The updating of the optimal routing information of the current node includes:

If the routing information from the current node to the IP address of the destination network is not the optimal routing information, then write the optimal routing information obtained by comparing with the neighbor node into the current node routing table entry;

Write the current node routing table entry into the update message and send it to the neighbor nodes.

Further, after obtaining the upstream and downstream relationships of each node, it also includes:

Construct directed edges from upstream nodes to downstream nodes among neighbor nodes;

The directed edges between multiple neighbors are cascaded to form a directed routing graph with the destination network IP address as the end point.

Further, if the update message received by the current node contains a routing table entry that does not exist in the routing table entry of the current node, the current node writes the routing table entry that it does not have into the routing table entry of the current node.

Further, determining the upstream and downstream relationship of each node includes:

Comparing the optimal distance to the IP address of the same destination network in the routing table entries of each node, the upstream node with the largest optimal distance, and the downstream node with the smallest optimal distance;

If the optimal distances to the same destination network address in the routing table entries of different nodes are the same, compare the router IDs of the nodes, the node with the larger router ID is the upstream node, and the node with the smaller router ID is the downstream node.

Further, the router ID is the smallest IP address among the interfaces of the current node.

Further, determining the upstream and downstream relationship of each node also includes: when the current node receives a routing entry that it does not have, setting the neighbor node that sent the routing entry as the downstream node of the current node, and when the When the above neighbor node is better than the original downstream node, the neighbor node is used to replace the original downstream node.

Further, the content of the update message includes: the IP address of each destination network, the subnet mask, the next-hop route, the distance to each destination network, and the router ID.

Further, the content of the update message is written into the No. 6 identifier of the RIP protocol message, and a field for storing the value of the router ID is added in the routing information part.

The embodiment of the present invention also provides a route generation device, including:

a receiving unit, configured to receive an update message sent by a neighbor node;

A comparing and updating unit, configured to compare the optimal routing information of the current node with the neighbor node, and update the optimal routing information of the current node, wherein the updating of the optimal routing information of the current node includes: if the current node reaches the IP address of the destination network When the routing information is not the optimal routing information, the optimal routing information compared with the neighbor node is written into the current node routing table item; the current node routing table item is written into the update message and sent to the neighbor node;

An identification and determination unit is used to determine the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node;

The obtaining unit is used to obtain the next-hop routing information of a plurality of IP addresses reaching the same destination network according to the upstream-downstream relationship of each node.

Further, the device embodiment also includes:

An edge building unit is used to construct directed edges from upstream nodes to downstream nodes among neighbor nodes;

The graph composition unit is used to cascade the directed edges between multiple neighbors to form a route directed graph with the IP address of the destination network as the end point.

Compared with the prior art, at least one or more available next-hop routes are provided in the embodiments of the present invention, and the transmission data can be quickly switched to other routes in the event of a link failure, which significantly reduces the traffic in data transmission. Packet loss rate.

In the embodiment of the invention, the routing directed graph obtained based on the mechanism of comparing the optimal distance and the router ID can ensure that there will be no loops during parallel data transmission, and solve the problem of bottleneck link congestion caused by single-next-hop routing .

In the embodiment of the present invention, obtaining at least one next-hop route can be realized by simple improvement based on the traditional RIP protocol update message, which is simple and easy.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained according to these drawings without any creative effort.

Fig. 1 is the flowchart of the method embodiment 1 of the present invention;

2 is a flow chart of steps for determining the upstream and downstream relationships of each node in Embodiment 1 of the present invention;

Fig. 3 is a flow chart of steps for determining the upstream and downstream relationships of each node in Embodiment 2 of the method of the present invention;

Fig. 4 is the routing directed graph with the IP address of the destination network as the end point constructed in the third embodiment of the method of the present invention;

FIG. 5 is a schematic structural diagram of a route generation device in Embodiment 4 of the device of the present invention.

Detailed ways

The embodiment of the present invention provides a route generation method and device.

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

In Embodiment 1 of the method of the present invention, referring to FIG. 1, the route generation method may include:

Step 101, receiving an update message sent by a neighbor node;

When implementing step 101, the content of the update message can include: the IP address of each destination network, the subnet mask, the next hop route, the distance to each destination network and the router ID; the router ID can be the current node's The smallest IP address in the interface.

Step 102, comparing the optimal routing information of the current node with the neighbor node, and updating the optimal routing information of the current node;

When implementing step 102, updating the optimal routing information of the current node may include:

If the routing information from the current node to the IP address of the destination network is not the optimal routing information, then write the optimal routing information compared with the neighbor node into the current node routing table item; write the current node routing table item into the update message sent to neighbor nodes. The current node can send the update message written in the routing table entry of the current node to the neighbor node at an interval of 30 seconds or 60 seconds. The sending time can be set according to the actual situation. The faster the update speed is, the slower it is vice versa. In general, in order to reduce the network bandwidth resources occupied by the routing update packets used to establish the routing table in the network, the timing update time is set to 30s, which refers to the RIP protocol has been 30s Of course, it can also be other time.

In the process of updating the optimal routing information, if the update message received by the current node contains routing table items that are not in the routing table items of the current node, the current node will write the routing table items that it does not have into the routing table of the current node item.

The content of the routing entry of the current node may include: the IP address of the destination network, the subnet mask of the destination network, the next-hop IP address, and the distance to the destination network. Write the content of the routing table entry of the current node containing the above content into the update message, the update message can use the RIP protocol message, and enable the No. 6 mark in the command field of the header of the message, And a 32-bit router ID field is added to the content of the update message. In the specific implementation, it should be noted that when the router is connected to the network, the host or LAN directly connected to the router interface will be added to the routing table entry of the current node as the reachable destination, and the current node will go to the host or LAN. The distance can be set to 0.

Step 103, determining the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node;

When implementing step 103, referring to FIG. 2, determining the upstream and downstream relationship of each node may include:

Step 201, comparing the optimal distances to the IP addresses of the same destination network in the routing table entries of each node, the one with the larger optimal distance is the upstream node, and the one with the smaller optimal distance is the downstream node;

Step 202, if the optimal distances to the same destination network address in the routing table entries of different nodes are the same, compare the router IDs of the nodes, the node with the larger router ID is the upstream node, and the node with the smaller router ID is the downstream node.

When implementing step 202, the router ID can be the smallest IP address in the interface of the current node; the router ID can also be the largest IP address in the interface of the current node, or the router ID can also be the IP address in the interface of the current node Any IP address; in short, when setting the router ID, ensure that the value of the router ID does not change during the entire route generation process.

Step 104, according to the upstream and downstream relationship of each node, obtain at least one next-hop routing information to the IP address of the same destination network.

When implementing step 104, according to the upstream and downstream relationship of each node, multiple routing information to the IP address of the same destination network can be obtained, including better routing and poorer routing information, and also including different next hops and different exits. Different routing information, these routing information can be saved, and used to forward data according to the situation in practical applications. Although the optimal routing information may be updated after obtaining more optimal routing information, as long as the exit of the transmitted data is different from the exit of the new optimal routing, it needs to be reserved as the suboptimal one, so that when encountering the optimal When the routing line is congested, the data transmission can be switched to other routing lines in time.

In the first embodiment above, the method for determining the upstream and downstream relationship of nodes is introduced in step 103. When determining the upstream and downstream relationship of each node, the potential energy difference can also be added in the routing table entry of the node, and the potential energy difference can be determined by the increased potential energy difference. Indicates the upstream and downstream relationship between the next hop node and the current node. The potential energy difference can be used as a parameter when data is forwarded, that is, the routing table entry when the potential energy difference is positive is the downstream node, which can be used for data forwarding; the potential energy difference is negative, which indicates the downstream node and cannot be used for data forwarding. Forward.

When transmitting data, it can be stipulated that the data is only transmitted from the upstream node to the downstream node. An upstream node can transmit data to multiple downstream nodes in parallel. It can also be based on the distance to the destination network and the potential energy difference in the current node routing entry The size is used to distinguish the priority of each input interface and the distribution ratio of data traffic. For example: two nodes A and B, the distance value to the destination network in the routing table entry of node A is larger than that of node B, then node A has a lower priority in data transmission; if the routing table entry of node A and node B If the distances to the destination network are equal, node A and node B have the same priority in data transmission; of course, if the distances to the destination network in the routing table entries of node A and node B are equal, node A can also be further compared The potential energy difference with node B, the node with a smaller potential energy difference has a higher priority, and the node with a larger potential energy difference has a lower priority. The distribution ratio of traffic during data transmission can be adopted: the distance value from the node routing table entry to the destination network is simply taken as the opposite number, and then the ratio of these opposite numbers is calculated to be the distribution ratio of the data flow of each node.

In the process of determining the upstream and downstream relationship of each node, when the current node receives a routing entry that it does not have, the neighbor node that sends the routing entry is set as the downstream node of the current node, and when the neighbor When a node is better than the original downstream node, the neighbor node is used to replace the original downstream node. The neighbor node described here is better than the original downstream node may mean: when the neighbor is used as the next hop, the distance from the current node to the destination is smaller than the distance from the current node to the destination network when the original downstream node is selected as the next hop. The calculation method of this distance may be: the result of extracting the distance information from the received routing entry and adding the link cost connected to the corresponding neighbor. For the specific calculation method, please refer to the second embodiment below.

The difference between the second embodiment of the method of the present invention and the first embodiment is that it introduces another method for determining the upstream and downstream relationship of each node. Referring to FIG. 3, it may include:

获取节点k经过节点i到目的网络j的代价信息，所述代价信息设为 $D_{\mathrm{jk}}^i;$ Step 301, preset the current node as i, the neighbor node as k, and the destination network as j, receive the update message sent by the neighbor node k, and obtain the link cost between node i and node k, and the link cost is set to

Obtain the cost information of node k passing through node i to the destination network j, the cost information is set to ${\mathrm{D.}}_{\mathrm{jk}}^i;$

Step 302, according to the information of the destination network j contained in the update message, check whether the routing table entry of node i contains the routing information to the destination network j, if yes, then go to step 304, otherwise go to step 303;

同所述链路代价

之和作为节点i到目的网络j的距离写入到节点i的路由表项中，将所述链路代价取正值后作为节点i的势能差值写入节点i的路由表项中，设置下一跳IP地址为与节点k相连的接口的IP地址；Step 303, the cost information

link cost

The sum is written into the routing table entry of node i as the distance from node i to destination network j, and the link cost Take a positive value and write it into the routing table entry of node i as the potential energy difference of node i, and set the next-hop IP address as the IP address of the interface connected to node k;

同所述链路代价

之和是否小于节点i的路由表项中到目的网络j的最优距离，如果是，则转入步骤305，否则转入步骤306；Step 304, judging the cost information

link cost

Whether the sum is less than the optimal distance to the destination network j in the routing table entry of node i, if yes, then proceed to step 305, otherwise proceed to step 306;

同所述链路代价

之和作为节点i到目的网络j的距离写入到节点i的最优路由表项中，将所述链路代价

取正值后作为节点i的势能差值写入节点i的最优路由表项中，设置下一跳IP地址为与节点k相连的接口的IP地址，将节点i原来的最优路由表项设为节点i的次优路由表项；Step 305, set node k as the downstream node of node i, replace node k as the original optimal downstream node of node i, and set the original optimal downstream node of node i as the suboptimal downstream node of node i; price information

link cost

The sum is written into the optimal routing entry of node i as the distance from node i to destination network j, and the link cost

After taking a positive value, write it into the optimal routing table item of node i as the potential energy difference of node i, set the next-hop IP address as the IP address of the interface connected to node k, and write the original optimal routing table item of node i Set as the suboptimal routing entry of node i;

是否小于节点i路由表项中到目的网络j的最优距离，如果是，则转入步骤307，否则，转入步骤308；Step 306, judging the cost information

Whether it is less than the optimal distance to the destination network j in the node i routing table entry, if yes, then proceed to step 307, otherwise, proceed to step 308;

Step 307, the optimal routing entry of node i remains unchanged, and node k is set as the suboptimal downstream node of node i, and the routing cost, potential energy difference and next-hop IP in the suboptimal node routing entry are set in the same step 303;

是否等于节点i路由表项中到目的网络j的最优距离，如果是，则转入步骤309，否则，转入步骤310；Step 308, judging the cost information

Whether it is equal to the optimal distance to the destination network j in the node i routing table entry, if yes, then proceed to step 309, otherwise, proceed to step 310;

Step 309, judge whether the router ID of node i is greater than the router ID of node k, if yes, then proceed to step 311, otherwise, proceed to step 312;

Step 310, set node k as the upstream node of node i, and the potential energy difference of node i is Take a negative value, the routing table entry of node i and the setting of the next hop IP address are the same as step 303;

Step 311, set node k as the downstream node of node i, and the potential energy difference of node i is The routing table entry of node i and the setting of the next hop IP address are the same as step 303;

取负值，节点i的路由表项及下一跳IP地址的设置同步骤303。Step 312, set node k as the upstream node of node i, and the potential energy difference is

If the value is negative, the setting of the routing table entry and next-hop IP address of node i is the same as step 303.

The above implementation examples describe in detail how to determine the upstream and downstream relationship of each node. After determining the upstream and downstream relationship of each node, in the third embodiment of the method of the present invention, after determining the upstream and downstream relationship of each node, further include :

Construct directed edges from upstream nodes to downstream nodes among neighbor nodes; cascade directed edges between multiple neighbors to form a routing directed graph with the IP address of the destination network as the end point. Data can be forwarded along the directed graph during data forwarding.

Directed edge is a conceptual term in mathematical graph theory. Since the network is generally abstracted as a graph (graph), routers are abstracted as nodes, links are abstracted as edges, and directed edges have directions. The edge, the direction of the directed edge here is that the upstream node points to the downstream node.

The constructed directed graph can be seen in Figure 4. Node D in the figure can be the destination network, and other nodes S and N1-7 can be nodes in the entire data transmission process. When data is transmitted, it can be from the upstream node S to the downstream Nodes N1, N3, and N6 transmit data in parallel. Node N6 can transmit data to destination network D via downstream nodes N2 and N7. Node N6 can also directly transmit data to destination network D. In practical applications, it is assumed that N6 directly transmits data to The cost of the route to the destination network D is the smallest, then N6 can choose to directly transfer the data to the destination network D, when this route is congested, then N6 can switch to the route via node N2 to the destination network D in time Data transmission can also be switched to the route from node N7 to destination network D to transmit data; or according to the actual application bandwidth, N6 can transmit data in parallel through the above three routing lines.

According to the routing directed graph, a multi-next-hop routing table can be established for data forwarding. When establishing a multi-next-hop routing table, multiple next-hop routing table entries of the IP address of the same destination network can be linked in the form of a linked list. The head of the linked list stores the routing table item with the best cost. For the optimal routing table entry, the routing table entry with a positive potential energy difference is in front, and the routing table entry with a negative potential energy difference is in the back; secondly, the routing table with a small optimal routing distance is in the front, and the optimal routing distance is large The routing table is after. After the multi-next-hop routing table is established, because the routing table also records the upstream node information, that is, contains entries with negative potential energy differences, it is necessary to first search for the entry that matches the destination address when performing data forwarding, and then search for For entries whose potential energy difference is positive, finally read the next-hop IP address for data forwarding.

The present invention also provides a fourth embodiment of a route generation device, referring to Figure 5, which may include:

A receiving unit 501, configured to receive an update message sent by a neighbor node;

A comparing and updating unit 502, configured to compare the optimal routing information of the current node with the neighbor node, and update the optimal routing information of the current node;

An identification and determination unit 503, configured to determine the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node;

The obtaining unit 504 is configured to obtain at least one next-hop routing information to an IP address of the same destination network according to the upstream-downstream relationship of each node.

Further can also include:

An edge construction unit 505, configured to construct a directed edge from an upstream node to a downstream node in a neighbor node;

The graph composition unit 506 is configured to cascade the directed edges between multiple neighbors to form a directed routing graph with the IP address of the destination network as the end point, and forward data along the directed graph.

Before forwarding the data, the receiving unit 501 first receives the update message sent by the neighbor node, and the receiving unit 501 sends the update message to the comparison and update unit 502, and the comparison and update unit 502 sends the neighbor node contained in the message to the latest update message of the destination network. Compare the optimal routing information with the optimal routing information in the routing table entry of the current node, write the compared optimal routing information into the routing table entry of the current node, and write the updated routing table entry of the current node into The update message is sent to the neighbor node; after the identification determination unit 503 receives the information of the comparison update unit 502, after the exchange of routing information between each node, the IP address of the same destination network in the routing table entry of each node can be used The optimal distance determines the upstream and downstream relationship of each node; the acquisition unit 504 obtains at least one next-hop routing information to the IP address of the same destination network according to the upstream and downstream relationship of each node determined by the identification determination unit 503 . Further, after receiving the information from the identification determination unit 503, the edge building unit 505 can construct the directed edge from the upstream node to the downstream node in each node according to the upstream and downstream relationship of each node; then the composition unit 506 obtains the edge building unit 505 After information, the directed edges between multiple neighbors are cascaded to form a routing directed graph with the IP address of the destination network as the end point, and data can be forwarded along the directed graph.

Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other. As for the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and for the related information, please refer to the description of the method part.

Professionals can understand that the units and method steps described in conjunction with the embodiments disclosed herein can be implemented by electronic hardware, computer software, or a combination of the two. In order to clearly illustrate the interchangeability of hardware and software In the above description, the components and steps of each example have been generally described according to their functions. Whether these functions are executed by hardware or software depends on the specific application and design constraints of the technical solution. Those skilled in the art may use different methods to implement the described functions for each specific application, but such implementation should not be regarded as exceeding the scope of the present invention.

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be completed by instructing related hardware through computer programs, and the programs can be stored in a computer-readable storage medium, so When the above-mentioned program is executed, it may include the processes of the embodiments of the above-mentioned methods. Wherein, the storage medium may be a magnetic disk, an optical disk, a read-only memory (Read-Only Memory, ROM) or a random access memory (Random Access Memory, RAM), etc.

The above description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be implemented in other embodiments without departing from the spirit or scope of the invention. Therefore, the present invention will not be limited to the embodiments shown herein, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (10)

1. A route generating method, characterized in that, comprising: Receive update messages sent by neighbor nodes; Comparing the optimal routing information of the current node with the neighbor node, updating the optimal routing information of the current node; Determine the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node; Obtain at least one next-hop routing information to the IP address of the same destination network according to the upstream and downstream relationship of each node; The updating of the optimal routing information of the current node includes: If the routing information from the current node to the IP address of the destination network is not the optimal routing information, then write the optimal routing information obtained by comparing with the neighbor node into the current node routing table entry; Write the current node routing table entry into the update message and send it to the neighbor nodes. 2. The method according to claim 1, characterized in that, after obtaining the upstream and downstream relationship of each node, it also includes: Construct directed edges from upstream nodes to downstream nodes among neighbor nodes; The directed edges between multiple neighbors are cascaded to form a directed routing graph with the destination network IP address as the end point. 3. The method according to claim 1, further comprising: if the update message received by the current node contains a routing table item that does not exist in the routing table item of the current node, then the current node adds the routing table item that it does not have The entry is written into the routing table entry of the current node. 4. The method according to claim 1, wherein said determining the upstream and downstream relationship of each node comprises: Comparing the optimal distance to the IP address of the same destination network in the routing table entries of each node, the upstream node with the largest optimal distance, and the downstream node with the smallest optimal distance; If the optimal distances to the same destination network address in the routing table entries of different nodes are the same, compare the router IDs of the nodes, the node with the larger router ID is the upstream node, and the node with the smaller router ID is the downstream node. 5. The method according to claim 4, wherein the router ID is the smallest IP address among the interfaces of the current node. 6. The method according to claim 4, wherein the determining the upstream-downstream relationship of each node further comprises: when the current node receives a routing entry that it does not have, sending the routing entry The neighbor node of is set as the downstream node of the current node, and when the neighbor node is better than the original downstream node, the neighbor node is used to replace the original downstream node. 7. The method according to claim 1, wherein the content of the update message includes: the IP address of each destination network, the subnet mask, the next hop route, the distance to each destination network and the router ID . 8. The method according to claim 7, wherein the content of the update message is written into the No. 5 mark of the RIP protocol message, and a field for storing the value of the router ID is added in the routing information part. 9. A route generation device, characterized in that, comprising: a receiving unit, configured to receive an update message sent by a neighbor node; A comparing and updating unit, configured to compare the optimal routing information of the current node with the neighbor node, and update the optimal routing information of the current node, wherein the updating of the optimal routing information of the current node includes: if the current node reaches the IP address of the destination network When the routing information is not the optimal routing information, the optimal routing information compared with the neighbor node is written into the current node routing table item; the current node routing table item is written into the update message and sent to the neighbor node; An identification and determination unit is used to determine the upstream and downstream relationship of each node according to the optimal distance to the IP address of the same destination network in the routing table entry of each node; The acquiring unit is configured to acquire at least one next-hop routing information to an IP address of the same destination network according to the upstream-downstream relationship of each node. 10. The apparatus of claim 9, further comprising: An edge building unit is used to construct directed edges from upstream nodes to downstream nodes among neighbor nodes; The graph composition unit is used to cascade the directed edges between multiple neighbors to form a route directed graph with the IP address of the destination network as the end point.

Images