Method of searching a data record for a valid identifier

• US 6,564,214 B1
• Filed: 06/28/2000
• Issued: 05/13/2003
• Est. Priority Date: 06/28/2000
• Status: Expired due to Fees

• Current Assignee: Visual Networks Operations, Inc. (Danaher Corporation)
• Original Assignee: Visual Networks Technologies, Inc.
• Inventors: Bhide, Chandrashekhar
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/605,680
• Time in Patent Office: 1,049 Days
• Field of Search: 707/2, 707/5, 707/6, 709/223, 709/226
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A backend data processor of a network monitoring system attempts to identify the point of presence (POP) associated with each uploaded network performance data record by comparing the POP identification information contained in each uploaded data record with the known, valid POP telephone numbers stored in a lookup phone book. A series of lookup searches are performed by comparing a certain number of the digits of the raw POP string with corresponding digits of the POP numbers stored in the lookup phone book until an exact, unique match is found. An initial “pessimistic” lookup search compares the rightmost N digits of the uploaded POP string with the rightmost N digits of each POP number in the lookup phone book for all countries. If the initial pessimistic lookup search is unsuccessful, an optimistic lookup search is conducted taking into account independent information indicating the country code and area code from which the data record originated. If the optimistic lookup search is unsuccessful, a final pessimistic lookup search is conducted by again comparing the rightmost N digits of the uploaded POP string with the rightmost N digits of each POP number in the lookup phone book for all countries, with successively smaller values of N.

Claims

1. In a system for organizing and associating a collection of data records in accordance with data record identifiers that indicate common attributes among sets of data records within the collection, a method of validating that a data segment within a data record is an identifier that matches one of a number of pre-stored identifiers, comprising the steps of:

(a) storing a set of valid identifiers;

(b) comparing the rightmost N digits of the data segment with the rightmost N digits of valid identifiers from the set of stored valid identifiers, where N is a positive integer; and

(c) determining that the data segment is a certain one of the valid identifiers when the digits of the data segment match the digits of the certain one of the valid identifiers.

2. The method of claim 1, wherein the data segment is contained within a data field of the data record, the method further comprising the step of:

(d) extracting the data segment from the data field by stripping out at least some portions of the data field other than the data segment.

3. The method of claim 1, wherein the data segment is a point of presence (POP) string identifying a POP corresponding to the data record, and the set of valid identifiers is a set of valid POP numbers, stored in a lookup phone book, that identify actual POPs in a communication network.

4. The method of claim 3, wherein the data string is embedded in a string with other data.

5. The method of claim 1, wherein step (b) includes:

performing a broad search involving comparison of the selected digits of the data segment with digits of the complete set of stored valid identifiers.

6. The method of claim 1, wherein step (b) includes:

performing an information-assisted search by comparing selected digits of the data segment with digits of only certain ones of the stored valid identifiers, wherein the certain ones of the stored identifiers are selected in accordance with supplemental information relating to the data record.

7. The method of claim 1, wherein:

the data segment is a point of presence (POP) string identifying a POP corresponding to the data record, and the set of valid identifiers is a set of valid POP numbers, stored in a lookup phone book, that identify actual POPs in a communication network; and

the initial search includes;

comparing the rightmost N digits of the POP string with the rightmost N digits of the valid POP numbers in the lookup phone book; and

, if an exact, unique match is found between the rightmost N digits of the POP string and the rightmost N digits of one of the stored valid POP numbers, determining that the data record corresponds to the POP identified by the matching valid POP number.

8. The method of claim 7, wherein the rightmost N digits of the POP string are compared to the rightmost N digits of valid POP numbers from more than one country.

9. The method of claim 7, wherein the initial search further includes decrementing the value of N and repeating the initial search if no match is found between the rightmost N digits of the POP string and the rightmost N digits of any of the stored valid POP numbers.

10. The method of claim 9, wherein the value of N is initially set to nine and decremented to eight.

11. The method of claim 1, wherein, if the initial search fails to produce a match, step (b) further includes performing an information-assisted search using supplemental information about the data record to refine search parameters for identifying a match between the data segment and a valid identifier from the set of stored valid identifiers.

12. The method of claim 11, wherein:

the data segment is a point of presence (POP) string identifying a POP corresponding to the data record, and the set of valid identifiers is a set of valid POP numbers, stored in a lookup phone book, that identify actual POPs in a communication network; and

the information-assisted search includes;

identifying information in the data record indicating a country of origin of the data record; and

narrowing the search for a matching valid POP number to stored valid POP numbers from the country of origin.

13. The method of claim 12, wherein a first stage of the information-assisted search includes:

retrieving a list of K POP rules each specifying a number of area code digits (AC) and a number of local number digits (LN) for a type of POP number format used in the country of origin, where K is the number of different POP number formats used in the country of origin;

for one of the POP rules, comparing the rightmost AC+LN digits of the POP string with the rightmost AC+LN digits of the valid POP numbers from the country of origin and, if an exact, unique match is found between the rightmost AC+LN digits of the POP string and the rightmost AC+LN digits of one of the stored valid POP numbers, determining that the data record corresponds to the POP identified by the matching valid POP number; and

if no match is found in the preceding step, repeating the preceding step with others of the K POP rules until an exact, unique match is found or all K POP rules have been tried.

14. The method of claim 13, wherein, if the first stage of the information-assisted search fails to find a match, a second stage of the information-assisted search includes:

identifying information in the data record indicating an area code of the data record;

for one of the POP rules, concatenating the area code and the rightmost LN digits of the POP string;

comparing the concatenated digits with the rightmost AC+LN digits of the valid POP numbers from the country of origin and, if an exact, unique match is found between the concatenated digits and the rightmost AC+LN digits of one of the stored valid POP numbers, determining that the data record corresponds to the POP identified by the matching valid POP number; and

if no match is found in the preceding step, repeating the preceding step with others of the K POP rules until an exact, unique match is found or all K POP rules have been tried.

15. The method of claim 14, wherein, if the second stage of the information-assisted search fails to find a match, a third stage of the information-assisted search includes:

identifying information in the data record indicating a service provider corresponding to the data record;

for one of the POP rules;

comparing the rightmost LN digits of the POP string with the rightmost LN digits of the valid POP numbers from the country of origin;

if an exact, unique match is found between the rightmost LN digits of the POP string and the rightmost LN digits of one of the stored valid POP numbers, determining that the data record corresponds to the POP identified by the matching valid POP number; and

, if matches are found between the rightmost LN digits of the POP string and the rightmost LN digits of plural valid POP numbers all corresponding to a same service provider, determining that the data record corresponds to the POP identified only by the rightmost LN digits of the POP string; and

if no match is found in the preceding step, repeating the preceding step with others of the K POP rules until a match is found or all K POP rules have been tried.

16. The method of claim 11, wherein, if the information-assisted search fails to produce a match, step (b) includes performing a final search by comparing the rightmost N digits of the data segment with the rightmost N digits of valid identifiers from the set of stored valid identifiers with successively smaller values of N until the compared digits of the data segment match the digits of at least one of the stored valid identifiers or until the value of N reaches a predetermined minimum value.

17. The method of claim 16, wherein:

the data segment is a point of presence (POP) string identifying a POP corresponding to the data record, and the set of valid identifiers is a set of valid POP numbers, stored in a lookup phone book, that identify actual POPs in a communication network; and

the final search includes;

comparing the rightmost N digits of the POP string with the rightmost N digits of the valid POP numbers in the lookup phone book;

if an exact, unique match is found between the rightmost N digits of the POP string and the rightmost N digits of one of the stored valid POP numbers, determining that the data record corresponds to the POP identified by the matching valid POP number; and

, if a match is found between the rightmost N digits of the POP string and the rightmost N digits of plural of the stored valid POP numbers, determining that the data record corresponds to a POP identified only by the rightmost N digits of the POP string.

18. The method of claim 17, wherein the rightmost N digits of the POP string are compared to the rightmost N digits of valid POP numbers from more than one country.

19. The method of claim 18, wherein the data record is identified by the rightmost N digits of the POP string matching the rightmost N digits of plural stored valid POP numbers only when the plural stored valid POP numbers all correspond to a same country and a same service provider.

20. The method of claim 17, wherein the final search further includes decrementing the value of N and repeating the final search if no match is found between the rightmost N digits of the POP string and the rightmost N digits of any of the stored valid POP numbers, until a match is found or N is decremented to a predetermined minimum value.

21. The method of claim 20, wherein the value of N is initially set to nine and the predetermined minimum value is six.

22. A method of determining whether or not a string within a data field of a data record contains a valid identifier of a point-of-presence (POP) corresponding to the data record, the method comprising the steps of:

(a) storing a set of valid POP numbers that identify actual POPs in a communication network;

(b) extracting the string from the data field;

(c) comparing digits of the string to digits of the valid POP numbers; and

(d) determining that the string contains a valid POP identifier when the digits of the string match the digits of a valid POP number in the set.