Patent ID: 7386606

Claim:
A method comprising: determining a first cost associated with a logical network link between an active node and a first neighboring node of the active node within an overlay network, the active node and the first neighboring node communicating through one or more physical network links, the overlay network comprising nodes with application-level interconnections that form the overlay network, where the nodes exchange application-level communications via the interconnections, and where the application-level communications are transmitted via a data network that the logical network overlays; determining a second cost associated with a proposed logical-network link between the first neighboring node and a second neighboring node of the active node within the overlay network, the first neighboring node and the second neighboring node communicating through one or more physical network links; and reorganizing the overlay network by replacing the logical network link with the proposed logical network link in the overlay network, where the replacing includes comparing a random number with a reorganization probability, and where the reorganization probability is based on the first and second costs and the size of a neighbor list of the active node, the size of a neighbor list of the first neighboring node, and the size of a neighbor list of the second neighboring node.