Method for fast network-aware clustering

• US 7,219,160 B1
• Filed: 11/03/2000
• Issued: 05/15/2007
• Est. Priority Date: 08/27/1999
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Buchsbaum, Adam Louis, Fowler, Glenn Stephen, Krishnamurthy, Balachander, Wang, Jia
• Primary Examiner(s): Chang, Jungwon
• Application Number:
  US09/705,675
• Time in Patent Office: 2,384 Days
• Field of Search: 703/2, 707/104.1, 709/249, 709/242, 709/223, 709/224, 709/229, 709/202, 709/227, 709/241, 709/220, 370/408, 370/392, 370/395.52, 370/351, 715/513
• US Class Current: 709/242
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method for clustering together network IP addresses is disclosed. A number of IP addresses are received and processed to determine which IP addresses share a longest prefix matching. The longest prefix matching process is performed according to radix encoded trie which facilitates on-line clustering of the IP addresses. Client and/or server IP addresses may be clustered in accordance with the teachings herein.

Claims

1. An on-line method of classifying IP addresses into related clusters within a distributed information network, the method comprising the steps of:

generating a unified prefix/netmask table from a plurality of network routing table prefix/netmask entries, said unified prefix/netmask entries comprising a plurality of IP addresses;

processing the plurality of IP addresses according to a radix encoded trie classification process to determine a common prefix between at least a portion of the plurality of IP addresses; and

grouping IP addresses which share a common prefix into a network client cluster.

2. The method of claim 1, wherein the plurality of IP addresses are received from one or more network routers.

3. The method of claim 1, wherein the IP addresses are network client IP addresses.

4. The method of claim 1, wherein the distributed information network is the World Wide Web.

5. A method for on-line grouping of a plurality of Web client IP addresses into related client clusters, the method comprising the steps of:

generating a unified prefix/netmask table from a plurality of network routing table prefix/netmask entries, each prefix/netmask entry in said plurality of network routing table prefix/netmask entries comprising a client IP address;

performing longest prefix matching on each client IP address; and

classifying all of the client IP addresses that have the same longest matched prefix into a client cluster based on a radix encoded trie matching process.

6. The method of claim 5, wherein the client IP addresses are extracted in real time from a network server.

7. The method of claim 5, wherein the distributed information network is the Internet.

8. A method for determining the relationships between a plurality of IP addresses in a unified prefix/netmask table, the method comprising:

generating a unified prefix/netmask table from a plurality of network routing table prefix/netmask entries, each prefix/netmask entry in said plurality of network routing table prefix/netmask entries comprising a client IP address;

processing the plurality of IP addresses according to a radix encoding trie (retrie) process to determine a common prefix between at least a portion of the plurality of IP addresses, said plurality of a IP addresses; and

grouping all of the IP addresses which share a common longest prefix matching into at least one IP grouping.

9. The method of claim 8, further comprising:

receiving the plurality of IP addresses from one or more network servers.

10. The method of claim 9, wherein the network servers are at least one of proxy servers, cache servers, content distribution servers and mirror servers.

11. The method of claim 8, wherein at least one address in said plurality of IP addresses is a client IP address.

12. The method of claim 8, wherein at least one address in said plurality of IP addresses is a server IP address.

13. The method of claim 8, wherein the retrie includes shift, mask values which are combined into a single value in a predecessor table.

14. The method of claim 8, wherein the elements in a last retrie table level contain only a next hop index so as to decrease the retrie table size.

15. The method of claim 8, wherein the retrie includes a fixed number of retrie levels.

16. The method of claim 8, wherein the number of retrie levels is fixed at two levels.

17. A computer-readable medium containing executable instructions which cause a computer to perform the steps of:

generating a unified prefix/netmask table from a plurality of network routing table prefix/netmask entries, each prefix/netmask entry in said plurality of network routing table prefix/netmask entries comprising at least one IP address;

performing longest prefix matching using a radix encoded trie matching process on at least one IP address; and

classifying said at least one IP addresses that have the same longest matched prefix into a client cluster.

18. The computer-readable medium of claim 17, wherein the at least one IP address is a client IP address.

19. The computer-readable medium of claim 17, wherein the at least one IP address is a server IP address, wherein the cluster is a server cluster.

20. The computer-readable medium of claim 17, wherein the radix encoded trie is described by the equation:

while(! ((r=r→

table1(x>

>

r→

shift)&

r→

mask] )&

1)

where x is the search key and r is the radix encode trie.