Probabalistic packet marking

• US 20030149777A1
• Filed: 02/04/2003
• Published: 08/07/2003
• Est. Priority Date: 02/07/2002
• Status: Active Grant

• Current Assignee: University Of Massachusetts
• Original Assignee: University Of Massachusetts
• Inventors: Adler, Micah
• Granted Patent: US 7,254,633 B2
• Time in Patent Office: Days
• US Class Current: 709/228
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

A method for probabilistic packet marking in a network includes encoding Internet Protocol (IP) traceback information using b bits located in a packet header. The IP traceback information includes information on an IP traceback path back to a source system and a count of each type of packet. The method also includes forming the IP traceback path as packets are received by a destination system and completing the traceback path after a determined number of packets are received by the destination system.

Claims

1. A method for probabilistic marking in a network comprising:

encoding Internet Protocol (IP) traceback information using b bits located in a packet header, the IP traceback information including information on an IP traceback path back to a source system and a count of each type of packet;

forming the IP traceback path as packets are received by a destination system; and

completing the traceback path after a determined number of packets are received by the destination system.

2. The method of claim 1 further comprising sending packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of 2²ⁿ packets, where n is a number of bits used to describe the IP traceback path.

3. The method of claim 1 further comprising sending packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of (2+ε

)²ⁿ packets, where n is a number of bits used to describe the IP traceback path and where ε

is a constant greater than 0.

4. The method of claim 1 further comprising sending packets from the source system to the destination system using a single path, wherein b>

1 and the determined number of packets is a function of bn²2^b(2+ε

)^4n/x, where x is equal to 2^b and where ε

is a constant greater than zero and n is a number of bits used to describe the IP traceback path.

5. The method of claim 1 further comprising sending packets from the source system to the destination system using a multi-path, wherein b bits is equal to log(2k+1), wherein k is the number of paths used by the source system.

6. An apparatus for probabilistic packet marking in a network, the apparatus comprising:

a memory that stores executable instructions; and

a processor that executes the instructions to;

encode Internet Protocol (IP) traceback information using b bits located in a packet header, the IP traceback information including information on an IP traceback path back to a source system and a count of each type of packet;

form the IP traceback path as packets are received by a destination system; and

complete the traceback path after a determined number of packets are received by the destination system.

7. The apparatus of claim 6 further comprising sending packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of 2²ⁿ packets, where n is a number of bits used to describe the IP traceback path.

8. The apparatus of claim 6 further comprising sending packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of (2+ε

)²ⁿ packets, where n is a number of bits used to describe the IP traceback path and where e is a constant greater than 0.

9. The apparatus of claim 6 further comprising sending packets from the source system to the destination system using a single path, wherein b>

1 and the determined number of packets is a function of bn²2^b(2+ε

)^4n/x, where x is equal to 2^b and where ε

is a constant greater than zero and n is a number of bits used to describe the IP traceback path.

10. The apparatus of claim 6 further comprising sending packets from the source system to the destination system using a multi-path, wherein b bits is equal to log(2k+1), wherein k is the number of paths used by the source system.

11. An article comprising a machine-readable medium that stores executable instructions for probabilistic packet marking in a network, the instructions causing a machine to:

encode Internet Protocol (IP) traceback information using b bits located in a packet header, the IP traceback information including information on an IP traceback path back to a source system and a count of each type of packet;

form the IP traceback path as packets are received by a destination system; and

complete the traceback path after a determined number of packets are received by the destination system.

12. The article of claim 11 further comprising instructions causing a machine to send packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of 2²ⁿ packets, where n is a number of bits used to describe the IP traceback path.

13. The article of claim 11 further comprising instructions causing a machine to send packets from the source system to the destination system using a single path, wherein b=1 and the determined number of packets is a function of (2+ε

)²ⁿ packets, where n is a number of bits used to describe the IP traceback path and where ε

is a constant greater than 0.

14. The article of claim 11 further comprising instructions causing a machine to send packets from the source system to the destination system using a single path, wherein b>

1 and the determined number of packets is a function of bn²2^b(2+ε

)^4n/x, where x is equal to 2^b and where ε

is a constant greater than zero and n is a number of bits used to describe the IP traceback path.

15. The article of claim 11 further comprising instructions causing a machine to send packets from the source system to the destination system using a multi-path, wherein b bits is equal to log(2k+1), wherein k is the number of paths used by the source system.