Routing loop determining method and device

• US 10,003,524 B2
• Filed: 11/23/2015
• Issued: 06/19/2018
• Est. Priority Date: 11/26/2014
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Li, Bin
• Primary Examiner(s): Hsu, Alpus H
• Application Number:
  US14/949,466
• Publication Number:
  US 20160149800A1
• Time in Patent Office: 939 Days
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A routing loop determining method and a device. The method includes: acquiring, by a forwarding device in a layer 3 network, a first packet, where a time to live (TTL) value of the first packet is reduced to 0 by the forwarding device; acquiring, by the forwarding device, a second packet whose destination Internet Protocol IP address is the same as that of the first packet; recording, by the forwarding device, a feature of the second packet; forwarding, by the forwarding device, the second packet; and acquiring, by the forwarding device, a third packet according to the feature of the second packet, where a feature of the third packet is the same as that of the second packet, and determining that a routing loop exists. The present disclosure resolves a problem that a loop in a layer 3 network cannot be detected, and improves accuracy of sending a packet.

Claims

1. A routing loop determining method, wherein the method comprises:

recording, by a forwarding device in a layer 3 network, a destination Internet Protocol (IP) address of a first packet when a time to live (TTL) value of the first packet is 1 and is reduced to 0 by the forwarding device;

discarding, by the forwarding device, the first packet;

acquiring, by the forwarding device, a second packet whose destination IP address is the same as that of the first packet;

recording, by the forwarding device, a feature of the second packet, wherein the feature of the second packet comprises a source IP address, the destination IP address, and a sequence number of the second packet;

forwarding, by the forwarding device, the second packet based on the destination IP address and a routing table when a TTL value obtained by reducing a TTL value of the second packet by 1 is greater than 0;

acquiring, by the forwarding device, a third packet according to the feature of the second packet, wherein a feature of the third packet is the same as the recorded feature of the second packet, wherein a source IP address of the third packet is the same as the source IP address of the second packet, wherein a destination IP address of the third packet is the same as the destination IP address of the second packet, and wherein a sequence number of the third packet is the same as the sequence number of the second packet; and

determining that a routing loop exists in response to acquiring the third packet.

2. The method according to claim 1, wherein after determining that the routing loop exists, the method further comprises:

performing, by the forwarding device, route tracking to obtain an address list comprising another forwarding device address for another forwarding device, wherein a destination address of the route tracking is the destination IP address of the second packet; and

determining, by the forwarding device, that the other forwarding device is a looping forwarding device when the other forwarding device address appears at least twice in the address list.

3. The method according to claim 1, wherein acquiring, by the forwarding device, the third packet according to the feature of the second packet and determining that a routing loop exists comprises:

attempting, by the forwarding device, to acquire an Nth packet according to the feature of the second packet, wherein a feature of the Nth packet is the same as that of the second packet, and N is a positive integer greater than 3;

calculating a plurality of TTL differences when the forwarding device acquires the Nth packet, wherein the TTL differences comprise a TTL difference between the third packet and the second packet and a TTL difference between the Nth packet and an (N−

1)th packet;

detecting, by the forwarding device, whether equal TTL differences exist among all of the calculated TTL differences; and

determining, by the forwarding device, that the routing loop exists when equal TTL differences exist among all of the TTL differences.

4. The method according to claim 1, wherein acquiring the second packet whose destination IP address is the same as that of the first packet comprises:

establishing, by the forwarding device, a first access control list (ACL), wherein a value of a destination address match item of the first ACL is the destination IP address of the first packet; and

finding, by the forwarding device, a match from all received packets using the first ACL, to acquire the second packet whose destination IP address is the same as that of the first packet.

5. The method according to claim 4, wherein acquiring the third packet according to the feature of the second packet comprises:

acquiring, by the forwarding device, a first IP address, a second IP address, and a packet sequence number, wherein the first IP address is a source IP address of the second packet, wherein the second IP address is the destination IP address of the second packet, and wherein the packet sequence number is a sequence number of the second packet;

establishing, by the forwarding device, a second ACL, wherein a value of a source address match item of the second ACL is the first IP address, wherein a value of a destination address match item of the second ACL is the second IP address, and wherein a value of a sequence number match item of the second ACL is the packet sequence number; and

finding, by the forwarding device, a match from all received packets using the second ACL, to acquire the third packet whose source IP address, destination IP address, and sequence number are all the same as those of the second packet.

6. A forwarding device, applied to a layer 3 network, wherein the forwarding device comprises:

a network interface; and

at least one processor coupled to the network interface, wherein the at least one processor is configured to;

record a destination Internet Protocol (IP) address of a first packet using the network interface when a time to live (TTL) value of the first packet is 1 and is reduced to 0 by the forwarding device;

discard the first packet;

acquire a second packet whose destination IP address is the same as that of the first packet using the network interface;

record a feature of the second packet, wherein the feature of the second packet comprises a source IP address, the destination IP address, and a sequence number of the second packet;

forward the second packet using the network interface based on the destination IP address and a routing table when a TTL value obtained by reducing a TTL value of the second packet by 1 is greater than 0;

acquire a third packet, using the network interface and according to the feature of the second packet, wherein a feature of the third packet is the same as the recorded feature of the second packet, wherein a source IP address of the third packet is the same as the source IP address of the second packet, wherein a destination IP address of the third packet is the same as the destination IP address of the second packet, and wherein a sequence number of the third packet is the same as the sequence number of the second packet; and

determine that a routing loop exists in response to acquiring the third packet.

7. The forwarding device according to claim 6, wherein the processor is further configured to:

perform route tracking to obtain an address list comprising another forwarding device address for another forwarding device after determining that the routing loop exists, wherein a destination address of the route tracking is the destination IP address of the second packet; and

determine that the other forwarding device is a looping forwarding device when the other forwarding device address appears at least twice in the address list.

8. The forwarding device according to claim 6, wherein the processor is further configured to:

attempt to acquire an Nth packet according to the feature of the second packet, wherein a feature of the Nth packet is the same as that of the second packet, and wherein N is a positive integer greater than 3;

calculate a plurality of TTL differences when the Nth packet is acquired, wherein the TTL differences comprise a TTL difference between the third packet and the second packet and a TTL difference between the Nth packet and an (N−

1)th packet;

detect whether equal TTL differences exist among all of the calculated TTL differences; and

determine that the routing loop exists when equal TTL differences exist among all of the TTL differences.

9. The forwarding device according to claim 6, wherein the processor is further configured to:

establish a first access control list (ACL), wherein a value of a destination address match item of the first ACL is the destination IP address of the first packet; and

find a match from all received packets using the first ACL, to acquire the second packet whose destination IP address is the same as that of the first packet.

10. The forwarding device according to claim 9, wherein the processor is further configured to:

acquire a first IP address, a second IP address, and a packet sequence number, wherein the first IP address is a source IP address of the second packet, the second IP address is the destination IP address of the second packet, and wherein the packet sequence number is a sequence number of the second packet;

establish a second ACL, wherein a value of a source address match item of the second ACL is the first IP address, wherein a value of a destination address match item of the second ACL is the second IP address, and wherein a value of a sequence number match item of the second ACL is the packet sequence number; and

find a match from all received packets using the second ACL, to acquire the third packet whose source IP address, destination IP address, and sequence number are all the same as those of the second packet.

11. A non-transitory computer-readable storage medium comprising instructions which, when executed by a computer, cause the computer to:

record a destination Internet Protocol (IP) address of a first packet when a time to live (TTL) value of the first packet is 1 and is reduced to 0;

discard the first packet;

acquire a second packet whose destination IP address is the same as that of the first packet;

record a feature of the second packet, wherein the feature of the second packet comprises a source IP address, a destination IP address, and a sequence number of the second packet;

forward the second packet based on the destination IP address and a routing table when a TTL value obtained by reducing a TTL value of the second packet by 1 is greater than 0;

acquire a third packet according to the feature of the second packet, wherein a feature of the third packet is the same as the recorded feature of the second packet, wherein a source IP address of the third packet is the same as the source IP address of the second packet, wherein a destination IP address of the third packet is the same as the destination IP address of the second packet, and wherein a sequence number of the third packet is the same as the sequence number of the second packet; and

determine that a routing loop exists in response to acquiring the third packet.

12. The non-transitory computer-readable storage medium according to claim 11, wherein the instructions further cause the computer to:

perform route tracking to obtain an address list comprising another forwarding device address for another forwarding device after determining that the routing loop exists, wherein a destination address of the route tracking is the destination IP address of the second packet; and

determine that the other forwarding device is a looping forwarding device when the other forwarding device address appears at least twice in the address list.

13. The non-transitory computer-readable storage medium according to claim 11, wherein the instructions further cause the computer to:

attempt to acquire an Nth packet according to the feature of the second packet, wherein a feature of the Nth packet is the same as that of the second packet, and wherein N is a positive integer greater than 3;

calculate a plurality of TTL differences when the Nth packet is acquired, wherein the TTL differences comprise a difference between the third packet and the second packet and a TTL difference between the Nth packet and an (N−

1)th packet;

detect whether equal TTL differences exist among all of the calculated TTL differences; and

determine that the routing loop exists when equal TTL, differences exist among all of the TTL differences.