US6147976A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast network layer packet filter
Assignee: Extreme Networks Inc
•
Filing: 1996-06-24
•
Granted: 2000-11-14
•
Expires: 2016-06-24
Abstract
Abstract A new packet filtering system associates domain identifiers with respective sets of addresses. A set of domain prefixes defines the set of addresses associated with a given domain identifier. Domain prefixes are found matching the source address and destination address of each received packet. These prefixes are associated with a source domain identifier and destination domain identifier respectively. The system similarly associates sets of one or more protocol types and port ranges with respective protocol domain identifiers. The protocol type, source port and destination port of the received packet determine source and destination protocol domain identifiers for the received packet. The system includes a filtering matrix including one or more entries, each indicating whether an associated received packed should be filtered. The source domain identifier, destination domain identifier, and source and destination protocol domain identifiers are used to index into the filtering matrix, for example using each as an index into one of the dimensions of a four dimensional array used to implement the filtering matrix. In an alternative embodiment, the source and destination protocol identifiers are used to obtain a protocol index from a protocol vector data structure. The protocol index, source domain identifier and destination identifier are then used to index into a three dimensional filtering matrix. The system further optimizes the filtering matrix for size, and the lookup time is dependent only on the number of filtering domains, and not the complexity or number of filtering rules.
Inventors
- 👤 Ian Michael Charles Shand
- 👤 John Anthony Harper
- 👤 Steven Richard Welch
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 18:23
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/02; H04L63/0227; H04L63/0236; H04L45/00; H04L45/74; H04L45/742; H04L49/00; H04L49/35; H04L49/351; H04L61/00; H04L61/35; H04L63/0263
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
141 words
A system for filtering a received packet, comprising: means for associating one or more network station addresses with one or more respective domain identifiers; first means for retrieving a source domain identifier from said associating means as a function of a source network station address of the received packet; second means for retrieving a destination domain identifier from said associating means as a function of a destination network station address of the received packet; a filtering matrix including one or more entries, each one of said entries including a forwarding flag; means for retrieving one of the entries in the filtering matrix as a function of the source domain identifier and the destination domain identifier; and means for forwarding said received packet if said forwarding flag in said retrieved one of said filtering matrix entries is equal to a first value.
Claim 2
Independent Claim
141 words
A system for filtering a received packet, comprising: means for associating one or more network station addresses with one or more respective domain identifiers; first means for retrieving a source domain identifier from said associating means as a function of a source network station address of the received packet; second means for retrieving a destination domain identifier from said associating means as a function of a destination network station address of the received packet; a filtering matrix including one or more entries, each one of said entries including a forwarding flag; means for retrieving one of the entries in the filtering matrix as a function of the source domain identifier and the destination domain identifier; and means for forwarding said received packet if said forwarding flag in said retrieved one of said filtering matrix entries is equal to a first value.
Claim 3
Dependent Claim
33 words
The system as in claim 1, further comprising: means for dropping said received packet if said forwarding flag in said one of said retrieved filtering matrix entries is equal to a second value.
Claim 4
Dependent Claim
46 words
The system as in claim 1, wherein said means for associating one or more network station addresses with a domain identifier includes an address table, said address table having one or more entries, each said address table entry including a domain prefix and a domain identifier.
Claim 5
Dependent Claim
46 words
The system as in claim 3, wherein said first and second means for retrieving a domain identifier performs a search on said address table for an address table entry having a domain prefix matching said source and destination network station addresses in said received packet respectively.
Claim 6
Dependent Claim
37 words
The system as in claim 4, further comprising: means for determining a port on which to forward said received packet responsive to said address table entry having a domain prefix matching said address in said received packet.
Claim 7
Independent Claim
217 words
A system for filtering a received packet, comprising: means for associating a first set of one or more network layer addresses with a first domain identifier; means for associating a second set of one or more network layer network addresses with a second domain identifier; means for associating a network protocol combined with a range of source port numbers and a range of destination port numbers with a protocol index; a filtering matrix including one or more entries, each one of said entries including a forwarding flag; means for determining that a network layer source address in said received packet is in said first set of one or more network layer addresses; means for determining that a network layer destination address in said received packet is in said second set of one or more network layer addresses; protocol domain determining means for determining that a protocol type of said received packet is equal to said network protocol, and that a source port number of said received packet is within said range of source port numbers, and that a destination port number of said received packet is within said range of destination port numbers; and means for generating an index into said filtering matrix responsive to said first domain identifier, said second domain identifier, and said protocol index.
Claim 8
Independent Claim
217 words
A system for filtering a received packet, comprising: means for associating a first set of one or more network layer addresses with a first domain identifier; means for associating a second set of one or more network layer network addresses with a second domain identifier; means for associating a network protocol combined with a range of source port numbers and a range of destination port numbers with a protocol index; a filtering matrix including one or more entries, each one of said entries including a forwarding flag; means for determining that a network layer source address in said received packet is in said first set of one or more network layer addresses; means for determining that a network layer destination address in said received packet is in said second set of one or more network layer addresses; protocol domain determining means for determining that a protocol type of said received packet is equal to said network protocol, and that a source port number of said received packet is within said range of source port numbers, and that a destination port number of said received packet is within said range of destination port numbers; and means for generating an index into said filtering matrix responsive to said first domain identifier, said second domain identifier, and said protocol index.
Claim 9
Dependent Claim
36 words
The system as in claim 6, wherein said means for generating combines the values of said first domain identifier, said second domain identifier, and said protocol domain identifier to generate said index into said filtering matrix.
Claim 10
Dependent Claim
61 words
The system as in claim 7, wherein said means for associating a first set of one or more network layer addresses with a first domain identifier includes a source address table, said source address table having one or more entries, each one of said source address table entries having a domain prefix and a domain identifier associated with that domain prefix.
Claim 11
Dependent Claim
58 words
The system as in claim 7 wherein said means for associating a second set of one or more network layer network addresses with a second domain identifier includes a destination address table having one or more entries, each one of said destination address table entries having a domain prefix and a domain identifier associated with that domain prefix.
Claim 12
Dependent Claim
74 words
The system as in claim 7 wherein said protocol determining means includes a protocol table having one or more entries, each said protocol table entry having a protocol type and port number range, a further having a protocol domain identifier associated with that protocol type and port number range, said protocol determining means further having a protocol vector, said protocol vector having a protocol index associated with each pair of said protocol domain identifiers.
Claim 13
Dependent Claim
49 words
The system as in claim 10 wherein said means for determining that a network layer source address in said received packet is in said first set of one or more network layer addresses searches said source address table for a longest domain prefix matching said network layer source address.
Claim 14
Dependent Claim
49 words
The system as in claim 10 where said means for determining that a network layer destination address in said received packet is in said second set of one or more network layer addresses searches said destination address table for a longest domain prefix matching said network layer destination address.
Claim 15
Dependent Claim
24 words
The system as in claim 7 further comprising a means for using said index into said filtering matrix to obtain a filtering matrix entry.
Claim 16
Dependent Claim
35 words
The system as in claim 13, further comprising means, responsive to said filtering matrix entry, for forwarding said received packet if said forwarding flag in said filtering matrix entry is equal to a first value.
Claim 17
Dependent Claim
35 words
The system as in claim 14, further comprising means, responsive to said filtering matrix entry, for dropping said received packet if said forwarding flag in said filtering matrix entry is equal to a second value.
Claim 18
Independent Claim
138 words
A system for forming a packet filtering data structure, responsive to a command script, comprising: means for forming an address table having one or more entries, each address table entry including a domain prefix and a domain identifier; means for forming a two dimensional filtering matrix having one or more entries, each row in said filtering matrix indexed by one of said domain identifiers, and each said filtering matrix entry having a filtering flag; means for identifying a first row in said filtering matrix, identical with a second row in said filtering matrix, said first row indexed by a first domain identifier, said second row indexed by a second domain identifier; and means for deleting said second row from said filtering matrix, and for replacing said second domain identifier in said address table with said first domain identifier.
Claim 19
Independent Claim
138 words
A system for forming a packet filtering data structure, responsive to a command script, comprising: means for forming an address table having one or more entries, each address table entry including a domain prefix and a domain identifier; means for forming a two dimensional filtering matrix having one or more entries, each row in said filtering matrix indexed by one of said domain identifiers, and each said filtering matrix entry having a filtering flag; means for identifying a first row in said filtering matrix, identical with a second row in said filtering matrix, said first row indexed by a first domain identifier, said second row indexed by a second domain identifier; and means for deleting said second row from said filtering matrix, and for replacing said second domain identifier in said address table with said first domain identifier.
Claim 20
Independent Claim
220 words
A system for forming a packet filtering data structure, responsive to a command script, comprising: means for forming an address table having one or more entries, each address table entry including a domain prefix and a domain identifier; means for forming a protocol table having one or more entries, each protocol table entry including a protocol type, port range, and associated protocol domain identifier; means for forming a two dimensional protocol vector having one or more entries, each entry in said protocol vector indexed by a pair of said protocol domain identifiers, each protocol vector entry including a protocol index; means for forming a three dimensional filtering matrix having one or more entries, a first and second dimension in said filtering matrix indexed by a first and a second one of said domain identifiers, a third dimension in said filtering matrix indexed by a protocol index, and each said filtering matrix entry having a filtering flag; means for identifying a first plane in said filtering matrix, identical with a second plane in said filtering matrix, said first plane indexed by a first protocol index, said second plane indexed by a second protocol index; and means for deleting said second plane from said filtering matrix, and for replacing said second protocol index in said protocol vector with said first protocol index.
Claim 21
Independent Claim
220 words
A system for forming a packet filtering data structure, responsive to a command script, comprising: means for forming an address table having one or more entries, each address table entry including a domain prefix and a domain identifier; means for forming a protocol table having one or more entries, each protocol table entry including a protocol type, port range, and associated protocol domain identifier; means for forming a two dimensional protocol vector having one or more entries, each entry in said protocol vector indexed by a pair of said protocol domain identifiers, each protocol vector entry including a protocol index; means for forming a three dimensional filtering matrix having one or more entries, a first and second dimension in said filtering matrix indexed by a first and a second one of said domain identifiers, a third dimension in said filtering matrix indexed by a protocol index, and each said filtering matrix entry having a filtering flag; means for identifying a first plane in said filtering matrix, identical with a second plane in said filtering matrix, said first plane indexed by a first protocol index, said second plane indexed by a second protocol index; and means for deleting said second plane from said filtering matrix, and for replacing said second protocol index in said protocol vector with said first protocol index.
Claim 22
Independent Claim
90 words
A method of filtering a packet received at a device comprising the steps of: extracting a source address and a destination address from said packet; identifying a source domain identifier and a destination domain identifier associated with said source address and destination address, respectively; retrieving one entry, of a plurality of entries in a filtering matrix as a function of said source and destination domain identifiers, each entry comprising a forwarding flag; and forwarding said packet if said forwarding flag in said retrieved entry is equal to a first value.
Claim 23
Independent Claim
90 words
A method of filtering a packet received at a device comprising the steps of: extracting a source address and a destination address from said packet; identifying a source domain identifier and a destination domain identifier associated with said source address and destination address, respectively; retrieving one entry, of a plurality of entries in a filtering matrix as a function of said source and destination domain identifiers, each entry comprising a forwarding flag; and forwarding said packet if said forwarding flag in said retrieved entry is equal to a first value.
Claim 24
Dependent Claim
18 words
The method according to claim 18, wherein said domain identifier indicates a network protocol associated with said address.
References Cited (Backward Citations)
US5455865A
Cited
US5136580A
Cited
US5657314A
Cited
US5327426A
Cited
US5519858A
Cited
US5475823A
Cited
US5313465A
Cited
US5644571A
Cited
US5425026A
Cited
US5590285A
Cited
US5617421A
Cited
US5623601A
Cited
US5619498A
Cited
US5802043A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-14 | 2004-05-15 | 2004-11-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-14 | 2008-05-15 | 2008-11-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-14 | 2012-05-15 | 2012-11-14 | $7700.00 | Window Closed / Lapsed |