Method and apparatus to support application and network awareness of collaborative applications using multi-attribute clustering

• US 7,975,039 B2
• Filed: 08/04/2009
• Issued: 07/05/2011
• Est. Priority Date: 12/01/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sahu, Sambit, Liu, Zhen, Popescu, George V.
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): Mejia; Anthony
• Application Number:
  US12/535,436
• Publication Number:
  US 20090292802A1
• Time in Patent Office: 700 Days
• Field of Search: 709/223, 717/1
• US Class Current: 709/223
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method of clustering communication nodes based on network attributes such as network delays and forwarding capacity; on communication interest attributes; and on application attributes such as quality of service preferences/constraints in providing communications between users and application servers. A multi-attribute communication feature vector is formed. That vector is comprised of network attributes, communication interests attributes, and quality of service requirements and is used to form efficient group communication mechanisms for distributed collaborative applications. Then the multi-attribute communication feature vectors are clustered. The clustering methods for multi-type attribute feature vectors are: iterative clustering using a generalized distance space with normalized attribute subspace metrics; fusion clustering, and nested clustering.

Claims

1. A computer readable storage device containing a program that, when executed by a processor, causes the processor to perform a method for clustering a plurality of network nodes in a multi-type vector space, where the method comprises:

forming a plurality of network attribute maps based on one or more network constraints;

forming a communication interest space map based on one or more application constraints, wherein the forming the communication interest space map is based on a distance measurement of a similarity between at least two of one or more communication interest feature vectors, and wherein the similarity is measured using a non-linear distance function;

extracting the one or more communication interest feature vectors from the communication interest space map;

extracting one or more network attribute feature vectors from the plurality of network attribute maps;

obtaining one or more network quality of service constraints;

forming a single feature vector for each of the plurality of network nodes, the single feature vector being based on the one or more communication interest feature vectors, the one or more network attribute feature vectors, and the one or more network quality of service constraints; and

forming a list in which one or more of the plurality of network nodes are labeled based on the single feature vector for each of the plurality of network nodes.

2. The computer readable storage device of claim 1, wherein forming network attribute maps includes steps of:

forming a plurality of delay maps from one or more measured network delays;

forming a path loss map based on one or more network path losses;

forming a bandwidth map based on one or more bandwidths of the plurality of network nodes; and

forming a forwarding capacity map based on one or more forwarding capacities at the plurality of network nodes.

3. Apparatus for clustering a plurality of network nodes in a multi-type vector space, comprising:

means for forming a plurality of network attribute maps based on one or more network constraints;

means for forming a communication interest space map based on one or more application constraints;

means for extracting one or more communication interest feature vectors from the communication interest space map, wherein the forming the communication interest space map is based on a distance measurement of a similarity between at least two of one or more communication interest feature vectors, and wherein the similarity is measured using a non-linear distance function;

means for extracting the one or more network attribute feature vectors from the plurality of network attribute maps;

means for obtaining one or more network quality of service constraints;

means for forming a single feature vector for each of the plurality of network nodes, the single feature vector being based on the one or more communication interest feature vectors, the one or more network attribute feature vectors, and the one or more network quality of service constraints; and

means for forming a list in which one or more of the plurality of network nodes are labeled based on the single feature vector for each of the plurality of network nodes.

4. A method of clustering a plurality of network nodes comprising:

using a processor to perform steps comprising;

forming a plurality of network attribute maps based on one or more network constraints;

forming a communication interest space map based on one or more application constraints, wherein the forming the communication interest space map is based on a distance measurement of a similarity between at least two of one or more communication interest feature vectors, and wherein the similarity is measured using a non-linear distance function;

extracting the one or more communication interest feature vectors from the communication interest space map;

extracting one or more network attribute feature vectors from the plurality of network attribute maps;

obtaining one or more network quality of service constraints;

forming a single feature vector for each of the plurality of network nodes, the single feature vector being based on the one or more communication interest feature vectors, the one or more network attribute feature vectors, and the one or more network quality of service constraints; and

forming a list in which one or more of the plurality of network nodes are labeled based on the single feature vector for each of the plurality of network nodes.

5. The method of claim 4, wherein the forming the communication interest space map is based on a distance measurement of a similarity between at least two of the plurality of network nodes that share a common interest.

6. The method of claim 4, wherein the one or more network constraints comprise at least one of:

available bandwidth, network delay, network packet loss, and node fanout.

7. The method of claim 4, wherein the one or more application constraints comprises a collaborative usage of an application described by the one or more application constraints.

8. The method of claim 4, wherein the forming the list is a result of performing clustering of the plurality of network nodes, the clustering being based on the single feature vector for each of the plurality of network nodes.

9. The method of claim 8, wherein the clustering is performed using a fusion method in which one or more of said plurality of network nodes are clustered in each attribute space on subspace classifiers.

10. The method of claim 8, wherein the clustering is performed using a nested method in which one or more of said plurality of network nodes are initially clustered based on a sub-set of attributes and then re-clustered by iteratively considering additional attributes.

11. The method of claim 8, wherein the clustering is based on one or more bandwidth constraints.

12. The method of claim 8, wherein the clustering is based on a weighted distance function modeled from normalized attribute subspace metrics.

13. The method of claim 4, wherein the communication interest space map indicates at least one of:

a user request for a content update or a user subscription to a specific data item or to a set of proximal data sources.

14. The method of claim 4, wherein the communication interest space map models a communication interest as a vector.

15. The method of claim 4, wherein the communication interest space map models a communication interest as a cell.

16. The method of claim 4, wherein the communication interest space map models a communication interest as a plurality of cells representing a communication interest of a single one of the plurality of network nodes.

17. The method of claim 4, wherein each point in each of the plurality of network attribute maps represents a set of virtual coordinates for one of the plurality of network nodes in a network overlay.

18. The method of claim 4, wherein the forming the plurality of network attribute maps comprises:

forming a plurality of delay maps from one or more measured network delays;

forming a path loss map based on one or more network path losses;

forming a bandwidth map based on one or more bandwidths of the plurality of network nodes; and

forming a forwarding capacity map based on one or more forwarding capacities at the plurality of network nodes.