Multicast transfer route setting method, and multicast label switching method for implementing former method

• US 20060147204A1
• Filed: 02/06/2004
• Published: 07/06/2006
• Est. Priority Date: 02/07/2003
• Status: Active Grant

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Uga, Masanori, Sugisono, Koji, Yasukawa, Seisho
• Granted Patent: US 7,583,601 B2
• Time in Patent Office: Days
• US Class Current: 398/26
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/16 Multipoint routing
• 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]
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A method of establishing a multicast transfer route is disclosed that can reduce the cost of entire route under a constraint on delay incurred between starting point and ending points. The method includes the steps of: computing the shortest route with respect to delay connecting the starting point and the plural ending points based on measurement result; computing delay from a node on the shortest route to each ending point and the greatest delay; removing, if the greatest delay satisfies a delay condition, the greatest-cost route from the shortest route in accordance with selection criteria effective for cost reduction; dividing the multicast transfer route into two route trees; and establishing separately computed route as a complementary route that complement the removed route for connecting the two route trees. A method of multicast label switching for realizing the above method is also disclosed. A multicast label switching route is established using hierarchical labels by establishing a common multicast label switching route using a first layer label and establishing plural partial multicast label switching routes for subgroup destinations using lower layer labels. A relay node recognizes the hierarchical labels thereby to label-switch using all hierarchical labels.

Claims

1. A method of setting multicast transfer routes in a multicast network comprising a plurality of points, the multicast transfer routes connecting a given starting point and a plurality of ending points, the multicast network comprising a multicast transfer apparatus provided to each point, a multicast transfer route computing apparatus that computes the multicast transfer routes, and a multicast transfer route setting apparatus that sets the computed multicast transfer routes, the method comprising the following steps:

the multicast transfer apparatus measures a traffic state of each direction in which data flow through each link of the network and requests the multicast transfer route computing apparatus to compute multicast transfer routes by transmitting the measured traffic state;

the multicast transfer route computing apparatus computes a shortest route with respect to delay connecting the starting point and the ending points based on the measured traffic state, computes delay from each point on the shortest route at the same time, and stores the computed delay in a recording medium;

the multicast transfer route computing apparatus computes a greatest delay in the data flow through the computed shortest route;

the multicast transfer route computing apparatus compares the greatest delay with a predefined delay condition, re-defines the delay condition if the greatest delay does not satisfy the delay condition, searches, if a condition that the shortest route satisfies is found, a partial route in the computed shortest route that has two of the same kind or different kinds of the starting point, the ending points, and branching points, as ending nodes of the partial route, that has none of the starting point, the ending points, and branching points in the middle, and that incurs the greatest cost, removes the searched partial route from the computed shortest route thereby to divide the multicast transfer route into two route trees, and sets a route computed separately as a complementary route that complements the removed route to connect the two route trees;

the multicast transfer route computing apparatus informs the multicast transfer route setting apparatus of the result of computation; and

the multicast transfer route setting apparatus sets the multicast transfer route in accordance with the informed result of computation.

2. The method as claimed in claim 1,

wherein

when computing the complementary route, the multicast transfer route computing apparatus computes a route that incurs delay between the starting point and the ending points, that is less than an upper limit, and that incurs the least cost.

3. The method as claimed in claim 2,

wherein

when computing the complementary route, the multicast transfer route computing apparatus selects the starting point of the complementary route to be computed from nodes in the route tree that include the starting point, and computes a route of which ending point is the ending point of the removed route.

4. The method as claimed in claim 3,

wherein

when computing the complementary route, the multicast transfer route computing apparatus applies a known k-th shortest path algorithm to delay, and repeats the applying of the k-th shortest path algorithm while the delay condition is satisfied.

5. The method as claimed in claim 4,

wherein

when computing the complementary route, the multicast transfer route computing apparatus applies the known k-th shortest path algorithm to cost, and repeats the applying of the k-th shortest path algorithm until a route that satisfies the delay condition is found.

6. The method as claimed in claim 4,

wherein

when computing the complementary route, the multicast transfer route computing apparatus uses the delay from the starting point of the multicast transfer route to the starting point of the complementary route stored in the recording medium when the shortest route is computed, and the delay from the ending point of the complementary route to each of the ending points of the multicast transfer route in order to determine whether the result of computation satisfies the delay condition.

7. An apparatus for computing a multicast transfer route in a multicast network, comprising:

a measurement result receiving unit that receives the result of measurement of traffic state in the multicast network;

a measurement information storing unit that stores the received result of measurement;

a measurement result storing unit that causes the measurement information storing unit to store the result of measurement; and

a route computing unit that reads the result of measurement from the measurement information storing unit, and computes the multicast transfer route based on the result of measurement,

wherein

the route computing unit further comprises;

a shortest route delay computing unit that computes a shortest route with respect to delay connecting the starting point and the ending points based on the measured traffic state, computes delay from each point on the shortest route at the same time, and stores the computed delay in a recording medium;

a maximum delay computing unit that computes a greatest delay in the data flow through the computed shortest route;

a maximum cost route searching unit that compares the greatest delay with a predefined delay condition, re-defines the delay condition if the greatest delay does not satisfy the delay condition, searches, if a condition that the shortest route satisfies is found, a partial route in the computed shortest route that has two of the same kind or different kinds of the starting point, the ending points, and branching points as ending nodes of the partial route, that has none of the starting point, the ending points, and branching points in the middle, and that incurs the greatest cost;

a route tree dividing unit that removes the searched partial route from the computed shortest route thereby to divide the multicast transfer route into two route trees; and

a complementary route computing unit that sets a route computed separately as a complementary route that complements the removed route to connect the two route trees.

8. The apparatus as claimed in claim 7,

wherein

the complementary route computing unit computes a route that incurs delay between the starting point and the ending points, that is less than an upper limit, and that incurs the least cost.

9. The apparatus as claimed in claim 8,

wherein

the complementary route computing unit selects the starting point of the complementary route to be computed from nodes in the route tree that includes the starting point, and computes a route of which ending point is the ending point of the removed route.

10. The apparatus as claimed in claim 9,

wherein

the complementary route computing unit applies a known k-th shortest path algorithm to delay, and repeats the applying of the k-th shortest path algorithm while the delay condition is satisfied.

11. The apparatus as claimed in claim 10,

wherein

the complementary route computing unit applies the known k-th shortest path algorithm to cost, and repeats the applying of the k-th shortest path algorithm until a route that satisfies the delay condition is found.

12. The apparatus as claimed in claim 10,

wherein

the complementary route computing unit uses the delay from the starting point of the multicast transfer route to the starting point of the complementary route stored in the recording medium when the shortest route is computed, and the delay from the ending point of the complementary route to each of the ending points of the multicast transfer route in order to determine whether the result of computation satisfies the delay condition.

13. The apparatus as claimed in claim 7, further comprising:

an indicating unit that indicates the result of computation by the route computing unit in a control message for setting the transfer route; and

a transmission unit that transmits the control message through the multicast transfer route indicated by the result of computation.

14. The apparatus as claimed in claim 7, further comprising:

a receiving unit that receives a request for computing the multicast transfer route from a multicast transfer route setting apparatus; and

a transmitting unit that transmits the result of computation to the multicast transfer route setting apparatus.

15. A computer readable recording medium that causes a computer to compute a multicast transfer route based on the result of measurement of traffic state incurred in links in a multicast network, the computer program comprising the steps of:

computing the shortest route with respect to delay connecting the starting point and the ending points based on the measured traffic state;

computing delay from each node on the shortest route at the same time;

storing the computed delay in a recording medium;

computing the greatest delay in data flow through the computed shortest route;

comparing the greatest delay with a predefined delay condition,

re-defining, if the greatest delay does not satisfy the delay condition, the delay condition;

searching, if a condition that the shortest route satisfies is found, a partial-route in the computed shortest route that has two of the same kind or different kinds of the starting node, the ending nodes, and branching nodes as ending nodes thereof, that has none of the starting node, the ending nodes, and branching nodes in the middle, and that incurs the greatest cost;

removing the searched partial route from the computed shortest route thereby to divide the multicast transfer route into two route trees;

setting a route computed separately as a complementary route that complements the removed route to connect the two route trees.

16. The computer readable recording medium as claimed in claim 15,

wherein

when computing the complementary route, the computer computes a route that incurs delay between the starting node and the ending nodes is less than an upper limit, and that incurs the least cost.

17. The computer readable recording medium as claimed in claim 16,

wherein

the computer selects the starting node of the complementary route to be computed from the nodes in the route tree that includes the starting node, and computes a route of which ending node is the ending node of the removed route.

18. The computer readable recording medium as claimed in claim 17,

wherein

the computer applies a known k-th shortest path algorithm to the delay, and repeats the application while the delay condition is satisfied.

19. The computer readable recording medium as claimed in claim 18,

wherein

the computer applies the known k-th shortest path algorithm to the cost, and repeats the application until a route that satisfies the delay condition is found.

20. The computer readable recording medium as claimed in claim 18,

wherein

the computer uses the delay from the starting node to the starting node of the complementary route stored in the recording medium when the shortest route is computed, and the delay from the ending node of the complementary route to the ending nodes in the downstream thereof in order to determine whether the result of computation satisfies the delay condition.

21. A recording medium storing a computer program that causes a computer to compute a multicast transfer route based on the result of measurement of traffic state incurred in links in a multicast network,

wherein

the recording medium stores the computer program as claimed in claim 15.

22. A method of multicast label switching in which label switching routes are established for multicast distribution from a multicast source node to a group of multicast leaf nodes, the method comprising the steps of:

establishing a point-to-multipoint label switching route of a first layer from the multicast source node to all multicast leaf nodes;

establishing a plurality of label switching routes of a second layer that configure partial trees of the label switching route of the first layer using second layer labels for respective subgroups of leaf nodes, the subgroup of leaf nodes being extracted as destinations from the group of leaf nodes for which the point-to-multipoint label switching route of the first layer has been established;

allocating traffics addressed to a destination leaf group corresponding to the second layer labels to a corresponding hierarchical labels using the first layer label switching route and the second layer label switching routes by an input label edge router;

label-switching packets in accordance with a label pair of the first layer and the second layer by a relay label switch router;

if a relay node is designated as a branching node of the point-to-multipoint label switching route of the first layer copying the traffic for each output branch and replacing input label pair with output labels corresponding to a plurality of output branches;

switching the traffic to an output line by an output label edge router, with identifying the group of the input hierarchical labels and removing the labels; and

label-switching traffic of each second layer subgroup using the point-to-multipoint label switching routes of the second layer forming the first layer partial tree forming different destination subgroups of the first layer leaf group nodes in the point-to-multipoint label switching routes with the first layer label switching route shared.

23. The method as claimed in claim 22,

wherein

a plurality of label switching routes of a third layer is provided in the multicast label switching routes of the second layer using the sub-tree forming a partial topology of the second layer label switching routes to the leaf nodes configuring a subset of leaf nodes forming the second layer label switching route;

if the label switching routes need to be classified into subgroups, establishing label switching routes of a lower layer in a recursive manner;

performing multicast-label-switching by the subgroup using the recursively established hierarchical label switching routes.

24. The method as claimed in claim 22,

wherein

connecting all provider edge routers of a provider network accommodating the VPN sites with first layer point-to-multipoint multicast LSP in a full-mesh manner;

establishing second layer multicast label switch routes for each VPN site accommodated in the provider network;

in the case in which the second layer label switch routes are established, if provider edge routers forming the VPN is the leaf node of the multicast label switch routes, adjusting the second layer label switching route depending on the VPN sites accommodated in each leaf;

configuring the second layer label switch route in the first layer multicast tree connecting the provider edge routers of the VPN.

25. The method as claimed in claim 24,

wherein

in the case of a multicast distribution route having a plurality of different site destinations in the VPN site, a third layer multicast distribution route is established as the partial tree route of the second layer multicast distribution route in the third layer under the second layer, of which destination leaf nodes are only VPN sites corresponding to respective multicast distribution routes;

even the multicast traffic belonging to the same VPN is distributed to only the VPN sites that wishes to receive multicast traffic.

26. The method as claimed in claim 22,

wherein

communication method is provided as a label switch router function;

and

the communication method is operated as the input multicast label switch router, the relay multicast label switch router, and the output multicast label switch router.