Apparatus and method for network flow scheduling

Patent metadata

Field	Value
Publication number	US-10129043-B2
Application number	US-201615187415-A
Country	US
Kind code	B2
Filing date	Jun 20, 2016
Priority date	Nov 4, 2015
Publication date	Nov 13, 2018
Grant date	Nov 13, 2018

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.

First claim

What is claimed is:

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, wherein the tree cost comprises a maximum number of links allowed for the multicast tree, and the maximum number of links is larger than the minimized number 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, wherein the maximum tree depth allowed for the multicast tree is larger than the minimized tree depth.

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, wherein the tree cost comprises a maximum number of links allowed for the multicast tree, and the maximum number of links is larger than the minimized number 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.

Assignees

• Huawei Tech Canada Co Ltd

Inventors

• Mccormick William Carson
• Ashwood-Smith Peter
• Kelly Francis Patrick

Classifications

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L12/189 Primary

  in combination with wireless systems (selective distribution or broadcast in wireless communication networks H04W4/06) · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L12/1877

  Measures taken prior to transmission · CPC title