Patent ID: 8014321

Claim:
In a federation infrastructure, a method for routing a message towards a destination node, the method comprising: an act of a receiving node receiving a message along with a destination identifier indicating a destination and a partially ordered list of proximity criterion, the receiving node being included in a root ring of nodes configured for bi-directional routing as well as a plurality of sub-rings of nodes defined by the proximity criterion, the partially ordered list of proximity criterion defining a plurality of classes of nodes in a hierarchy of node classes, the receiving node being part of a plurality of classes of nodes in the hierarchy of node classes corresponding to the plurality of sub-rings, including a current class of nodes selected from among the one or more classes of nodes in the hierarchy of node classes corresponding to a current sub-ring; an act of determining a next appropriate node that is to receive the message based on the position of the receiving node in the plurality of sub-rings of nodes and the partially ordered list of proximity criterion, the next appropriate node being numerically closer to the destination than other routing nodes in a routing table at the receiving node while still being within the current class of nodes defined by the partially ordered list or proximity criterion, the routing table representing separate routing information for the root ring of nodes and for each of the plurality of sub-rings of nodes, including at least a logarithmic index of other nodes in each ring of nodes, the routing table being populated at least based on the number base utilized to generate the identifier space for generating identifiers in the federation infrastructure, the receiving node having a symmetric relationship with nodes in the receiving node's routing table; an act of sending the message to the next appropriate node; and an act of sending a previously received status message back to the node that sent the received message to the receiving node, the status message related to the received message.