US 6,687,363 B1Granted

Method of designing signaling networks for internet telephony

AssigneeLucent Technologies Inc.

InventorsMurali Aravamudan, Krishnan Kumaran, Kajamalai Gopalaswamy Ramakrishnan, Aravind Srinivasan

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method is disclosed for designing a signaling network of call coordinators (CCs) for internet telephony. The new method can be used to design a CC network of arbitrary size that satisfies, with high probability, limitations on the maximum number of sockets per CC and on the maximum number of hops between an arbitrary pair of switches in the network. According to the disclosed method, the network of CCs is treated initially as a collection of isolated points, one point for each CC. Then, links are added between pairs of CCs, excluding pairs lying within the same switch. The links are added randomly, but with a particular probability p, which may be different for different pairs. Thus, whether a given link is added depends, in effect, upon the outcome of a loaded coin toss in which the probability of a positive outcome is p.

Claims20

Dependent claims

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.

3 more elements

Dependencies are inferred from the claim text.