QoS-based routing method

• US 6,813,272 B1
• Filed: 06/16/2000
• Issued: 11/02/2004
• Est. Priority Date: 06/23/1999
• Status: Expired due to Term

• Current Assignee: Korea Telecommunication Authority
• Original Assignee: Korea Telecommunication Authority
• Inventors: An, Sun Shin, Yoon, Young Hyun, Choi, Eun Ho, Jeon, Hong Beom, Kim, Doo Seok
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US09/595,862
• Time in Patent Office: 1,600 Days
• Field of Search: 370/230, 370/235, 370/238, 370/395.1, 370/395.2, 370/390, 370/396, 370/408, 370/432, 370/465, 370/468, 370/237, 370/238.1, 370/395.21, 370/392
• US Class Current: 370/395.21
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/52 Multiprotocol routers

Abstract

A routing method with routing algorithms applicable to a one-level hierarchical network, including a first algorithm in which a shortest one among all paths established in association with one destination is selected, a second algorithm in which the first method is conducted in a distributed fashion to achieve a fast routing, and a third algorithm in which any one of paths established in association with one destination may be selected as a shortest path when the QoS value calculated in association therewith is more optimum than a required reference QoS value, for preventing problems caused by errors at the single path. The method also provides algorithms that are modified versions of the second and third algorithm for the multi-level hierarchical network. Accordingly, the method is advantageous in that users can select an algorithm, most suitable for the system environment, from the above algorithms.

Claims

1. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; and

(B) designating a routing start point after completion of the initialization, and executing a routing process from the designated routing start point,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

2. The routing method in accordance with claim 1, wherein the step (A) comprises the steps of:

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about nodes linked between a source note and the optional node along a shortest path, and a total value of QoSs accumulated at the optional node along the shortest path;

(A-c) initializing, for optional node, a neighbor set containing information about neighbor nodes linked to the node;

(A-d) determining links associated with the optional node along with respective QOS values of the associated links;

(A-e) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-f) repeatedly executing the steps (A-b) to (A-e); and

(A-g) designating a selected one of the nodes as a routing start point, initializing the node information of the route set of the selected node with the routing start point, and initializing the total QoS value information of the route set of the selected node with a value of 0, to begin a routing procedure starting from the selected node.

3. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links; and

(B) designating a routing start point after completion of the initialization, and executing a routing process from the designated routing start point,

wherein the step (A) for constructing the neighbor set for the optional node comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about nodes linked between a source node and the optional node along a shortest path, and a total value of QoSs accumulated at the optional node along the shortest path;

(A-c) initializing, for the optional node, a neighbor set containing information about neighbor nodes linked to the node;

(A-d) determining links associated with the optional node along with respective QoS values of the associated links;

(A-e) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-f) repeatedly executing the steps (A-b) to (A-e); and

(A-g) designating a selected one of the nodes as a routing start point, initializing the node information of the route set of the selected node with the routing start point, and initializing the total QoS value information of the route set of the selected node with a value of 0, to begin a routing procedure starting from the selected node, and wherein the step (B) comprises the steps of;

(B-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-b) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is less than the current total QoS value;

(B-c) if it is determined at step (B-b) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-d) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-c) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-e) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node; and

(B-f) subtracting the resultant route set of the current node from the resultant neighbor set of the current node; and

(B-g) repeatedly executing the steps (B-a) to (B-f) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

4. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

5. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made, wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-e) repeatedly executing the steps (A-b) to (A-d);

(A-f) designating a selected one of the nodes as a routing start point, determining whether or not the selected node corresponds to a source node;

(A-g) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(A-h) if the selected node does not correspond to the source node, than waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, and calling the routing means in response to a reception of the routing message at the selected node.

6. The routing method in accordance with claim 5, wherein the step (A-d) for constructing the neighbor set for the optional node comprises the steps of:

determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node; and

if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node, then additionally registering the neighbor node in the neighbor set of the optional node.

7. The routing method in accordance with claim 5, wherein the step (B) comprises the steps of:

(B-a) calculating a total value of QoSs accumulated at a node currently route along a current path;

(B-b) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the first current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-c) if it is determined at step (B-b) that the current total QoS value is more optimum than the previous total QoS value then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-d) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-c) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-e) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-f) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(B-g) repeatedly executing the steps (B-a) to (B-f) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

8. A routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS value which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

9. A routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made, wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-e) repeatedly executing the steps (A-b) to (A-d);

(A-f) designating a selected one of the nodes as a routing start point, determining whether or not the selected node corresponds to a source node;

(A-g) if the selected node corresponds to the source node, initializing the node information of the route set of the selected node with the source node, then initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(A-h) if the selected node does not correspond to the source node, then waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, along with the reference QoS value, and calling the routing means in response to a reception of the routing message at the selected node.

10. The routing method in accordance with claim 9, wherein the step (A-d) for constructing the neighbor set for the optional node comprises the steps of:

determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node; and

if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node, then additionally registering the neighbor node in the neighbor set of the optional node.

11. The routing method in accordance with claim 9, wherein the step (B) comprises the steps of:

(B-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-b) determining whether or not the currently calculated total QoS value meets the reference QoS value, and stopping the current routing when the currently calculated total QoS value does not meet the reference QoS value;

(B-c) if the currently calculated total QoS value meets the reference QoS value, then comparing the currently calculated total QoS value with a previously calculated total of QoS accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-d) if it is determined at step (B-c) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-f) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-g) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of infuriation about the resultant route set along with the reference QoS value, to the node waiting for the message; and

(B-g) repeatedly executing the steps (B-a) to (B-f) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

12. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

13. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting a shortest path among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made, wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-e) repeatedly executing the steps (A-b) to (A-d);

(A-f) designating a selected one of the nodes as a routing start point, determining whether or not the selected node corresponds to a source node;

(A-g) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(A-h) if the selected node does not correspond to the source node, then waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, and calling the routing means in response to a reception of the routing message at the selected node.

14. The routing method in accordance with claim 13, wherein the step (A-d) for constructing the neighbor set for the optional node comprises the steps of:

determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node; and

if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node, then additionally registering the neighbor node in the neighbor set of the optional node.

15. The routing method in accordance with claim 13, wherein the step (B) comprises the steps of:

(B-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-b) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-c) if it is determined at step (B-b) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-d) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-c) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-e) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-f) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(B-g) repeatedly executing the steps (B-a) to (B-f) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

16. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

17. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made, wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values;

(A-e) repeatedly executing the steps (A-b) to (A-d);

(A-f) designating a selected one of the nodes as a routing start point, determining whether or not the selected node corresponds to a source node;

(A-g) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(A-h) if the selected node does not correspond to the source node, then waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, along with the reference QoS value, and calling the routing means in response to a reception of the routing message at the selected node.

18. The routing method in accordance with claim 18, wherein the step (A-d) for constructing the neighbor set for the optional node comprises the steps of:

determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node; and

if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node, then additionally registering the neighbor node in the neighbor set of the optional node.

19. The routing method in accordance with claim 18, wherein the step (B) comprises the steps of:

(B-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-b) determining whether or not the currently calculated total QoS value meets the reference QoS value, and stopping the current routing when the currently calculated total QoS value does not meet the reference QoS value;

(B-c) if the currently calculated total QoS value meets the reference QoS value, then comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-d) if it is determined at step (B-c) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node

(B-f) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-g) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of information about the resultant route set along with the reference QoS value, to the node waiting for the message; and

(B-h) repeatedly executing the steps (B-a) to (B-g) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

20. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and each of destination nodes for multicasting comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and

(C) controlling the multi-casting routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

21. The routing method in accordance with claim 20, wherein the step (A) comprises the steps of:

(A-a) initializing respective QoS valves of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated wvith the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values; and

(A-e) repeatedly executing the steps (A-b) to (A-d).

22. A routing method in a data communication network for selecting a shortest path among a plurality of paths established between a single source node and each of destination nodes for multicasting comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and

(C) controlling the multi-casting routing means to execute the routing process in response to the call, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links;

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values; and

(A-e) repeatedly executing the steps (A-b) to (A-d), and wherein the step (B) comprises the steps of;

(B-a) designating a selected one of the nodes as a routing start point, and determining whether or not the selected node corresponds to a source node;

(B-b) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, transmitting a multi-casting routing request message to nodes neighboring to the source node, and waiting for a path detection message generated in response to the multi-casting routing request message for a predetermined period of delay time; and

(B-c) if the selected node does not correspond to the source node, then waiting for a routing message subsequently transmitted to the selected node during a routing executed in association with a node other than the selected node, and calling, in response to a reception of the routing message at the selected node, the multi-casting routing means or weight comparing and routing means selected by the routing message.

23. The routing method in accordance with claim 22, wherein the step (B-c) comprises the steps of:

(B-c-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-c-b) determining whether or not the current node corresponds to one of the destination nodes, and if the current node corresponds to one of the destination nodes, then determining whether or not the currently calculated total QoS value meets a predetermined reference QoS value;

(B-c-c) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path when the current node does not corresponds to any one of the destination nodes, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-c-d) if it is determined at step (B-b) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-c-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-c-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-c-f) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-c-g) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(B-c-h) repeatedly executing the steps (B-c-a) to (B-c-g) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

24. The routing method in accordance with claim 23, wherein the step (B-c-b) comprises the steps of informing the source node of a path detection when it is determined that the currently calculated total QoS value meets a predetermined reference QoS value;

and

transmitting a path detection message to a node just preceding to the current node to determine a weightiest one of intermediate paths established between the source node and the destination node by a value of 1.

25. The routing method in accordance with claim 22, wherein the step (B) comprises the steps of:

determining a weightiest one of paths established between the source node and the destination nodes in response to a reception of the path detection message, and informing the destination nodes of a detection of the weightiest path; and

informing the destination nodes of a routing failure when there is not path detection message received within the predetermined period of delay time.

26. The routing method in accordance with claim 22, wherein the weight comparing and routing means carries out, in response to the calling associated therewith at the step (C), the steps of:

determining whether or not there is a path having a higher weight than that stored in the selected node; and

if there is a weightier path, substituting the stored weight of the selected node by the weight of the weightier path, and incrementing the substituted weight by a value of 1; and

subtracting the selected node from a route set indicative of information about the weightier path, and transmitting the resultant route set along with the resultant weight associated therewith, as a path detection message, to a node just preceding the selected node.

27. A routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

28. The routing method in accordance with claim 27, wherein the step (A) comprises the steps of:

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values.

29. A routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QOS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while reflecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values, and

wherein the step (B) comprises the steps of;

(B-a) designating a selected one of the nodes as a routing start point, and determining whether or not the selected node corresponds to a source node;

(B-b) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(B-c) if the selected node does not correspond to the source node, then waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, and calling the routing means in response to a reception of the routing message at the selected node.

30. A routing method in a data communication network for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of the nodes, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node alone with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values, and wherein the step (C) comprises the steps of;

(C-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(C-b) comparing the currently calculated total QOS value with a previously calculated total value of QoSs accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(C-c) if it is determined at step (C-b) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the current path has at least one node overlapping with other paths previously routed;

(C-d) if the current path has no overlapping node, then determining whether or not the last node of the current path corresponds to the current node;

(C-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (C-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(C-f) registering the total QoS value calculated at the step (C-a) in the total QoS value term of the route set of the current node, and inputting the current path at an appropriate position in the route set of the current node in accordance with a predetermined priority order

(C-g) adding information about the current node, as hop information, to respective neighbor sets of the nodes of all the previous paths while adding information about the current path, as route information, to respective route sets of the nodes of all the previous paths;

(C-h) transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(C-i) repeatedly executing the steps (C-a) to (C-h) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

31. The routing method in accordance with claim 30, further comprising the step of:

if the current path has at least one overlapping node, stopping the routing process associated with the current node.

32. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting a shortest path among a plurality of paths established between a single source node and each of destination nodes comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and

(C) controlling the multi-casting routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node along with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

33. The routing method in accordance with claim 32, wherein the step (A) comprises the steps of:

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values.

34. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting a shortest path among a plurality of paths established between a single source node and each of destination nodes comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and Quality of Service (QoS) values for the links;

(B) designating a routing start point after completion of the initialization, calling a multi-casting routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the multi-casting routing means responding to the call; and

(C) controlling the multi-casting routing means to execute the routing process in response to the call in such a fashion that those of the layers once routed are not routed again, and to transmit the routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values, and wherein the step (B) comprises the steps of;

(B-a) designating a selected one of the nodes as a routing start point, and determining whether or not the selected node corresponds to a source node;

(B-b) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, transmitting a multi-casting routing request message to nodes neighboring to the source node, and waiting for a path detection message generated in response to the multi-casting routing request message for a predetermined period of delay time; and

(B-c) if the selected node does not correspond to the source node, then waiting for a routing message subsequently transmitted to the selected node during a routing executed in association with a node other than the selected node, and calling, in response to a reception of the routing message at the selected node, the multi-casting routing means or weight comparing and routing means selected by the routing message.

35. The routing method in accordance with claim 34, wherein the step (B-c) comprises the steps of:

(B-c-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(B-c-b) determining whether or not the current node corresponds to one of the destination nodes, and if the current node corresponds to one of the destination nodes, then determining whether or not the currently calculated total QoS value meets a predetermined reference QoS value;

(B-c-c) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path when the current node does not corresponds to any one of the destination nodes, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(B-c-d) if it is determined at step (B-b) that the current total QoS value is (less than) more optimum than the previous total QoS value, then determining whether or not the last node of the current path corresponds to the current node, to conduct a correction of routing information based on the current path;

(B-c-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (B-c-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(B-c-f) registering the total QoS value calculated at the step (B-a) in the total QoS value term of the route set of the current node, and registering the current path in the route term of the route set of the current node;

(B-c-g) subtracting the resultant route set of the current node from the resultant neighbor set of the current node, and transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(B-c-h) repeatedly executing the steps (B-c-a) to (B-c-g) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

36. The routing method in accordance with claim 35, wherein the step (B-c-b) comprises the steps of informing the source node of a path detection when it is determined that the currently calculated total QoS value meets a predetermined reference QoS value;

and

transmitting a path detection message to a node just preceding to the current node to determine a weightiest one of intermediate paths established between the source node and the destination nodes while substituting a weight of the current node by a value of 1.

37. The routing method in accordance with claim 34, wherein the step (B) comprises the steps of:

determining a weightiest one of paths established between the source node and the destination nodes in response to a reception of the path detection message, and informing the destination nodes of a detection of the weightiest path; and

informing the destination nodes of a routing failure when there is no path detection message received within the predetermined period of delay time.

38. The routing method in accordance with claim 34, wherein the weight comparing and routing means carries out, in response to the calling associated therewith at the step (C), the steps of:

determining whether or not there is a path having a higher weight than that stored in the selected node; and

if there is a weightier path, substituting the stored weight of the selected node by the weight of the weightier path, and incrementing the substituted weight by a value of 1; and

subtracting the selected node from a route set indicative of information about the weightier path, and transmitting the resultant route set along with the resultant weight associated therewith, as a path detection message, to a node just preceding the selected node.

39. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) includes the step of constructing a neighbor set for an optional node based on links and QoS values which are obtained by determining the links associated with the optional node alone with the respective QoS values of the associated links, by determining whether or not a node neighboring to the optional node is not the same as the optional node while being linked to the optional node and additionally registering the neighbor node in the neighbor set of the optional node if it is determined that the node neighboring to the optional node is not the same as the optional node while being linked to the optional node.

40. The routing method in accordance with claim 39, wherein the step (A) comprises the steps of:

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values.

41. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing in the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with restective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values, and wherein the step (B) comprises the steps of;

(B-a) designating a selected one of the nodes as a routing start point, and determining whether or not the selected node corresponds to a source node;

(B-b) if the selected node corresponds to the source node, then initializing the node information of the route set of the selected node with the source node, initializing the QoS value information of the route set of the selected node with a value of 0, and calling the routing means; and

(B-c) if the selected node does not correspond to the source node, then waiting for route information and an associated total QoS value subsequently transmitted, as a routing message, to the selected node during a routing executed in association with a node other than the selected node, and calling the routing means in response to a reception of the routing message at the selected node.

42. A routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting paths satisfying a reference Quality of Service (QoS) value among a plurality of paths established between a single source node and a single destination node comprising the steps of:

(A) initializing a set of information about links of nodes in all paths existing n the network and QoS values for the links;

(B) designating a routing start point after completion of the initialization while setting the reference QoS value, calling a routing means to execute a distributed routing process from the designated routing start point, and waiting for a routing message from the routing means responding to the call; and

(C) controlling the routing means to execute the routing process in response to the call in such a fashion that only one of routed paths having at least one overlapping node thereamong is selected while rejecting the remaining routed paths, and to transmit the resultant routing message to the routing start point from which the call is made,

wherein the step (A) comprises the steps of;

(A-a) initializing respective QoS values of the links;

(A-b) initializing, for an optional one of nodes existing in an optional one of the layers, a route set containing information about the optional node and a neighbor set containing information about neighbor nodes linked to the optional node;

(A-c) determining links associated with the optional node along with respective QoS values of the associated links; and

(A-d) constructing the neighbor set for the optional node, based on the determined links and QoS values, and wherein the step (C) comprises the steps of;

(C-a) calculating a total value of QoSs accumulated at a node currently routed along a current path;

(C-b) comparing the currently calculated total QoS value with a previously calculated total value of QoSs accumulated at the current node along another path, and stopping the current routing while waiting for another routing call when the previous total QoS value is more optimum than the current total QoS value;

(C-c) if it is determined at step (C-b) that the current total QoS value is more optimum than the previous total QoS value, then determining whether or not the current path has at least one node overlapping with other paths previously routed;

(C-d) if the current path has no overlapping node, then determining whether or not the last node of the current path corresponds to the current node;

(C-e) additionally registering the last node of the current path in the neighbor set of the current node when it is determined at the step (C-d) that the last node of the current path does not correspond to the current node, while omitting the additional registration when it is determined that the last node of the current path corresponds to the current node;

(C-f) registering the total QoS value calculated at the step (C-a) in the total QoS value term of the route set of the current node, and inputting the current path at an appropriate position in the route set of the current node in accordance with a predetermined priority order;

(C-g) adding information about the current node, as hop information, to respective neighbor sets of the nodes of all the previous paths while adding information about the current path, as route information, to respective route sets of the nodes of all the previous paths;

(C-h) transmitting a routing message, indicative of information about the resultant route set, to the node waiting for the routing message; and

(C-i) repeatedly executing the steps (C-a) to (C-h) for each of neighbor nodes registered in the neighbor set of the current node, to conduct for a routing for the neighbor node.

43. The routing method in accordance with claim 42, further comprising the step of:

if the current path has at least one overlapping node, stopping the routing process associated with the current node.