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

• US 7,206,862 B2
• Filed: 04/24/2002
• Issued: 04/17/2007
• Est. Priority Date: 04/24/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wheeler, Graham A.
• Primary Examiner(s): Prieto; Beatriz
• Assistant Examiner(s): Meucci; Michael D.
• Application Number:
  US10/128,919
• Publication Number:
  US 20030204626A1
• Time in Patent Office: 1,819 Days
• Field of Search: 709/245, 709/203, 709/217, 709/218, 709/219
• 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:

at the network node, receiving an outgoing packet for which a response is expected, the 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 first mapped data value, the bitmap residing at the network node;

forwarding the outgoing packet to an end node, the end node comprising a name resolution cache;

at the network node, receiving an incoming packet from the end node, the incoming packet including state information comprising a second set of data bit values, the second set of data bit values corresponding to the first set of data bit values;

wherein the incoming packet is a response to the outgoing packet;

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;

wherein the one or more bitmaps include positions set in accordance with the setting step, the positions corresponding to the second mapped data value;

establishing a match between the first mapped data value and the second mapped data value 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 at least 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 tangible 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 tangible computer-readable medium having computer-executable instructions facilitating performing the steps of:

receiving an outgoing packet for which a response is expected, the 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 first 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 corresponding to the first set of data bit values;

wherein the incoming packet is a response to the outgoing packet;

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;

wherein the one or more bitmaps include positions set in accordance with the setting step, the positions corresponding to the second mapped data value;

establishing a match between the first mapped data value and the second mapped data value 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 tangible 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 tangible computer-readable medium of claim 14 wherein the clearance threshold event comprises expiration of a time period.

16. The tangible 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 tangible 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 tangible computer-readable medium of claim 13 further comprising changing a key incorporated into the mapping function.

19. The tangible 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 tangible 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 at least three bitmaps.

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

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

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

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

25. A system for packet handling within a network node including a network interface for receiving and forwarding outgoing packets and corresponding incoming packets between network entities comprising:

a mapping function;

at least one bitmap residing at the node; and

a received packet processor including executable instructions for;

receiving an outgoing packet for which a response is expected, the 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 first 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;

wherein the incoming packet is a response to the outgoing packet;

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;

wherein the one or more bitmaps include positions set in accordance with the setting step, the positions corresponding to the second mapped data value;

establishing a match with a mapping function value rendered from state information for a previous request packet, the match between the first mapped data value and the second mapped data value; 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 system 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 system 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 system 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 system 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 system of claim 25 further comprising a key generator for changing a key incorporated into the mapping function.

31. The packet handling system 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 lest one bitmap.

32. The packet handling system 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 at least three bitmaps.

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

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

35. The packet handling system 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 system of claim 25 wherein the mapping function comprises a hashing operation.