1. Field of the Invention
The present invention relates to a method for providing a QoS-guaranteeing multi-path, and more particularly to a method for providing a QoS-guaranteeing multi-path to find multiple paths satisfying two QoS parameters (i.e., a required bandwidth and a required delay time) from a start node to a destination node in a path-based communication network, and a method for providing a disjoint path using the same method.
2. Description of the Prior Art
Presently, an Internet network provides users with only a best-effort service. However, following the current trend of not only rapidly increasing an amount of traffic due to increased Internet users, but also developing a variety of applications, techniques for guaranteeing an appropriate QoS in a network are increasingly developed. In recent times, many developers are intensively conducting research into a new technique for extending a link state protocol, for example, an OSPF (Open Shortest Path First), and an ISIS (Intermediate System to Intermediate System), etc., to transmit various QoS metrics in an IETF.
A distance vector algorithm has been widely adapted as a general path search method for performing a routing function guaranteeing a QoS required for transmitting multimedia information over a variety of communication networks. The distance vector algorithm has been adapted as a representative RIP (Routing Information Protocol) Internet routing protocol. The distance vector algorithm can be easily implemented due to its own simple configuration. However, the distance vector algorithm consumes much time and bandwidth to collect all path information at individual nodes, and is unable to select an optimal QoS path at each node.
A path search operation in a QoS routing service is different from that in a best-effort service. In more detail, the QoS routing service adapts at least one metric of individual links, and finds a path from a start node to a destination node on the basis of the start node, differently from the best-effort service. A problem caused when finding an optimum path for fully optimizing at least two metrics in a network having the two metrics is well known as an NP-complete problem. Recently, there have been proposed a variety of effective algorithms for solving the NP-complete problem. Particularly, an inventor “Xin Yuan” proposed a path search algorithm satisfying two QoS parameters using a Bellman-Ford algorithm during a predetermined time 0(n3), and an inventor “Gang” proposed a path search algorithm for finding an almost optimum path using a Dijkstra algorithm during a predetermined time 0(n3). An inventor “Wang” proposed a path search algorithm for finding a plurality of paths using the Gang's algorithm, and selecting one path from among the found paths, resulting in reduction of a failure rate in a path setup process. An inventor “Yanxia” proposed a variety of QoS-path algorithms for finding K paths during a specific time 0(km). However, because the aforementioned conventional algorithms periodically provide users with link state information, the aforementioned conventional algorithms consume a great deal of bandwidth. Further, if there is no consideration for multimedia services or a variety of multimedia services are requested at different nodes, the aforementioned conventional algorithms cannot satisfy various QoSs for every multimedia service.
In the meantime, a conventional art for finding a path guaranteeing a QoS is described in Korean Patent Application No. 1999-23623, which is incorporated herein by reference. This conventional art includes a method for finding the shortest path close to one destination so as to find multiple QoS paths during an optimum time using the shortest distance algorithm of Point-to-Multipoint access, a method for finding a path during a short time by distributing paths, and a method for setting up all paths satisfying a reference QoS associated with one destination, etc. However, these methods may be adapted for QoS routing functioning as a hop-by-hop routing model, and have a relatively long execution time, respectively.
An example of a Constraint-Base Routing Algorithm for finding a path that satisfies given constraints and at the same time optimizes a scalar metric of a conventional routing has been proposed by Young-Hwan JIN, et al., who have published a research paper entitled “IMPROVENEMENT OF CSPF ROUTING ALGORITHM FOR TRAFFIC ENGINEERING IN MPLS NETWORK” in the Korean Institutes of Communication Sciences Proceeding pp. 262 on 2001, which is incorporated herein by reference. The constraint-base routing algorithm is an optimum time algorithm for finding a path that satisfies a bandwidth and has the shortest delay time, repeatedly uses a conventional algorithm as it is, and selects one path, resulting in a hop-by-hop routing.
An example of a method for finding paths satisfying a variety of parameters, for example, a bandwidth value, a delay value, and a safety value, in the range from one start point to a destination has been proposed by Wang Jianxin, Wanf Weiping, Chen Jianer, and Chen Songqiao, who have published a research paper entitled “A RANDOMIZE QOS ROUTING ALGORITHM ON NETWORKS WITH INACCURATE LINK-STATE INFORMATION” in Communication Technology Proceedings 2000, WCC-ICCT 2000, and International Conference, vol. 2, pp. 1617˜1622, on 2000, which is incorporated herein by reference. However, each of the aforementioned conventional methods has a complicated path calculation process and does not guarantee an optimum calculation time, such that it is not considered to be an optimum time algorithm.
USPTO Backgrounds
USPTO Backgrounds