Method and apparatus for a fault resilient collaborative media serving array

• US 20080091805A1
• Filed: 10/12/2006
• Published: 04/17/2008
• Est. Priority Date: 10/12/2006
• Status: Active Grant

• Current Assignee: Vecima Networks Incorporated
• Original Assignee: Concurrent Computer Corporation
• Inventors: Malaby, Stephen, Barkley, James
• Granted Patent: US 8,943,218 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04N 21/2182 involving memory arrays, e.g. RAID disk arrays RAID arrays per se G06F3/0689; use of parity to protect data in RAID systems G06F11/1008
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/26258 for generating a list of items to be played back in a given order, e.g. playlist, or scheduling item distribution according to such list retrieval of multimedia data based on playlists G06F16/40
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests

Abstract

Embodiments of the present invention provide methods, systems, and apparatuses for a fault resilient collaborative media serving array comprising a plurality of nodes. In one embodiment, the present invention provides a method for creating a fault resilient collaborative media serving array where the array nodes do not share memory, the serving of a content file is accomplished by the collaborative efforts of many nodes in the array, and where there is no fixed allocation of sessions to nodes.

Claims

1. A system for delivering content, the system comprising:

a. a plurality of nodes comprising at least a first node and a second node, wherein each node of the plurality of nodes comprises a memory and a processor;

b. content file that has been partitioned into an ordered list of parts comprising at least a first part and a second part, wherein the first part is stored in the memory of the first node and the second part is stored in the memory of the second node; and

c. a client device for receiving the parts over a network, wherein the first node and the second node are synchronized to send the first part and the second part to the client device in-order over the network.

2. The system of claim 1, further comprising a broker connected to the network, wherein the broker determines which of the plurality of nodes is the second node.

3. The system of claim 1, wherein the processor of the first node determines independently which of the plurality of nodes is the second node.

4. The system of claim 1, further comprising a token that is received by the second node over the network, wherein the token indicates that the second node should send the second part to the user over the network.

5. The system of claim 4, further comprising a broker connected to the network, wherein the broker sends the token to the second node.

6. The system of claim 4, wherein the token is sent by the first node.

7. The system of claim 1, wherein the processor of the second node uses a common time reference to determine when to send the second part to the user over the network.

8. The system of claim 1, wherein client device plays the parts in the order that they are received.

9. The system of claim 8, wherein the client device comprises a buffer.

10. The system of claim 1, wherein the memory of the first node and the memory of the second node are separate.

11. The system of claim 10, wherein the memory of the first node and the memory of the second node comprise random access memory.

12. The system of claim 1, wherein at least one of the first part and the second part further comprise trick content for implementing track mode playback comprising at least one of fast forward or rewind.

13. The system of claim 1, wherein at least one of the first node and the second node further comprises a stream pump for sending parts in-order to the client device over the network.

14. The system of claim 1, wherein the processor of the first node uses seed information to independently determine which of the plurality of nodes is the second node, wherein seed information includes at least one of the number of nodes that contain parts of the content file, metadata describing the content file, or a common time reference.

15. A node for delivering content to a user, wherein the content is partitioned into an ordered list of parts with one or more parts allocated to each of a plurality of nodes so that the user can play the parts in the order that they are received, the node comprising:

a. a stream pump for sending one or more parts in-order to the user over a downstream network;

b. a processor for determining when the node should send the one or more over the downstream network;

c. a first communications interface for connecting the stream pump to the downstream network; and

d. a data retriever for receiving the one or more parts allocated to the node.

16. The node of claim 15, further comprising:

a. a command receiver for receiving control commands from the user, control commands including at least one of start, stop, pause, write, and delete; and

b. a command sender for sending control commands to one or more of the plurality of nodes.

17. The node of claim 15, further comprising:

a. a fault detector for detecting a fault in one or more of the plurality of nodes; and

b. a fault transmitter for propagating a fault condition to one or more of the plurality of nodes.

18. The node of claim 15, wherein the stream pump comprises:

a. a firing queue decoupling the receipt of tokens from the stream pump; and

b. a buffer for storing the one or more parts allocated to the node.

19. The node of claim 15, further comprising:

a. a token receiver for receiving a token which indicates that the node should send its one or more parts to the user;

b. a token sender for sending a token to a successor node in the plurality of nodes, the token indicating that the successor node should send its one or more parts to the user; and

c. a second communications interface for sending and receiving one or more tokens.

20. The node of claim 15, wherein the processor uses a common time reference to determine when the node should send the one or more parts over the downstream network.

21. The node of claim 15, wherein the processor determines when the node should send the one or more parts over the downstream network based on a token received by the node.

22. The node of claim 15, wherein the processor independently determines a second node from among the plurality of nodes, such that the second node will send a next part occurring after the one or more parts in the ordered list of parts.

23. A method for delivering content over a network, comprising the steps of:

a. partitioning the content into an ordered list of parts;

b. allocating the parts among a plurality of nodes;

c. synchronizing the plurality of nodes so that the parts can be sent in-order from the plurality of nodes to the user; and

d. delivering the content to the user by sending the parts in-order from the plurality of nodes over the network to the user.

24. The method of claim 23, wherein the allocating step comprises allocating the parts among a plurality of nodes before the delivering step.

25. The method of claim 23, wherein the allocating step comprises allocating the parts among a plurality of nodes dynamically during delivery of the content to the user.

26. The method of claim 23, wherein the user is not aware that the content will be delivered from a plurality of nodes.

27. The method of claim 23, wherein the nodes do not share memory.

28. The method of claim 27, wherein memory comprises random access memory.

29. The method of claim 23, wherein the user is participating in an on-demand session, the on-demand session being one of content-on-demand, movie-on-demand, video-on-demand, subscription video-on-demand, free-on-demand, or network-based digital video recording session.

30. The method of claim 23, wherein the content is a single content file.

31. The method of claim 23, wherein the content includes multimedia data.

32. The method of claim 23, wherein at least one part comprises multimedia content and trick content associated with the multimedia content.

33. The method of claim 32, wherein the trick content is used to implement trick mode playback comprising at least one of fast forward or rewind.

34. The method of claim 23, wherein the allocating step comprises allocating the parts among a plurality of nodes according to a deterministic algorithm.

35. The method of claim 34, wherein the algorithm is a round-robin algorithm.

36. The method of claim 23, wherein the allocating step comprises allocating the parts among a plurality of nodes according to a non-deterministic algorithm.

37. The method of claim 36, wherein the algorithm randomly allocates parts among the plurality of nodes.

38. The method of claim 23, wherein the synchronizing step comprises synchronizing the plurality of nodes so that the parts can be sent in-order from the plurality of nodes to the user by passing a token among the plurality of nodes, the token indicating when a receiving node should send its one or more parts to the user.

39. The method of claim 23, wherein the delivering step comprises delivering the content to the user by sending the parts in-order from a stream pump over the network to the user.

40. The method of claim 23, wherein the synchronizing step comprises synchronizing the plurality of nodes using a common time reference so that the parts can be sent in-order from the plurality of nodes to the user.

41. A method for sending content to a user, comprising the steps of:

a. partitioning the content into an ordered list of parts comprising a first part and a second part;

b. allocating the first part to a first node;

c. allocating the second part to a second node;

d. sending the first part from the first node to the user;

e. determining which of a plurality of nodes is the second node;

f. indicating to the second node that it should send the second part to the user; and

g. sending the second part from the second node to the user.

42. The method of claim 41, wherein the determining step comprises determining by a broker which of a plurality of nodes is the second node.

43. The method of claim 42, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by sending a token from the broker to the second node.

44. The method of claim 42, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by using a common time reference.

45. The method of claim 41, wherein the determining step comprises determining independently by the first node which of a plurality of nodes is the second node.

46. The method of claim 45, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by receiving a token at the second node.

47. The method of claim 45, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by using a common time reference.

48. The method of claim 41, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by receiving a token at the second node.

49. The method of claim 48, wherein the determining step comprises determining by a broker which of a plurality of nodes is the second node.

50. The method of claim 48, wherein the determining step comprises determining independently by the first node which of a plurality of nodes is the second node.

51. The method of claim 41, wherein the indicating step comprises indicating to the second node that it should send the second part to the user by using a common time reference.

52. The method of claim 51, wherein the determining step comprises determining by a broker which of a plurality of nodes is the second node.

53. The method of claim 51, wherein the determining step comprises determining independently by the first node which of a plurality of nodes is the second node.

54. The method of claim 45, wherein the determining step comprises determining independently by the first node which of a plurality of nodes is the second node using seed information received by the first node.

55. The method of claim 54, wherein the seed information includes at least one of the number of nodes which contain parts of the content, metadata describing the content, or a common time reference.

56. The method of claim 41, wherein nodes do not share memory.

57. The method of claim 56, wherein memory comprises random access memory.

58. The method of claim 41, wherein the user is participating in an on-demand session, the on-demand session being one of content-on-demand, movie-on-demand, video-on-demand, subscription video-on-demand, free-on-demand, or network-based digital video recording session.

59. The method of claim 41, wherein the content includes multimedia data which is at least one of MPEG, MPEG-2, or MPEG-4 data.

60. The method of claim 59, wherein at least one part comprises at least one Group of Pictures.

61. The method of claim 41, wherein at least one part comprises multimedia content and trick content associated with the multimedia content, and wherein the trick content is used to implement trick mode playback comprising at least one of fast forward or rewind.

62. A method for recovering from fault in a content serving array comprising at least a first node, a second node, and a third node, the method comprising the steps of:

a. partitioning the content into an ordered list of parts comprising at least a first part and a second part;

b. allocating the first part to the first node;

c. allocating the second part to the second node;

d. indicating to the first node that it should send the first part to a client device;

e. failing to receive by the second node an indication that the first node has sent the first part to the client device;

f. indicating to the third node that it should send the first part to the client device;

g. sending by the third node the first part to the client device; and

h. sending by the second node the second part to the client device.

63. The method of claim 62, wherein the indicating to the first node step comprises indicating to the first node that it should send the first part to the user by sending a token to the first node.

64. The method of claim 62, wherein the indicating to the first node step comprises indicating to the first node that it should send the first part to the user by using a common time reference.

65. The method of claim 62, wherein the failing step comprises failing to receive at the second node, within a predetermined time, a token indicating that the first node has sent the first part to the client device.

66. The method of claim 62, wherein the indicating to the third node step comprises indicating to the third node that it should send the first part to the user by sending a token to the third node.

67. The method of claim 62, wherein the indicating to the third node step comprises indicating to the third node that it should send the first part to the user by using a common time reference.

68. The method of claim 62, further comprising the step of determining independently by the second node that the third node should send the first part to the client device.

69. The method of claim 62, further comprising the step of determining by a broker that the third node should send the first part to the client device.

70. The method of claim 62, wherein the third node is the second node.

71. The method of claim 62, further comprising the step of reallocating the first part to the third node.

72. The method of claim 62, wherein the client device buffers at least some of the received content.

73. The method of claim 62, wherein the client device presents received parts in the order that they are received.

74. The method of claim 62, wherein the client device is not aware that the content is being delivered from more than one node.

75. The method of claim 62, wherein the nodes do not share memory.

76. The method of claim 62, wherein at least one part includes trick content for implementing trick mode playback.

77. The method of claim 62, further comprising the step of allocating the parts among the first node, the second node, and the third node using a deterministic algorithm.

78. The method of claim 62, further comprising the step of allocating the parts among the first node, the second node, and the third node using a non-deterministic algorithm.