US5473607A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet filtering for data networks
Assignee: Cisco Technology Inc
•
Filing: 1993-08-09
•
Granted: 1995-12-05
•
Expires: 2013-08-09
Abstract
Abstract An improved partial packet filter (10) for filtering data packets (210) in a computer network (12) wherein a candidate field (413) of the data packet (210) is hashed to a plurality of bit-wise subsets (636) each being an independent representation of the candidate field (413). Each of the bit-wise subsets (636) is compared to a reference hash table (644) which has been prepared in a preliminary operation series (514). The preliminary operation series (512) configures a plurality of target fields (714) to set selected memory locations (312) in the reference hash table (644).
Inventors
- 👤 Richard J. Hausman
- 👤 Lazar Birenbaum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:05
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/74; H04L45/745; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/462; H04L12/4625; H04L9/00; H04L9/40
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
174 words
A method for selectively forwarding a data packet and controlling the distribution of data packets in a computer network system, the data packet having a candidate field containing information about the data packet, the method comprising: configuring a target memory of a controller to contain a target hash array in steps including; aa determining a target field and extracting a plurality of target indices from said target field, the target indices being a binary number having a value; ab setting memory locations in the target memory corresponding to the value of each of the target indices; and processing the data packet in steps including: ba extracting the candidate field from the data packet; bb extracting from the candidate field a plurality of candidate field indices; bc comparing the values of each of the candidate field indices to the target hash array; and bd forwarding the packet when each of the values of each of the candidate field indices corresponds to a memory location of the target hash array which was set in step ab.
Claim 2
Independent Claim
174 words
A method for selectively forwarding a data packet and controlling the distribution of data packets in a computer network system, the data packet having a candidate field containing information about the data packet, the method comprising: configuring a target memory of a controller to contain a target hash array in steps including; aa determining a target field and extracting a plurality of target indices from said target field, the target indices being a binary number having a value; ab setting memory locations in the target memory corresponding to the value of each of the target indices; and processing the data packet in steps including: ba extracting the candidate field from the data packet; bb extracting from the candidate field a plurality of candidate field indices; bc comparing the values of each of the candidate field indices to the target hash array; and bd forwarding the packet when each of the values of each of the candidate field indices corresponds to a memory location of the target hash array which was set in step ab.
Claim 3
Dependent Claim
73 words
The method of claim 1, wherein: step aa is accomplished in substeps including: aa1 reducing the target fields to a plurality of target representative fields; and aa2 selecting one or more target string subsets from the target representative field; and step bb is accomplished in substeps including: bb1 reducing the candidate field to a plurality of candidate representative fields; and bb2 selecting one or more candidate string subsets from the target representative field.
Claim 4
Dependent Claim
38 words
The method of claim 1, wherein: step ab is accomplished by causing only those memory locations in the target memory which correspond to the value of each of the target string subsets to contain a value of one.
Claim 5
Dependent Claim
40 words
The method of claim 2, wherein: step aa1 is accomplished by applying a cyclic redundancy check algorithm to each of the target fields; and step bb1 is accomplished by applying the same cyclic redundancy check algorithm to the candidate field.
Claim 6
Dependent Claim
51 words
The method of claim 2, wherein: in step aa2 the target string subsets are selected by extracting a plurality of target bit-wise subsets from the target representative field; and in step bb2 the candidate string subsets are selected by extracting a plurality of candidate bit-wise subsets from the representative candidate field.
Claim 7
Dependent Claim
59 words
The method of claim 2, and further including: an additional process step preceding step ab wherein a subset quantity is determined, the subset quantity being the number of target string subsets to be extracted from each of the target representative fields and also the number of candidate string subsets to be extracted from each of the candidate representative fields.
Claim 8
Dependent Claim
26 words
The method of claim 6, wherein: the additional process step is accomplished, at least initially, by selecting the subset quantity from a table of subset quantities.
Claim 9
Dependent Claim
22 words
The method of claim 2, wherein: each of the target representative target and the candidate representative field are 32 bits in length.
Claim 10
Dependent Claim
23 words
The method of claim 1, wherein: steps aa through ab are repeated when a change in the distribution of data packets is desired.
Claim 11
Dependent Claim
17 words
The method of claim 1, wherein: steps ba through bd are repeated for each incoming data packet.
Claim 12
Dependent Claim
55 words
The method of claim 1, and further including: an additional process step preceding step ab wherein a subset quantity is determined, the subset quantity being the number of target indices to be extracted from each of the target fields and also the number of candidate indices to be extracted from each of the candidate fields.
Claim 13
Dependent Claim
33 words
The method of claim 11, wherein: the additional process step is accomplished, at least initially, by selecting the subset quantity from a table of subset quantities appropriate to a quantity of target quantities.
Claim 14
Dependent Claim
18 words
The method of claim 1, wherein: the candidate field includes a target address field of the data packet.
Claim 15
Dependent Claim
15 words
The method of claim 1, wherein: the data packet is a standardized Ethernet data packet.
Claim 16
Dependent Claim
31 words
The method of claim 1, wherein: the target hash array is an unapportioned array such that each of the target indices is used to set memory locations in that unapportioned array.
Claim 17
Dependent Claim
31 words
The method of claim 1, wherein: the target hash array is apportioned such that at least some of the target indices are directed to different portions of the target hash array.
Claim 18
Dependent Claim
22 words
The method of claim 1, wherein: the target indices and the candidate indices are each a binary string of fixed bit length.
References Cited (Backward Citations)
US4399531A
Cited
US4627052A
Cited
US4679193A
Cited
US4933937A
Cited
US5032987A
Cited
US4891803A
Cited
US5247620A
Cited
US5210748A
Cited
US5218638A
Cited
US5274631A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-04 | 1999-06-05 | 1999-12-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-04 | 2003-06-05 | 2003-12-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-04 | 2007-06-05 | 2007-12-05 | $7700.00 | Window Closed / Lapsed |