Allocating and reclaiming resources within a rendezvous federation
First Claim
1. At a receiving node in a federation infrastructure of a ring of nodes, the receiving node including a processor and system memory, the ring of nodes configured for bi-directional routing, the ring of nodes also including 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 identifying a node responsible for processing a message, the method comprising:
- an act of the receiving node receiving a message including a ring identifier, the ring identifier indicating that the message is directed to a destination on the ring of nodes, the destination being on the ring of nodes somewhere between the receiving node and an immediate neighborhood node, the immediate neighborhood node selected from among;
the immediate predecessor neighbor node and the immediate successor neighborhood node;
an act of the processor identifying a node, selected from among the receiving node and an immediate neighborhood node, that is responsible for processing the message based on the ring identifier included in the received message, including;
an act of the receiving node referring to a two-way agreement cached at the receiving node, the two-way agreement previously agreed to between the receiving node and the immediate neighbor node subsequent to the receiving node and the immediate neighbor node detecting their locations relative to one another on the ring of nodes in response to a change in the configuration of the ring of nodes, the two-way agreement defining message processing responsibility between the receiving node and the immediate neighborhood node for ring identifiers on the ring of nodes between the receiving node and the immediate neighborhood node in accordance with configurable rules, caching the two-way agreement at the receiving node providing the receiving node with local knowledge of ring identifiers that are the responsibility of the immediate neighborhood node, the defined processing responsibility for ring identifiers in the cached two-way agreement having previously been split between the immediate predecessor neighbor node and the immediate successor neighborhood prior to the change in the configuration of the ring such that the receiving node is responsible for at least some ring identifiers that were previously the responsibility of the immediate predecessor neighbor node and at least some ring identifiers that were previously the responsibility of the immediate successor neighborhood; and
an act of the receiving node determining from the two-way agreement whether the receiving node or the immediate neighborhood node is responsible for processing the message based on the ring identifier included in the message; and
an act of the receiving node directing the message to the next appropriate component to process the message based on the determination of message processing responsibility.
2 Assignments
0 Petitions
Accused Products
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.
117 Citations
20 Claims
-
1. At a receiving node in a federation infrastructure of a ring of nodes, the receiving node including a processor and system memory, the ring of nodes configured for bi-directional routing, the ring of nodes also including 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 identifying a node responsible for processing a message, the method comprising:
-
an act of the receiving node receiving a message including a ring identifier, the ring identifier indicating that the message is directed to a destination on the ring of nodes, the destination being on the ring of nodes somewhere between the receiving node and an immediate neighborhood node, the immediate neighborhood node selected from among;
the immediate predecessor neighbor node and the immediate successor neighborhood node;an act of the processor identifying a node, selected from among the receiving node and an immediate neighborhood node, that is responsible for processing the message based on the ring identifier included in the received message, including; an act of the receiving node referring to a two-way agreement cached at the receiving node, the two-way agreement previously agreed to between the receiving node and the immediate neighbor node subsequent to the receiving node and the immediate neighbor node detecting their locations relative to one another on the ring of nodes in response to a change in the configuration of the ring of nodes, the two-way agreement defining message processing responsibility between the receiving node and the immediate neighborhood node for ring identifiers on the ring of nodes between the receiving node and the immediate neighborhood node in accordance with configurable rules, caching the two-way agreement at the receiving node providing the receiving node with local knowledge of ring identifiers that are the responsibility of the immediate neighborhood node, the defined processing responsibility for ring identifiers in the cached two-way agreement having previously been split between the immediate predecessor neighbor node and the immediate successor neighborhood prior to the change in the configuration of the ring such that the receiving node is responsible for at least some ring identifiers that were previously the responsibility of the immediate predecessor neighbor node and at least some ring identifiers that were previously the responsibility of the immediate successor neighborhood; and an act of the receiving node determining from the two-way agreement whether the receiving node or the immediate neighborhood node is responsible for processing the message based on the ring identifier included in the message; and an act of the receiving node directing the message to the next appropriate component to process the message based on the determination of message processing responsibility. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. At a receiving node in a federation infrastructure of a ring of nodes, the receiving node including a processor and system memory, the ring of nodes configured for bi-directional routing, the ring of nodes also including an immediate predecessor neighborhood node to the receiving node on the ring of nodes, and an immediate successor neighborhood node to the receiving node on the ring of nodes, a method for identifying the node responsible for processing a message , the method comprising:
-
an act of the receiving node receiving a message including a ring identifier, the ring identifier indicating that the message is directed to a destination on the ring of nodes, the destination being on the ring of nodes somewhere between the immediate predecessor neighborhood node and the immediate successor neighborhood node; an act of the processor identifying a node, selected from among the receiving node, the immediate predecessor neighborhood node, and the immediate successor neighborhood node, that is responsible for processing the message based on the ring identifier included in the received message, including; an act of the receiving node referring to a first two-way agreement cached at the receiving node, the first two-way agreement previously agreed to between the receiving node and the immediate predecessor neighborhood node in response to a change in configuration of the rings of nodes, the first two-way agreement defining message processing responsibility between the receiving node and the immediate predecessor neighborhood node for ring identifiers on the ring of nodes between the receiving node and the immediate predecessor neighborhood node, caching the first two-way agreement at the receiving node providing the receiving node with knowledge of ring identifiers that are the responsibility of the immediate predecessor neighborhood node, the defined processing responsibility for ring identifiers in the first two-way agreement having previously been split between the immediate predecessor neighbor node and the immediate successor neighborhood prior to the change in the configuration of the ring such that the receiving node is responsible for at least some ring identifiers that were previously the responsibility of the immediate predecessor neighbor node; an act of the receiving node referring to a second two-way agreement cached at the receiving node, the second two-way agreement previously agreed to between the receiving node and the immediate successor neighborhood node, in response to a change in configuration of the rings of nodes, the second two-way agreement defining message processing responsibility between the receiving node and the immediate successor neighborhood node for ring identifiers on the ring of nodes between the receiving node and the immediate successor node, caching the second two-way agreement at the receiving node providing the receiving node with knowledge of ring identifiers that are the responsibility of the immediate successor neighborhood node, the defined processing responsibility for ring identifiers in the second two-way agreement having previously been split between the immediate predecessor neighbor node and the immediate successor neighborhood prior to the change in the configuration of the ring such that the receiving node is responsible for at least some ring identifiers that were previously the responsibility of the immediate successor neighbor node; an act of the receiving node determining from the first and second two-way agreements whether the receiving node, the immediate predecessor neighborhood node, or the immediate successor neighborhood node is responsible for processing the message based on the ring identifier included in the message; and an act of the receiving node directing the message to the next appropriate component to process the message based on the determination of message processing responsibility.
-
-
12. At a node in a federation infrastructure of a ring of nodes, the current node including a processor and system memory, the ring of nodes configured for bi-directional routing, the ring of nodes also including a current immediate predecessor neighbor node preceding the node on the ring of nodes, and a current immediate successor neighbor node succeeding the node on the ring of node, a method for formulating a two-way agreement between the node and an immediate neighborhood node that provides the node with local knowledge of ring identifiers that are the responsibility of the immediate neighborhood node, the method comprising:
-
an act of the processor at 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 one of the current immediate predecessor node and the current immediate successor node, the change resulting in a new immediate neighbor node replacing the at least one of the current immediate predecessor node and the current immediate successor node, the indication further indicative of a need to formulate a new two-way agreement dividing responsibility for ring identifiers on the ring of nodes between the node and the new immediate neighbor node; an act of the node and the new immediate neighbor node establishing a new two-agreement defining message processing responsibilities in accordance with configurable rules subsequent to the node and the immediate neighbor node detecting their locations relative to one another on the ring of nodes in response to the change in the configuration of the ring of nodes, including; an act of the current node and new immediate neighbor node agreeing with one another to a responsibility boundary between the current node and new immediate neighbor node for a range of ring identifiers between the current node and the immediate neighbor node, the responsibility boundary defining message processing responsibility for messages directed to ring identifiers in the range of ring identifiers, the defined processing responsibility for ring identifiers in the range of ring identifiers having previously been split between the immediate predecessor neighbor node and the immediate successor neighborhood prior to the change in the configuration of the ring of nodes; an act of the current node becoming responsible for at least some ring identifiers that were previously the responsibility of the immediate predecessor neighbor node and at least some ring identifiers that were previously the responsibility of the immediate successor neighborhood; an act of the current node and new immediate neighbor node agreeing that the node is to have responsibility for processing messages directed to ring identifiers between the current node and the responsibility boundary on the ring of nodes; and an act of act of the current node and new immediate neighbor node agreeing that the new immediate neighbor node is to have responsibility for processing messages directed to ring identifiers between the responsibility boundary and the new immediate neighbor node on the ring of nodes; and an act of the processor caching the new two-way agreement at the node, caching the new two-way agreement at the node providing the node with local knowledge of ring identifiers that are the responsibility of the new immediate neighborhood node. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification