Method and apparatus for efficiently matching responses to requests previously passed by a network node

• US 20030204626A1
• Filed: 04/24/2002
• Published: 10/30/2003
• Est. Priority Date: 04/24/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wheeler, Graham A.
• Granted Patent: US 7,206,862 B2
• Time in Patent Office: Days
• US Class Current: 709/245
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: H04L 63/1466 Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks

Abstract

A method and system are disclosed for efficiently matching incoming packets to previously forwarded outgoing packets within a network node to ensure a response received by a network node corresponds to a previously forwarded request. The network node receives an outgoing packet including state information and computes a mapping (e.g., hash) function value based upon the state information. Thereafter, the network node sets and entry within a bitmap at a position corresponding to the mapping function value. The network node also receives an incoming packet purportedly responsive to an earlier outgoing packet and includes state information of a type corresponding to the state information of an outgoing packet. The network node computes a mapping function value based upon the state information in the incoming packet. The network node then tests an entry corresponding to the mapping function value within one or more bitmaps including bits set at positions corresponding to previously forwarded outgoing packets. If the corresponding bit is not set within at least one of the bitmaps, then the network node discards the corresponding packet. Finally, in order to maintain a relative sparse bitmap, the entries are reset after detecting a clearance threshold event.

Claims

1. A method for ensuring that a received response message corresponds to a previously forwarded request message on a network node including a mapping function, the method comprising the steps of:

receiving an outgoing packet including state information comprising a first set of data bit values;

first mapping, by the mapping function, the first set of data bit values to render a first mapped data value;

setting an entry within a bitmap at a position corresponding to the mapped data value;

receiving an incoming packet including state information comprising a second set of data bit values, the second set of data bit values being of a type corresponding to the first set of data bit values;

second mapping, by the mapping function, the second set of data bit values to render a second mapped data value;

testing an entry within one or more bitmaps, having positions set in accordance with the setting step, corresponding to the second mapped data value to establish a match with a mapping function value rendered from state information for a previous request packet; and

performing at least one function upon the incoming packet based upon whether the match is established during the testing step.

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

resetting at least a portion of the contents of at least one bitmap, having entries set in accordance with the setting step, upon detecting a clearance threshold event.

3. The method of claim 2 wherein the clearance threshold event comprises expiration of a time period.

4. The method of claim 2 wherein the network node includes at least a first bitmap having entries set during the setting step, and a second bitmap, and wherein the method comprises the further step of:

replacing contents of the second bitmap with contents of the first bitmap upon detecting the clearance threshold event.

5. The method of claim 4 wherein the testing step comprises testing entries in both an entry in the first bitmap and the second bitmap corresponding to the second mapped data value and wherein the match is established, for application during the performing step, if at least one of the corresponding entries in the first bitmap or the second bitmap is set.

6. The method of claim 1 further comprising changing a key incorporated into the mapping function.

7. The method of claim 1 further comprising:

monitoring a level of packets received during a time period; and

modifying, based upon the level of packets received during the time period, at least a size of the bitmap having entries set during the setting step.

8. The method of claim 2 wherein the network node comprises a set of at least three bitmaps arranged as shift registers wherein contents of the first bitmap are shifted into corresponding positions within a second bitmap and contents of the second bitmap are shifted into a third bitmap upon detecting the threshold event, and wherein the method further comprises:

applying a classification rule to a received request to determine which of the set of at least three bitmaps to have a bit set in accordance with the first mapping step, thereby facilitating varying a delay period before a set bit is cleared from the set of three bitmaps.

9. The method of claim 1 wherein the incoming packet is a naming request.

10. The method of claim 9 wherein the naming request is a peer-to-peer name resolution protocol request.

11. The method of claim 1 wherein the setting step comprises conditionally incrementing a multi-bit entry within the bitmap.

12. The method of claim 1 wherein the mapping function comprises a hashing operation.

13. A computer-readable medium having computer-executable instructions for ensuring that a received response message corresponds to a previously forwarded request message on a network node including a mapping function, the computer-readable medium having computer-executable instructions facilitating performing the steps of:

receiving an outgoing packet including state information comprising a first set of data bit values;

first mapping, by the mapping function, the first set of data bit values to render a first mapped data value;

setting an entry within a bitmap at a position corresponding to the mapped data value;

receiving an incoming packet including state information comprising a second set of data bit values, the second set of data bit values being of a type corresponding to the first set of data bit values;

second mapping, by the mapping function, the second set of data bit values to render a second mapped data value;

testing an entry within one or more bitmaps, having positions set in accordance with the setting step, corresponding to the second mapped data value to establish a match with a mapping function value rendered from state information for a previous request packet; and

performing at least one function upon the incoming packet based upon whether the match is established during the testing step.

14. The computer-readable medium of claim 13 further comprising computer-executable instructions facilitating performing the step of:

resetting at least a portion of the contents of at least one bitmap, having entries set in accordance with the setting step, upon detecting a clearance threshold event.

15. The computer-readable medium of claim 14 wherein the clearance threshold event comprises expiration of a time period.

16. The computer-readable medium of claim 14 wherein the network node includes at least a first bitmap having entries set during the setting step, and a second bitmap, and wherein the method comprises the further step of:

replacing contents of the second bitmap with contents of the first bitmap upon detecting the clearance threshold event.

17. The computer-readable medium of claim 16 wherein the testing step comprises testing entries in both an entry in the first bitmap and the second bitmap corresponding to the second mapped data value and wherein the match is established, for application during the performing step, if at least one of the corresponding entries in the first bitmap or the second bitmap is set.

18. The computer-readable medium of claim 13 further comprising changing a key incorporated into the mapping function.

19. The computer-readable medium of claim 13 further comprising:

monitoring a level of packets received during a time period; and

modifying, based upon the level of packets received during the time period, at least a size of the bitmap having entries set during the setting step

20. The computer-readable medium of claim 14 wherein the network node comprises a set of at least three bitmaps arranged as shift registers wherein contents of the first bitmap are shifted into corresponding positions within a second bitmap and contents of the second bitmap are shifted into a third bitmap upon detecting the threshold event, and wherein the method further comprises:

applying a classification rule to a received request to determine which of the set of at least three bitmaps to have a bit set in accordance with the first mapping step, thereby facilitating varying a delay period before a set bit is cleared from the set of three bitmaps.

21. The computer-readable medium of claim 13 wherein the incoming packet is a naming request.

22. The computer-readable medium of claim 21 wherein the naming request is a peer-to-peer name resolution protocol request.

23. The computer-readable medium of claim 13 wherein the setting step comprises conditionally incrementing a multi-bit entry within the bitmap.

24. The computer-readable medium of claim 13 wherein the mapping function comprises a hashing operation.

25. A packet handling infrastructure for a network node including a network interface for receiving and forwarding outgoing packets and corresponding incoming packets between network entities, the packet processing infrastructure comprising:

a mapping function;

at least one bitmap; and

a received packet processor including executable instructions for;

receiving an outgoing packet including state information comprising a first set of data bit values;

first mapping, by the mapping function, the first set of data bit values to render a first mapped data value;

setting an entry within the at least one bitmap at a position corresponding to the mapped data value;

receiving an incoming packet including state information comprising a second set of data bit values, the second set of data bit values being of a type corresponding to the first set of data bit values;

second mapping, by the mapping function, the second set of data bit values to render a second mapped data value;

testing an entry within one or more bitmaps, having positions set in accordance with the setting step, corresponding to the second mapped data value to establish a match with a mapping function value rendered from state information for a previous request packet; and

performing at least one function upon the incoming packet based upon whether the match is established during the testing step.

26. The packet handling infrastructure of claim 25 wherein the received packet processor includes executable instructions for:

resetting at least a portion of the contents of at least one bitmap, having entries set in accordance with the setting step, upon detecting a clearance threshold event.

27. The packet handling infrastructure of claim 26 further comprising a period timer, and wherein the clearance threshold event comprises expiration of a time period measured by the period timer.

28. The packet handling infrastructure of claim 26 wherein the network node includes at least a first bitmap having entries set during the setting step, and a second bitmap, and wherein the received packet processor includes executable instructions for performing the further step of:

replacing contents of the second bitmap with contents of the first bitmap upon detecting the clearance threshold event.

29. The packet handling infrastructure of claim 28 wherein the testing step comprises testing entries in both an entry in the first bitmap and the second bitmap corresponding to the second mapped data value and wherein the match is established, for application during the performing step, if at least one of the corresponding entries in the first bitmap or the second bitmap is set.

30. The packet handling infrastructure of claim 25 further comprising a key generator for changing a key incorporated into the mapping function.

31. The packet handling infrastructure of claim 25 further comprising:

a packet counter for monitoring a level of packets received during a time period; and

modifying, based upon the level of packets received during the time period, a size of the at least one bitmap.

32. The packet handling infrastructure of claim 26 wherein the at least one bitmap comprises a set of at least three bitmaps arranged as shift registers wherein contents of the first bitmap are shifted into corresponding positions within a second bitmap and contents of the second bitmap are shifted into a third bitmap upon detecting the threshold event, and wherein the received packet processor further comprises executable instructions for:

applying a classification rule to a received request to determine which of the set of at least three bitmaps to have a bit set in accordance with the first mapping step, thereby facilitating varying a delay period before a set bit is cleared from the set of three bitmaps.

33. The packet handling infrastructure of claim 25 wherein the incoming packet is a naming request.

34. The packet handling infrastructure of claim 33 wherein the naming request is a peer-to-peer name resolution protocol request.

35. The packet handling infrastructure of claim 25 wherein the setting step performed by the received packet processor comprises conditionally incrementing a multi-bit entry within the bitmap.

36. The packet handling infrastructure of claim 25 wherein the mapping function comprises a hashing operation.