DETECTION OF ROUTING LOOPS BASED ON TIME-TO-LIVE EXPIRIES

• US 20090161567A1
• Filed: 12/21/2007
• Published: 06/25/2009
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Inventors: Jayawardena, Thusitha, Shugard, William J.
• Granted Patent: US 7,752,666 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 43/0847 Transmission error
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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/247 using M:N active or standby paths
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A method and system for detecting routing loops and time-to-live (TTL) expiry attacks in a telecommunications network are disclosed. The detection of routing loops and TTL expiry attacks can be achieved based on the comparison of TTL expiries occurring on two or more routers in the network. A quantity of TTL expiries associated with a router can be summed. Additionally, a quantity of TTL expiries associated with other routers that are operatively coupled to the router can be summed. A difference between the sums can be calculated and a determination of whether a routing loop exists can be made in response to the difference.

Claims

1. A method of detecting routing loops in a network comprising determining whether a routing loop exists based on a relationship between a quantity of time-to-live (TTL) expiries associated with at least one first router in a network and a quantity of TTL expiries associated with at least one second router in the network.

2. The method of claim 1, wherein the quantity of TTL expiries associated with the at least one first router in the network comprises a first sum of TTL expiries and the quantity of TTL expiries associated with at least one second router in the network comprises a second sum of TTL expiries.

3. The method of claim 2, wherein determining whether a routing loop exists comprises calculating a difference between the first sum and the second sum, the method further comprising determining that a routing loop exists in response to the difference exceeding a predetermined value.

4. The method of claim 1, further comprising determining whether a TTL expiry attack exists based on the quantities of TTL expiries associated with the at least one first router and the at least one second router.

5. The method of claim 1, wherein the at least one second router is operatively coupled to the at least one first router.

6. The method of claim 1, wherein determining whether a routing loop exists comprises:

identifying a signature based on the quantities of TTL expiries associated with the at least one first router and the at least one second router; and

distinguishing between a routing loop and a TTL expiry attack based on the signature.

7. A computer-readable storage medium comprising instructions, wherein execution of the instructions by at least one computing device detects a routing loop in a network by determining whether a routing loop exists based on a relationship between a quantity of time-to-live (TTL) expiries associated with at least one first router in a network and a quantity of TTL expiries associated with at least one second router in the network.

8. The medium of claim 7, wherein the quantity of time-to-live (TTL) expiries associated with the at least one first router in the network comprises a first sum of TTL expiries and the quantity of TTL expiries associated with at least one second router in the network comprises a second sum of TTL expiries.

9. The medium of claim 8, wherein determining whether a routing loop exists comprises calculating a difference between the first sum and the second sum, the medium further comprising determining that a routing loop exists in response to the difference exceeding a predetermined value.

10. The medium of claim 7, further comprising determining whether a TTL expiry attack exists based on the quantities of TTL expiries associated with the at least one first router and the at least one second router.

11. The medium of claim 7, wherein the at least one second router is operatively coupled to the at least one first router.

12. The medium of claim 7, wherein determining whether a routing loop exists comprises:

identifying a signature based on the quantities of TTL expiries associated with the at least one first router and the at least one second router; and

distinguishing between a routing loop and a TTL expiry attack based on the signature.

13. The medium of claim 7, wherein the determining comprises distinguishing between a persistent and transient routing loop based on the TTL expiry quantities associated with a plurality of time intervals.

14. The medium of claim 7, wherein determining whether a routing loop exists comprises comparing the quantity of TTL expiries associated with the at least the one first router to quantities of TTL expiries from historical data to distinguish between a persistent routing loop, a transient routing loop, or a TTL expiry attack.

15. The medium of claim 7, further comprising:

determining a TTL expiry attack occurred based on the quantities of TTL expiries associated with the at least one first router and the at least one second router; and

determining the routers involved in a TTL expiry attack in response to a signature.

16. A system for detecting routing loops in a network having a plurality of routers, the system comprising a computing device configured to determine whether a routing loop exists based on a relationship between a quantity of TTL expiries associated with at least one first router and a quantity of TTL expiries associated with at least one second router in the network.

17. The system of claim 16, wherein the quantity of TTL expiries associated with at least one first router in the network comprises a first sum of TTL expiries and the quantity of TTL expiries associated with at least one second router in the network comprises a second sum of TTL expiries.

18. The system of claim 17, wherein the computing device calculates a difference between the first sum and the second sum and determines a routing loop exists in response to the difference exceeding a predetermined value.

19. The system of claim 16, wherein the computing device identifies a signature based on the quantity TTL expiries associated with the at least one first router and the quantity of TTL expiries associated with the at least one second router and distinguishes between a routing loop and a TTL expiry attack in response to the signature.

20. The system of claim 16, wherein the computing device associated with the at least one first router and the at least one second router associated with a plurality of time intervals, the computing device distinguishing between a persistent and transient routing loop based on the TTL expiry quantities associated with the plurality of time intervals.