Method for providing QoS (quality of service)—guaranteeing multi-path and method for providing disjoint path using the same

• US 7,366,114 B2
• Filed: 07/18/2003
• Issued: 04/29/2008
• Est. Priority Date: 08/28/2002
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Park, Hye Kyeong, Kim, Tae Il
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): SMITH, MARCUS
• Application Number:
  US10/622,877
• Publication Number:
  US 20040042473A1
• Time in Patent Office: 1,747 Days
• Field of Search: 370254-256
• US Class Current: 370/256
• 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/124 using a combination of metrics
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for providing a QoS-guaranteeing multi-path and a method for providing disjoint paths using the same are provided. The method configures the shortest path tree by adapting the start node “s” and the destination node “d”. When a new node is selected as a tree node in a tree configuration process according to the “s” or the “d”, the closest node to either the “s” or the “d” is selected. If a specified node “v” is contained in both a tree oriented from the “s” and another tree oriented from the “d”, one path of “s”-“v”-“d” is created. If all nodes are contained in either the tree of “s” or the other tree of “d”, then a program of path creation process is terminated. Further, the method further includes a step for determining two disjoint paths from the “s” to the “d” among the found multiple paths above.

Claims

1. A method for performing a process associated with a QoS-guaranteeing multi-path in a path-based communication network having a plurality of nodes, comprising the steps of:

a) determining a start node, a destination node and a requirement condition associated with a reference cost consumed in a range from the start node to the destination node;

b) creating a first tree adapting the start node as its root and a second tree adapting the destination node as its root, including nodes close to the start node in a first node group, and including nodes close to the destination node in a second node group;

c) selecting a node having a minimum cost associated with the roots from among a plurality of nodes contained in the first and second node groups, and including the selected node having the minimum cost in a tree of a corresponding root;

d) if the selected node included in the tree at the step (c) is also included in the first and second trees, and a cost consumed in the range from the start node to the destination node on the basis of the selected node is less than the reference cost, providing a corresponding path associated with the cost;

e) including a nearby node of the selected node in a node group having the selected node when the selected node included in the tree at the step (c) is also included in either one of the first and second trees, comparing two paths ranging from a root to the nearby node when the nearby node is previously included in the node group, and deleting a link of a cheaper one of the two paths; and

f) determining whether there is a node contained in the first node group and the second node group, repeatedly performing a process from the step (c) when the node is found in the first and second node groups, or terminating the process from the step (c) when no node is found in the first and second node groups.

2. The method according to claim 1, further comprising the steps of:

g) determining a maximum number of paths satisfying the determined requirement condition; and

h) if a number of output paths is higher than the maximum number of paths, terminating a path setup program.

3. The method according to claim 1, wherein the step (d) for outputting a path includes the steps of:

d1) determining whether the same path as a currently calculated path is previously outputted; and

d2) if the same path as the current path is not outputted, outputting a corresponding path equal to the current path.

4. The method according to claim 3, wherein the step (d1) includes the step of:

if it is determined that a node equal to another node “

Si+1”

is found in child nodes of output paths (S1, S2, . . . , Si, . . . , Sn) from a start root S1 to a root Si, determining that the same path as a path associated with the node “

Si+1”

has been previously outputted.

5. The method according to claim 3, wherein the step (d2) includes the steps of:

if it is determined that a node equal to another node “

Si+1”

is not found in son nodes of output paths (S1, S2, . . . , Si, . . . , Sn) from a start root S1 to a root Si, creating the node “

Si+1”

as a child node of the node Si and outputting the path associated with the node “

Si+1”

.

6. The method as set forth in claim 1, further comprising the steps of:

i) selecting a first path from the start node to the destination node from among a plurality of paths outputted at the step (d); and

j) selecting at least one second path disjointed from an intermediate node existing in the first path from among multiple paths ranging from the start node to the destination node, and providing a disjoint path.

7. The method as set forth in claim 6, wherein the step (h) includes the steps of:

h1) determining whether the start node or the destination node has a degree of less than 2; and

h2) if the start node or the destination node has a degree of less than 2, determining that there is no disjoint path.

8. The method as set forth in claim 1, further comprising the steps of:

k) selecting two paths from among a plurality of paths outputted at the step (d); and

l) determining whether the selected two paths are disjointed from each other, and providing a disjoint path according the determination result.

9. The method as set forth in claim 8, wherein the step (l) includes the step of:

determining whether a nearby node of the start node of a first node contained in the two paths is equal to that of the destination node of a second node contained in the two paths, and determining a disjoint path according to the determination result.

10. A computer-readable recording medium for storing a program executed by a computer, said program comprising the steps of:

determining a start node, a destination node and a requirement condition associated with a reference cost consumed in a range from the start node to the destination node;

b) creating a first tree adapting the start node as its root and a second tree adapting the destination node as its root, including nodes close to the start node in a first node group, and including nodes close to the destination node in a second node group;

c) selecting a node having a minimum cost associated with the roots from among a plurality of nodes contained in the first and second node groups, and including the selected node having the minimum cost in a tree of a corresponding root;

d) if the selected node included in the tree at the step (c) is also included in the first and second trees, and a cost consumed in the range from the start node to the destination node on the basis of the selected node is less than the reference cost, outputting a corresponding path associated with the cost;

e) including a nearby node of the selected node in a node group having the selected node when the selected node included in the tree at the step (c) is also included in either one of the first and second trees, comparing two paths ranging from a root to the nearby node when the nearby node is previously included in the node group, and deleting a link of a cheaper one of the two paths; and

f) determining whether there is a node contained in the first node group and the second node group, repeatedly performing a process from the step (c) when the node is found in the first and second node groups, or terminating the process from the step (c) when no node is found in the first and second node groups.