Static dense multicast path and bandwidth management

• US 20050038909A1
• Filed: 06/06/2003
• Published: 02/17/2005
• Est. Priority Date: 06/06/2003
• Status: Active Grant

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Yoshiba, Harumine, Chen, Shiwen
• Granted Patent: US 7,246,172 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

Improved algorithms are provided for performing path management for a plurality of select data transmission sessions in a multicast network. The algorithms include: constructing a weighted graph which represents topology of the network; assigning load correlated costs to network links; and computing least cost paths for each of the data transmission sessions which accounts for global bandwidth utilization.

Claims

1. A method for performing path management for a plurality of select data transmission sessions in a multicast network, the network having a plurality of nodes interconnected by a plurality of links, comprising:

(a) constructing a weighted graph which represents topology of the network;

(b) assigning a cost to each link in the network;

(c) determining a path for a given data transmission session based on link cost and bandwidth utilization;

(d) adjusting link cost associated with each link along the path, such that the adjusted link cost accounts for load on the respective link; and

(e) repeating steps (c) and (d) for the remaining data transmission sessions, thereby assigning a set of flow paths for each of the plurality of selected data transmission sessions.

2. The method of claim 1 wherein the step of constructing a weighted graph further comprises constructed a weighted, directed graph.

3. The method of claim 1 wherein the step of adjusting link cost further comprises increasing the link cost for each link along the path by an incremental cost whose accumulation will not exceed a bound, Ĉ

, where the bound is a function of at least the network topology.

4. The method of claim 3 wherein the bound is defined as Ĉ

=1/|E|, where |E| is a number of edges in the weighted graph.

5. The method of claim 3 wherein the bound is defined as Ĉ

=1/|V|, where |V| is a number of nodes in the weighted graph.

6. The method of claim 1 wherein the step of adjusting link cost minimizes global bandwidth utilization for the plurality of select data transmission sessions.

7. The method of claim 1 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, where the incremental cost is a function of at least one of the total number of transmission sessions, bandwidth demand, link capacity, network topology and a previous cost adjustment to the link cost.

8. The method of claim 3 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, Δ

, where

$\mathrm{\Delta <br><br>}=\frac{b_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{c}}{u_e<br><br><br><br>F<br><br>}$

such that b_i is bandwidth demand of the given data transmission session, u_e is capacity of the given link, and |F| is the total number of data transmission sessions.

9. The method of claim 1 wherein the step of assigning a cost to each link further comprises setting the cost to one for each link.

10. The method of claim 1 wherein the step of determining a path further comprises selecting an optimum path with regard to link cost and bandwidth utilization.

11. The method of claim 1 wherein the step of determining a path further comprises finding a Steiner tree for the given data transmission session, where the Steiner tree roots from a source node associated with the given data transmission session and reaches each destination node associated with the given data transmission session.

12. The method of claim 11 further comprises building a virtual graph by discarding links from the weighted graph which do not meet bandwidth requirement of the given data transmission session and removing orphan nodes from the weighted graph, prior to the step of finding a Steiner tree.

13. The method of claim 11 wherein the step of finding a Steiner tree further comprises using a KMB algorithm.

14. The method of claim 11 wherein the step of finding a Steiner tree further comprises enumerating all possible trees and selecting an optimum tree having a least cost value.

15. The method of claim 1 further comprises determining a total global bandwidth utilization value for the set of assigned flow paths.

16. The method of claim 15 further comprises re-ordering the plurality of selected data transmission sessions and repeating steps c) through (e) for the re-ordered plurality of selected data transmission sessions, thereby assigning a second set of flow paths for each of the plurality of selected data transmission sessions.

17. The method of claim 16 further comprises determining a total global bandwidth utilization value for the second set of assigned flow paths;

and selecting the set of assigned flow paths having a smaller total global bandwidth utilization value, thereby minimizing the global bandwidth utilization.

18. The method of claim 1 wherein the multicast network is further defined as an IP-based surveillance network.

24. The algorithm of claim 18 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, where the incremental cost is a function of the total number of transmission sessions, bandwidth demand, link capacity, network topology and a previous cost adjustment to the link cost.

32. The method of claim 3 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, Δ

, where

$\mathrm{\Delta <br><br>}=\frac{b_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{c}}{u_e<br><br><br><br>F<br><br>}<br><br>c_e<br><br>\left(t-1\right),$

such that b_i is bandwidth demand of the given data transmission session, c_e(t−

1) is a previous incremental cost value, u_e is capacity of the given link, and |F| is the total number of data transmission sessions.

19. A load adaptive cost algorithm for routing a select data transmission session in a multicast network, the network having a plurality of nodes interconnected by a plurality of links, comprising:

constructing a virtual graph from a weighted graph which represents the topology of the network by discarding links from the weighted graph which do not meet bandwidth requirement associated with the select data transmission session and removing orphan nodes from the weighted graph;

finding a Steiner tree for the select data transmission session, where the Steiner tree roots from a source node associated with the select data transmission session and reaches each destination node associated with the select data transmission session, thereby identifying a path for the select data transmission session; and

adjusting link cost associated with each link along the path, such that the adjusted link cost accounts for load on the respective link.

20. The method of claim 19 wherein the step of constructing a virtual graph further comprises constructing the virtual graph from a weighted, directed graph.

21. The algorithm of claim 19 wherein the step of adjusting link cost further comprises increasing the link cost for each link along the path by an incremental cost whose accumulation will not exceed a bound, Ĉ

, where the bound is a function of at least the network topology.

22. The algorithm of claim 21 wherein the bound is defined as Ĉ

=1/|E|, where |E| is a number of edges in the weighted graph.

23. The algorithm of claim 21 wherein the bound is defined as Ĉ

=1/|V|, where |V| is a number of nodes in the weighted graph.

25. The algorithm of claim 21 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, Δ

, where

$\mathrm{\Delta <br><br>}=\frac{b_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{c}}{u_e<br><br><br><br>F<br><br>}$

such that b_i is bandwidth demand of the select data transmission session, u_e is bandwidth capacity of the given link, and |F| is a total number of data transmission sessions.

33. The method of claim 21 wherein the step of adjusting link cost further comprises increasing link cost for a given link along the path by an incremental cost, Δ

, where

$\mathrm{\Delta <br><br>}=\frac{b_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{c}}{u_e<br><br><br><br>F<br><br>}<br><br>c_e<br><br>\left(t-1\right),$

such that b_i is bandwidth demand of the given data transmission session, c_e(t−

1) is a previous incremental cost value, u_e is capacity of the given link, and |F| is the total number of data transmission sessions.

26. An iterative cost adjustment algorithm for a plurality of data transmission sessions in a multicast network, the network having a plurality of nodes interconnected by a plurality of links, comprising

(a) selecting one or more of the plurality of data transmission sessions;

(b) finding a Steiner tree for each select data transmission session, where each Steiner tree roots from a source node associated with a given select data transmission session and reaches each destination node associated with the given select data transmission, thereby identifying a network path for each of the plurality of select data transmission sessions;

(c) determining total bandwidth for each link;

(d) identifying a link where the total bandwidth of the identified link exceeds bandwidth capacity of the identified link; and

(e) adjusting link cost for at least one identified link.

27. The algorithm of claim 26 further comprises identifying one or more links, where the total bandwidth of an identified link exceeds bandwidth capacity of the identified link;

and adjusting link cost for each of the identified links.

28. The algorithm of claim 26 further comprises selecting one of more of the plurality of data transmission sessions, where at least one of the selected data transmission sessions varies from the initial group of selected data transmission session;

and repeating steps (b) through (e).

29. The algorithm of claim 26 further comprises repeating steps (b) through (e) until the total bandwidth for each link is less than or equal to the corresponding bandwidth capacity for each link.

30. The algorithm of claim 26 further comprises repeating steps (b) through (e) until at least one of the total bandwidth for each link is less than or equal to bandwidth capacity for each link or a predefined maximum iteration value.

31. The algorithm of claim 26 further comprises assigning each of the plurality of select data transmission sessions to its respective identified network path when the total bandwidth is less than or equal to bandwidth capacity for each link.