Methods and apparatus for managing data distribution in a network

• US 7,171,491 B1
• Filed: 05/24/2001
• Issued: 01/30/2007
• Est. Priority Date: 01/25/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: O'Toole, James, Jannotti, John H.
• Primary Examiner(s): Burgess; Glenton B.
• Assistant Examiner(s): Barqadle; Yasin M.
• Application Number:
  US09/865,161
• Time in Patent Office: 2,077 Days
• Field of Search: 709/206, 709/213, 709/214, 709216-219, 709225-227, 709/232, 709/238, 709244-245, 707/10
• US Class Current: 709/244
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

The invention is directed to techniques for managing data distribution in a network. A source or root node distributes data (e.g., video data) throughout a network of nodes by distributing data from parent to child through a tree of nodes. The nodes distribute the data through the network concurrently in a real-time manner, but retain copies of the data in nonvolatile data storage on each node. Thus, the data remains accessible on each node so that the data is available after the real-time distribution of the data. After the real-time distribution of the data, a new node can attach to any of the nodes currently in the network as a child of that node, and then the new node can request a copy of the data from the data storage of that parent node.

Claims

1. In a transferring node, a method for distributing data in an overlay network based on logical relationships, said overlay network including a hierarchical network of nodes, said overlay network implemented as an abstraction on top of an existing network based on other connections, the method comprising the steps of:

receiving at the transferring node a collection of data from a provider node in the hierarchical network of nodes;

transferring a copy of the collection of data to a child node of the transferring node in the hierarchical network of nodes in response to the step of receiving the collection of data; and

storing the collection of data in a data storage in the transferring node after completing the step of transferring the copy of the collection of data;

wherein the collection of data represents content distributed as a stream of packets to the hierarchical network from a source node, and wherein;

the step of receiving the collection of data comprises receiving the stream of packets in a buffer;

the step of transferring the copy of the collection of data comprises propagating the stream of packets from the buffer to descendent nodes of the transferring node for access by a first client making a first request for the collection of data from the descendent node; and

the step of storing the collection of data comprises transferring the stream of packets from the buffer to the data storage in the transferring node in a manner enabling access to the collection of data by a second client making a second request for the collection of data.

2. The method of claim 1, wherein the child node is one of a plurality of child nodes, and the step of transferring the copy of the collection of data comprises transferring copies of the collection of data to each of the plurality of child nodes, if each child node is available over the hierarchical network.

3. The method of claim 1, wherein the step of transferring the collection of data comprises receiving a verification from the child node that the copy of the collection of data received by the child node is a complete copy of the collection of data.

4. The method of claim 1, wherein the collection of data comprises a plurality of packets of data and the step of transferring the copy of the collection of data comprises:

(i) receiving an indication from the child node that the copy of the collection of data received by the child node is incomplete; and

(ii) transferring copies of at least one packet of data to the child node to complete the copy of the collection of data received by the child node.

5. The method of claim 1, wherein the step of transferring the copy of the collection of data comprises transferring an additional copy of the collection of data to an additional child node of the transferring node based on a request from the additional child node.

6. The method of claim 1, wherein the step of transferring the copy of the collection of data comprises transferring the copy of the collection of data between the provider node and the child node through the transferring node in a delayed timing mode.

7. The method of claim 1, wherein the step of storing the collection of data comprises retaining the collection of data after confirming the receipt of the copy of the collection of data by the child node.

8. The method of claim 1, wherein the step of receiving the collection of data comprises a step of providing an acknowledgment indicating that the collection of data is complete and the step of transferring the collection of data is performed after the step of providing the acknowledgment.

9. The method of claim 1, further comprising the step of:

maintaining a connection among the network of nodes in order to transfer the collection of data.

10. A method according to claim 1, wherein the provider node is a first provider node from which the transfer node receives the collection of data, and further comprising the steps, performed in the event that the provider node becomes unavailable during the transfer of the copy of the collection of data to the child node, of:

contacting another node of the overlay network to obtain the collection of data; and

continuing to transfer the collection of data to the child node based on copying the collection of data from the other node.

11. A method according to claim 10, wherein the other node is a grandparent node of the transferring node.

24. The method of claim 1 further comprising allowing access to the collection of data in the data storage at the transferring node at a later time by at least one of the child node and another node.

25. The method of claim 1 wherein the step of receiving the collection of data from the provider node includes the step of obtaining a multicast video stream and buffering a version of the multicast video stream completely in volatile memory;

wherein the step of transferring the copy of the collection of data includes the step of reading the buffered version of the multicast video stream from the volatile memory and sending that buffered version of the multicast video stream to the child node;

wherein the step of storing the collection of data in the data storage includes the step of, in response to completing transfer of the buffered version of the multicast video stream to the child node, saving a copy of the buffered version of the multicast video stream in non-volatile memory; and

wherein the method further comprises the steps of (i) acquiring a request for the data from a requesting node at a later time, (ii) retrieving the saved copy of the buffered version of the multicast video stream from the non-volatile memory, and (iii) sending the saved copy to the requesting node.

29. The transferring node of claim 1 wherein said hierarchical network of nodes comprise a distribution tree.

30. The transferring node of claim 29 wherein said distribution tree is rooted at a source node, said source node comprising said transferring node.

12. A computer system for distributing data in an overlay network based on logical relationships, said overlay network including an hierarchical network of nodes, said overlay network implemented as a network abstraction on top off an existing network based on other connections, the computer system comprising:

a memory;

a data storage;

a network interface in communication with the memory and the data storage; and

a processor in communication with the memory, the data storage, and the network interface,

wherein the memory is encoded with logic instructions for a data manager application that, when performed on the processor, cause the processor to form a data manager that manages the distribution of data in the hierarchical network by performing operations of;

receiving a collection of data at a transferring node from a provider node in the hierarchical network of nodes;

transferring a copy of the collection of data to a child node of the transferring node in the hierarchical network of nodes in response to the step of receiving the collection of data; and

storing the collection of data in a data storage at the transferring node after completing the transferring of the copy of the collection of data;

and further comprising a buffer;

and wherein the collection of data represents content distributed a stream of packets to the hierarchical network from a source node and the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform operations of;

receiving the stream of packets in the buffer;

propagating the stream of packets from the buffer to descendent nodes of the transferring node for access by a first client making a first request for the collection of data from the descendent node; and

transferring the stream of packets from the buffer to the data storage in the transferring node in a manner enabling access to the collection of data by a second client making a second request for the collection of data.

13. The computer system of claim 12, wherein the child node is one of a plurality of child nodes, and the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of transferring copies of the collection of data to each of the plurality of child nodes, if each child node is available over the hierarchical network.

14. The computer system of claim 12, wherein the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of receiving a verification from the child node that the copy of the collection of data received by the child node is a complete copy of the collection of data.

15. The computer system of claim 12, wherein the collection of data comprises a plurality of packets of data and the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform operations of:

(i) receiving an indication from the child node that the copy of the collection of data received by the child node is incomplete; and

(ii) transferring copies of at least one packet of data to the child node to complete the copy of the collection of data received by the child node.

16. The computer system of claim 12, wherein the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of transferring an additional copy of the collection of data to an additional child node of the transferring node based on a request from the additional child node.

17. The computer system of claim 12, wherein the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of transferring the copy of the collection of data between the provider node and the child node through the transferring node in a delayed timing mode.

18. The computer system of claim 12, wherein the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of retaining the collection of data after confirming the receipt of the copy of the collection of data by the child node.

19. The computer system of claim 12, wherein the logic instructions for the data manager application comprise further logic instructions, that, when performed on the processor, cause the data manager to perform an operation of transferring the collection of data after providing an acknowledgment indicating that the collection of data is complete.

20. A computer system according to claim 12, wherein the provider node is a first provider node from which the transfer node receives the collection of data, and wherein the logic instructions for the data manager application comprise further logic instructions that, when performed on the processor in the event that the provider node becomes unavailable during the transfer of the copy of the collection of data to the child node, cause the data manager to perform operations of:

contacting another node of the overlay network to obtain the collection of data; and

continuing to transfer the collection of data to the child node based on copying the collection of data from the other node.

21. A computer system according to claim 20, wherein the other node is a grandparent node of the transferring node.

26. The computer system of claim 12 wherein the memory is encoded with logic instructions for a data manager application that, when performed on the processor, cause the processor to form a data manager that manages the distribution of data in the hierarchical network by performing operations of:

allowing access to the collection of data in the data storage at the transferring node at a later time by at least one of the child node and another node.

27. The computer system of claim 12 wherein the memory is encoded with logic instructions for a data manager application that, when performed on the processor, cause the processor to form a data manager that manages the distribution of data in the hierarchical network by performing operations of:

wherein the step of receiving the collection of data from the provider node includes the step of obtaining a multicast video stream and buffering a version of the multicast video stream completely in volatile memory;

wherein the step of transferring the copy of the collection of data includes the step of reading the buffered version of the multicast video stream from the volatile memory and sending that buffered version of the multicast video stream to the child node;

wherein the step of storing the collection of data in the data storage includes the step of, in response to completing transfer of the buffered version of the multicast video stream to the child node, saving a copy of the buffered version of the multicast video stream in non-volatile memory; and

wherein the method further comprises the steps of (i) acquiring a request for the data from a requesting node at a later time, (ii) retrieving the saved copy of the buffered version of the multicast video stream from the non-volatile memory, and (iii) sending the saved copy to the requesting node.

31. The computer system of claim 12 wherein said hierarchical network of nodes comprise a distribution tree.

32. The computer system of claim 31 wherein said distribution tree is rooted at a source node, said source node comprising said transferring node.

22. A computer program product that includes a computer readable medium having instructions stored thereon for distributing data in an overlay network based on logical relationships, said overlay network including an hierarchical network, the overlay network implemented as a network abstraction on top of an existing network based on other connections, such that the instructions, when carried out by a computer, cause the computer to perform steps of:

receiving a collection of data at a transferring node from a provider node in the hierarchical network of nodes;

transferring a copy of the collection of data to a child node of the transferring node in the hierarchical network of nodes in response to the step of receiving the collection of data; and

storing the collection of data in a data storage at the transferring node after completing the step of transferring the copy of the collection of data

wherein the collection of data represents content distributed as a stream of packets to the hierarchical network from a source node, and wherein;

the step of receiving the collection of data comprises receiving the stream of packets in a buffer;

the step of transferring the copy of the collection of data comprises propagating the stream of packets from the buffer to descendent nodes of the transferring node for access by a first client making a first request for the collection of data from the descendent node; and

the step of storing the collection of data comprises transferring the stream of packets from the buffer to the data storage in the transferring node in a manner enabling access to the collection of data by a second client making a second request for the collection of data.

28. The computer program product of claim 22 further comprising:

instructions wherein the step of receiving the collection of data from the provider node includes the step of obtaining a multicast video stream and buffering a version of the multicast video stream completely in volatile memory;

instructions wherein the step of transferring the copy of the collection of data includes the step of reading the buffered version of the multicast video stream from the volatile memory and sending that buffered version of the multicast video stream to the child node;

instructions wherein the step of storing the collection of data in the data storage includes the step of, in response to completing transfer of the buffered version of the multicast video stream to the child node, saving a copy of the buffered version of the multicast video stream in non-volatile memory; and

instructions wherein the method further comprises the steps of (i) acquiring a request for the data from a requesting node at a later time, (ii) retrieving the saved copy of the buffered version of the multicast video stream from the non-volatile memory, and (iii) sending the saved copy to the requesting node.

33. The computer program product of claim 22 wherein said hierarchical network of nodes comprise a distribution tree.

34. The computer program product of claim 33 wherein said distribution tree is rooted at a source node, said source node comprising said transferring node.

23. A computer system for distributing data in an overlay network based on logical relationships, said overlay network including an hierarchical network of nodes, the overlay network implemented as a network abstraction on top off an existing network based on other connections, the computer system comprising:

means for receiving a collection of data at a transferring node from a provider node in the hierarchical network of nodes;

means for transferring a copy of the collection of data to a child node of the transferring node in the hierarchical network of nodes in response to the step of receiving the collection of data; and

means for storing the collection of data in a data storage at the transferring node after completing the step of transferring the copy of the collection of data;

and wherein the collection of data represents content distributed as a stream of packets to the hierarchical network from a source node, and wherein;

the receiving means includes means for receiving the stream of packets in a buffer;

the transferring means includes means for propagating the stream of packets from the buffer to descendent nodes of the transferring node for access by a first client making a first request for the collection of data from the descendent node; and

the storing means includes means for transferring the stream of packets from the buffer to the data storage in the transferring node in a manner enabling access to the collection of data by a second client making a second request for the collection of data.

35. The computer system of claim 23 wherein said hierarchical network of nodes comprise a distribution tree.

36. The computer system of claim 35 wherein said distribution tree is rooted at a source node said source node comprising aid transferring node.

37. In a transferring node, a method for distributing data in an overlay network based on logical relationships, said overlay network including a hierarchical network of nodes, said overlay network implemented as an abstraction on top of an existing network based on other connections, the method comprising the steps of:

receiving at the transferring node a collection of data from a provider node in the overlay network including a hierarchical network of nodes, said overlay network implemented as an abstraction on top of an existing network based on other connections;

transferring a copy of the collection of data to a child node of the transferring node in the overlay network including a hierarchical network of nodes in response to the step of receiving the collection of data; and

storing the collection of data in a data storage in the transferring node after completing the step of transferring the copy of the collection of data;

wherein the collection of data represents content distributed as a stream of packets to the hierarchical network from a source node, and wherein;

the step of receiving the collection of data comprises receiving the stream of packets in a buffer;

the step of transferring the copy of the collection of data comprises propagating the stream of packets from the buffer to descendent nodes of the transferring node for access by a first client making a first request for the collection of data from the descendent node; and

the step of storing the collection of data comprises transferring the stream of packets from the buffer to the data storage in the transferring node in a manner enabling access to the collection of data by a second client making a second request for the collection of data.