Apparatus and Method for Network Flow Scheduling

• US 20170126416A1
• Filed: 06/20/2016
• Published: 05/04/2017
• Est. Priority Date: 11/04/2015
• Status: Active Grant

• Current Assignee: Huawei Technologies Canada Co., Ltd (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Canada Co., Ltd (Huawei Investment & Holding Co., Ltd.)
• Inventors: Ashwood-Smith, Peter, McCormick, William Carson, Kelly, Francis Patrick
• Granted Patent: US 10,129,043 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Embodiments are provided for path flow scheduling of multicast traffic through a network. The paths for traffic flow are determined to optimize link utilization in terms of bandwidth and link capacity, and limit link cost. In an embodiment, a method is implemented for network flow scheduling. The method includes establishing, by a controller of a network, a multicast tree which includes a plurality of links for sending multicast traffic from a source to multiple destinations. The tree is established based on minimizing a number of links in the multicast tree. The tree is then adjusted by replacing one or more of the plurality of links to reduce the link utilization. The tree adjustment is repeated by further replacing one or more links in the multicast tree to further reduce the link utilization.

Claims

1. A method for network flow scheduling, the method comprising:

establishing, by a controller of a network, a multicast tree, including a plurality of links for sending multicast traffic from a source to multiple destinations, based on minimizing a number of links in the multicast tree, the multicast tree having a link utilization and a tree cost for the plurality of links;

evaluating the tree cost of the multicast tree in accordance with an acceptable tree cost requirement;

adjusting the multicast tree by replacing one or more of the plurality of links in accordance with a link utilization objective; and

re-evaluating the tree cost of the adjusted multicast tree, and re-adjusting the evaluated multicast tree until the acceptable tree cost requirement is satisfied.

2. The method of claim 1, wherein step of adjusting the multicast tree includes replacing a link in the plurality of links to reduce the link utilization.

3. The method of claim 1, wherein the step of adjusting the multicast tree includes replacing a link in the plurality of links to avoid placing traffic on a hot link.

4. The method of claim 1 wherein the step of adjusting the multicast tree includes replacing a link in the plurality of links to avoid placing traffic on a cold link.

5. The method of claim 1, wherein the tree cost is a measure of tree depth or a number of links in the multicast tree.

6. The method of claim 1, wherein the link utilization is a ratio of bandwidth for sending the multicast traffic on the links to a total capacity for routing traffic on the links.

7. The method of claim 1, wherein the multicast tree is established and adjusted using mixed integer linear programming (MILP).

8. The method of claim 1, wherein establishing the multicast tree includes:

building a plurality of unicast paths from the source to the multiple destinations in accordance with minimizing the number of links in the multicast tree; and

combining the unicast paths into a multipath tree.

9. The method of claim 1, wherein adjusting the multicast tree increases the tree cost of the multicast tree.

10. A method for network flow scheduling, the method comprising:

establishing, by a controller of a network, a multicast tree including a plurality of links for sending multicast traffic from a source to multiple destinations based on minimizing a tree depth of the multicast tree and according to a link capacity constraint; and

replacing one or more of the links to reduce link utilization on the multicast tree, until reaching or exceeding a maximum tree depth allowed for the multicast tree, the link utilization representing a total bandwidth used for sending the multicast traffic on the links to a total capacity of the links.

11. The method of claim 10, wherein the link capacity constraint ensures that each link in the multicast tree has enough capacity to support the multicast traffic.

12. The method of claim 10, wherein the network is a multiprotocol label switching (MPLS) network.

13. The method of claim 10, wherein the network is a Software Defined Networking (SDN) network.

14. The method of claim 10, wherein the multicast traffic includes Internet Protocol Television (IPTV) packets for digital terrestrial television (DTTV), ad hoc traffic for video applications, or best effort traffic.

15. A network entity for scheduling traffic flow, the network entity comprising:

at least one processor coupled to a memory; and

a non-transitory computer readable storage medium storing programming for execution by the at least one processor, the programming including instructions to;

establish a multicast tree, including a plurality of links for sending multicast traffic from a source to multiple destinations, based on minimizing a number of links in the multicast tree, the multicast tree having a link utilization and a tree cost for the plurality of links;

evaluate the tree cost of the multicast tree in accordance with an acceptable tree cost requirement;

adjust the multicast tree by replacing one or more of the plurality of links in accordance with a link utilization objective; and

re-evaluate the tree cost of the adjusted multicast tree, and re-adjust the evaluated multicast tree until the acceptable tree cost requirement is satisfied.

16. The network entity of claim 15, wherein the tree cost is a measure of tree depth or a number of links in the multicast tree.

17. The network entity of claim 15, wherein the link utilization is a ratio of bandwidth for sending the multicast traffic on the links to a total capacity for routing traffic on the links.

18. The network entity of claim 15, wherein the programming is mixed integer linear programming (MILP).

19. The network entity of claim 15, wherein the network entity is a Software Defined Networking (SDN) controller.

20. The network entity of claim 15, wherein the multiple destinations are transmit stations for wireless communications.