ALLOCATING AND RECLAIMING RESOURCES WITHIN A RENDEZVOUS FEDERATION

• US 20080031246A1
• Filed: 05/22/2007
• Published: 02/07/2008
• Est. Priority Date: 10/22/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malkhi, Dahlia, Xun, Lu, Kakivaya, Gopala, Hasha, Richard
• Granted Patent: US 7,958,262 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 61/4535 using an address exchange platform which sets up a session between two nodes, e.g. rendezvous servers, session initiation protocols [SIP] registrars or H.323 gatekeepers

Abstract

The present invention extends to methods, systems, and computer program products for allocating and reclaiming resources within a rendezvous federation. Embodiments of the invention include formulating and routing messages in accordance with cached two-way agreements between adjacent nodes on a ring of nodes. Cached two-way agreements divide responsibility for at least unoccupied identifiers between the adjacent nodes on a ring. When a message is received at a node, the node can refer to a cached two-way agreement to determine if it or an adjacent node is responsible for the message. The node then sends the message to the next appropriate component in accordance with the cached two-way agreement.

Claims

1. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including at least a receiving node, an immediate predecessor neighbor node preceding the receiving node on the ring of nodes, and an immediate successor neighbor node succeeding the receiving node on the ring of nodes, 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 on the ring of nodes, the destination identifier located between the receiving node and an immediate neighborhood node selected from among the immediate predecessor neighbor node and the immediate successor neighborhood node;

an act of the receiving node referring to a cached two-way agreement between the receiving node and the immediate neighbor node to determine the next appropriate node that is to receive the message, the cached two-way agreement at least implying a division of responsibility for the identifier space between the receiving node and an immediate neighbor node;

an act of sending the message to the next appropriate component based on the determination of the next appropriate node.

2. The method as recited in claim 1, wherein the act of a receiving node receiving a message along with a destination identifier indicating a destination on the ring of nodes comprises an act of receiving a message along with a destination identifier that is an unoccupied identifier between the receiving node and the immediate predecessor neighborhood node.

3. The method as recited in claim 1, wherein the act of a receiving node receiving a message along with a destination identifier indicating a destination on the ring of nodes comprises an act of receiving a message along with a destination identifier that is an unoccupied identifier between the receiving node and the immediate successor neighborhood node.

4. The method as recited in claim 1, wherein the act the receiving node referring to a cached two-way agreement between the receiving node and the immediate neighbor node comprises an act of referring to a cached two-way agreement between the receiving node and the immediate predecessor neighbor node.

5. The method as recited in claim 4, further comprising:

an act of determining that the destination identifier is not between the receiving node and the immediate predecessor neighbor node; and

an act of referring to a second cached two-way agreement between the receiving node and the immediate successor node to determine the next appropriate node that is to receive the message.

6. The method as recited in claim 1, wherein the act the receiving node referring to a cached two-way agreement between the receiving node and the immediate neighbor node comprises an act of referring to a cached two-way agreement between the receiving node and the immediate successor neighbor node.

7. The method as recited in claim 6, further comprising:

an act of determining that the destination identifier is not between the receiving node and the immediate successor neighbor node; and

an act of referring to a second cached two-way agreement between the receiving node and the immediate predecessor node to determine the next appropriate node that is to receive the message.

8. The method as recited in claim 1, wherein an act of sending the message to the next appropriate component based on the determination of the next appropriate node comprises an act of sending the message to the immediate predecessor neighbor node.

9. The method as recited in claim 1, wherein an act of sending the message to the next appropriate component based on the determination of the next appropriate node comprises an act of sending the message to the immediate successor neighbor node.

10. The method as recited in claim 1, wherein an act of sending the message to the next appropriate component based on the determination of the next appropriate node comprises an act of sending the message to a resource handler instance corresponding to the destination identifier.

11. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including at least a receiving node, an immediate predecessor neighborhood node for the receiving node, and an immediate successor neighborhood node for the receiving node, 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 on the ring of nodes;

an act of the receiving node referring to a first cached two-way agreement with the immediate predecessor neighborhood node and a second cached two-way agreement with the immediate successor neighborhood node to determine the next appropriate node that is to receive the message, the first and second cached two-way agreements at least implying a division of responsibility for the identifier space between the immediate predecessor neighbor node and the immediate successor neighbor node; and

an act of sending the message to the next appropriate component based on the determination of the next appropriate node.

12. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including at least a current node, a current immediate predecessor neighbor node preceding the receiving node on the ring of nodes, and a current immediate successor neighbor node succeeding the receiving node on the ring of node, a method for formulating a two-way agreement between the current node and an immediate neighborhood node, the method comprising:

an act of the current node accessing an indication that the configuration of the ring of nodes has changed, the indication indicative of a change in at least a current immediate neighbor node selected from among the current immediate predecessor node and the current immediate successor node, the change resulting in a new immediate neighbor node, the indication further indicative of a need to formulate a two-way agreement dividing responsibility for at least unoccupied identifiers on the ring between the current node and the new immediate neighbor node; and

an act of the current node and the new immediate neighbor node agreeing to a responsibility boundary between the current node and new immediate neighbor node that is to divide responsibility for the unoccupied identifiers between the current node and the new immediate neighbor node, unoccupied identifiers between the current node and the responsibility boundary being the responsibility of the current node and unoccupied identifiers between the responsibility boundary and the new immediate neighbor node being the responsibility of the new immediate neighbor node.

13. The method as recited in claim 12, wherein the act of the current node accessing an indication that the configuration of the ring of nodes has changed comprises an act of the current node detecting that the current immediate predecessor neighbor node has departed the ring of nodes.

14. The method as recited in claim 12, wherein the act of the current node accessing an indication that the configuration of the ring of nodes has changed comprises an act of the current node detecting that a new node has joined the ring of nodes between the current node and the immediate predecessor neighbor

15. The method as recited in claim 13 or 14, further comprising:

an act of the current node identifying a new immediate predecessor neighbor node on the ring of nodes in response to accessing the indication that the configuration of the ring of nodes has changed.

16. The method as recited in claim 15, wherein the current node and the new immediate neighbor node agreeing to a responsibility boundary between the current node and new immediate neighbor node comprises an act of the current node and the new immediate predecessor node agreeing to a responsibility boundary between the current node and new immediate predecessor neighbor node.

17. The method as recited in claim 12, wherein the act of the current node accessing an indication that the configuration of the ring of nodes has changed comprises an act of the current node detecting that the current immediate successor neighbor node has departed the ring of nodes.

18. The method as recited in claim 12, wherein the act of the current node accessing an indication that the configuration of the ring of nodes has changed comprises an act of the current node detecting that a new node has joined the ring of nodes between the current node and the immediate successor neighbor node.

19. The method as recited in claim 17 or 18, further comprising:

an act of the current node identifying a new immediate successor neighbor node on the ring of nodes in response to accessing the indication that the configuration of the ring of nodes has changed.

20. The method as recited in claim 19, wherein the current node and the new immediate neighbor node agreeing to a responsibility boundary between the current node and new immediate neighbor node comprises an act of the current node and the new immediate successor node agreeing to a responsibility boundary between the current node and new immediate successor neighbor node.