Multicast packet video system and hardware

• US 20070147371A1
• Filed: 09/26/2006
• Published: 06/28/2007
• Est. Priority Date: 09/26/2005
• Status: Abandoned Application

• Current Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Original Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Inventors: Karande, Shirish, Wu, Mingquan, Radha, Hayder
• Application Number:
  US11/527,247
• Publication Number:
  US 20070147371A1
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/6473 Monitoring network processes errors for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: H04N 21/64784 Data processing by the network data processing in packet switching systems H04L12/56; flow control in packet networks H04L47/10; intermediate storage or scheduling H04L49/90; provisioning of proxy services in data packet switching networks H04L67/56

Abstract

A multicast packet video system includes a codec placement module placing codecs in nodes of a multicasting network. In some aspects, the placement includes receiving, at a parent node of the network, feedback from its child nodes indicating a number of the child nodes unable to decode FEC blocks, and placing a codec at the parent node if the number exceeds a threshold. In alternative or additional aspects, the placement includes placing codecs in nodes of a multicasting tree of the network by recursively performing a search of a network topology T to find an optimum node c at which to place a codec in order to obtain a maximum improvement in average video-packet throughput over nodes of the tree as a result of the codec recovering lost video and parity packets and transmitting them downstream.

Claims

1. A multicast packet video system having machine instructions stored in a computer readable medium, the system comprising:

a codec placement module placing codecs in nodes of a multicasting network, said module including at least one of;

(a) distributed codec placement machine instructions receiving, at a parent node of the network, feedback from its child nodes indicating a number of the child nodes unable to decode FEC blocks, and placing a codec at the parent node if the number exceeds a threshold;

or

(b) centralized codec placement machine instructions placing codecs in nodes of a multicasting tree of the network by recursively performing a search of a network topology T to find an optimum node c at which to place a codec in order to obtain a maximum improvement in average video-packet throughput over nodes of the tree as a result of the codec recovering lost video and parity packets and transmitting them downstream.

2. The system of claim 1, wherein said codec placement module places codecs in nodes of the multicasting network by receiving, at the parent node of the network, feedback from its child nodes indicating the number of the child nodes unable to decode FEC blocks, and places the codec at the parent node if the number exceeds the threshold.

3. The system of claim 2, wherein a node of the network keeps a first record of a largest number of parity packets required by the node itself and its immediate children, and a second record of a total number of nodes in a subtree rooted at the node (including itself) that, on average, can not decode FEC blocks if they do not receive parity packets produced by an immediate codec upstream.

4. The system of claim 3, wherein the first record and the second record are updated by the node when it receives feedback from its children, and the node sends feedback to its parent periodically, thereby ensuring that, as information is passed from leaf nodes toward a root of the multicast tree, each node in the multicast stream eventually knows the largest number of parity packets required among the nodes that belong to a subtree rooted at that node, and each node also knows a total number of nodes in its subtree that, on average, can not decode FEC blocks if they do not receive extra parity packets from the immediate codec upstream of that node.

5. The system of claim 2, wherein, in order for a node to act as a codec, it is required that:

on average, the node must be able to decode FEC blocks successfully; and

a number of children of the node that require extra parity packets must exceed the threshold.

6. The system of claim 2, wherein a node has a data structure storing information associated with each of its immediate children, including a first data member indicating the parity packets required by the child from its immediate codec upstream, and a second data member indicating a number of child nodes in the sub-tree rooted at the node that, on average, can not decode FEC blocks if it does not receive parity packets produced by an immediate codec upstream, the immediate codec upstream being a closest codec to the child node on a path that leads the child node to a source.

7. The system of claim 2, wherein a node keeps a record of each codec upstream from the node, and, when the node receives a parity packet produced by the codec, it records its IP address and a hop-count from the codec to itself so that the node can tell which codec is its immediate codec upstream.

8. The system of claim 2, wherein a node keeps an estimate of its average received packets per FEC block.

9. The system of claim 2, wherein a node keeps an estimate of its average received packets per FEC block without counting any parity packets it receives from its immediate codec upstream.

10. The system of claim 1, further comprising:

a topology datastore storing a datastructure representing the given network topology T of a multicasting network, wherein said codec placement module accesses said topology datastore and places codecs in nodes of the multicasting tree of the network by recursively performing the search of the network topology T to find an optimum node c at which to place the codec in order to obtain the maximum improvement in average video-packet throughput over nodes of the tree as the result of the codec recovering lost video and parity packets and transmitting them downstream.

11. The system of claim 10, wherein said codec placement module places codecs until a quality of service guarantee requirement is met.

12. The system of claim 11, wherein said network is a p2p network, and said codec placement module averages throughput over all nodes of the tree.

13. The system of claim 11, wherein said network is a proxy-based, overlay network, and said codec placement module averages throughput over only leaf nodes of the tree.

14. The system of claim 11, wherein said codec placement module places FEC codecs.

15. A network router, comprising:

an input receptive of a multicasting stream from upstream;

a plurality of outputs transmitting the multicasting stream downstream;

a routing table adapted to rout the multicasting stream downstream via said outputs; and

an FEC codec recovering lost video and parity packets and transmitting them downstream,

wherein a position of said codec in a multicasting tree of a network is at least one of;

(a) dynamically determined in response to feedback at a node that is the router from its child nodes indicating a number of the child nodes unable to decode FEC blocks;

or

(b) an optimal position, in view of a topology of the network, at which to place the FEC codec in order to maximize average video-packet throughput over nodes of a multicasting tree of the network.

16. The router of claim 15, further comprising a codec placement module placing the codec at the node in response to the feedback from its child nodes if the number of its child nodes unable to decode FEC blocks exceeds a threshold.

17. The router of claim 16, further comprising a data structure storing information associated with each of the node'"'"'s immediate children, including a first data member indicating the parity packets required by the child from the child'"'"'s respective immediate codec upstream, and a second data member indicating a number of child nodes in the sub-tree rooted at the node that, on average, can not decode FEC blocks if they do not receive parity packets produced by their immediate codecs upstream, wherein a particular node'"'"'s immediate codec upstream is a closest codec to the particular node on a path that connects the particular node to a multicasting source.

18. The router of claim 16, wherein the rnode keeps a record of each codec upstream from the node, and, when the node receives a parity packet produced by a codec, it records the codec'"'"'s IP address and a hop-count from the codec to itself so that the node can tell which codec is its immediate codec.

19. The router of claim 16, wherein the node keeps an estimate of its average received packets per FEC block.

20. The router of claim 16, wherein the node keeps an estimate of its average received packets per FEC block without counting any parity packets it receives from its immediate codec upstream.

21. The router of claim 16, wherein the node keeps a first record of a largest number of parity packets required by the node itself and its immediate children, and a second record of a total number of nodes in a subtree rooted at the node, including itself, that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream.

22. The router of claim 15, further comprising:

a topology datastore storing a datastructure representing the given network topology T of a multicasting network, wherein said codec placement module accesses said topology datastore and places codecs in nodes of the multicasting tree of the network by recursively performing the search of the network topology T to find an optimum node c at which to place the codec in order to obtain the maximum improvement in average video-packet throughput over nodes of the tree as the result of the codec recovering lost video and parity packets and transmitting them downstream.

23. The router of claim 22, wherein said network is a p2p network, and said average-video packet throughput is averaged over all nodes of the tree.

24. The router of claim 22, wherein said network is a proxy-based, overlay network, and said average-video packet throughput is averaged over only leaf nodes of the tree.

25. A codec placement method for use with a multicast packet video system, the method comprising:

placing codecs in nodes of a multicasting network by at least one of;

(a) receiving, at a parent node of the network, feedback from its child nodes indicating a number of the child nodes unable to decode FEC blocks, and placing a codec at the parent node if the number exceeds a threshold;

or

(b) placing codecs in nodes of a multicasting tree of the network by recursively performing a search of a network topology to find an optimum node c at which to place a codec in order to obtain a maximum improvement in average video-packet throughput over nodes of the tree as a result of the codec recovering lost video and parity packets and transmitting them downstream.

26. The method of claim 25, wherein placing codecs in nodes of the multicasting network includes receiving, at the parent node of the network, feedback from its child nodes indicating the number of the child nodes unable to decode FEC blocks, and placing the codec at the parent node if the number exceeds the threshold.

27. The method of claim 26, further comprising requiring that, in order for a node to act as a codec:

on average, the node must be able to decode FEC blocks successfully; and

a number of children of the node that require extra parity packets must exceed the threshold.

28. The method of claim 26, further comprising recording at a node information associated with each of its immediate children, including a first data member indicating the parity packets required by each child from the child'"'"'s respective immediate codec upstream, and a second data member indicating a number of child nodes in the sub-tree rooted at the node i that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream, wherein a particular node'"'"'s immediate codec upstream is a closest codec to the particular node on a path that connects the particular node to a multicasting source.

29. The method of claim 26, further comprising recording at a node information concerning each codec upstream from the node, and, when the node receives a parity packet produced by a codec, recording the codec'"'"'s IP address and a hop-count from the codec to itself so that the node can tell which codec is its immediate codec.

30. The method of claim 26, further comprising estimating at a node its average received packets per FEC block.

31. The method of claim 26, further comprising estimating at a node its average received packets per FEC block without counting any parity packets it receives from its immediate codec upstream.

32. The method of claim 26, further comprising recording at a node a first record of a largest number of parity packets required by the node itself and its immediate children, and a second record of a total number of nodes in a subtree rooted at the node, including itself, that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream.

33. The method of claim 32, further comprising:

updating the first record and the second record when the node receives feedback from its children; and

sending feedback from the node to its parent periodically, thereby ensuring that, as information is passed from leaf nodes toward a root of the multicast tree, each node eventually knows the largest number of parity packets required among the nodes that belong to a subtree rooted at that node, and each node also knows a total number of nodes in its subtree that, on average, can not decode FEC blocks if they do not receive extra parity packets from their respective immediate codecs upstream.

34. The method of claim 25, wherein placing the codecs includes placing NEF codecs within a given network topology T.

35. The method of claim 34, further comprising employing a greedy calculation to place m codecs in a multicast tree for the network topology T, including:

(a) performing an exhaustive search of the network topology T to find an optimum node c at which to place a codec in order to obtain a maximum improvement in average video-packet throughput over nodes of the tree as a result of the codec recovering lost video and parity packets and transmitting them downstream;

(b) placing the codec at the optimum node c in the network topology T;

(c) performing steps (b) and (c) respective of the network topology T containing the codec placed in the network topology T during previous performance of step (b); and

(d) iteratively performing step (c) respective of the network topology T containing all codecs placed in the network topology T during previous performance of step (b) until all m codecs are placed in the network topology T.

36. The method of claim 35, further comprising determining a number of codecs m based on required quality of service guarantees.

37. The method of claim 36, wherein determining m includes in step (c):

averaging distortion level over all nodes, thereby obtaining an average distortion level;

comparing the average distortion level to a lossless distortion level, thereby calculating a quality of service measure obtainable with a current value of m;

observing a termination condition based on a comparison of the quality of service measure to the required quality of service guarantees; and

incrementing m if the termination condition is not satisfied.

38. The method of claim 35, wherein the network topology T is for a p2p multicast network, and step (a) includes identifying the optimum node c by finding c∈

T that maximizes the following;

$\underset{c\in <br><br>T}{\max }<br><br>\left[\underset{v\in <br><br>T^c}{\sum <br><br>}<br><br>\left(E^{\mathrm{\prime <br><br>}}<br><br>\left[r_d<br><br>\left(v\right)\right]-E<br><br>\left[r_d<br><br>\left(v\right)\right]\right)\right],$

wherein E[r_d(v)] and E′

[r_d(v)] denote average received packets for node v∈

T^c before and after node c is set as a codec node, respectively, and T^c⊂

T is a sub tree rooted at node c∈

T, not including c.

39. The method of claim 35, wherein the network topology T is for a proxy-based, overlay multicast network, and step (a) includes identifying the optimum node c by finding c∈

T that maximizes a function similar to the following;

$\underset{c\in <br><br>T}{\max }<br><br>\left[\underset{v\in <br><br>T^c}{\sum <br><br>}<br><br>\left(E^{\mathrm{\prime <br><br>}}<br><br>\left[r_d<br><br>\left(v\right)\right]-E<br><br>\left[r_d<br><br>\left(v\right)\right]\right)\right],$

wherein E[r_d(v)] and E′

[r_d(v)] denote average received packets for node v∈

T^c before and after node c is set as a codec node, respectively, and T^c⊂

T is a sub tree rooted at node c∈

T, not including c, and the function differs in that the summation only occurs over leaf nodes of the network topology T.

40. The method of claim 35, further comprising placing NEF codecs in step (b).

41. A multicast network, comprising:

a plurality of network nodes; and

an FEC codec at one of said nodes recovering lost video and parity packets, and transmitting the lost video and parity packets downstream,

wherein a position of said codec in a multicasting tree of the network is at least one of;

(a) dynamically determined in response to feedback at a node of the network from its child nodes indicating a number of the child nodes unable to decode FEC blocks;

or

(b) an optimal position, in view of a topology of the network, at which to place the FEC codec in order to maximize average video-packet throughput over nodes of a multicasting tree of the network.

42. The network of claim 41, further comprising a codec placement module placing the codec at the node of the network in response to the feedback from its child nodes if the number of its child nodes unable to decode FEC blocks exceeds a threshold.

43. The network of claim 42, further comprising a data structure storing information associated with each of the node'"'"'s immediate children, including a first data member indicating the parity packets required by a child from the child'"'"'s respective immediate codec upstream, and a second data member indicating a number of child nodes in the sub-tree rooted at the node that, on average, can not decode FEC blocks if they do not receive parity packets produced by their immediate codecs upstream, wherein a particular node'"'"'s immediate codec upstream is a closest codec to the particular node on a path that connects the particular node to a multicasting source.

44. The network of claim 42, wherein the node keeps a record of each codec upstream from the node, and, when the node receives a parity packet produced by a codec, it records the codec'"'"'s IP address and a hop-count from the codec to itself so that the node can tell which codec is its immediate codec.

45. The network of claim 42, wherein the node keeps an estimate of its average received packets per FEC block.

46. The network of claim 42, wherein the node keeps an estimate of its average received packets per FEC block without counting any parity packets it receives from its immediate codec upstream.

47. The network of claim 42, wherein the node keeps a first record of a largest number of parity packets required by the node itself and its immediate children, and a second record of a total number of nodes in a subtree rooted at the node, including itself, that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream.

48. The network of claim 41, further comprising:

a first NEF codec placed at a first selected node of said multicast tree, said first selected node being selected to obtain a maximum improvement in average video-packet throughput over nodes of said tree as a result of said first NEF codec recovering lost video and parity packets and transmitting them downstream.

49. The network of claim 48, further comprising a second NEF codec placed at a second selected node of said multicast tree, said first selected node being selected to obtain a maximum improvement in average video-packet throughput over nodes of said tree as a result of said first NEF codec and said second NEF codec recovering lost video and parity packets and transmitting them downstream.

50. The network of claim 49, further comprising a third NEF codec placed at a third selected node of said multicast tree, said third selected node being selected to obtain a maximum improvement in average video-packet throughput over nodes of said tree as a result of said first NEF codec, said second NEF codec, and said third NEF codec recovering lost video and parity packets and transmitting them downstream.

51. The network of claim 48, further comprising m−

1 additional NEF codecs placed at m−

1 selected nodes of said tree, each of said m−

1 selected nodes being selected one by one to obtain a maximum improvement in average video-packet throughput over nodes of said tree as a result of one by one placement of said additional NEF codecs at said m−

1 selected nodes, said maximum improvement in average video packet throughput being evaluated after placement of each of the m−

1 additional NEF codecs based on the first node and all additional nodes thus far placed in the tree recovering lost video and parity packets and transmitting them downstream, wherein m is determined based on achievement of a target average throughput over nodes of the tree.

52. The network of claim 48, wherein said network is a p2p network, and the throughput is averaged over all nodes of the tree.

53. The network of claim 48, wherein said network is a proxy-based, overlay network, and the throughput is averaged over only leaf nodes of the tree.

54. Computer software, stored in a computer readable storage medium, for placing codecs in nodes of a multicast tree of a network, comprising:

first machine instructions receiving, at a parent node of the network, feedback from its child nodes indicating a number of the child nodes unable to decode FEC blocks; and

second machine instructions placing a codec at the parent node if the number exceeds a threshold.

55. The software of claim 54, further comprising third machine instruction requiring that, in order for a node to act as a codec:

on average, the node must be able to decode FEC blocks successfully; and

a number of children of the node that require extra parity packets must exceed the threshold.

56. The software of claim 54, further comprising third machine instruction recording at a node information associated with each of its immediate children, including a first data member indicating the parity packets required by each child from the child'"'"'s respective immediate codec upstream, and a second data member indicating a number of child nodes in the sub-tree rooted at the node i that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream, wherein a particular node'"'"'s immediate codec upstream is a closest codec to the particular node on a path that connects the particular node to a multicasting source.

57. The software of claim 54, further comprising third machine instruction recording at a node information concerning each codec upstream from the node, and, when the node receives a parity packet produced by a codec, recording the codec'"'"'s IP address and a hop-count from the codec to itself so that the node can tell which codec is its immediate codec.

58. The software of claim 54, further comprising third machine instruction estimating at a node its average received packets per FEC block.

59. The software of claim 54, further comprising third machine instruction estimating at a node its average received packets per FEC block without counting any parity packets it receives from its immediate codec upstream.

60. The software of claim 54, further comprising third machine instruction recording at a node a first record of a largest number of parity packets required by the node itself and its immediate children, and a second record of a total number of nodes in a subtree rooted at the node, including itself, that, on average, can not decode FEC blocks if they do not receive parity packets produced by their respective immediate codecs upstream.

61. The software of claim 60, further comprising fourth machine instruction updating the first record and the second record when the node receives feedback from its children, and sending feedback from the node to its parent periodically, thereby ensuring that, as information is passed from leaf nodes toward a root of the multicast tree, each node eventually knows the largest number of parity packets required among the nodes that belong to a subtree rooted at that node, and each node also knows a total number of nodes in its subtree that, on average, can not decode FEC blocks if they do not receive extra parity packets from their respective immediate codecs upstream.

62. Computer software, stored in a computer readable storage medium, for placing codecs in nodes of a multicast tree of a network, comprising:

first machine instructions performing an exhaustive search of a network topology T to find an optimum node c at which to place a codec in order to obtain a maximum improvement in average video-packet throughput over nodes of the tree as a result of the codec recovering lost video and parity packets and transmitting them downstream;

second machine instructions placing the codec at the optimum node c in the network topology T;

third machine instructions iteratively performing said first machine instructions and said second machine instructions respective of the network topology T containing the codec placed in the network topology T during previous performance of said second machine instructions; and

fourth machine instructions iteratively performing said third machine instructions respective of the network topology T containing all codecs placed in the network topology T during previous performance of said second machine instructions until a number of codecs m are placed in the network topology T.

63. The software of claim 62, further comprising fifth machine instructions determining the number of codecs m based on required quality of service guarantees.

64. The software of claim 63, wherein said fifth machine instructions include:

a first machine instruction component that averages distortion level over all nodes, thereby obtaining an average distortion level;

a second machine instruction component that compares the average distortion level to a lossless distortion level, thereby calculating a quality of service measure obtainable with a current value of m;

a third machine instruction component that observes a termination condition based on a comparison of the quality of service measure to the required quality of service guarantees; and

a fourth machine instruction component that increments m if the termination condition is not satisfied.

65. The software of claim 62, wherein the network topology T is for a p2p multicast network, and said first machine instructions identify the optimum node c by averaging throughput over all nodes of the tree.

66. The software of claim 65, wherein said first machine instructions identify the optimum node c by finding c∈

T that maximizes the following expression;

$\underset{c\in <br><br>T}{\max }<br><br>\left[\underset{v\in <br><br>T^c}{\sum <br><br>}<br><br>\left(E^{\mathrm{\prime <br><br>}}<br><br>\left[r_d<br><br>\left(v\right)\right]-E<br><br>\left[r_d<br><br>\left(v\right)\right]\right)\right],$

wherein E[r_d(v)] and E′

[r_d(v)] denote average received packets for node v∈

T^c before and after node c is set as a codec node, respectively, and T^c⊂

T is a sub tree rooted at node c∈

T, not including c.

67. The software of claim 62, wherein the network topology T is for a proxy-based, overlay multicast network, and said first machine instructions identify the optimum node c by averaging throughput over only leaf nodes of the tree.

68. The software of claim 67, wherein said first machine instructions identify the optimum node c by finding c∈

T that maximizes a function similar to the following;

$\underset{c\in <br><br>T}{\max }<br><br>\left[\underset{v\in <br><br>T^c}{\sum <br><br>}<br><br>\left(E^{\mathrm{\prime <br><br>}}<br><br>\left[r_d<br><br>\left(v\right)\right]-E<br><br>\left[r_d<br><br>\left(v\right)\right]\right)\right],$

wherein E[r_d(v)] and E′

[r_d(v)] denote average received packets for node v∈

T^c before and after node c is set as a codec node, respectively, and T^c⊂

T is a sub tree rooted at node c∈

T, not including c, and the function differs in that the summation only occurs over leaf nodes of the network topology T.

69. The software of claim 62, wherein said second machine instructions place NEF codecs.