Optimal design of signaling networks for Internet Telephony

We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an Integer Programming approach to solve this problem, it quickly becomes intractable even for modest-size networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks.