Packet parser

• US 7,606,263 B1
• Filed: 04/28/2004
• Issued: 10/20/2009
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Parker, David K.
• Primary Examiner(s): Sing, Simon
• Assistant Examiner(s): King, Simon
• Application Number:
  US10/835,272
• Time in Patent Office: 2,001 Days
• Field of Search: 370/474, 370/254, 370/466, 370/389, 370/238, 370/392, 370/250, 370/469
• US Class Current: 370/474
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A packet parser is described that parses a packet by identifying the locations of respective packet layers. A staged approach to parsing the packet is employed whereby a first stage tests the packet data units within a first window for the presence of a first packet layer, and a second stage, at least partly in parallel with the first stage, tests the packet data units within a second overlapping window for the presence of a second packet layer. In response to an embedded packet comprising a first packet forming the payload portion of a second packet, the parser produces a data structure comprising first data that identifies the location of the first packet, second data that identifies the location of the second packet, third data that identifies one or more layers of the first packet, and fourth data that identifies one or more layers of the second packet.

Claims

1. A method of parsing a packet in a system comprising one or more processors, the packet comprising a plurality of packet data units and a plurality of packet layers, each having locations, the method comprising:

testing one or more of the packet data units within a first window for the presence of a first packet layer;

identifying the location of the first packet layer within the packet if the first packet layer is detected within the first window;

testing one or more of the packet data units within a second window for the presence of a second packet layer, the second packet layer corresponding to a layer in an applicable reference model distinct from that the first packet layer corresponds to, the one or more packet data units in the second window partially but not completely overlapping the one or more packet data units in the first window to account for uncertainty in the location of the second layer relative to the first, and the testing of the one or more packet data units in the second window occurring in parallel with the testing of the one or more packet data units in the first window, such that parallel testing for the presence of the first and second packet layers is performed; and

as part of or following this parallel testing, identifying the location of the second packet layer within the packet if the second packet layer is detected within the second window, including deferring completing such identifying until after completing the identifying of the location of the first packet layer or it has been determined that such first layer is absent from the packet, to allow more accurate identification of the location of the second packet layer relative to the first.

2. The method of claim 1 wherein the packet data units are of a predetermined size.

3. The method of claim 1 wherein the step of identifying the location of the first packet layer within the packet comprises forming first data identifying the location of the first packet layer.

4. The method of claim 3 wherein the first data identifies the beginning of the first packet layer.

5. The method of claim 3 wherein the first data is expressed in absolute terms.

6. The method of claim 3 wherein the first data is expressed in relative terms.

7. The method of claim 6 wherein the packet is the outer packet of an embedded packet, and the first data is expressed relative to the location of the outer packet.

8. The method of claim 7 wherein the first data is expressed relative to the beginning of the outer packet.

9. The method of claim 6 wherein the packet is the inner packet of an embedded packet, and the first data is expressed relative to the location of the inner packet.

10. The method of claim 9 wherein the first data is expressed relative to the beginning of the inner packet.

11. The method of claim 3 wherein the first data is pointer data.

12. The method of claim 1 wherein the step of identifying the location of the second packet layer with the packet comprises forming second data identifying the location of the second packet layer.

13. The method of claim 12 wherein the second data identifies the beginning of the second packet layer.

14. The method of claim 12 wherein the second data is expressed in absolute terms.

15. The method of claim 12 wherein the second data is expressed in relative terms.

16. The method of claim 15 wherein the packet is the outer packet of an embedded packet, and the second data is expressed relative to the location of the outer packet.

17. The method of claim 16 wherein the second data is expressed relative to the beginning of the outer packet.

18. The method of claim 15 wherein the packet is the inner packet of an embedded packet, and the second data is expressed relative to the location of the inner packet.

19. The method of claim 18 wherein the second data is expressed relative to the beginning of the inner packet.

20. The method of claim 12 wherein the second data is pointer data.

21. The method of claim 1 further comprising testing for the presence of additional packet layers within the packet, and identifying the locations of such additional packet layers if such are detected within the packet, the additional packet layers being distinct from both the first packet layer and the second packet layer within an applicable reference model.

22. The method of claim 1 wherein the first and second windows are of the same predetermined size.

23. A processor readable medium storing one or more software instructions embodying the method of claim 1.

24. A system for parsing a packet, the packet comprising a plurality of packet data units and a plurality of packet layers, each having locations, the system comprising:

a buffer for buffering a plurality of the packet data units;

a first stage configured to test one or more of the buffered packet data units within a first window for the presence of a first packet layer, and to identify the location of the first packet layer within the packet if the first packet layer is detected within the first window; and

a second stage configured to test one or more of the buffered packet data units within a second window for the presence of a second packet layer, the second packet layer corresponding to a layer of an applicable reference model distinct from that the first packet layer corresponds to, the one or more buffered packet data units in the second window partially but not completely overlapping the one or more buffered packet data units in the first window to account for uncertainty in the location of the second packet layer relative to the first, and the testing of the one or more buffered packet data units in the second window occurring in parallel with the testing of the one or more buffered packet data units in the first window, such that parallel testing for the presence of the first and second packet layers is performed;

the second stage further configured to identify, as part of or following this parallel testing, the location of the second packet layer within the packet if the second packet layer is detected within the second window, and defer completing such identification until after the identification of the location of the first packet layer has been completed or it has been determined that such first layer is absent from the packet, to allow more accurate identification of the location of the second packet layer relative to the first.

25. The system of claim 24 wherein each of the first and second stages are implemented as software executing on a processor.

26. The system of claim 24 wherein the first stage is configured to identify the location of the first packet layer by forming first data identifying the location of that packet layer.

27. The system of claim 26 wherein the first data identifies the beginning of the first packet layer.

28. The system of claim 24 wherein the second stage is configured to identify the location of the second packet layer by forming second data identifying the location of that packet layer.

29. The system of claim 28 wherein the second data identifies the beginning of the second packet layer.

30. The system of claim 24 further comprising one or more additional stages configured to test for the presence of additional packet layers within the packet, the additional packet layers being distinct from both the first packet layer and the second packet layer within an applicable reference model.

31. The system of claim 24 wherein the packet is an embedded packet comprising a first packet forming the payload portion of a second packet, and the first stage is configured to test for the presence of the first packet layer in the first and second packets.

32. The system of claim 24 wherein the packet is an embedded packet comprising a first packet forming the payload portion of a second packet, and the second stage is configured to test for the presence of the second packet layer in the first and second packets.

33. A system for parsing a packet, the packet comprising a plurality of packet data units and a plurality of layers, each having a location within the packet, the system comprising:

buffer means for buffering a plurality of the packet data units;

first stage means for testing one or more of the buffered packet data units within a first window for the presence of a first packet layer, and identifying the location of the first packet layer within the packet if the first packet layer is detected within the first window; and

second stage means for testing one or more of the buffered packet data units within a second window for the presence of a second packet layer, the second packet layer corresponding to a layer of an applicable reference model distinct from that the first packet layer corresponds to, the one or more buffered packet data units in the second window partially but not completely overlapping the one or more buffered packet data units in the first window, and the testing of the one or more buffered packet data units in the second window occurring in parallel with the testing of the one or more buffered packet data units in the first window to account for uncertainty in the location of the second packet layer relative to the first, such that parallel testing for the presence of the first and second packet layers is performed; and

(2) identifying, as part of or following this parallel testing, the location of the second packet layer within the packet if the second packet layer is detected within the second window, including deferring completing such identifying until after the identifying of the location of the first packet layer has been completed or it has been determined that such first layer is absent from the packet, to allow more accurate identification of the location of the second packet layer relative to the first.