Routing table creation method, electronic device, and network

Patent metadata

Field	Value
Publication number	US-10708167-B2
Application number	US-201816022729-A
Country	US
Kind code	B2
Filing date	Jun 29, 2018
Priority date	Dec 30, 2015
Publication date	Jul 7, 2020
Grant date	Jul 7, 2020

Abstract

A routing table creation method, an electronic device, and a network are provided. The method includes: generating a first probe packet, where the first probe packet has a source address and a destination address; sending, from a source node corresponding to the source address, the first probe packet on a network including at least two nodes, until the first probe packet reaches a destination node corresponding to the destination address, and recording addresses of nodes through which the first probe packet passes, to form a first path; generating a second path according to the first path, where the second path is a reverse path of the first path; generating a first response packet, sending the first response packet along a second path until the first response packet reaches the source node; and creating a routing table entry according to the second path.

First claim

What is claimed is:

1. A routing table creation method, comprising:
obtaining, by a first node, a first probe packet, wherein the first probe packet has a source address and a destination address, and the first node is a source node corresponding to the source address or an intermediate node on a path between the source node and a destination node corresponding to the destination address;
obtaining, by the first node, a new first probe packet, wherein when the first node is the intermediate node, the first node records an address of the first node in the first probe packet to form the new first probe packet, and when the first node is the source node, the new first probe packet is the first probe packet;
sending, by the first node, the new first probe packet;
receiving, by the first node, a first response packet, wherein the first response packet describes a second path, the second path is a reverse path of a first path, and the first path comprises addresses of nodes through which the new first probe packet passes; and
creating, by the first node, a routing table entry according to a preceding address of the address of the first node on the second path, wherein the routing table entry comprises the destination address, and an address of a next hop node and an outbound interface, and wherein the address of the next hop node is the preceding address of the first node on the second path.

2. The method according to claim 1 , wherein the method further comprises:
creating, by the first node, a path evaluation table entry, wherein the path evaluation table entry comprises the source address and the destination address, the address of the next hop node and the outbound interface, an evaluated value that is of both the next hop node and the outbound interface, and a service identifier and/or a service target, and the address of the next hop node is the preceding address.

3. The method according to claim 1 , wherein the sending, by the first node, the new first probe packet comprises:
randomly selecting, by the first node, a next hop node and an outbound interface, and sending the new first probe packet.

4. A routing table management method, comprising:
obtaining, by a first node, a second probe packet, wherein the second probe packet has a source address and a destination address, and the first node is a source node corresponding to the source address or an intermediate node on a path between the source node and a destination node corresponding to the destination address;
obtaining, by the first node, a new second probe packet, wherein when the first node is the intermediate node, the first node records an address of the first node in the second probe packet to form the new second probe packet, and when the first node is the source node, the new second probe packet is the second probe packet;
sending, by the first node and with a predetermined probability, the new second probe packet according to a pre-created routing table entry;
receiving, by the first node, a second response packet, wherein the second response packet comprises a fourth path, the fourth path is a reverse path of a third path, and the third path comprises addresses of nodes through which the new second probe packet passes; and
if a match is successfully found in the routing table entry, and a preceding address of the address of the first node on the fourth path is the same as an address of a next hop node in the routing table entry, updating, by the first node, an evaluated value that is of both the next hop node and an outbound interface in a pre-created path evaluation table entry.

5. The method according to claim 4 , wherein the method further comprises:
if no match is successfully found in the routing table entry, creating, by the first node, a new routing table entry according to the preceding address of the address of the first node on the fourth path.

6. The method according to claim 4 , wherein the method further comprises:
if a match is successfully found in the routing table entry, and the preceding address of the address of the first node on the fourth path is different from the address of the next hop node in the routing table entry, determining, by the first node, whether to update the routing table entry.

7. The method according to claim 6 , wherein the determining whether to update the routing table entry comprises:
determining, by the first node, an evaluated value that is of both a new next hop node and a new outbound interface; and
determining, by the first node according to the evaluated value that is of both the new next hop node and the new outbound interface and the evaluated value that is of both the next hop node and the outbound interface in the path evaluation table entry, whether to update the routing table entry.

8. The method according to claim 6 , wherein the determining whether to update the routing table entry comprises:
determining an evaluated value that is of both a new next hop node and a new outbound interface; and
inputting the evaluated value that is of both the new next hop node and the new outbound interface into a random neural network; and determining, according to a computation result of the random neural network, whether to update a routing table entry, wherein each neuron of the random neural network is corresponding to an outbound interface, and the random neural network is trained by using a historical evaluated value that is of both a next hop node and an outbound interface.

9. A routing table creation method, comprising:
generating, by a source node, a first probe packet, wherein the first probe packet has a source address and a destination address, and the source address is an address of the source node;
sending, by the source node, the first probe packet;
receiving, by the source node, a first response packet, wherein the first response packet describes a second path, the second path is a reverse path of a first path, and the first path comprises addresses of nodes through which the first probe packet passes;
generating, by the source node, a first-path creation packet, wherein the first-path creation packet comprises the first path; and
creating, by the source node, a routing table entry according to an address of a next hop node and an outbound interface of the source address on the first path, wherein the routing table entry comprises the destination address, and the address of the next hop node and the outbound interface.

10. The method according to claim 9 , wherein the method further comprises:
if a routing table entry has been created, and an outbound interface in the already-created routing table entry is different from an outbound interface corresponding to the first path, determining, by the source node, whether the outbound interface corresponding to the first path is better; and
when the outbound interface corresponding to the first path is better, updating, by the source node, the already-created routing table entry.

11. The method according to claim 9 , wherein the method further comprises:
sending, by the source node, the first-path creation packet to an intermediate node between the source node and a destination node on the first path, so that the intermediate node updates a routing table entry of the intermediate node according to an address of a next hop and an outbound interface of an address of the intermediate node on the first path.

12. A network, wherein the network comprises a source node, a destination node, and intermediate nodes between the source node and the destination node;
the source node is configured to: generate a second probe packet, and send the second probe packet to a neighboring intermediate node,

Assignees

• Huawei Tech Co Ltd

Inventors

• Jiang Sheng
• Du Zongpeng

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04W40/28

  for reactive routing · CPC title

• H04L45/26

  Route discovery packet · CPC title

• H04L45/54

  Organization of routing tables · CPC title

• H04L45/14

  Routing performance; Theoretical aspects · CPC title