Distributed kernel operating system

• US 7,840,682 B2
• Filed: 06/03/2005
• Issued: 11/23/2010
• Est. Priority Date: 06/03/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Company (Blackberry Limited)
• Inventors: Boyd, Andrew
• Primary Examiner(s): JEAN GILLES, JUDE
• Application Number:
  US11/145,293
• Publication Number:
  US 20060277285A1
• Time in Patent Office: 1,999 Days
• Field of Search: 709/227, 709/203, 709/223, 709/246, 709/213, 709/214
• US Class Current: 709/227
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066

Abstract

An improved distributed operating system over a network of computer systems is described. Existing distributed operating systems have transmission performance limitations dictated by their inability to (1) reliably handle transient communication failures and rapid node reboots, (2) provide a transmission protocol that adapts to link reliability, and (3) allow transmissions to occur over an arbitrary combinations of communication links. The systems and methods described herein solve these problems by providing a reliable node-to-node session protocol that offers high performance message delivery and multi-interface management and support. This is done by transmitting all data between two nodes of the operating system over a single connection that may dynamically exploit multiple interfaces between the nodes.

Claims

1. A method for establishing a connection between nodes of a distributed operating system comprising:

generating a transmission request by a local node that includes a local thread for a remote node;

establish, in response to receiving a transmission request from the local thread, a node-to-node connection with the local node; and

transmitting an initial packet by the local node to the remote node, the initial packet including

a local node descriptor indicative of the remote node and

a local connection identifier;

receiving the initial packet by the remote node;

generating, by the remote node, a receive connection structure associated with the local node descriptor;

transmitting, in response to the receiving of the initial packet, a confirmation packet to the local node to establish the transmission connection, the confirmation packet including

the local node descriptor,

the local connection identifier,

a remote node descriptor indicative of the local node, and

a remote connection identifier; and

receiving, by the local node, the confirmation packet.

2. The method of claim 1, wherein the local connection identifier and the remote connection identifier comprise monotonically increasing counters.

3. The method of claim 1, further comprising the local node performing the steps of:

generating a plurality of transmit requests for the remote node; and

servicing the plurality of transmission requests in order.

4. The method of claim 1 further comprising the local node performing the step of:

generating a transmit connection structure capable of storing the local node descriptor and the local connection identifier.

5. The method of claim 4, further comprising:

generating a queue of the plurality of transmission requests by the local node; and

storing the queue of transmission requests in the transmit connection structure.

6. The method of claim 1 further comprising polling the remote node after the expiration of a threshold period of time.

7. The method of claim 6 further comprising destroying the transmit connection if no response to the polling is received.

8. The method of claim 1, where the receive connection structure is capable of storing the local node descriptor, the local connection identifier, the remote node descriptor, and the remote connection identifier.

9. A distributed operating system embodied on a computer readable medium comprising:

a local node including a local thread running on a local processor, the local node operable to pass messages and receive messages;

a remote node in communication with the local node via a plurality of networks, the remote node including a remote thread running on a remote processor, the remote node operable to pass messages and receive messages;

where the local node is further operable to;

establish, in response to receiving a transmission request from the local thread, a node-to-node connection with the remote node, the node-to-node-connection associated with a local connection identifier and a remote connection identifier, the local connection identifier associated with the local node and the remote connection identifier associated with the remote node;

manage message passing from the local node to the remote node over the plurality of network interfaces, and

receive messages from the remote node and forward the messages to the local thread,

where the remote node is further operable to;

establish the node-to-node connection with the local node, and

receive messages from the local node and forward the messages to the remote thread.

10. The operating system of claim 9, wherein the local connection identifier and the remote connection identifier comprise monotonically increasing counters.

11. The operating system of claim 9, where the local node is further operable to:

generate a plurality of transmit requests for the remote node; and

service the plurality of transmission requests in order.

12. The operating system of claim 9, where the local node is further operable to:

generate a transmit connection structure capable of storing the local connection identifier.

13. The operating system of claim 12, where the local node is further operable to:

generate a queue of the plurality of transmission requests; and

store the queue of transmission requests in the transmit connection structure.

14. The operating system of claim 9, where the local node is further operable to poll the remote node after the expiration of a threshold period of time.

15. The operating system of claim 14, where the local node is further operable to destroy the node-to-node connection if no response to the polling is received.

16. The operating system of claim 9, where the remote node is further operable to generate a receive connection structure capable of storing the local connection identifier and the remote connection identifier.

17. The operating system of claim 9, where the node-to-node connection is established by transmitting an initial packet from the local node to the remote node, the initial packets including the local connection identifier.

18. The operating system of claim 17, where the node-to-node connection is established by transmitting, in response to the initial packet, a confirmation packet from the remote node to the local node, the confirmation packet including the remote connection identifier.

19. A distributed operating system embodied on a non-transitory computer readable medium comprising:

a local node including a local thread running on a local processor, the local node operable to pass messages from the local node and receive messages at the local node;

a remote node in communication with the local node via a plurality of network interfaces, the remote node including a remote thread running on a remote processor, the remote node operable to pass messages from the remote node and receive messages at the remote node;

where the local node is further operable to;

establish a node-to-node connection with the remote node in response to receiving a transmission request from the local thread;

manage message passing from the local node to the remote node over the plurality of network interfaces, and

receive messages from the remote node and forward the messages to the local thread,

where the remote node is further operable to;

establish the node-to-node connection with the local node, and

receive messages from the local node and forward the messages to the remote thread;

where the node-to-node connection is established by;

generating, by a local node, a transmission request for a remote node and transmitting, by the local node, an initial packet to the remote node, the initial packet including

a local node descriptor indicative of the remote node and

a local connection identifier;

receiving, by a remote node, the initial packet;

generating, by the remote node, a receive connection structure associated with the local node descriptor;

transmitting, by the remote node and in response to the receiving of the initial packet, a confirmation packet to the local node to establish the transmission connection, the confirmation packet including

the local node descriptor,

the local connection identifier,

a remote node descriptor indicative of the local node, and

a remote connection identifier; and

receiving, by the local node, the confirmation packet.

20. The operating system of claim 19, where the local connection identifier and the remote connection identifier comprise monotonically increasing counters.

21. The method of claim 19, where the local node is further operable to:

generate a plurality of transmit requests for the remote node; and

service the plurality of transmission requests in order.

22. The operating system of claim 19, where the local node is further operable to:

generate a transmit connection structure capable of storing the local node descriptor and the local connection identifier.

23. The operating system of claim 22, where the local node is further operable to:

generate a queue of the plurality of transmission requests by the local node; and

store the queue of transmission requests in the transmit connection structure.

24. The operating system of claim 19, where the local node is further operable to:

poll the remote node after the expiration of a threshold period of time.

25. The method of claim 24 where the local node is further operable to:

destroy the transmit connection if no response to the polling is received.

26. The operating system of claim 19, where the receive connection structure is capable of storing the local node descriptor, the local connection identifier, the remote node descriptor, and the remote connection identifier.

27. A method of managing communications between nodes of a distributed message-passing operating system, the method comprising:

generating, at a local node that includes a local thread, a transmit request to transmit data to a remote node, the local node and the remote node capable of communicating via both a first interface and a second interface;

establishing in response to receiving the transmission request from the local thread, a connection between the local node and a remote node, the connection associated with a local connection identifier and a remote connection identifier, the local connection identifier associated with the local node and the remote connection identifier associated with the remote node;

transmitting data over the connection;

transmitting, by the local node and after transmitting the data, a poll packet to the remote node via both the first interface and the second interface, the poll packet including the local connection identifier and the remote connection identifier; and

determining if the first and second interfaces are operational based on responses to the poll packets are received.

28. The method of claim 27, wherein the local connection identifier and the remote connection identifier comprise monotonically increasing counters.

29. The method of claim 27, further comprising the local node performing the steps of:

generating a plurality of transmit requests for the remote node; and

servicing the plurality of transmission requests in order.

30. The method of claim 27 further comprising the local node performing the step of:

generating a transmit connection structure capable of storing the local node descriptor and the local connection identifier.

31. The method of claim 30, further comprising:

generating a queue of the plurality of transmission requests by the local node; and

storing the queue of transmission requests in the transmit connection structure.

32. The method of claim 27 further comprising polling the remote node after the expiration of a threshold period of time.

33. The method of claim 32 further comprising destroying the transmit connection if no response to the polling is received.

34. The method of claim 27, where the receive connection structure is capable of storing the local node descriptor, the local connection identifier, the remote node descriptor, and the remote connection identifier.