Methods and apparatus for performing content distribution in a content distribution network

• US 20050076104A1
• Filed: 06/23/2003
• Published: 04/07/2005
• Est. Priority Date: 11/08/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Li, Dan, Liskov, Barbara, Morris, Stephen Jeffrey, Stavisky, Dmitry
• Granted Patent: US 7,257,628 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 67/01 Protocols
• 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
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Mechanisms and techniques provide a system that operates in a computerized device(s) to establish a data distribution path for content within a content distribution network by receiving a network topology definition defining at least one hierarchical interconnection of network groups. Each network group comprises at least one content engine. The system also receives a channel definition comprising a selection of a plurality of content engines that are to distribute content within the content distribution network. The plurality of content engines in the channel definition is selected from content engines within the network groups defined within the network topology definition. The system determines an assignment of at least one root content engine within the channel definition and applies a content distribution path determination technique to the network topology definition in relation to the channel definition to determine a set of content distribution paths in the content distribution network to be used for distribution of content from the root content engine(s) to the content engines defined in the channel definition.

Claims

1. A method for establishing a data distribution path for content within a content distribution network, the method comprising the steps of:

receiving a network topology definition defining at least one hierarchical interconnection of network groups, each network group comprising at least one content engine;

receiving a channel definition comprising a selection of a plurality of content engines that are to distribute content within the content distribution network, the plurality of content engines in the channel definition selected from content engines within the network groups defined within the network topology definition;

determining an assignment of at least one root content engine within the channel definition; and

applying a content distribution path determination technique to the network topology definition in relation to the channel definition to determine a set of content distribution paths in the content distribution network to be used for distribution of content from the at least one root content engine to the plurality of content engines defined in the channel definition.

2. The method of claim 1 wherein:

each network group in the network topology definition containing one of the at least one root content engine is a root network group;

each network group in the network topology definition that does not contain one of the at least one root content engine but that contains a selection of at least one content engine in the channel definition is a non-root network group;

wherein the step of applying a content distribution path determination technique comprises the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition.

3. The method of claim 2 wherein:

each network group in the network topology that contains a selected content engine within the channel definition is a selected network group;

each network group in the network topology that does not contain a selected content engine within the channel definition is a non-selected network group; and

wherein the step of determining an ideal data distribution path comprises the step of selecting the ideal data distribution path to include only selected network groups.

4. The method of claim 3 wherein the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition comprises the steps of:

for each non-root network group that is a selected network group, performing the steps of;

determining if the non-root network group shares an ancestor selected network group with the at least one root network group in the network topology; and

if the non-root network group shares an ancestor selected network group with the at least one root network group, then defining the ideal data distribution path from the non-root network group to the at least one root network group to include all selected groups interconnected by a path of links in the network topology beginning at the non-root network group and extending to the ancestor selected network group and then extending from the ancestor selected network group to the at least one root group that shared the ancestor selected network group with the non-root network group.

5. The method of claim 4 wherein the ancestor selected network group shared by the non-root network group and the at least one root network group is a lowest common ancestor selected network group.

6. The method of claim 3 wherein the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition comprises the steps of:

for each non-root network group that is a selected network group, performing the steps of;

determining if the non-root network group does not share an ancestor selected network group with the at least one root network group in the network topology; and

if the non-root network group does not share an ancestor selected network group with the at least one root network group, then defining the ideal data distribution path from the non-root network group to the at least one root network group to include all selected groups interconnected by a path of links in the network topology beginning at the non-root network group and extending to highest ancestor network group associated with the non-root network group and then extending to the highest ancestor network group associated with the at least one root group, and then extending from the highest ancestor network group associated with the at least one root group to the at least one root group.

7. The method of claim 6 wherein the highest ancestor network group associated with the at least one root network group is the highest selected ancestor network group associated with the at least one root network group.

8. The method of claim 1 wherein the step of receiving a network topology definition defining at least one hierarchical interconnection of network groups comprises the steps of:

obtaining identities of a set of content engines that define a network group, each identified content engine being able to communicate with other identified content engines in the network group;

repeating the step of obtaining identities of a set of content engines that define a network group in order to define a plurality of network groups within the network topology; and

for each network group that is not a top level network group in the hierarchical interconnection of network groups, obtaining only one link definition between that network group and only one parent network group, the one link definition allowing any content engine in that network group to communicate with any content engine in the one parent group.

9. The method of claim 6 wherein the step of determining an assignment of at least one root content engine within the channel definition comprises the step of:

designating, as the at least one root content engine, at least one content engine within the channel definition that exists in a network group that is highest in the at least one hierarchical interconnection of network groups.

10. The method of claim 1 wherein the step of determining an assignment of at least one root content engine within the channel definition is performed automatically based on at least one of:

a performance metric associated with the at least one content engine; and

a bandwidth metric associated with the network group that contains the at least one content engine.

11. The method of claim 1 comprising the steps of:

receiving, at the at least one root content engine, content to be distributed to the plurality of content engines defined in the channel definition;

distributing, from the at least one root content engine, the content to network groups containing content engines defined in the channel definition using the set of content distribution paths determined from the step of applying a content distribution path determination technique.

12. The method of claim 1 wherein the steps of receiving a network topology definition, receiving a channel definition, determining an assignment of at least one root content engine, and applying a content distribution path determination technique are performed locally within at least one computerized device and wherein the method comprises the steps of:

disseminating the set of content distribution paths to at least a portion of the plurality of content engines defined in the channel definition such that each content engine in the at least a portion of the plurality of content engines can determine a distribution path to use to disseminate content within the content distribution network from the at least one root content engine.

13. The method of claim 1 wherein each of the content engines defined in the channel definiton performs the steps of receiving a network topology definition, receiving a channel definition, determining an assignment of at least one root content engine, and applying a content distribution path determination technique such that each content engine in the channel definition independently determines a distribution path to use to disseminate content within the content distribution network from the at least one root content engine.

14. The method of claim 1 comprising the step of:

identifying at least one of;

a firewall condition in the channel definition in which at least two content engines within the channel definition are capable of communicating in only one direction with respect to the location of the at least one root content engine within the channel definition;

an efficiency condition indicating inefficiencies in transferring content in the set of distribution paths; and

a tree-restructuring condition in which the set of distribution paths are not optimally organized; and

in response to the step of identifying, applying a tree restructuring correction technique to restructure the set of distribution paths for the parent network group.

15. The method of claim 14 wherein one of the at least two content engines is an at least one root content engine and wherein the step of identifying a firewall condition determines that communication between the at least one root content engine is capable only in a direction that is opposite of a direction required for distribution of content from the at least one root content engine.

16. The method of claim 1 comprising the steps of:

determining, for selected parent network groups in the network topology, if a number of selected child network groups for that selected parent network group exceeds a predetermined threshold;

identifying a tree restructuring condition; and

applying a tree restructuring correction technique to restructure the set of distribution paths for the parent network group.

17. The method of claim 15 wherein the step of applying a tree restructuring correction technique comprises:

comparing a metric of each child network group to the parent network group and to at least one other child network group to determine if that child network group should be a child of that patent network group, and if so, assigning that child network group as a child of the parent network group, and if that child network group should be a child of another child network group, then assigning that child network group as a child of the another child network group.

18. A computerized device comprising:

at least one communications interface;

a memory;

a processor; and

an interconnection mechanism coupling the at least one communications interface, the memory and the processor; and

wherein the memory is encoded with an path manager application that when performed on the processor, produces a path manager process that causes the computerized device to establish a data distribution path for content within a content distribution network by performing the steps of;

receiving a network topology definition defining at least one hierarchical interconnection of network groups, each network group comprising at least one content engine;

receiving a channel definition comprising a selection of a plurality of content engines that are to distribute content within the content distribution network, the plurality of content engines in the channel definition selected from content engines within the network groups defined within the network topology definition;

determining an assignment of at least one root content engine within the channel definition; and

applying a content distribution path determination technique to the network topology definition in relation to the channel definition to determine a set of content distribution paths in the content distribution network to be used for distribution of content from the at least one root content engine to the plurality of content engines defined in the channel definition.

19. The computerized device of claim 18 wherein:

each network group in the network topology definition containing one of the at least one root content engine is a root network group;

each network group in the network topology definition that does not contain one of the at least one root content engine but that contains a selection of at least one content engine in the channel definition is a non-root network group;

wherein when the computerized device performs the step of applying a content distribution path determination technique the computerized device performs the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition.

20. The computerized device of claim 19 wherein:

each network group in the network topology that contains a selected content engine within the channel definition is a selected network group;

each network group in the network topology that does not contain a selected content engine within the channel definition is a non-selected network group; and

wherein when the computerized device performs the step of determining an ideal data distribution path the computerized device performs the step of selecting the ideal data distribution path to include only selected network groups.

21. The computerized device of claim 20 wherein when the computerized device performs the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition the computerized device performs the steps of:

for each non-root network group that is a selected network group, performing the steps of;

determining if the non-root network group shares an ancestor selected network group with the at least one root network group in the network topology; and

if the non-root network group shares an ancestor selected network group with the at least one root network group, then defining the ideal data distribution path from the non-root network group to the at least one root network group to include all selected groups interconnected by a path of links in the network topology beginning at the non-root network group and extending to the ancestor selected network group and then extending from the ancestor selected network group to the at least one root group that shared the ancestor selected network group with the non-root network group.

22. The computerized device of claim 20 wherein the ancestor selected network group shared by the non-root network group and the at least one root network group is a lowest common ancestor selected network group.

23. The computerized device of claim 20 wherein when the computerized device performs the step of determining an ideal data distribution path from each non-root network group to at least one root network group in the network topology definition the computerized device performs the steps of:

for each non-root network group that is a selected network group, performing the steps of;

determining if the non-root network group does not share an ancestor selected network group with the at least one root network group in the network topology; and

if the non-root network group does not share an ancestor selected network group with the at least one root network group, then defining the ideal data distribution path from the non-root network group to the at least one root network group to include all selected groups interconnected by a path of links in the network topology beginning at the non-root network group and extending to highest ancestor network group associated with the non-root network group and then extending to the highest ancestor network group associated with the at least one root group, and then extending from the highest ancestor network group associated with the at least one root group to the at least one root group.

24. The computerized device of claim 23 wherein the highest ancestor network group associated with the at least one root network group is the highest selected ancestor network group associated with the at least one root network group.

25. The computerized device of claim 18 wherein when the computerized device performs the step of receiving a network topology definition defining at least one hierarchical interconnection of network groups the computerized device performs the steps of:

obtaining identities of a set of content engines that define a network group, each identified content engine being able to communicate with other identified content engines in the network group;

repeating the step of obtaining identities of a set of content engines that define a network group in order to define a plurality of network groups within the network topology; and

for each network group that is not a top level network group in the hierarchical interconnection of network groups, obtaining only one link definition between that network group and only one parent network group, the one link definition allowing any content engine in that network group to communicate with any content engine in the one parent group.

26. The computerized device of claim 18 wherein when the computerized device performs the step of determining an assignment of at least one root content engine within the channel definition the computerized device performs the step of:

designating, as the at least one root content engine, at least one content engine within the channel definition that exists in a network group that is highest in the at least one hierarchical interconnection of network groups.

27. The computerized device of claim 18 wherein the step of determining an assignment of at least one root content engine within the channel definition is performed automatically by the computerized device based on at least one of:

a performance metric associated with the at least one content engine; and

a bandwidth metric associated with the network group that contains the at least one content engine.

28. The computerized device of claim 18 wherein the computerized device performs the steps of:

receiving, at the at least one root content engine, content to be distributed to the plurality of content engines defined in the channel definition;

distributing, from the at least one root content engine, the content to network groups containing content engines defined in the channel definition using the set of content distribution paths determined from the step of applying a content distribution path determination technique.

29. The computerized device of claim 18 wherein when the computerized device performs the step of receiving a network topology definition, receiving a channel definition, determining an assignment of at least one root content engine, and applying a content distribution path determination technique are performed locally within at least one computerized device and wherein the computerized device further performs the step of:

disseminating the set of content distribution paths to at least a portion of the plurality of content engines defined in the channel definition such that each content engine in the at least a portion of the plurality of content engines can determine a distribution path to use to disseminate content within the content distribution network from the at least one root content engine.

30. The computerized device of claim 18 wherein each of the content engine defined in the channel definition performs the steps of receiving a network topology definition, receiving a channel definition, determining an assignment of at least one root content engine, and applying a content distribution path determination technique such that each content engine in the channel definition independently determine a distribution path to use to disseminate content within the content distribution network from the at least one root content engine.

31. The computerized device of claim 18 wherein the computerized device performs the step of:

identifying at least one of;

a firewall condition in the channel definition in which at least two content engines within the channel definition are capable of communicating in only one direction with respect to the location of the at least one root content engine within the channel definition;

an efficiency condition indicating inefficiencies in transferring content in the set of distribution paths; and

a tree-restructuring condition in which the set of distribution paths are not optimally organized; and

in response to the step of identifying, the computerized device applies a tree restructuring correction technique to restructure the set of distribution paths for the parent network group.

32. The computerized device of claim 31 wherein one of the at least two content engines is an at least one root content engine and wherein when the computerized device performs the step of identifying a firewall condition, the computerized device performs the step determining that communication between the at least one root content engine is capable only in a direction that is opposite of a direction required for distribution of content from the at least one root content engine.

33. The computerized device of claim 18 wherein the computerized device performs the step of:

determining, for selected parent network groups in the network topology, if a number of selected child network groups for that selected parent network group exceeds a predetermined threshold, and if so, performing the steps of;

identifying a tree restructuring condition; and

applying a tree restructuring correction technique to restructure the set of distribution paths for the parent network group.

34. The computerized device of claim 33 wherein when the computerized device performs the step of applying a tree restructuring correction technique, the computerized device:

compares a metric of each child network group to the parent network group and to at least one other child network group to determine if that child network group should be a child of that patent network group, and if so, assigning that child network group as a child of the parent network group, and if that child network group should be a child of another child network group, then assigning that child network group as a child of the another child network group.

35. A computer program product having a computer-readable medium including computer program logic encoded thereon that, when performed in a computerized device having a coupling of a memory, a processor, and at least one communications interface, provides a method for establishing a data distribution path for content within a content distribution network by causing the computerized device to perform the operations of:

receiving a network topology definition defining at least one hierarchical interconnection of network groups, each network group comprising at least one content engine;

receiving a channel definition comprising a selection of a plurality of content engines that are to distribute content within the content distribution network, the plurality of content engines in the channel definition selected from content engines within the network groups defined within the network topology definition;

determining an assignment of at least one root content engine within the channel definition; and

applying a content distribution path determination technique to the network topology definition in relation to the channel definition to determine a set of content distribution paths in the content distribution network to be used for distribution of content from the at least one root content engine to the plurality of content engines defined in the channel definition.