Method and apparatus for protocol pattern identification in protocol data units
Method and apparatus for protocol pattern identification in protocol data units (PDUs). Techniques disclosed utilize the concept of stages. Within each stage, a protocol identification apparatus attempts to find a pattern match between the bits of the protocol data unit and the predefined bits of search patterns for a particular layer of protocol encapsulation. Once found the apparatus resets itself and begins the search anew for the next layer of encapsulation. The user is provided the ability to look for a particular pattern in a higher layer protocol without having knowledge of which lower layer protocols were used. Both hardware and software implementations of this apparatus provide for very fast identification of the protocol data units. Information regarding which encapsulations are present in a particular protocol data unit are provided saving software routines time when they process each packet. Also, by informing the apparatus regarding the encapsulation patterns desired, the protocol identification apparatus can filter the protocol data unit at runtime which saves additional software routines from spending time later processing packets that are not needed, and in addition, can save valuable capture buffer space by discarding those protocol data units not of interest.
1. A method for identifying computer network protocols used to encapsulate data in a protocol data unit, which comprises the steps of:
receiving the protocol data unit, wherein the protocol data unit comprises data and multiple encapsulation protocol patterns; and
while there remains at least one stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining stages, and
while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining search patterns, and
searching the protocol data unit for the selected search pattern.
2. The method as recited in claim 1 , which further comprises the steps of:
prior to the while there remains at least one stage iterative loop:
assigning a group indicator for at least one pre-defined group of search patterns, wherein the group comprises at least one sub-set which comprises at least one preselected search pattern, wherein the preselected search pattern identifies at least one preselected network protocol used to encapsulate data; and
initializing the group indicator to specify that at least one sub-set is present in the expected locations in the protocol data unit; and
after the while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched iterative loop:
when all search patterns associated with each sub-set of the group for the selected stage are absent from the expected locations in the protocol data unit, setting the group indicator to specify that all sub-sets of that group are absent from the protocol data unit.
3. The method as recited in claim 2 , which following the method step searching the protocol data unit for the selected search pattern further comprises the step of:
after the while there remains at least one stage iterative loop:
when at least one of the sub-sets is present in the expected locations in the protocol data unit, placing the protocol data unit in a buffer.
4. The method as recited in claim 1 , wherein the method step searching the protocol data unit for the selected search pattern comprises the steps of:
while there remains at least one part of the search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern, and
searching the protocol data unit for the selected part of the selected search pattern.
5. The method as recited in claim 4 , which further comprises the steps of:
when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part in the protocol data unit,
exiting the while there remains at least one part of the search pattern of the selected stage for which the protocol data unit is to be searched iterative loop and
exiting the while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched iterative loop.
6. The method as recited in claim 1 , which following the method step selecting one of the remaining search patterns further comprises the steps of:
when there remains at least one additional search pattern of the selected stage for which the protocol data unit is to be searched,
selecting at least one of the additional remaining search patterns, and
in parallel with the method step of searching the protocol data unit for the selected search pattern, searching the protocol data unit for the additional selected search pattern.
7. The method as recited in claim 6 , wherein the parallel method steps of searching the protocol data unit for the selected search pattern and of searching the protocol data unit for the additional selected search pattern comprise the steps of:
while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched and at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern,
selecting one of the remaining un-searched parts of the additional selected search pattern,
searching the protocol data unit for the selected part of the selected search pattern, and
in parallel with the method step of searching the protocol data unit for the selected part of the selected search pattern, searching the protocol data unit for the selected part of the additional selected search pattern;
otherwise, while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern, and
searching the protocol data unit for the selected part of the selected search pattern; and
otherwise, while there remains at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the additional selected search pattern, and
searching the protocol data unit for the selected part of the additional selected search pattern.
8. The method as recited in claim 7 , which further comprises the steps of:
when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part of the selected search pattern in the protocol data unit and when the parallel method step of searching the protocol data unit for the selected part of the additional selected search pattern fails to find the selected part of the additional selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched and at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop;
otherwise when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part of the selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop; and
otherwise when the method step searching the protocol data unit for the selected part of the additional selected search pattern fails to find the selected part of the additional selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop.
9. A storage medium readable by a protocol identification apparatus, tangibly embodying a computer program of instructions executable by the protocol identification apparatus to perform method steps for identifying computer network protocols used to encapsulate data in a protocol data unit, the steps comprising:
receiving the protocol data unit, wherein the protocol data unit comprises data and multiple encapsulation protocol patterns; and
while there remains at least one stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining stages, and
while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining search patterns, and
searching the protocol data unit for the selected search pattern.
10. The storage medium as recited in claim 9 , the steps further comprising:
prior to the while there remains at least one stage iterative loop:
assigning a group indicator for at least one pre-defined group of search patterns, wherein the group comprises at least one sub-set which comprises at least one preselected search pattern, wherein the preselected search pattern identifies at least one preselected network protocol used to encapsulate data; and
initializing the group indicator to specify that at least one sub-set is present in the expected locations in the protocol data unit; and
after the while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched iterative loop:
when all search patterns associated with each sub-set of the group for the selected stage are absent from the expected locations in the protocol data unit, setting the group indicator to specify that all sub-sets of that group are absent from the protocol data unit.
11. The storage medium as recited in claim 10 , wherein following the step searching the protocol data unit for the selected search pattern, the steps further comprising:
after the while there remains at least one stage iterative loop:
when at least one of the sub-sets is present in the expected locations in the protocol data unit, placing the protocol data unit in a buffer.
12. The storage medium as recited in claim 9 , wherein the step searching the protocol data unit for the selected search pattern comprising the steps of:
while there remains at least one part of the search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern, and
searching the protocol data unit for the selected part of the selected search pattern.
13. The storage medium as recited in claim 12 , the steps further comprising:
when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part in the protocol data unit,
exiting the while there remains at least one part of the search pattern of the selected stage for which the protocol data unit is to be searched iterative loop and
exiting the while there remains at least one search pattern of the selected stage for which the protocol data unit is to be searched iterative loop.
14. The storage medium as recited in claim 9 , wherein following the method step selecting one of the remaining search patterns, the steps further comprising:
when there remains at least one additional search pattern of the selected stage for which the protocol data unit is to be searched,
selecting at least one of the additional remaining search patterns, and
in parallel with the method step of searching the protocol data unit for the selected search pattern, searching the protocol data unit for the additional selected search pattern.
15. The storage medium as recited in claim 14 , wherein the parallel method steps of searching the protocol data unit for the selected search pattern and of searching the protocol data unit for the additional selected search pattern comprise the steps of:
while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched and at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern,
selecting one of the remaining un-searched parts of the additional selected search pattern,
searching the protocol data unit for the selected part of the selected search pattern, and
in parallel with the method step of searching the protocol data unit for the selected part of the selected search pattern, searching the protocol data unit for the selected part of the additional selected search pattern;
otherwise, while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the selected search pattern, and
searching the protocol data unit for the selected part of the selected search pattern; and
otherwise, while there remains at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched, iteratively performing:
selecting one of the remaining un-searched parts of the additional selected search pattern, and
searching the protocol data unit for the selected part of the additional selected search pattern.
16. The storage medium as recited in claim 15 , the steps further comprising:
when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part of the selected search pattern in the protocol data unit and when the parallel method step of searching the protocol data unit for the selected part of the additional selected search pattern fails to find the selected part of the additional selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched and at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop;
otherwise when the method step searching the protocol data unit for the selected part of the selected search pattern fails to find the selected part of the selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop; and
otherwise when the method step searching the protocol data unit for the selected part of the additional selected search pattern fails to find the selected part of the additional selected search pattern in the protocol data unit,
exiting the while there remains at least one part of the additional selected search pattern of the selected stage for which the protocol data unit is to be searched iterative loop.
17. An apparatus for identifying those computer network protocols used to encapsulate data in a protocol data unit, comprising:
a control circuit, wherein the control circuit is capable of receiving the protocol data unit and is capable of obtaining at least one search pattern for each of multiple stages, wherein each search pattern identifies one of the network protocols used to encapsulate data; and
a pattern comparator, wherein the pattern comparator is connected to the control circuit, wherein the pattern comparator is capable of receiving the protocol data unit from the control circuit, wherein the control circuit is capable of successively selecting individual stages, and wherein for the selected stage the pattern comparator is capable of receiving at least one search pattern for the selected stage from the control circuit and of separately searching the protocol data unit for the received search pattern.
18. The apparatus as recited in claim 17 , wherein the pattern comparator is capable of separately searching the protocol data unit for part of the received search pattern.
19. The apparatus as recited in claim 17 , wherein the pattern comparator is capable of separately searching the protocol data unit for multiple received search patterns in parallel.
20. The apparatus as recited in claim 17 , further comprising a first accumulator, wherein the first accumulator is connected to the pattern comparator and is capable of accumulating results from searches of the selected stage.
21. The apparatus as recited in claim 20 , further comprising:
a mapping circuit, wherein the mapping circuit is connected to the first accumulator and wherein the mapping circuit maps the contents of the first accumulator against a preselected group of search patterns.
22. The apparatus as recited in claim 21 , further comprising a second accumulator, wherein the second accumulator is connected to the mapping circuit and is capable of accumulating results from maps of the first accumulator for each stage against the preselected group of search patterns.