Resource reservation protocol over unreliable packet transport

• US 9,185,160 B2
• Filed: 02/12/2007
• Issued: 11/10/2015
• Est. Priority Date: 02/12/2007
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Wu, Yuguang, Zhou, Charles J.
• Primary Examiner(s): BIAGINI, CHRISTOPHER D
• Application Number:
  US11/673,915
• Publication Number:
  US 20080195719A1
• Time in Patent Office: 3,193 Days
• Field of Search: 709/214, 709/226
• US Class Current: 1/1
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A system and method for allocating physical memory in a distributed, shared memory system and for maintaining interaction with the memory using a reservation protocol is disclosed. In various embodiments, a processor node may broadcast a memory request message to a first subset of nodes connected to it via a communication network. If none of these nodes is able to satisfy the request, the processor node may broadcast the request message to additional subsets of nodes until a positive response is received. The reservation protocol may include a four-way handshake between the requesting processor node and a memory node that can fulfill the request. The method may include creation of a reservation structure on the requesting processor and on one or more responding memory nodes. The reservation protocol may facilitate the use of a proximity-based search methodology for memory allocation in a system having an unreliable underlying transport layer.

Claims

1. A system, comprising:

a processor node comprising a processor and a network interface;

a plurality of memory nodes, wherein each memory node comprises a memory and a network interface;

a communication network configured to interconnect said processor node and said plurality of memory nodes via said network interfaces according to a network topology, wherein each of said memory nodes is removed from said processor node by a respective number of network hops according to said network topology;

wherein said processor node is configured to;

broadcast, over the communication network, a packet comprising a memory request message to a subset of said plurality of memory nodes comprising two or more memory nodes, wherein the memory request message comprises a unique identifier of a given memory request and a requested memory size;

receive, over the communication network, a reservation acknowledgment message from one or more of the memory nodes in the subset of memory nodes;

send, over the communication network, a confirmation message comprising the unique identifier to a particular one of the memory nodes in the subset of memory nodes from which a reservation acknowledgment message was received;

receive, over the communication network, a commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request; and

access memory on the particular one of the memory nodes in response to receiving the commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request.

2. The system of claim 1, wherein the processor node is further configured to create a reservation structure for the given memory request comprising the unique identifier and a timeout value, and wherein in response to a timer reaching the timeout value before a reply message is received in response to a given message being sent by the processor node, the processor node is further configured to re-send the given message.

3. The system of claim 1, wherein the particular one of the memory nodes is configured to reserve a portion of memory at least as large as the requested memory size and to send a reservation acknowledgement message comprising the unique identifier to the processor node in response to receiving the given memory request and determining that the given memory request can be satisfied by the particular one of the memory nodes.

4. The system of claim 1, wherein the particular one of the memory nodes is further configured to create a reservation structure for the given memory request comprising the unique identifier and a timeout value, and wherein in response to a timer reaching the timeout value before a reply message is received in response to a given message being sent by the particular one of the memory nodes, the particular one of the memory nodes is further configured to re-send the given message.

5. The system of claim 1, wherein the particular one of the memory nodes is further configured to send a commit message comprising the unique identifier to the processor node in response to receiving the confirmation message from the processor node.

6. The system of claim 1, wherein the particular one of the memory nodes is further configured to send a read acknowledgement message comprising the unique identifier to the processor node in response to receiving a read request message comprising the unique identifier from the processor node subsequent to receiving the confirmation message, and wherein the particular one of the memory nodes is further configured to send a write acknowledgement message comprising the unique identifier to the processor node in response to receiving a write request message comprising the unique identifier from the processor node subsequent to receiving the confirmation message.

7. The system of claim 1, wherein the processor node is further configured to send a reject message comprising the unique identifier to the particular one of the memory nodes to indicate that it no longer requires access to the memory allocated for the given memory request.

8. The system of claim 7, wherein the particular one of the memory nodes is further configured to free the memory allocated for the given memory request and to send a reject acknowledgement message comprising the unique identifier to the processor node in response to receiving the reject message from the processor node.

9. The system of claim 8, wherein the processor node is further configured to send a reject confirmation message comprising the unique identifier to the particular one of the memory nodes in response to receiving the reject acknowledgement message from the particular one of the memory nodes.

10. The system of claim 1,

wherein each memory node of said subset is removed from said processor node by no more than a given number of network hops;

and

wherein in response to failing to receive a reservation acknowledgement message from any memory node of said subset indicating that it can satisfy the given memory request, the processor node is further configured to increase said given number of network hops and to broadcast the memory request message to a second subset of said plurality of memory nodes, wherein each memory node of said second subset is removed from said processor node by no more than said increased given number of network hops.

11. The system of claim 10, wherein in response to failing to receive a reservation acknowledgement message from any memory node of said second subset indicating that it can satisfy the given memory request, the processor node is further configured to continue to increase said given number of network hops and to broadcast the memory request message to a corresponding subset of said plurality of memory nodes, wherein each memory node of said corresponding subset is removed from said processor node by no more than said increased given number of network hops, until at least one of the following occurs:

one or more of said plurality of memory nodes indicates that it can satisfy the given memory request in response to receiving the given memory request, said processor node has broadcast the memory request message to each of said plurality of memory nodes, or a time-out condition has been met.

12. A method, comprising:

broadcasting, by a processor node, over a communication network, a packet comprising a memory request message to a plurality of memory nodes, wherein the memory request message comprises a unique identifier of a given memory request and a requested memory size, and wherein said plurality of memory nodes and said processor node are interconnected via the communication network according to a network topology;

receiving, by the processor node, over the communication network, a reservation acknowledgment message from one or more of the plurality of memory nodes;

sending, by the processor node, over the communication network, a confirmation message to a particular one of the plurality of memory nodes from which a reservation acknowledgment message was received;

receiving, by the processor node, over the communication network, a commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request; and

accessing, by the processor node, memory on the particular one of the memory nodes in response to receiving the commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request.

13. The method of claim 12, further comprising:

creating, by the processor node, a reservation structure for the given memory request comprising the unique identifier and a timeout value; and

re-sending, by the processor nod, a given message in response to a timer reaching the timeout value before a reply message is received in response to the given message being sent by the processor node.

14. The method of claim 12, further comprising:

reserving, by the particular one of the memory nodes, a portion of memory at least as large as the requested memory size; and

sending, by the particular one of the memory nodes, a reservation acknowledgement message comprising the unique identifier to the processor node in response to receiving the given memory request and determining that the given memory request can be satisfied by the particular one of the memory nodes.

15. The method of claim 12, further comprising:

creating, by the particular one of the memory nodes, a reservation structure for the given memory request comprising the unique identifier and a timeout value, wherein the timeout value is dependent on a time-to-live value included in the memory request message; and

re-sending, by the particular one of the memory nodes, a given message in response to a timer reaching the timeout value before a reply message is received in response to the given message being sent by the particular one of the memory nodes.

16. The method of claim 12, further comprising:

sending, by the processor node, a reject message comprising the unique identifier to the particular one of the memory nodes to indicate that it no longer requires access to the memory allocated for the given memory request;

freeing, by the particular one of the memory nodes, the memory allocated for the given memory request in response to receiving the reject message from the processor node;

sending, by the particular one of the memory nodes, a reject acknowledgement message comprising the unique identifier to the processor node in response to receiving the reject message from the processor node; and

sending, by the processor nod, a reject confirmation message comprising the unique identifier to the particular one of the memory nodes in response to receiving the reject acknowledgement message from the particular one of the memory nodes.

17. A processor node, comprising:

an input/output interface comprising electronic circuitry that is configured for communicating with a communication network, wherein said communication network is configured to interconnect a plurality of memory nodes according to a network topology; and

execution logic comprising electronic circuitry that is configured to;

broadcast, over the communication network, a packet comprising a memory request message to the plurality of memory nodes, wherein the memory request message comprises a unique identifier of a given memory request and a requested memory size;

receive, over the communication network, a reservation acknowledgment message from one or more of the memory nodes;

send, over the communication network, a confirmation message to a particular one of the memory nodes from which a reservation acknowledgment message was received;

receive, over the communication network, a commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request; and

access memory on the particular one of the memory nodes in response to receiving the commit message from the particular one of the memory nodes indicating that the memory has been allocated for the given memory request.

18. The processor node of claim 17, wherein the execution logic is further configured to:

send a reject message comprising the unique identifier to the particular one of the memory nodes to indicate that it no longer requires access to the memory allocated for the given memory request; and

send a reject confirmation message comprising the unique identifier to the particular one of the memory nodes in response to receiving a reject acknowledgement message comprising the unique identifier from the particular one of the memory nodes.

19. A memory node, comprising:

a memory;

an input/output interface configured for communicating with a communication network, wherein said communication network is configured to interconnect a processor node and a plurality of memory nodes according to a network topology; and

execution logic configured to;

receive from the processor node, over the communication network, a packet comprising a memory request message, wherein the packet comprises a transaction code indicating that the packet type is a broadcast packet, and wherein the memory request message comprises a unique identifier of a given memory request and a requested memory size;

in response to receiving the given memory request and determining that the given memory request can be satisfied by the memory node;

reserve a portion of memory at least as large as the requested memory size; and

send, over the communication network, a reservation acknowledgement message comprising the unique identifier to the processor node;

receive, over the communication network, a confirmation message from the processor node; and

send to the processor node, over the communication network, a commit message indicating that the memory has been allocated for the given memory request and comprising the unique identifier in response to receiving the confirmation message from the processor node.

20. The memory node of claim 19, wherein the execution logic is further configured to:

free the memory allocated for the given memory request and send a reject acknowledgement message comprising the unique identifier to the processor node in response to receiving a reject message from the processor node.