Two tiered packet labeling for data network traceback

• US 20080002725A1
• Filed: 06/30/2006
• Published: 01/03/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Alicherry, Mansoor Ali Khan, Muthusrinivasan, Muthuprasanna, Kumar, Vijay Pochampalli, Manimaran, Govindarasu
• Granted Patent: US 7,619,990 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 49/55 Prevention, detection or correction of errors
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

Disclosed is a two tier packet labeling technique for use in connection with network traceback in a network having multiple autonomous systems, with routers and other network resources within each autonomous system. Tier 1 labels are assigned at the autonomous system level, and tier 2 labels are assigned at the router level. In order to reduce the number of labels that are required, a technique called logical partitioned coloring may be used, in which certain autonomous systems and border routers may be logically partitioned into a plurality of mesh connected nodes, and the labels are assigned to these mesh-connected nodes. During network operation the network routers store either tier 1 or tier 2 labels in data packets. The determination of whether to store a label in any particular packet, and the determination of which label to store, may be determined probabilistically by the network router.

Claims

1. A method for operation of a network router within an autonomous system comprising the steps of:

receiving data packets;

storing a label in at least a plurality of said data packets, said label chosen from a group comprising;

a first tier label associated with said autonomous system; and

a second tier label associated with said network router; and

transmitting said data packets to another network router.

2. The method of claim 1 further comprising the step of:

storing a random identifier associated with said network router in said plurality of data packets.

3. The method of claim 1 further comprising the step of:

determining probabilistically whether a label is to be stored in a data packet.

4. The method of claim 1 further comprising the step of:

determining probabilistically whether said first tier or said second tier label is stored in said data packet.

5. The method of claim 1 wherein said first tier label is pre-assigned to said autonomous system utilizing distance-k labeling.

6. The method of claim 5 wherein k=2.

7. A method for assigning network traceback labels comprising the steps of:

assigning at least one tier 1 label to each of a plurality of autonomous systems utilizing distance-k labeling; and

assigning at least one tier 2 label to each border router within said autonomous systems, each of said tier 2 labels being unique within a particular autonomous system.

8. The method of claim 7 further comprising:

assigning a plurality of tier 1 labels to at least one of said autonomous systems.

9. The method of claim 8 wherein said step of assigning a plurality of tier 1 labels to at least one of said autonomous systems comprises:

logically partitioning said at least one of said autonomous systems into a plurality of mesh connected nodes; and

assigning a different tier 1 label to each of said mesh connected nodes.

10. The method of claim 9 wherein said step of assigning a plurality of tier 1 labels to at least one of said autonomous systems further comprises:

associating each of said plurality of mesh connected nodes with at least one border router in said at least one of said autonomous systems.

11. The method of claim 7 further comprising:

assigning a plurality of tier 2 labels to at least one of said border routers.

12. The method of claim 11 wherein said step of assigning a plurality of tier 2 labels to at least one of said border routers comprises:

logically partitioning said at least one of said border routers into a plurality of mesh connected nodes; and

assigning a different tier 2 label to each of said mesh connected nodes.

13. The method of claim 12 further comprising the step of:

associating each of said plurality of mesh connected nodes with at least one interface of said at least one of said border routers.

14. The method of claim 7 further comprising the step of:

identifying an overlay network comprising said plurality of autonomous systems.

15. The method of claim 7 wherein k=2.

16. A network router associated with an autonomous system, said network router comprising:

means for receiving data packets;

means for storing a label in at least a plurality of said data packets, said label chosen from a group comprising;

a first tier label associated with said autonomous system; and

a second tier label associated with said network router; and

means for transmitting said data packets to another network router.

17. The network router of claim 16 further comprising:

means for storing a random identifier associated with said network router in said plurality of data packets.

18. The network router of claim 16 further comprising:

means for determining probabilistically whether a label is to be stored in a data packet.

19. The network router of claim 16 further comprising:

means for determining probabilistically whether said first tier or said second tier label is stored in said data packet.

20. The network router of claim 16 wherein said first tier label is pre-assigned to said autonomous network utilizing distance-k labeling.