Static dense multicast path and bandwidth management
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
33 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 24, 32)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 25, 33)
-
-
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. - View Dependent Claims (27, 28, 29, 30, 31)
-
Specification