US5394394A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Message header classifier
Assignee: Cisco Technology Inc
•
Filing: 1993-06-24
•
Granted: 1995-02-28
•
Expires: 2013-06-24
Abstract
Abstract The classifier device disclosed herein analyzes message headers of the type which comprise a sequence of bit groups presented successively. The device employs a read/write memory for storing at a multiplicity of addresses, an alterable parse graph of instructions. The parse graph instructions include node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for previously characterized header types. A logical processor responds to a node instruction read from memory either by initiating another memory read at a next address which, given the current state of the processor, is determinable from the current node instruction and the current header bit group or by outputting data indicating recognition failure if no next address is determinable. The logical processor responds to a terminator instruction by outputting respective header identifying data. Accordingly, for a previously characterized header type, a corresponding pattern of node instruction and a terminator instruction can be written into memory thereby enabling the device to identify the respective header type in a time which is essentially proportional to the length of the header and thus also to the time of presentation of the header. The parse graph can be updated dynamically during the operation of the classifier.
Inventors
- 👤 William R. Crowther
- 👤 Stanley A. Lackey, Jr.
- 👤 C. Philip Levin
- 👤 Daniel C. Tappan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 10:56
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/40; H04L69/00; H04L69/22
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
188 words
In a device for directing selected messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for different header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address determinable from the current node instruction .just read from memory and a header bit group obtained by said reading means, said logic means being responsive to a terminator instruction read from said memory for outputting respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 2
Dependent Claim
188 words
In a device for directing selected messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for different header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address determinable from the current node instruction .just read from memory and a header bit group obtained by said reading means, said logic means being responsive to a terminator instruction read from said memory for outputting respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 3
Dependent Claim
23 words
Apparatus as set forth in claim 1 wherein neither said node instruction nor said terminator instructions cause writing of data into said memory.
Claim 4
Dependent Claim
18 words
Apparatus as set forth in claim 1 wherein said logic means does not write data to said memory.
Claim 5
Dependent Claim
199 words
In a device for directing selected messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for different header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the current node instruction just read from memory and a header bit group obtained by said reading means, said logic means being responsive to a terminator instruction read from said memory for outputting respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 6
Dependent Claim
199 words
In a device for directing selected messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for different header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the current node instruction just read from memory and a header bit group obtained by said reading means, said logic means being responsive to a terminator instruction read from said memory for outputting respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 7
Dependent Claim
50 words
Apparatus as set forth in claim 4 wherein said node instructions include a jump to subroutine instruction which causes a memory read at a next address determinable from the instruction and wherein said logic means includes a register for retaining data identifying the address of the jump to subroutine instruction.
Claim 8
Dependent Claim
42 words
Apparatus as set forth in claim 5 wherein said node instructions include a return from subroutine instruction which causes a memory read at a next address which is offset from the address of the jump to subroutine instruction by a preselectable offset.
Claim 9
Dependent Claim
221 words
In a packet switched device for directing selected digital messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying previously characterized headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for previously characterized header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the current node instruction just read from memory and a header bit group obtained by said reading means or for outputting data indicating recognition failure if no next address is determinable, said logic means being responsive to a terminator instruction read from said memory for outputting the respective header identifying data whereby, for each previously characterized header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 10
Dependent Claim
221 words
In a packet switched device for directing selected digital messages to a selected one of a plurality of output paths in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying previously characterized headers; said apparatus comprising: a memory; stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for previously characterized header types; means for reading a selected one of said bit groups from the header of a message being received; and logic means responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the current node instruction just read from memory and a header bit group obtained by said reading means or for outputting data indicating recognition failure if no next address is determinable, said logic means being responsive to a terminator instruction read from said memory for outputting the respective header identifying data whereby, for each previously characterized header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to identify the respective header.
Claim 11
Dependent Claim
50 words
Apparatus as set forth in claim 4 wherein said node instructions include a jump to subroutine instruction which causes a memory read at a next address determinable from the instruction and wherein said logic means includes a register for retaining data identifying the address of the jump to subroutine instruction.
Claim 12
Dependent Claim
19 words
Apparatus as set forth in claim 8 wherein said jump to subroutine instruction inhibits output of recognition failure data.
Claim 13
Dependent Claim
42 words
Apparatus as set forth in claim 8 wherein said node instructions include a return from subroutine instruction which causes a memory read at a next address which is offset from the address of the jump to subroutine instruction by a preselectable offset.
Claim 14
Dependent Claim
45 words
Apparatus as set forth in claim 7 wherein said node instructions include a compare for equality instruction which first masks a header bit group with a preselected mask value and generates a next instruction address if a match is obtained with a preselected compare value.
Claim 15
Dependent Claim
42 words
Apparatus as set forth in claim 7 wherein said node instructions include a multiple compare instruction in which a succession of header bit groups are compared with respective mask values and a next instruction address is generated if all matches are obtained.
Claim 16
Dependent Claim
33 words
Apparatus as set forth in claim 7 wherein said node instructions include a range instruction which generates a next instruction address if a header bit group falls within a given range of values.
Claim 17
Dependent Claim
34 words
Apparatus as set forth in claim 7 wherein said node instructions includes a case instruction which generates a next instruction address which is a function of the value of the current header bit group.
Claim 18
Dependent Claim
24 words
Apparatus as set forth in claim 14 wherein said case instruction includes a value which is logically ORed with the current header bit group.
Claim 19
Dependent Claim
207 words
In a device for selecting digital messages for further processing in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying previously characterized headers; said apparatus comprising: a register for storing a plurality of said bit groups; a memory;. stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for previously characterized header types; logic means which reads bit groups from said register and which reads node and terminator instructions from said memory and is responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the node instruction just read from memory and the header bit group just read from said register, said logic means being responsive to a terminator instruction read from said memory for outputting the respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to output the respective header identifying data.
Claim 20
Dependent Claim
207 words
In a device for selecting digital messages for further processing in accordance with the contents of a message header which comprises a sequence of bit groups presented successively, apparatus for quickly classifying previously characterized headers; said apparatus comprising: a register for storing a plurality of said bit groups; a memory;. stored in said memory, at a multiplicity of addresses, node instructions which comprise opcodes in association with respective next address characterizing data and terminator instructions which comprise identifying data for previously characterized header types; logic means which reads bit groups from said register and which reads node and terminator instructions from said memory and is responsive to a node instruction read from memory for initiating a memory read at a next address which, given the current state of the logic means, is determinable from only the node instruction just read from memory and the header bit group just read from said register, said logic means being responsive to a terminator instruction read from said memory for outputting the respective header identifying data whereby, for each header type to be classified, a corresponding pattern of node instructions and a terminator instruction can be written into said memory, thereby enabling said apparatus to output the respective header identifying data.
Claim 21
Dependent Claim
35 words
Apparatus as set forth in claim 16 wherein said node instructions include a skip instruction which cause said logic means to pass by a selected number of said bit groups in reading from said register.
Claim 22
Dependent Claim
24 words
Apparatus as set forth in claim 16 wherein said node instructions include jump instructions which generate next address values independently of bit group values.
Claim 23
Dependent Claim
23 words
Apparatus as set forth in claim 16 wherein neither said node instruction nor said terminator instructions cause writing of data into said memory.
Claim 24
Dependent Claim
18 words
Apparatus as set forth in claim 16 wherein said logic means does not write data to said memory.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-02-27 | 1998-08-29 | 1999-02-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-02-27 | 2002-08-29 | 2003-02-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-02-27 | 2006-08-29 | 2007-02-28 | $7700.00 | Window Closed / Lapsed |