QoS-based routing method

[0002] 1. Field of the Invention

[0003] The present invention relates to a routing method providing a requested quality of service, and more particularly to a routing method for establishing a routing based on a specific Quality of Service (QoS) requested in a transmission of multimedia information in various data communication networks.

[0004] 2. Description of the Prior Art

[0005] One of general routing methods is a distance vector algorithm which is mainly used as a routing algorithm in the Internet.

[0006] An operation of such a distance vector algorithm will be described in brief hereinafter. In accordance with the distance vector algorithm, each of nodes linked to one of networks communicating together initializes the distance value associated therewith to be 0 (zero) while initializing respective distance values of the remaining nodes linked to the network to be infinite. In this state, a routing procedure is conducted for every node in order to find the shortest distance between the node and each of the remaining nodes. The shortest distances found for all nodes are registered in a routing table N. The following expression is an expression for deriving a shortest distance between two nodes:

[0007] D(v)←Min[(D(ν), D(ω)+L(ω,ν))

[0008] where, “D(ν)” represents the distance between an origin node, namely, a current node, and a destination node, and “L(ω,ν)” represents the distance between a node ω and a node ν.

[0009] Information about the shortest distance derived for each node is transmitted to all nodes adjacent thereto. This procedure is repeated for each node until the node completely collects the entire shortest distance information associated with all nodes linked thereto.

[0010] Where no further information about path change is generated from any node and where there is no further information, being transmitted, in links connecting nodes, the path information collection procedure is completed because that condition corresponds to a complete collection of the entire shortest distance information.

[0011] The above mentioned distance vector algorithm provides an important advantage in that it is simple. As apparent from the above procedures, this algorithm can be easily implemented because it is very simple.

[0012] However, the distance vector algorithm has disadvantages in that it takes a relatively extended period of time and consumes a relatively increased quantity of network bandwidth because each node should collect information about all paths associated therewith. There is a more serious disadvantage in that a ping-pong phenomenon may occur. That is, information changed in each node in an environment involving a frequent change in network state and transmitted from each node to adjacent nodes may be returned to the node. Furthermore, intermediate nodes have no function for determining an optimum QoS.

[0013] Another routing method is a link-state algorithm. This link-state algorithm is a routing algorithm also called a “Shortest Path First” algorithm. The link-state algorithm is provided with a distributed data based model while using a “Dijkstra's Shortest Path” algorithm in order to determine a shortest path.

[0014] An operation of such a link-state algorithm will be described in brief hereinafter. In accordance with the link-state algorithm, each local node supplies the current link state thereof to other nodes. The status information of each node includes information about an interface, being in operation, of the node, transmission time taken to transmit information via the interface, and destinations to which the interface is connected.

[0015] The state information of each node is transmitted to other nodes using a flooding function. Each node receives such information from other nodes and stores the received information in its link-state database.

[0016] Using the stored information, each node determines the shortest distance path between the node and each of other nodes in accordance with the “Dijkstra's Shortest Path” algorithm and stores it in its routing table.

[0017] However, the link-state algorithm has a disadvantage in that it is complex, as compared to the distance vector algorithm. There is another disadvantage in that a large quantity of bandwidth is consumed because link state information should be periodically supplied.

[0018] In accordance with the above mentioned link-state algorithm, an optimum path is initially established, based on all routing information completely collected. For this reason, when different nodes request different multimedia services, respectively, it is impossible to provide a variety of QoS meeting about the requested multimedia services because all link states and all distance vectors have been fixedly set in association with the optimum paths initially established for those nodes, so that they may be unsuitable.

[0019] For another routing method, there is a Dynamic Source Routing (DSR) algorithm. This DSR algorithm is an algorithm proposed by the “MANET” group of Internet Engineering Task Force (IETF). The DSR algorithm is not a general routing algorithm used in cable and radio environments, but a routing algorithm for “ad-hoc” networks, that is, specific radio mobile networks in which no base station exists. In this algorithm, any provision of QoS is not taken into consideration in association with multimedia services.

[0020] Such a DSR algorithm will be described in brief hereinafter. In accordance with the DSR algorithm, a source node, which requests transmission of data, forwards a request for setting of routing to all nodes adjacent thereto toward a destination node.

[0021] Each intermediate node, which receives routing setting requests respectively transmitted from other intermediate nodes, but being the same as that originally transmitted from the source node, forwards only the routing setting request, first-arrived thereto, toward the destination node while rejecting the remaining routing setting requests arriving later so as to avoid their transmission toward the destination node.

[0022] The routing setting request arriving to the destination node is returned to the source node along with a list of intermediate nodes through which the routing setting request was passed during the transmission thereof to the destination node. Thus, the shortest path between the source and destination nodes is established. In this state, all data packets to be transmitted contains information about the list of the intermediate nodes through which the packets are to pass. Accordingly, the data packets are transmitted in accordance with an order determined by the intermediate node list.

[0023] However, the above mentioned DSR algorithm has a disadvantage in that it can operate only in a specific network environment, that is, the “ad-hoc” radio network. Since the DSR algorithm is configured to always transmit packets along a path involving the shortest time delay, there is also a disadvantage in that no consideration for multimedia services is made.

[0024] In order to implement a routing algorithm capable of providing multimedia services in cable and radio networks, the following factors should be taken into consideration.

[0025] First, the most important problem involved in design of a routing algorithm for multimedia services is that an optimum path meeting all parameters cannot exist in accordance with conventional techniques even though at least one optimum path meeting each of those parameters may exist. Where two parameters, for example, bandwidth and time delay, are taken into consideration for a routing, the optimum path for bandwidth and the optimum path for time delay are different from each other in most cases. Therefore, it is necessary to provide a decisive protocol for determining whether or not a path established is optimum for a desired QoS, in association with a routing providing QoS.

[0026] Second, there is another problem in that mobile terminals operating in radio networks are frequently movable. Such mobile terminals frequently change the topology of the network while moving. For this reason, static routing methods are unsuitable in which a communication path is established prior to a request for a routing. Therefore, adaptive routing protocols should be taken into consideration.

[0027] Third, terminals operating in radio networks have a reduced memory space and a reduced computation ability, as compared to routers operating in cable networks. For this reason, routing protocols requiring a complex computation are unsuitable. Therefore, simple routing protocols are necessary.

[0028] Fourth, terminals operating in radio networks should run a distributed routing protocol operable in distributed environments. In the case of a protocol, in which a path is established for a routing by a central node in a radio network environment, frequent changes of data occur due to the frequent-movement characteristics of the radio terminals. It is also necessary to use terminal routing information at intervals of time for a maintenance of changed data. This results in an increased consumption of network bandwidth. For this reason, the above mentioned protocol is unsuitable in radio network environments. Consequently, for radio mobile communications, it is necessary to provide a distributed routing protocol in which routers operate to maintain and manage a minimum quantity of information required for a routing.

[0029] Therefore, the present invention has been made in view of the above mentioned problems involved in the prior art, and an object of the invention is to provide a QoS-based optimum routing method capable of providing QOS for multimedia services in general cable and radio networks.

[0030] Another object of the invention is to provide a routing method for providing route information about nodes passed between a source node and a destination node to those nodes in order to prevent re-transmission of the route information to nodes already passed, thereby preventing a waste of CPU capacity and bandwidth.

[0031] Another object of the invention is to provide a routing method capable of achieving a reduction in routing time.

[0032] Another object of the invention is to provide a routing method capable of using various route information arrived at a destination node to establish a back-up path or a multi-path for an increase in transmission rate.

[0033] Another object of the invention is to provide a routing method for providing efficient data services in an ATM-based multi-level hierarchical network.

[0034] In accordance with one aspect, the present invention provides a routing method in a data communication network for selecting the 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.

[0035] In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting the 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.

[0036] In accordance with another aspect, the present invention provides 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.

[0037] In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting the 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.

[0038] In accordance with another aspect, the present invention provides 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.

[0039] In accordance with another aspect, the present invention provides a routing method in a data communication network for selecting the 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.

[0040] In accordance with another aspect, the present invention provides 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.

[0041] In accordance with another aspect, the present invention provides a routing method in a multi-level hierarchical data communication network having a plurality of layers for selecting the 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 multio-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.

[0042] In accordance with another aspect, the present invention provides 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.

[0043] The above objects, and other features and advantages of the present invention will become more apparent after a reading of the following detailed description when taken in conjunction with the drawings, in which:

[0044] FIG. 1 is a flow chart illustrating a Generic Shortest Path Algorithm (GSPA) according to a first embodiment of the present invention;

[0045] FIG. 2 is a flow chart illustrating the routing procedure of FIG. 1 in detail;

[0046] FIG. 3 is a flow chart illustrating a Distributed Generic Shortest Path Algorithm (DGSPA) in accordance with a second embodiment of the present invention;

[0047] FIG. 4 is a flow chart illustrating the routing procedure of FIG. 3 in detail;

[0048] FIG. 5 is a flow chart illustrating a QoS Restricted Generic Shortest Path Algorithm (QRDGSPA) in accordance with a third embodiment of the present invention;

[0049] FIG. 6 is a flow chart illustrating the routing procedure of FIG. 5 in detail;

[0050] FIG. 7 is a flow chart illustrating a Hierarchical Distributed Generic Shortest Path Algorithm (HDGSPA) applied to a two level hierarchical network in accordance with a fourth embodiment of the present invention;

[0051] FIG. 8 is a flow chart illustrating the routing procedure of FIG. 7 in detail;

[0052] FIG. 9 is a flow chart illustrating a QoS Restricted Hierarchical Generic Shortest Path Algorithm (QRHDGSPA) applied to a two level hierarchical network in accordance with a fifth embodiment of the present invention;

[0053] FIG. 10 is a flow chart illustrating the routing procedure of FIG. 9 in detail;

[0054] FIG. 11 is a flow chart illustrating a Multi-Casting Distributed Generic Shortest Path Algorithm (MCDGSPA) in accordance with a sixth embodiment of the present invention;

[0055] FIG. 12 is a flow chart illustrating a routing procedure executed where a routing start point corresponds to a source node in the procedure of FIG. 11;

[0056] FIG. 13 is a flow chart illustrating a routing procedure executed where the routing start point does not corresponds to the source node in the procedure of FIG. 11;

[0057] FIG. 14 is a flow chart illustrating a disjointed multi-path routing algorithm (DMDGSPA) for providing QoS in accordance with a seventh embodiment of the present invention;

[0058] FIG. 15 is a flow chart illustrating the routing procedure of FIG. 14 in detail;

[0059] FIG. 16 is a flow chart illustrating a Multi-Casting Hierarchical Distributed Generic Shortest Path Algorithm (MCHDGSPA) applied to a two level hierarchical network in accordance with an eighth embodiment of the present invention; and

[0060] FIG. 17 is a flow chart illustrating a QoS-based disjointed multi-path routing algorithm (DMHDGSPA) applied to a two level hierarchical network in accordance with a ninth embodiment of the present invention.

[0061] Hereinafter, a preferred embodiment of the present invention will be described in detail, in conjunction with the annexed drawings.

[0062] FIG. 1 is a flow chart illustrating a Generic Shortest Path Algorithm (GSPA) according to a first embodiment of the present invention. The GSPA involves an initialization procedure S1 for initializing a set of information about links of nodes in all paths existing in a network and QoS values for those links, and a routing procedure S2 for designating a routing start point after completion of the initialization, and executing a routing process from the designated routing start point, thereby determining an optimum path.

[0063] First, the initialization procedure S1 of the GSPA will be described. In the initialization procedure S1, respective QoS values of all links existing in the network, is initialized with a predetermined maximum value “MAXQ” using a repetitive paragraph for each node i (i=0 to N) The maximum QoS value MAXQ is indicative of the fact that no path reaching the node i is found.

[0064] A set of information about the shortest path, that is, a route set, is also initialized in the form of an empty set {@} for each node i (Step S11). The shortest path for the node i is established from a source node to the node i. The route set for the node i contains information about nodes linked between the source node and the node i along the shortest path, and a total value of QoSs accumulated at the node i along the shortest path for the node i.

[0065] For reference, the algorithm and parameters used are defined as follows:

[0066] struct{Qos tqos; Oset set;} node[N]; /* node information*./

[0067] Oset neighbor_set[N];/*ordered neighbor set of a node*/

[0068] Qos linkqos[N, N];/*Qos information between nodes*/

[0069] Typedef struct {QoS tqos; Oset set;} Route;

[0070] Main(int ss)/*source number*/

[0071] {

[0072] int i,j; Route route;

[0073] for(i=0; i<N; i++){node[i].tqos=MAXQ; node[i].set={@};}

[0074] Thereafter, a set of information about neighbor nodes linked to each node i, that is, a neighbor set, is initialized. The initialization of the neighbor set is also carried out using a repetitive paragraph so that the set is initialized in the form of an empty set (Step S12).

[0075] For this initialization, the following algorithm may be used:

[0076] for(i=0; i<N; i++)neighbor_set[i]={@};/*{@}; empty set*/

[0077] Subsequently, links associated with each node i are determined along with respective QoS values of those links in order to construct a neighbor set for the node i (Step S13). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node i and a node j neighboring to the node i are the same. When the nodes i and j are different from each other, a predetermined QoS value is used. On the other hand, when the nodes i and j are the same, a QoS value of 0 is used.

[0078] For this determination, the following algorithm may be used:

[0079] for (i=0; i<N; i++) for (j=0; j<N; j++){

[0080] if (i==j)linkqos[i,j]=ZERO else linkqos [i,j]=getlinkqos( );

[0081] }/*connected: QoS value, disconnected: MAXQ*/

[0082] Using the links and link QoS values determined for each node i as mentioned above, a neighbor set for the node i is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0083] That is, when a node j neighboring to the current node i is not the same as the current node i while being linked to the current node, it is additionally registered in the neighbor set (Step S14).

[0084] This may be executed using the following algorithm:

[0085] for (i=0; i<N; i++) for (j=0; j<N; j++){

[0086] if (linkqos[i, j]!=ZERO && linkqos[i, j]!=MAXQ)

[0087] neighbor_set[i]=neighbor_set[i] ∪ j;

[0088] }/*neighbor set construction, ∪: ∪ordered set union*/

[0089] Thereafter, a start point is designated to execute a routing for the shortest path from the designated start point. The route set is initialized with the start point. The route QoS value is also initialized with a value of 0 so that a routing is begun (Step S15).

[0090] After completion of all the above mentioned initialization processes, a routing algorithm is called to execute a routing starting from the routing start point (Step S2).

[0091] This is executed using the following algorithm:

[0092] route.set={ss}; route.tqos=ZERO;

[0093] QoSpath(ss, route)

[0094] FIG. 2 is a flow chart illustrating the routing procedure S2 for determining an optimum path in accordance with a routing algorithm “QoSpath(ss, route)” operating in response to the above mentioned calling. In the routing procedure S2, the total value of QoSs accumulated at the node currently routed is first calculated (Step S21).

[0095] For reference, the algorithm and parameters used are defined as follows:

[0096] QoSpath(int s, Route route)

[0097] {

[0098] Qos tqos;

[0099] int i;

[0100] tqos=F(route.tqos, linkQos[E(route.set), s]);

[0101] The function “E( )” is used to find the last one of the nodes included in the route set associated with a path used as a factor. On the other hand, the function “F( )” is used to determine the QoS value of the path including two nodes, used as a factor, based on the QoS value between those nodes. Accordingly, the total QoS value of the current path including the current node can be determined by finding the current node and the node just previous to the current node in accordance with the function “E( )”, and then calculating the QoS value between the current and previous nodes in accordance with the function.

[0102] The currently calculated total QoS value is then compared with the previously calculated total value of QoSs accumulated at the currently routed node along another path. Such a comparison is necessary because there are a plurality of paths reaching the current node. Where the previous total QoS value is more optimum than the current total QoS value, the current routing is stopped. The procedure then waits for another routing call [C(tqos)<C(node[s].tqos)] (Step S22).

[0103] On the other hand, where the current total QoS value is more optimum than the previous total QoS value, a correction of routing information should be made, based on the current path, because the current path is less optimum than the previous path. In this case, accordingly, it is determined whether or not the last node of the current path corresponds to the current node [E(route.set)!=] (Step S23).

[0104] Where the last node of the current path does not correspond to the current node, this node is additionally registered in the route set (Step S24). The procedure then proceeds to step S25.

[0105] On the other hand, where the last node of the current path corresponds to the current node, step S24 is omitted. In this case, the total value of route QoSs accumulated at the current node along the current path is directly calculated. The reason why step S24 is omitted is because an addition of link information in this case results in a duplication of the current node.

[0106] At step S25, the total QoS value calculated at step S21 is registered in the total QoS value term of the route set, and the current path is registered in the route term of the route set. That is, the route set is updated using the current path and the total QoS value of the current path.

[0107] This may be executed using the following algorithm:

[0108] if (C(tqos)<C(node[s].tqos)){/*C: cost function for given Qos*/

[0109] if (E(route.set)!=s)route.set=route.set ∪ s;

[0110] route.tqos=tqos;

[0111] node[s].set=route.set;

[0112] After completion of the above procedure, that is, after the determination of the optimum path for the currently called node is completed, steps S21 to S25 are repeatedly executed using a repetitive paragraph for a determination of an optimum path for each neighbor node linked to the current path.

[0113] Similar to the above mentioned case, this routing is executed, starting from a calling of the above mentioned routing algorithm. In particular, the routing in this case for each node linked to the path previously routed is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed (Step S26).

[0114] This may be executed using the following algorithm:

[0115] for (each iε(neighbor_set[s]−route.set)) QoSpath(i, route);

[0116] Although the routing is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in accordance with the above mentioned method, the algorithm of the present invention may be configured to give a shortest path when the loop value has a positive value in the meaning of the cost function.

[0117] FIG. 3 is a flow chart illustrating a routing algorithm for determining an optimum path in accordance with another embodiment of the present invention. This routing algorithm is a Distributed Generic Shortest Path Algorithm (DGSPA). This algorithm is different from the above mentioned GSPA in that it executes a routing only for neighboring nodes linked to each other without executing the routing for all nodes existing in the network.

[0118] In accordance with the DGSPA, a routing is executed for only one path when only an optimum one of route messages reaching the destination node is selected. However, when all paths meeting a requested QoS are selected, a multi-routing is executed.

[0119] The DGSPA of FIG. 3 involves an initialization procedure T1 for initializing a set of information about neighbor nodes directly linked to an optional node and QoS values for links each connected between the optional node and an associated one of those neighbor nodes, and a routing procedure T2 for waiting for a call associated with an execution of a routing process after completion of the initialization, and executing the routing process in response to the call.

[0120] First, the initialization procedure T1 of the DGSPA will be described. In the initialization procedure T1, respective link QoS values of neighbor nodes directly linked to each node s existing in the network, is initialized with a predetermined maximum value “MAXQ”. The maximum QoS value MAXQ is indicative of the fact that no path linked to the node i is found. Also, information about the optional node s and information about neighbor nodes directly linked to the node s are initialized in the form of empty sets, respectively (T11).

[0121] For reference, the algorithm and parameters used are defined as follows:

[0122] Typedef struct{Qos tqos; Oset set;}Route;

[0123] struct{Qos tqos; Oset set;}node[s];

[0124] Oset neighbor_set[s];

[0125] Qos linkqos[s][N];

[0126] Route route; node[s].tqos=MAXQ;

[0127] node[s].set={@};

[0128] neighbor_set[s]={@};

[0129] Subsequently, links associated with each node s are determined along with respective QoS values of those links in order to construct a neighbor set for the node i (Step T12). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node s and a node j neighboring to the node s are the same. When the nodes s and j are different from each other, a predetermined QoS value is used. On the other hand, when the nodes s and j are the same, a QoS value of 0 is used.

[0130] For this initialization, the following algorithm may be used:

[0131] for (j=0; j<N; j++){

[0132] if (s==j)

[0133] linkqos[s][j]=ZERO;

[0134] else

[0135] linkqos[s][j]=getlinkqos( );

[0136] }

[0137] Using the links and link QoS values determined for each node s as mentioned above, a neighbor set for the node s is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0138] That is, when a node j neighboring to the current node s is not the same as the current node s while being linked to the current node s, it is additionally registered in the neighbor set (Step T13).

[0139] This may be executed using the following algorithm:

[0140] for (j=0; j<N; j++){

[0141] if (linkqos[s][j]!=ZERO && linkqos[s][j]!=MAXQ)

[0142] neighbor_set[s]=neighbor_set[s] ∪ j;

[0143] }

[0144] /*connected: QoS value, disconnected: MAXQ, neighbor_set[s]: neighbor set of s*/

[0145] After completion of all the above mentioned initialization processes, a routing algorithm is begun. It is determined whether or not the current node corresponds to the source node. Where the current node corresponds to the source node, the route set is initialized with the current node. In this case, the route QoS value is also initialized with a value of 0. In this state, the routing algorithm is called for an execution thereof [QoSpath(s, route)].

[0146] Where the current node does not correspond to the source node, the procedure waits for route information and a route QoS value subsequently transmitted to the current node during a routing executed in association with a node other than the current node. In response to reception of those values, the routing algorithm is called [QoSpath(s, route)] (Steps T14 and T2).

[0147] This procedure may be executed using the following algorithm:

[0148] if (s is the source node){

[0149] route.set={s};

[0150] route.tqos=ZERO;

[0151] }

[0152] else {

[0153] receive (s, Qospath(s, route));

[0154] call (Qospath(s, route));

[0155] }

[0156] FIG. 4 is a flow chart illustrating the routing procedure T2 for determining an optimum path in accordance with the routing algorithm “Qospath(int s, Route route)” operating in response to the above mentioned calling. In the routing procedure T2, the total value of QoSs accumulated at the node currently routed is first calculated (Step T21).

[0157] For reference, the algorithm and parameters used are defined as follows:

[0158] Qospath(int s, Route route)

[0159] {

[0160] Qos tqos;

[0161] int i;

[0162] tqos=F(route.tqos, linkqos[E(route.set), s]);

[0163] The currently calculated total QoS value is then compared with the previously calculated total value of QoSs accumulated at the currently routed node along another path. Such a comparison is necessary because there are a plurality of paths reaching the current node. Where the previous total QoS value is more optimum than the current total QoS value, the current routing is stopped. The procedure then waits for another routing call (Step T22).

[0164] On the other hand, where the current total QoS value is more optimum than the previous total QoS value, a correction of routing information should be made, based on the current path, because the current path is less optimum than the previous path. In this case, accordingly, it is determined whether or not the last node of the current path corresponds to the current node (Step T23).

[0165] Where the last node of the current path does not correspond to the current node, this node is additionally registered in the route set (Step T24). The procedure then proceeds to step T25.

[0166] On the other hand, where the last node of the current path corresponds to the current node, step T24 is omitted. In this case, the total value of route QoSs accumulated at the current node along the current path is directly calculated. The reason why step T24 is omitted is because an addition of link information in this case results in a duplication of the current node.

[0167] At step T25, the total QoS value calculated at step T21 is registered in the total QoS value term of the route set, and the current path is registered in the route term of the route set. That is, the route set is updated using the current path and the total QoS value of the current path.

[0168] This may be executed using the following algorithm:

[0169] if (C(tqos)<C(node[s].tqos)){/*C: cost function for given QoS*/

[0170] if (E(route.set)!=s)route.set=route.set ∪ s;

[0171] route.tqos=tqos;

[0172] node[s].set=route.set;

[0173] }

[0174] After completion of the above procedure, that is, completion of the routing for determining an optimum path for the called node, a routing message is sent to nodes neighboring to the current node [send(i, route)]. This message is transmitted to the call receiving step T14 involved in the initialization procedure T1. In response to a calling executed in accordance with the transmission of the message, steps T21 to T25 are repeatedly executed.

[0175] In particular, where the routing algorithm is repeatedly executed in response to the calling, the routing for each node linked to the path previously routed is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed (Step T26).

[0176] This may be executed using the following algorithm:

[0177] for (each iε(neighbor_set[s]−route.set))

[0178] send (i, route);

[0179] FIG. 5 is a flow chart illustrating a routing algorithm for determining an optimum path in accordance with another embodiment of the present invention. This routing algorithm is a QoS Restricted Generic Shortest Path Algorithm (QRDGSPA). This algorithm is different from the above-mentioned GSPA as follows.

[0180] The GSPA illustrated in FIG. 1 is a method in which the shortest one of paths reaching a destination is selected.

[0181] That is, in accordance with the GSPA, the total QoS value calculated in association with the current path is compared with the total QoS value previously calculated in association with a path other than the current path in the cost comparison procedure. When the current total QoS value is more optimum than the previous total QoS value, the previous path is deleted, and the current path is set as the shortest path. In such a fashion, only one path is established.

[0182] However, in accordance with the QRDGSPA, a reference QoS value is set in the cost comparison procedure.

[0183] For example, a particular function should be used in accordance with the QoS factor to be referenced. To this end, the calculation according to the function “F( )” should be made on the basis of the QoS factor to be referenced. In order to achieve a routing for multimedia services, each node typically use the following rules associated with an evaluation of the QoS factor to be referenced.

[0184] Additive rule: This rule is adapted to evaluate a QoS factor such as transmission delay, delay jitter, or transmission costs. This rule is expressed as follows:

[0185] d(p)=d(i,j)+d(j,k)+ . . . +d(l,m)

[0186] Multiplicative rule: This rule is used for a QoS factor evalulation as expressed as follows:

[0187] d(p)=d(i,j)×d(j,k)× . . . ×d(l,m)

[0188] Concave rule: This rule is adapted to evaluate a QoS factor such as bandwidth for data transmission. This rule is expressed as follows:

[0189] d(p)=min[(d(i,j), d(j,k), . . . ,d(l,m))

[0190] Composition rule: This rule is adapted to evaluate a QoS factor such as transmission failure probability. This rule is expressed as follows:

[0191] d(p)=1−(1−d(i,j))×(1−d(j,k))× . . . ×(1−d(l,m))

[0192] Any path may be set as a shortest path when the QoS value calculated in association therewith is more optimum than the set reference QoS value. Accordingly, in this case, at least one shortest path may exist.

[0193] That is, where there are several paths reaching one destination determined, all of them may be selected as a shortest path in so far as their QoS values meet the above mentioned QoS value condition.

[0194] Although the routing process executed along a single shortest path in accordance with the GSPA may proceed no longer when an error is generated at the single path, the QRDGSPA can avoid such a problem.

[0195] The algorithm of FIG. 5 is substantially similar to that of FIG. 3, except that a calling factor is additionally used at steps of calling a routing algorithm and receiving the result. This calling factor corresponds to the above mentioned reference QoS value.

[0196] That is, “receive(s, route)” in the algorithm of FIG. 3 is changed into “receive(s, route, req)” in the algorithm of FIG. 5.

[0197] No description will be made in association with the remaining algorithm of FIG. 5 because it is the same as that of FIG. 3.

[0198] FIG. 6 is a flow chart illustrating a routing algorithm called in the QRDGSPA. This routing algorithm additionally involves the following procedure after the calculation of the total QoS value executed in the procedure T1 of the routing algorithm illustrated in FIG. 4, as compared to the routing algorithm of FIG. 4.

[0199] That is, the routing algorithm of FIG. 6 additionally involves a procedure for determining whether or not the total value of QoSs accumulated from the source node to the current node meets with a required QoS value set as the reference value. If the total QoS value meets with the required reference QoS value, the routing algorithm is further executed. If not, the routing algorithm is ended [S(tqos, req)==FALSE] (Step T27).

[0200] At the final step of the routing algorithm, transmission of a routing message is executed in order for a repeated execution of the routing algorithm (Step T28).

[0201] Since the remaining algorithm of FIG. 6 is the same as that of FIG. 4, no description thereof will be made.

[0202] All the above mentioned algorithms are associated with a routing procedure applied to a one level hierarchical network. Hereinafter, a routing procedure applied to a two level hierarchical network will be described.

[0203] For a routing procedure applied to a two level hierarchical network, the address of the two level hierarchical network is first defined by two integers [n, m].

[0204] Here, “n” represents a higher address whereas “m” represents a lower address.

[0205] A set of nodes assigned with the same higher address is defined as a “region”. In particular, in this two level hierarchical network, link address lists cannot have address groups having the same higher address while being separated from each other by an address or an address group having a higher address different therefrom.

[0206] In other words, a node link, which leaves a region after passing through that region, cannot enter again that region.

[0207] For example, a routing address list of [1,2][1,4][1,3][3,1][3,2][3,3][2,1][2,2] is suitable for an address list for a hierarchical routing. However, a routing address list of [1,2][1,4][1,3][3,1][2,1][3,2][3,3][2,2] is not unsuitable for an address list for a hierarchical routing because the address groups having the same higher address of “3” are separated from each other by an address having a higher address of “2” different from that of the address groups.

[0208] In the latter case, a node link is made which leaves a region corresponding to the higher address of “3” (that is, the region 3) after passing through the region 3, and then enters the region 3 at a node [3,2] after passing through a node [2,1]. That is, the node link conflicts with the condition in which it cannot enter a region after leaving that region.

[0209] Now, a routing method in the two level hierarchical network in accordance with the present invention will be described.

[0210] FIG. 7 is a flow chart illustrating a routing algorithm for determining an optimum path in a two level hierarchical network in accordance with another embodiment of the present invention. This routing algorithm is a Hierarchical Distributed Generic Shortest Path Algorithm (HDGSPA). This algorithm is substantially similar to the above mentioned DGSPA, except that the hierarchical layers of both levels should be initialized.

[0211] In accordance with the HDGSPA, an initialization procedure (Step P11) is first executed. In the initialization procedure, respective QoS values associated with links of an optional node p belonging to an optional layer i are initialized with a “MAXQ” value indicative of the fact that no path reaching the node p is found. Also, a set of information about the node p belonging to the layer i and a set of information about nodes belonging to a neighbor layer linked to the node p are set as empty sets, respectively.

[0212] For reference, the algorithm and parameters used are defined as follows:

[0213] struct{Qos tqos; Oset set;}node[H,N]; /*hierarchical address*/

[0214] Qos linkqos[[H,N],[H,N]]

[0215] Oset neighbor_set[H,N];

[0216] struct Route{Qos tqos; Oset set;}route;

[0217] struct Node{int s; int p;};

[0218] node[i,p].tqos=MAXQ;

[0219] node[i,p].set={@};

[0220] neighbor_set[i,p]={@}

[0221] Subsequently, links associated with each node p belonging to each layer i are determined along with respective QoS values of those links in order to construct a neighbor set for the node p (Step S13). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node p and a node q neighboring to the node p while belonging to the layer i or belonging to a layer j neighboring to the layer i are the same. When the nodes p and q are different from each other, a predetermined QoS value is used. On the other hand, when the nodes p and q are the same, a QoS value of 0 is used (Step P12).

[0222] This may be executed using the following algorithm:

[0223] for(i=0; i<H; i++)for(j=0; j<H; j++){

[0224] for(p=0; p<N; p++)for(q=0; q<N; q++){

[0225] if ((i,p)==(j,q))

[0226] linkqos[[i,p],[j,q]]=ZERO;

[0227] else

[0228] linkqos[[i,p],[j,q]]=getlinkqos( );

[0229] }

[0230] }

[0231] Using the links and link QoS values determined for each node p as mentioned above, a neighbor set for the node p is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0232] That is, when a node q neighboring to the current node p of the current layer i while belonging to the layer i or belonging to a layer j neighboring to the layer i does not correspond to the current node p while being a node passed, it is additionally registered in the neighbor set (Step P13).

[0233] This may be executed using the following algorithm:

[0234] for(i=0; i<H; i++)for(j=0; j<H; j++){

[0235] for(p=0; p<N; p++)for(q=0; q<N; q++){

[0236] if(linkqos[[i,p],[j,q]]!=ZERO && linkqos[[i,p], [j,q]]!=MAXQ)

[0237] neighbor_set[i,p]=neighbor_set[i,p] ∪ (j,q);

[0238] }

[0239] }

[0240] /*connected: QoS value, disconnected: MAXQ*/

[0241] After completion of all the above mentioned initialization processes, a routing algorithm is begun. It is determined whether or not the current node of the current layer corresponds to the source node. Where the current node of the current layer corresponds to the source node, the route set is initialized with the current node. In this case, the total route QoS value is also initialized with a value of 0. In this state, the routing algorithm is called for an execution thereof [QoSpath(s, route)].

[0242] Where the current node does not correspond to the source node, the procedure waits for a route information and a total route QoS value subsequently transmitted to the current node during a routing executed in association with a node other than the current node [receive(s, route)]. In response to reception of those values, the routing algorithm is called [QoSpath(s, route)] (Steps P14 and P2).

[0243] This procedure may be executed using the following algorithm:

[0244] if (s is the source node){

[0245] route.set={s};

[0246] route.tqos=ZERO;

[0247] }

[0248] else {

[0249] receive (s, Qospath(s, route));

[0250] call (Qospath(s, route));

[0251] }

[0252] FIG. 8 is a flow chart illustrating the routing procedure P2 for determining an optimum path in accordance with the routing algorithm “Qospath(int s, Route route)” operating in response to the above mentioned calling. In the routing procedure P2, the total value of QoSs accumulated at the node of the layer currently routed is first calculated (Step T21).

[0253] For reference, the algorithm and parameters used are defined as follows:

[0254] Qospath(int s, Route route){

[0255] Qos tqos;

[0256] int i;

[0257] tqos=F(route.tqos, linkqos[E(route.set), s]);

[0258] The currently calculated total QoS value is then compared with the previously calculated total value of QoSs accumulated at the currently routed node of the current layer along another path. Such a comparison is necessary because there are a plurality of paths reaching the current node. Where the previous total QoS value is more optimum than the current total QoS value, the current routing is stopped. The procedure then waits for another routing call (Step P22).

[0259] On the other hand, where the current total QoS value is more optimum than the previous total QoS value, a correction of route information should be made, based on the current path, because the current path is more optimum than the previous path. In this case, accordingly, it is determined whether or not the last node of the current path corresponds to the current node (Step P23).

[0260] Where the last node of the current path does not correspond to the current node, it is additionally registered in the neighbor set (Step P24). The procedure then proceeds to step P25.

[0261] On the other hand, where the last node of the current path corresponds to the current node, step T24 is omitted. In this case, the total value of route QoSs accumulated at the current node along the current path is directly calculated. The reason why step T24 is omitted is because an addition of link information in this case results in a duplication of the current node.

[0262] At step P25, the total QoS value calculated at step P21 is registered in the total QoS value term of the route set, and the current path is registered in the route term of the route set. That is, the route set is updated using the current path and the total QoS value of the current path.

[0263] This may be executed using the following algorithm:

[0264] if (C(tqos)<C(node[s].tqos)){/*C: cost function for given Qos*/

[0265] if (E(route.set)!=s)route.set=route.set ∪ s;

[0266] route.tqos=tqos;

[0267] node[s].set=route.set;

[0268] After completion of the above procedure, that is, completion of the routing for determining an optimum path for the called node, a routing message is sent to nodes neighboring to the current node. This message is transmitted to the call receiving step P14 involved in the initialization procedure. In response to a calling executed in accordance with the transmission of the message, steps P21 to P25 are repeatedly executed.

[0269] In particular, where the routing algorithm is repeatedly executed in response to the calling, the routing is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed (Step P26).

[0270] For example, the following expression may be established:

[0271] {(s,p),(w,r),(f,g),(h,k)}−{(c,p),(w,r),(f,v),(h,r)}={(s,p),(h,k)}

[0272] This expression represents that where a routing starting from the layer h is executed, the layer s is left as a path to be routed because it has not been passed yet. In this case, the layers w and f are not to be routed because they have been passed. Also, the node k in the layer h is left as a node to be routed because it has not been passed yet.

[0273] The above procedure may be executed using the following algorithm:

[0274] for (each iε(neighbor_set[s] route.set))

[0275] send (i, route);

[0276] FIG. 9 is a flow chart illustrating a routing algorithm for determining an optimum path in a two level hierarchical network in accordance with another embodiment of the present invention. This routing algorithm is a QoS Restricted Hierarchical Generic Shortest Path Algorithm (QRHDGSPA). This algorithm is substantially similar to the above mentioned QRDGSPA, except that the hierarchical layers of both levels should be initialized. The QRHDGSPA is different from the QRDGSPA in that all nodes satisfying a required reference QoS value are selected for optimum paths.

[0277] The algorithm of FIG. 9 is substantially similar to that of FIG. 7, except that a calling factor is additionally used at steps of calling a routing algorithm and receiving the result. This calling factor corresponds to the above mentioned reference QoS value.

[0278] That is, “receive(s, route)” in the algorithm of FIG. 7 is changed into “receive(s, route, req)” in the algorithm of FIG. 9 (Step P15). Also, “QoSpath(s, route)” in the algorithm of FIG. 7 is changed into “QoSpath(s, route, req)” in the algorithm of FIG. 9 (Step P2).

[0279] No description will be made in association with the remaining algorithm of FIG. 9 because it is the same as that of FIG. 7.

[0280] FIG. 10 is a flow chart illustrating a routing algorithm called in the QRHDGSPA. This algorithm is substantially similar to that of FIG. 8, except that a routing is executed for layers and that regions once routed are not to be routed again during a repeated routing.

[0281] The routing procedure illustrated in FIG. 10 is substantially similar to that of FIG. 8, except that it additionally involves the following procedure after the calculation of the total QoS value executed at step P21, as compared to the routing algorithm of FIG. 8.

[0282] That is, the routing algorithm of FIG. 10 additionally involves a procedure for determining whether or not the total value of QoSs accumulated from the source node to the current node of the current layer meets with a required QoS value set as the reference value. If the total QoS value meets with the reference QoS value, the routing algorithm is further executed. If not, the routing algorithm is ended [S(tqos, req)==FALSE] (Step P27).

[0283] At the final step of the routing algorithm, transmission of a routing message “(send(i, route, req))” is executed in order for a repeated execution of the routing algorithm (Step P28), as in the case of FIG. 8.

[0284] Since the remaining algorithm of FIG. 10 is the same as that of FIG. 8, no description thereof will be made.

[0285] In addition, where values to be compared with each other using the cost function “C( )” include delay values for reception of a message transmitted and respective numbers of hops existing between the source node and the destination node, it is preferred that the values generated in the current path be more optimum than those generated in the previous path. On the other hand, the values to be compared with each other include bandwidth values, it is preferred that the value generated in the current path be more than that generated in the previous path.

[0286] Such conditions may be optionally selected by the user in accordance with the routing method used.

[0287] Although the HDGSPA and QRHDGSPA according to the present invention have been described as being applied to a network having a two-level hierarchical architecture, for the convenience of description, they may be applied to a to network having a multi-level hierarchical architecture. In the latter case, the number of sets used are simply increased in accordance with the increased number of levels.

[0288] FIG. 11 is a flow chart illustrating a Multi-Casting Distributed Generic Shortest Path Algorithm (MCDGSPA) for providing QoS in accordance with another embodiment of the present invention.

[0289] This algorithm is used in the case in which a plurality of destinations are set by one source sending a message. In accordance with this algorithm, where the paths reaching respective destinations overlap together between the source and a certain intermediate node, messages are forwarded to the intermediate node via the same path, and then transmitted to respective destinations.

[0290] First, an initialization procedure S1 is executed in accordance with the algorithm of FIG. 11. In the initialization procedure S1, respective link QoS values for each node s existing in the network is initialized with a predetermined maximum value “MAXQ”. The maximum QoS value MAXQ is indicative of the fact that no path reaching the node s is found. Also, information about the optional node s and information about neighbor nodes linked to the node s are initialized in the form of empty sets, respectively (S1).

[0291] For reference, the algorithm and parameters used are defined as follows:

[0292] typedef struct{Qos tqos; Oset set;}Route;

[0293] struct[Qos tos; Oset set;]node[s];

[0294] Oset neighbor_set[s];

[0295] Qos linkqos[s][N];

[0296] Route route;

[0297] node[s].tqos MAXQ;

[0298] node[s].set={@};

[0299] neighbor_set[s]={@};

[0300] Subsequently, links associated with each node s are determined along with respective QoS values of those links in order to construct a neighbor set for the node s (Step S2). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node s and a node j neighboring to the node s are the same. When the nodes s and j are different from each other, a predetermined QoS value is used. On the other hand, when the nodes s and j are the same, a QoS value of 0 is used.

[0301] For this determination, the following algorithm may be used:

[0302] for (j=0; j<N; j++){

[0303] if (s==j)

[0304] linkqos[s][j]=ZERO

[0305] else

[0306] linkqos [s][j]=getlinkqos( );

[0307] }

[0308] Using the links and link QoS values determined for each node s as mentioned above, a neighbor set for the node s is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0309] That is, when a node j neighboring to the current node s is not the same as the current node s while being linked to the current node, it is additionally registered in the neighbor set (Step S3).

[0310] This may be executed using the following algorithm:

[0311] for (j=0; j<N; j++){

[0312] if (linkqos[s][j]!=ZERO && linkqos[s][j]!=MAXQ)

[0313] neighbor_set[s]=neighbor_set[s] ∪ j;

[0314] }

[0315] /*connected: QOS value, disconnected: MAXQ, neighbor_set[s]: neighbor set of s*/

[0316] After completion of all the above mentioned initialization processes, a routing algorithm is begun. In order to begin the routing algorithm, it is determined whether or not a start point node corresponds to the source node (Step S4). Where the start point node corresponds to the source node, the route set is initialized with the current node (Step S5). In this case, the route QoS value is also initialized with a value of 0. In this state, a multi-casting routing algorithm “MC_qospath( )” is called. Subsequently, a routing message is transmitted. In this state, the source node waits for reception of a signal indicative of the fact that a path is detected for a period of time corresponding to two times a required delay time.

[0317] When the source node receives a path detection message REPLY, it determines a path having a highest weight, and informs of the fact that this path has been detected.

[0318] For reference, the weight W is defined by the condition in which the paths reaching respective destinations overlap together between the source node and a certain intermediate node.

[0319] In other words, a path having a weight is a path extending between the source node and a node forwardly diverged into nodes reaching respective destination nodes along different paths.

[0320] On the other hand, where the start point node does not correspond to the source node, that is, where the start point corresponds to a hop, a desired routing algorithm is called in accordance with the kind of a message subsequently received (Step S6). The routing algorithm may be a routing algorithm (MC-qospath( )) or a routing algorithm (MC_back_qospath( )). The routing algorithm “MC-qospath( )” is called by an intermediate node between the source node and the destination node when the intermediate node transmits a request message to the destination node along a path selected by the source node. In accordance with the routing algorithm “MC-qospath( )”, the routing process is executed in a sequential fashion. On the other hand, the routing algorithm “MC_back_qospath( )” is called by an intermediate node between the source node and the destibation node when the intermediate node transmits a reply message to the source node along a path selected by the destination node. In accordance with the routing algorithm “MC back qospath( )”, the path up to the current node is transmitted to the source node without any further execution of the routing process.

[0321] This procedure may be executed using the following algorithm:

[0322] route.set={ss};

[0323] route.tqos=ZERO;

[0324] if(ss is the source node){

[0325] MC_qospath(ss, route, req));

[0326] while(delay<2*requested_QoS_delay){

[0327] wait_message_from_socket( );

[0328] if (received the REPLY message from all destination nodes){

[0329] select the weightiest route from source to destination nodes;

[0330] exit(success);

[0331] }

[0332] exit(fail);

[0333] }

[0334] else}

[0335] while(1){

[0336] wait_message_from_socket);

[0337] if(message_type=REQ)

[0338] MC_qospath( );

[0339] else if(message_type==REP)

[0340] MC_back_qospath( );

[0341] }

[0342] }

[0343] FIG. 12 is a flow chart illustrating the routing procedure “(MC_qospath( ))” executed where the start point corresponds to the source node in the procedure of FIG. 11. In accordance with this routing procedure, the total value of QoSs accumulated at the node currently routed is calculated (Step T1).

[0344] For reference, the algorithm and parameters used are defined as follows:

[0345] Qospath(int s, Route route){

[0346] Qos tqos;

[0347] int i;

[0348] tqos=F(route.tqos, linkqos[E(route.set), s]);

[0349] It is then determined whether or not an input node to be routed corresponds to one of the destination nodes. Where the input node corresponds to one of the destination nodes, it is then determined whether or not the calculated total QoS value meets a predetermined reference QoS value. That is, it is determined whether or not the calculated total QoS value is more optimum than the predetermined reference QoS value. When the calculated total QoS value is more optimum than the reference QoS value, the source node is informed of paths detected. In order to determine a weightiest one of intermediate paths detected, a REPLY message is transmitted to a node just preceding the input node. At this time, the weight W is set to a value of 1 to (Step T2).

[0350] On the other hand, when it is determined that the input node does not correspond to any destination node, the currently calculated total QoS value is compared with the previously calculated total value of QoSs accumulated at the currently routed node along another path. Such a comparison is necessary because there are a plurality of paths reaching the current node. Where the previous total QoS value is more optimum than the current total QoS value, the current routing is stopped. The procedure then waits for another routing call (Step T3).

[0351] When it is determined at step T3 that the current total QoS value is more optimum than the previous total QoS value, a correction of routing information should be made, based on the current path, because the current path is less optimum than the previous path. In this case, accordingly, it is determined whether or not the last node of the current path corresponds to the current node (Step T4).

[0352] Where the last node of the current path does not correspond to the current node, this node is additionally registered in the node set (Step T5). The procedure then proceeds to step T6.

[0353] On the other hand, where the last node of the current path corresponds to the current node, step T5 is omitted. In this case, the total value of route QoSs accumulated at the current node along the current path is directly calculated. The reason why step T5 is omitted is because an addition of link information in this case results in a duplication of the current node.

[0354] At step T6, the total QoS value calculated at step T1 is registered in the total QoS value term of the route set, and the current path is registered in the route term of the route set. That is, the route set is updated using the current path and the total QoS value of the current path.

[0355] This may be executed using the following algorithm:

[0356] if(s is in a Destination set){

[0357] if(C(tqos)<C(req)){

[0358] R_node=E(route.set);

[0359] route.set=route.set−R_node;

[0360] send(REP, R_node route.set, W=1);

[0361] };

[0362] };

[0363] else if(C(tqos)<C(node[s].tqos)){/*C: cost function for given Qos*/

[0364] if(E(route.set)!=s) route.set=route.set Us;

[0365] route.tqos=tqos;

[0366] node[s].set=route.set;

[0367] }

[0368] After completion of the above procedure, that is, completion of the routing for determining an optimum path for the called node, a routing message “(i, Qospath(i, route)” is sent to nodes neighboring to the current node. This message is transmitted to the call receiving step S5 of FIG. 11. In response to a calling executed in accordance with the transmission of the message, steps T1 to T6 are repeatedly executed.

[0369] In particular, where the routing algorithm is repeatedly executed in response to the calling, the routing for each node linked to the path previously routed is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed (Step T7).

[0370] This may be executed using the following algorithm:

[0371] for (each iε(neighbor_set[s] route.set)) send (i, route);

[0372] FIG. 13 is a flow chart illustrating the routing procedure “(MC_back_qospath( ))” executed where the start point does not correspond to the source node in the procedure of FIG. 11. In accordance with this routing procedure, it is first determined whether or not there is a path having a weight higher than the weight stored in the current node. Where there is a path having a weight higher than the weight of the current node, the current weight is substituted by that of the path newly detected as having a higher weight, and then incremented by a value of 1 (Step T11).

[0373] Thereafter, the current node is subtracted from the path currently routed. A REPLY message is subsequently transmitted to a node just preceding the current node (Step T12).

[0374] This procedure may be executed using the following algorithm:

[0375] if(node.W<W){/* path with weight higher than weight stored in current node detected*/

[0376] node.W=W;

[0377] W++;

[0378] R_node=E(route.set);

[0379] route.set=route.set−R_node;

[0380] send(REP, R_node, route, W);

[0381] }

[0382] FIG. 14 is a flow chart illustrating a disjointed multi-path routing algorithm (DMDGSPA) for providing QoS in accordance with another embodiment of the present invention. This algorithm is used to avoid a duplication of intermediate nodes in multiple optimum paths selected in accordance with the QRDGSPA in which all paths established between a single source node and a single destination node while meeting a required QoS are selected as optimum paths.

[0383] Where this algorithm is applied, there is no duplicated intermediate node in multiple optimum paths. Accordingly, there is an advantage in that it is possible to avoid an occasion in which multiple paths having a duplicated intermediate node cannot be used due to errors generated at the intermediate node.

[0384] Now, the disjointed multi-path routing algorithm will be described.

[0385] This algorithm basically includes the steps of calculating the total QoS value of an optional path established between a source node and a destination node (U1), determining whether or not the current path has nodes overlapping with the previous path (U2), conducting a path designation in accordance with a predetermined priority order between the current and previous paths when there is no node overlapping between the current and previous paths (U3), and registering the current node in the route set (U4).

[0386] In accordance with this algorithm, respective link QoS values for each node s existing in the network is initialized with a predetermined maximum value “MAXQ”. The maximum QoS value MAXQ is indicative of the fact that no path reaching the node s is found. Also, information about the optional node s and information about neighbor nodes linked to the node s are initialized in the form of empty sets, respectively (S1).

[0387] For reference, the algorithm and parameters used are defined as follows:

[0388] typedef struct{Qos tqos; Oset set;}Route;

[0389] struct[Qos tos; Oset set;]node[s];

[0390] Oset neighbor_set[s];

[0391] Qos linkqos[s][N];

[0392] Route route;

[0393] node[s].tqos=MAXQ;

[0394] node[s].set={@};

[0395] neighbor_set[s]={@};

[0396] Subsequently, links associated with each node s are determined along with respective QoS values of those links in order to construct a neighbor set for the node s (Step S2). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node s and a node j neighboring to the node s are the same. When the nodes s and j are different from each other, a predetermined QoS value is used. On the other hand, when the nodes s and j are the same, a QoS value of 0 is used.

[0397] For this determination, the following algorithm may be used:

[0398] for (j=0; j<N; j++){

[0399] if (s==j)

[0400] linkqos[s][j]=ZERO

[0401] else

[0402] linkqos [s][j]=getlinkqos( );

[0403] Using the links and link QoS values determined for each node s as mentioned above, a neighbor set for the node s is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0404] That is, when a node j neighboring to the current node s is not the same as the current node s while being linked to the current node, it is additionally registered in the neighbor set.

[0405] This may be executed using the following algorithm:

[0406] for (j=0; j<N; j++){

[0407] if (linkqos[s][j]!=ZERO && linkqos[s][j]!=MAXQ)

[0408] neighbor_set[s]=neighbor_set[s] ∪ j;

[0409] }

[0410] /*connected: QOS value, disconnected: MAXQ, neighbor_set[s]: neighbor set of s*/

[0411] After completion of all the above mentioned initialization processes, a routing algorithm is begun. In order to begin the routing algorithm, it is determined whether or not the current node corresponds to the source node (Step S4). Where the current node corresponds to the source node, the route set is initialized with the current node (Step S5). In this case, the route QoS value is also initialized with a value of 0. In this state, a routing algorithm is called [QoSpath(s, route, req)].

[0412] On the other hand, where the current node does not correspond to the source node, the procedure waits for route information and a route QoS value subsequently transmitted to the current node during a routing executed in association with a node other than the current node [receive(s, route, req)]. In response to reception of those values, the routing algorithm is called [QoSpath(s, route, req)].

[0413] This procedure may be executed using the following algorithm:

[0414] if (s is the source node){

[0415] route.set={s};

[0416] route.tqos=ZERO;

[0417] }

[0418] else}

[0419] receive (s, Qospath(s, route, req));

[0420] call (Qospath(s, route, req));

[0421] }

[0422] FIG. 15 is a flow chart illustrating the routing procedure of FIG. 14 in detail. In accordance with this routing procedure, the total value of QoSs accumulated at the node currently routed is first calculated (Step U51).

[0423] For reference, the algorithm and parameters used are defined as follows:

[0424] tqos=F(route.tqos, linkqos[E(route.set), s]);

[0425] The currently calculated total QoS value is then compared with the previously calculated total value of QoSs accumulated at the currently routed node along another path. Such a comparison is necessary because there are a plurality of paths reaching the current node. Where the previous total QoS value is more optimum than the current total QoS value, the current routing is stopped. The procedure then waits for another routing call (Step U52).

[0426] On the other hand, where the current total QoS value is more optimum than the previous total QoS value, a correction of routing information should be made, based on the current path, because the current path is less optimum than the previous path. In this case, it is determined whether or not the current path has a hop overlapping with the previous paths because all the routed paths should not have any duplicated hop.

[0427] Where the current path has a duplicated hop, the current path associated with the current node should not be added as a new path. In this case, accordingly, the routing algorithm executed no longer (Step U53).

[0428] On the other hand, where there is no duplicated hop in the current path, it is then determined whether or not the last node of the current path corresponds to the current node (Step U54). Where the last node of the current path does not correspond to the current, this node is additionally registered in the node set (Step U55).

[0429] On the other hand, where the last node of the current path corresponds to the current node, step U55 is omitted. In this case, the total value of route QoSs accumulated at the current node along the current path is directly calculated. The reason why step U55 is omitted is because an addition of link information in this case results in a duplication of the current node.

[0430] At step U56, the total QoS value calculated at step U51 is registered in the total QoS value term of the route set, and the current path is registered in the route term of the route set. That is, the current path and the total QoS value of the current path are inputted at an appropriate position in the route set in accordance with a predetermined priority order. The order of registered paths is then adjusted.

[0431] Thereafter, the information about the current node is added, as hop information, to respective neighbor sets of the nodes of all previous paths (Step U57). Also, the information about the current path is added, as path information, to respective route sets of the nodes of all previous paths.

[0432] After completion of the above procedure, that is, completion of the routing for determining an optimum path for the called node, a routing message “(send(i, route, req))” is sent to nodes neighboring to the current node without belonging to any one of the previous paths. This message is transmitted to the call receiving step involved in the initialization procedure. In response to a calling executed in accordance with the transmission of the message, steps U51 to U57 are repeatedly executed.

[0433] In particular, where the routing algorithm is repeatedly executed in response to the calling, the routing is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed (Step U58).

[0434] This may be executed using the following algorithm:

[0435] if(C(tqos)<C(node[s].tqos[p])){

[0436] find the position p, meeting the QoS order, among diverse paths;

[0437] /* 0=<p<m, p: the order of current path among m paths routed*/

[0438] if(route.set−node[s].sset)==(route.set−ss)){

[0439] if(E(route.set)!=s) route.set=route.set ∪ s;

[0440] route.tqos=tqos;

[0441] for(k=p;k<m−1; k++){

[0442] node[s].tqos[k+1]=node[s].tqos[k]

[0443] node[s].set[k+1]=node[s].set[k]

[0444] }

[0445] node[s].sset=node[s].set ∪ route.set;

[0446] node[s].tqos[p]=tqos;

[0447] node[s].set[p]=route.set;

[0448] for(each iε(neighbor_set[s]−route.set))

[0449] send(i, route, req);

[0450] }

[0451] }

[0452] The above description relates to a routing procedure for an one level hierarchical network. Now, a routing procedure for a two level hierarchical network will be described.

[0453] For a routing procedure applied to a two level hierarchical network, the address of the two level hierarchical network is first defined by two integers [n, m].

[0454] Here, “n” represents a higher address whereas “m” represents a lower address.

[0455] A set of nodes assigned with the same higher address is defined as a “region”. In particular, in this two level hierarchical network, link address lists cannot have address groups having the same higher address while being separated from each other by an address or an address group having a higher address different therefrom.

[0456] In other words, a node link, which leaves a region after passing through that region, cannot enter again that region.

[0457] For example, a routing address list of [1,2][1,4][1,3][3,1][3,2][3,3][2,1][2,2] is suitable for an address list for a hierarchical routing. However, a routing address list of [1,2][1,4][1,3][3,1][2,1][3,2][3,3][2,2] is not unsuitable for an address list for a hierarchical routing because the address groups having the same higher address of “3” are separated from each other by an address having a higher address of “2” different from that of the address groups.

[0458] In the latter case, a node link is made which leaves a region corresponding to the higher address of “3” (that is, the region 3) after passing through the region 3, and then enters the region 3 at a node [3,2] after passing through a node [2,1]. That is, the node link conflicts with the condition in which it cannot enter a region after leaving that region.

[0459] FIG. 16 is a flow chart illustrating a routing algorithm for determining an optimum path in a two level hierarchical network in accordance with another embodiment of the present invention. This routing algorithm is a Multi-Casting Hierarchical Distributed Generic Shortest Path Algorithm (MCHDGSPA). This algorithm is substantially similar to the above mentioned MCDGSPA, except that the hierarchical layers of both levels should be initialized.

[0460] In accordance with the MCHDGSPA, an initialization procedure is first executed (Step V1). In the initialization procedure, respective QoS values associated with links of an optional node p belonging to an optional layer i are initialized with a “MAXQ” value indicative of the fact that no path reaching the node p is found. Also, a set of information about the node p belonging to the layer i and a set of information about nodes belonging to a neighbor layer linked to the node p are set as empty sets, respectively.

[0461] For reference, the algorithm and parameters used are defined as follows:

[0462] struct{Qos tqos; Oset set;} node[H,N]; /*hierarchical address*/

[0463] Qos linkqos[[H,N],[H,N]]

[0464] Oset neighbor_set[H,N];

[0465] struct Route{Qos tqos; Oset set;}route;

[0466] struct Node{int s; int p;};

[0467] node[i,p].tqos=MAXQ;

[0468] node[i,p].set={@};

[0469] neighbor_set[i,p]={@}

[0470] Subsequently, links associated with each node p belonging to each layer i are determined along with respective QoS values of those links in order to construct a neighbor set for the node p (Step V2). This determination is executed for all nodes existing in the network using a repetitive paragraph. For the QoS value determination, it is first determined whether or not the node p and a node q neighboring to the node p while belonging to the layer i or belonging to a layer j neighboring to the layer i are the same. When the nodes p and q are different from each other, a predetermined QoS value is used. On the other hand, when the nodes p and q are the same, a QoS value of 0 is used.

[0471] This may be executed using the following algorithm:

[0472] for(i=0; i<H; i++)for(j=0; j<H; j++){

[0473] for(p=0; p<N; p++)for(q=0; q<N; q++){

[0474] if((i,p)==(j,q))

[0475] linkqos[[i,p],[j,q]]=ZERO;

[0476] else

[0477] linkqos[[i,p],[j,q]]=getlinkqos( );

[0478] }

[0479] }

[0480] Using the links and link QoS values determined for each node p as mentioned above, a neighbor set for the node p is then constructed. The construction of the neighbor set is executed for all nodes using a repetitive paragraph.

[0481] That is, when a node q neighboring to the current node p of the current layer i while belonging to the layer i or belonging to a layer j neighboring to the layer i does not correspond to the current node p while being a node passed, it is additionally registered in the neighbor set (Step V3).

[0482] This may be executed using the following algorithm:

[0483] for(i=0; i<H; i++)for(j=0; j<H; j++){

[0484] for(p=0; p<N; p++)for(q=0; q<N; q++){

[0485] if(linkqos[[i,p],[j,q]]!=ZERO && linkqos [[i,p], [j,q]]!=MAXQ)

[0486] neighbor_set[i,p]=neighbor_set[i,p] ∪ (j,q);

[0487] }

[0488] }

[0489] /*connected: QoS value, disconnected: MAXQ*/

[0490] After completion of all the above mentioned initialization processes, a routing algorithm is begun. In order to begin the routing algorithm, it is determined whether or not a start point node corresponds to the source node (Step V4).

[0491] Where the start point node corresponds to the source node, the route set is initialized with the start point node (Step V5). In this case, the route QoS value is also initialized with a value of 0. In this state, a multi-casting routing algorithm “MC_qospath( )” is called. Subsequently, a routing message is transmitted. In this state, the source node waits for reception of a signal indicative of the fact that a path is detected, for a period of time corresponding to two times a required delay time. When the source node receives a path detection message REPLY, it determines a path having a highest weight, and informs of the fact that this path has been detected. When the source node does not receive any path detection message REPLY, it informs of a failure of path detection.

[0492] For reference, the weight W is defined by the condition in which the paths reaching respective destinations overlap together between the source node and a certain intermediate node.

[0493] In other words, a path having a weight is a path extending between the source node and a node forwardly diverged into nodes reaching respective destination nodes along different paths.

[0494] On the other hand, where the start point node does not correspond to the source node, that is, where the start point corresponds to a hop, a desired routing algorithm is called in accordance with the kind of a message subsequently received (Step V6). The routing algorithm may be a routing algorithm (MC-qospath( )) or a routing algorithm (MC_back_qospath( )). The routing algorithm “MC-qospath( )” is called by an intermediate node between the source node and the destination node when the intermediate node transmits a request message to the destination node along a path selected by the source node. In accordance with the routing algorithm “MC-qospath( )”, the routing process is executed in a sequential fashion. On the other hand, the routing algorithm “MC_back_qospath( )” is called by an intermediate node between the source node and the destibation node when the intermediate node transmits a reply message to the source node along a path selected by the destination node. In accordance with the routing algorithm “MC back qospath( )”, the path up to the current node is transmitted to the source node without any further execution of the routing process.

[0495] This procedure may be executed using the following algorithm:

[0496] route.set={ss};

[0497] route.tqos=ZERO;

[0498] if(ss is the source node){

[0499] MC_qospath(ss, route, req));

[0500] while(delay<2*requested_QoS_delay){

[0501] wait_message_from_socket( );

[0502] if (received the REPLY message from all destination nodes){

[0503] select the weightiest route from source to destination nodes;

[0504] exit(success);

[0505] }

[0506] }

[0507] exit(fail);

[0508] }

[0509] else{

[0510] while(1){

[0511] wait_message_from_socket;

[0512] if(message_type==REQ)

[0513] MC_qospath( );

[0514] else if(message_type==REP)

[0515] MC_back_qospath( );

[0516] }

[0517] }

[0518] The routing procedures of FIG. 16 respectively conducted where the start point node corresponds to the source node and where the start point node does not correspond to the source node are the same as those illustrated in FIGS. 12 and 13. Accordingly, no further description will be made for those routing procedures. Of course, the routing procedures of FIG. 16 are different from those illustrated in FIGS. 12 and 13 in that the procedure for transmitting a routing message is different from the step T7 in the procedure of FIG. 12.

[0519] That is, where the routing algorithm is repeatedly executed in response to the calling, the routing is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed.

[0520] For example, the following expression may be established:

[0521] {(s,p),(w,r),(f,g),(h,k)}−{(c,p),(w,r),(f,v),(h,r){={(s,p),(h,k)}

[0522] This expression represents that where a routing starting from the layer h is executed, the layer s is left as a path to be routed because it has not been passed yet. In this case, the layers w and f are not to be routed because they have been passed. Also, the node k in the layer h is left as a node to be routed because it has not been passed yet.

[0523] FIG. 17 is a flow chart illustrating a QoS-based disjointed multi-path hierarchical routing algorithm (DMHDGSPA) for a two level hierarchical network in accordance with another embodiment of the present invention. This algorithm involves the same initialization procedure (Steps V1 to V3) as that in the algorithm of FIG. 16. Accordingly, the following description will be made only for different procedures.

[0524] After the initialization procedure is completely executed in accordance with completion of steps V1 to V3, a routing algorithm is begun. In order to begin the routing algorithm, it is determined whether or not the current node corresponds to the source node (Step V7). Where the current node corresponds to the source node, the route set is initialized with the current node. In this case, the route QoS value is also initialized with a value of 0. In this state, a routing algorithm is called [QoSpath(s, route, req)] (Step V8).

[0525] On the other hand, where the current node does not correspond to the source node, the procedure waits for route information and a route QoS value subsequently transmitted to the current node during a routing executed in association with a node other than the current node [receive(s, route, req)]. In response to reception of those values, the routing algorithm is called [QoSpath(s, route, req)].

[0526] This procedure may be executed using the following algorithm:

[0527] if (s is the source node){

[0528] route.set={s};

[0529] route.tqos=ZERO;

[0530] }

[0531] else{

[0532] receive (s, Qospath(s, route, req));

[0533] call (Qospath(s, route, req));

[0534] }

[0535] The routing procedure of FIG. 17 is the same as that illustrated in FIG. 15. Accordingly, no further description will be made for the routing procedure. Of course, the routing procedure of FIG. 17 is different from that of FIG. 15 in that the procedure for transmitting a routing message is different from the step U58 in the procedure of FIG. 15.

[0536] That is, where the routing algorithm is repeatedly executed in response to the calling, the routing is begun after subtracting the route set of the previously routed node from the neighbor set of the same node in order to avoid a repeated routing for the path already routed. Since the routing procedure is the same as the above described routing procedure of FIG. 16, no further description will be made.

[0537] Heretofore, various routing methods according to the present invention have been described. In addition, where values to be compared with each other using the cost function (C) include delay values for reception of a message transmitted and respective numbers of hops existing between the source node and the destination node, it is preferred that the values generated in the current path be more optimum than those generated in the previous path. On the other hand, the values to be compared with each other include bandwidth values, it is preferred that the value generated in the current path be more than that generated in the previous path.

[0538] Such conditions may be optionally selected by the user in accordance with the routing method used. Although the HDGSPA and QRHDGSPA according to the present invention have been described as being applied to a network having a two-level hierarchical architecture, for the convenience of description, they may be applied to a network having a multi-level hierarchical architecture. In the latter case, the number of sets used are simply increased in accordance with the increased number of levels.

[0539] As apparent from the above description, the present invention provides various routing methods based on a QoS required for the transmission of multimedia information in a variety of data communication networks. That is, the present invention provides routing algorithms for providing a shortest path routing applicable to a one level hierarchical network, which algorithms include a GSPA, in which a shortest one among all paths established in association with one destination is selected, a DGSPA in which the routing of GSPA is conducted in a distributed fashion to achieve a fast routing, and a QRDGSPA, 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, in order to prevent problems caused by an error generated at the single path in the GSPA. The present invention also provides routing algorithms for providing a shortest path routing applicable to a multi-level hierarchical network. These algorithms include HDGSPA and QRHDGSPA which are respective modified versions of DGSPA and QRDGSPA adapted to allow those DGSPA and QRDGSPA to be applicable to a multi-level hierarchical network.

[0540] The present invention further provides an MCDGSPA which is a routing algorithm for providing a shortest path routing applicable to a one level hierarchical network. The MCDGSPA is applied to the case in which there are a plurality of destinations for the same source. Also, there is a DMDGSPA which is a modified version of QRDGSPA adapted to avoid a duplication of intermediate nodes in multiple optimum paths selected in accordance with the QRDGSPA in which all paths established between a single source node and a single destination node while meeting a required QoS are selected as optimum paths. The present invention also provides MCHDGSPA and DMHDGSPA which are respective modified versions of MCDGSPA and DMDGSPA adapted to allow those to MCDGSPA and DMDGSPA to be applicable to a multi-level hierarchical network. Accordingly, the present invention provides an advantage in that the user can select an algorithm, most suitable for the environment of the system used, from the above routing algorithms.