Sparsification of pairwise cost information

Patent metadata

Field	Value
Publication number	US-9667499-B2
Application number	US-201414484688-A
Country	US
Kind code	B2
Filing date	Sep 12, 2014
Priority date	Sep 12, 2014
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

A capability for sparsifying a representation of pairwise cost information is presented herein. The capability for sparsifying a representation of pairwise cost information may be used to sparsify a representation of pairwise cost information for a set of nodes. The sparsification of a representation of pairwise cost information for a set of nodes may provide thereby a sparsified representation of the pairwise cost information for the set of nodes. The sparsification of the representation of pairwise cost information for the set of nodes may be based on clustering of the nodes of the set of nodes into clusters. The sparsification of the representation of pairwise cost information for the set of nodes may be based on calculation of intra-cluster costs and inter-cluster costs, where the intra-cluster costs and inter-cluster costs are calculated based on the pairwise cost information of the representation of the pairwise cost information for the set of nodes.

First claim

What is claimed is:

1. An apparatus, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
receive a representation of pairwise cost information for a set of nodes;
determine a clustering of the nodes into a set of clusters; and
sparsify the representation of pairwise cost information for the set of nodes, based on the clustering of the nodes into the set of clusters, to form a sparsified representation of the pairwise cost information for the set of nodes;
wherein, to sparsify the representation of the pairwise cost information for the set of nodes, the processor is configured to:
determine, for at least one of the clusters based on the pairwise cost information for the set of nodes, a respective intra-cluster cost for the respective cluster that is indicative of an average minimum cost between pairs of nodes of the respective cluster; and
determine, for at least one pair of clusters based on the pairwise cost information for the set of nodes, a respective inter-cluster cost for the respective pair of clusters that is indicative of an average minimum cost between pairs of nodes included in respective clusters in the respective pair of clusters;

wherein the sparsified representation of the pairwise cost information for the set of nodes comprises a matrix of cells, wherein ones of the cells associated with respective ones of the clusters include the respective intra-cluster costs for the respective ones of the clusters, wherein ones of the cells associated with respective pairs of the clusters include the respective inter-cluster costs for the respective pairs of the clusters.

2. The apparatus of claim 1 , wherein the pairwise cost information is based on at least one cost measure, wherein the at least one cost measure comprises at least one of a measure of distance of paths between node pairs or a measure of failure probability along paths between node pairs.

3. The apparatus of claim 1 , wherein the representation of pairwise cost information for the set of nodes comprises an N×N matrix with N being a number of nodes in the set of nodes, wherein the matrix of cells of the sparsified representation of pairwise cost information for the set of nodes comprises a k×k matrix, wherein N>k.

4. The apparatus of claim 1 , wherein the processor is configured to:
cluster the nodes of the set of nodes to form the set of clusters.

5. The apparatus of claim 4 , wherein, to cluster the nodes of the set of nodes to form the set of clusters, the processor is configured to:
determine a number of clusters (k) in the set of clusters;
create the k clusters by selecting k nodes from the set of nodes and respectively adding the k nodes to the k clusters; and
group remaining nodes of the set of nodes into the k clusters.

6. The apparatus of claim 5 , wherein, to create the k clusters by selecting k nodes from the set of nodes and respectively adding the k nodes to the k clusters, the processor is configured to:
select a first node from the set of nodes and add the first node to a first cluster of the k clusters; and
select a second node from the set of nodes and add the second node to a second cluster of the k clusters, wherein the second node is a node of the set of nodes having a maximum distance from the first node of the first cluster.

7. The apparatus of claim 5 , wherein, to group any remaining nodes of the set of nodes into the k clusters, the processor is configured to:
for at least one of the remaining nodes of the set of nodes, identify one of the k clusters closest to the one of the remaining nodes of the set of nodes and group the one of the remaining nodes of the set of nodes into the one of the k clusters closest to the one of the remaining nodes of the set of nodes.

8. A method, comprising:
receiving, via a processor, a representation of pairwise cost information for a set of nodes;
determining, by the processor, a clustering of the nodes into a set of clusters; and
sparsifying, by the processor, the representation of pairwise cost information for the set of nodes, based on the clustering of the nodes into the set of clusters, to form a sparsified representation of the pairwise cost information for the set of nodes;
wherein sparsifying the representation of the pairwise cost information for the set of nodes comprises:
determining, for at least one of the clusters based on the pairwise cost information for the set of nodes, a respective intra-cluster cost for the respective cluster that is indicative of an average minimum cost between pairs of nodes of the respective cluster; and
determining, for at least one pair of clusters based on the pairwise cost information for the set of nodes, a respective inter-cluster cost for the respective pair of clusters that is indicative of an average minimum cost between pairs of nodes included in respective clusters in the respective pair of clusters;

wherein the sparsified representation of the pairwise cost information for the set of nodes comprises a matrix of cells, wherein ones of the cells associated with respective ones of the clusters include the respective intra-cluster costs for the respective ones of the clusters, wherein ones of the cells associated with respective pairs of the clusters include the respective inter-cluster costs for the respective pairs of the clusters.

9. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:
receiving a representation of pairwise cost information for a set of nodes;
determining a clustering of the nodes into a set of clusters; and
sparsifying the representation of pairwise cost information for the set of nodes, based on the clustering of the nodes into the set of clusters, to form a sparsified representation of the pairwise cost information for the set of nodes;
wherein sparsifying the representation of the pairwise cost information for the set of nodes comprises:
determining, for at least one of the clusters based on the pairwise cost information for the set of nodes, a respective intra-cluster cost for the respective cluster that is indicative of an average minimum cost between pairs of nodes of the respective cluster; and
determining, for at least one pair of clusters based on the pairwise cost information for the set of nodes, a respective inter-cluster cost for the respective pair of clusters that is indicative of an average minimum cost between pairs of nodes included in respective clusters in the respective pair of clusters;

wherein the sparsified representation of the pairwise cost information for the set of nodes comprises a matrix of cells, wherein ones of the cells associated with respective ones of the clusters include the respective intra-cluster costs for the respective ones of the clusters, wherein ones of the cells associated with respective pairs of the clusters include the respective inter-cluster costs for the respective pairs of the clusters.

Assignees

• Zhang Yihao
• Wilfong Gordon
• Scharf Michael
• Alcatel Lucent
• Alcatel Lucent Usa Inc

Inventors

• Zhang Yihao
• Wilfong Gordon
• Scharf Michael

Classifications

• H04L41/0893

  Assignment of logical groups to network elements · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L41/147

  for predicting network behaviour · CPC title

• H04L41/0813

  characterised by the conditions triggering a change of settings · CPC title