Method for storing and updating information describing data traffic on a network

• US 6,098,157 A
• Filed: 04/24/1998
• Issued: 08/01/2000
• Est. Priority Date: 04/24/1998
• Status: Expired due to Term

• Current Assignee: Viavi Solutions, Inc. (Lumentum Holdings Inc.)
• Original Assignee: Shomiti Systems, Inc. (II-VI Incorporated)
• Inventors: Leong, Reynold C., Cuppett, Jeffrey W., Hsu, Matthew A.
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/066,803
• Time in Patent Office: 830 Days
• Field of Search: 711/168, 711/156, 711/157, 707/6
• US Class Current: 711/157
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for storing and updating records in a first table containing information corresponding to specific nodes of a network, and in a second table containing information corresponding to a combination of two specific nodes on a network, by indexing the first table with hashed forms of the node addresses, and the second table with hashed forms of a concatenation of the two node addresses, interleaving reads between the two tables to account for memory latency, and using the results of previous reads to reduce the number of future reads necessary for locating and updating the tables'"'"' records.

Claims

1. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in table stored in the memory, each record including a unique identifier having a number of portions, the method comprising:

interleaving reads of portions of the identifiers of records of the table with reads of portions of the identifiers of the other records of the table;

comparing the read portions of the identifiers with a corresponding portion of the known data value, the comparison of the portion of the identifier of at least one read record with the corresponding portion of the known data value occurring concurrently with the reading of a portion of the identifier of at least one other record;

for only those records having a previous portion of the identifier matching a corresponding previous portion of the known data value;

interleaving reads of a next portion of the identifiers of records of the table with reads of a next portion of the identifiers of the other records of the table; and

comparing the read next portion of the identifiers with a corresponding next portion of the known data value;

for each record in the table for which all portions of its identifier matches all portions of the known data value, updating the record.

2. The method of claim 1, further comprising creating a new record in the table if at least one portion of the identifiers of the records does not match a corresponding portion of the known data value.

3. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in a first and second table stored in the memory, each table including a plurality of records, each record including a status field indicating whether the record is empty or full, and a unique identifier having a number of portions, each portion equal to the byte width of the data bus, and the known data value having a corresponding number of portions, the method comprising:

interleaving reads of the status fields of a selected number of records in the first table with reads of the status fields of a selected number of records from the second table, the number of records read determined according to the read latency of the memory;

for at least one read record, determining concurrently with the reading of the status field of another record, whether the status field of the read record indicates the record being full or empty;

for only those records read having a status field indicating a full record;

interleaving reads of first portions of the identifiers of records of the first table with reads of the first portions of the identifiers of the records of the second table; and

comparing the read first portions of the identifiers with a corresponding first portion of the known data value, the comparison of the first portion of the identifier of at least one read record with the corresponding first portion of the known data value occurring concurrently with the reading of a first portion of the identifier of at least one other record;

for each of the portions of the known data value;

for only those records having a previous portion of the identifier matching a corresponding previous portion of the known data value, interleaving reads of a next portion of the identifiers of records of the first table with reads of a next portion of the identifiers of the records of the second table; and

comparing the read next portion of the identifiers with a corresponding next portion of the known data value;

for each record in the first and second table for which all portions of its identifier matches all portions of the known data value, updating the record.

4. The method of claim 3, further comprising creating a new record in the first table and a new record in the second table if at least one portion of the identifiers of the records in the first and second tables does not match a corresponding portion of the known data value.

5. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in a first and second table stored in the memory, each table including a plurality of records, each record including a status field indicating whether the record is empty or full, and a unique identifier having N portions, each portion equal to the byte width of the data bus, the method comprising:

interleaving reads of the status fields of a selected number of records in the first table with reads of the status fields of a selected number of records from the second table, the number of records read determined according to the read latency of the memory;

for only those records read having a status field indicating a full record;

interleaving reads of first portions of the identifiers of records of the first table with reads of the first portions of the identifiers of the records of the second table; and

comparing the read first portions of the identifiers with a corresponding first portion of the known data value;

for only those records having a first portion of the identifiers matching the first portion of the known data value;

for each jth portion of the identifiers, where j=2 to N, for only those records having a (j-1)th portion of the identifiers matching the (j-1)th portion of the known data value;

interleaving reads of the jth portions of the identifiers of records of the first table with reads of the jth portions of the identifiers of the records of the second table; and

comparing the read jth portions of the identifiers with a corresponding jth portion of the known data value;

for each record in the first and second table for which all portions of its identifier matches all portions of the known data value, updating the record.

6. The method of claim 5, further comprising creating a new record in the first table and a new record in the second table if at least one portion of the identifiers of the records in the first and second tables does not match a corresponding portion of the known data value.

7. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in a table stored in the memory, the table including a plurality of records, each record including a status field indicating whether the record is empty or full, and a unique identifier having a number of portions, each portion equal to the byte width of the data bus, and the known data value having a corresponding number of portions, the method comprising:

interleaving reads of the status fields of a selected number of records in the table with reads of the status fields of a selected number of other records from the table, the number of records read determined according to the read latency of the memory;

determining whether the status fields of each read record indicates the record being full or empty, the determination of the status field of at least one read record occurring concurrently with the reading of the status fields of at least one other record;

for only those records read having a status field indicating a full record;

interleaving reads of first portions of the identifiers of records of the table with reads of the first portions of the identifiers of the other records of the table;

comparing the read first portions of the identifiers with a corresponding first portion of the known data value, the comparison of the first portion of the identifier of at least one read record with the corresponding first portion of the known data value occurring concurrently with the reading of a first portion of the identifier of at least one other record;

for each of the portions of the known data value;

for only those records having a previous portion of the identifier matching a corresponding previous portion of the known data value, interleaving reads of a next portion of the identifiers of records of the table with reads of a next portion of the identifiers of the other records of the table; and

comparing the read next portion of the identifiers with a corresponding next portion of the known data value;

for each record in the table for which all portions of its identifier matches all portions of the known data value, updating the record.

8. The method of claim 7, further comprising creating a new record in the table if at least one portion of the identifiers of the records in the table does not match a corresponding portion of the known data value.

9. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in a first and second table stored in the memory, each record including a unique identifier having a number of portions, the method comprising:

interleaving reads of portions of the identifiers of records of the first table with reads of portions of the identifiers of the records of the second table;

comparing the read portions of the identifiers with a corresponding portion of the known data value, the comparison of the portion of the identifier of at least one read record with the corresponding portion of the known data value occurring concurrently with the reading of a portion of the identifier of at least one other record;

for only those records having a previous portion of the identifier matching a corresponding previous portion of the known data value;

interleaving reads of a next portion of the identifiers of records of the first table with reads of a next portion of the identifiers of the records of the second table; and

comparing the read next portion of the identifiers with a corresponding next portion of the known data value;

for each record in the first and second table for which all portions of its identifier matches all portions of the known data value, updating the record.

10. The method of claim 9, further comprising creating a new record in the first table and a new record in the second table if at least one portion of the identifiers of the records in the first and second tables does not match a corresponding portion of the known data value.

11. In a computer system including a memory having a fixed number of clock cycles of read latency and a data bus having a fixed byte width, a computer implemented method matching a known data value with records in a first and second table stored in the memory, each table including a plurality of records, each record including a status field indicating whether the record is empty or full, and a unique identifier having a number of portions, each portion equal to the byte width of the data bus, and the known data value having a corresponding number of portions, the method comprising:

interleaving reads of the status fields of a selected number of records in the first table with reads of the status fields of a selected number of records from the second table, the number of records read determined according to the read latency of the memory;

determining whether the status fields of each read record indicates the record being full or empty, the determination of the status field of at least one read record occurring concurrently with the reading of the status fields of at least one other record;

for only those records read having a status field indicating a full record;

interleaving reads of first portions of the identifiers of records of the first table with reads of the first portions of the identifiers of the records of the second table;

comparing the read first portions of the identifiers with a corresponding first portion of the known data value, the comparison of the first portion of the identifier of at least one read record with the corresponding first portion of the known data value occurring concurrently with the reading of a first portion of the identifier of at least one other record;

for each of the remaining portions of the known data value;

for only those records having a previous portion of the identifier matching a corresponding previous portion of the known data value, interleaving reads of a next portion of the identifiers of records of the first table with reads of a next portion of the identifiers of the records of the second table; and

comparing the read next portion of the identifiers with a corresponding next portion of the known data value;

for each record in the first and second table for which all portions of its identifier matches all portions of the known data value, updating the record.

12. The method of claim 11, further comprising creating a new record in the first table and a new record in the second table if at least one portion of the identifiers of the records in the first and second tables does not match a corresponding portion of the known data value.