Patent ID: 6687363
Filing Date: 2004-02-03
Classification: H04M,H04Q

Abstract:
A method for designating links between nodes of a communication network of the kind that includes n nodes, n a positive integer, a plurality of switches, each switch containing some of the n nodes, and links connecting some pairs of the nodes, the method comprising:(a) at least once, performing a random assignment of edges to pairs of vertices of a graph wherein each vertex represents a node of the communication network, the random assignment carried out such that: (i) any vertex pair, denominated a fraternal pair, whose corresponding nodes reside within the same switch has zero probability of being assigned an edge, but all other vertex pairs, denominated admissible pairs, have a finite probability of being assigned an edge; and (ii) at least one resulting graph, denominated a low-degree graph, has a maximum degree less than 2{square root over (n(ln n))}; (b) adding edges, if any are needed, to a low-degree graph until all admissible vertex pairs of the resulting graph are connected by a path of at most two edges; and (c) mapping vertices of the resulting graph to nodes of the communication network.