Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-16
2004-11-02
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S237000, C370S238000, C370S392000, C370S408000, C370S468000
Reexamination Certificate
active
06813272
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
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.
2. Description of the Prior Art
One of general routing methods is a distance vector algorithm which is mainly used as a routing algorithm in the Internet.
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:
D
(
v
)←Min[(
D
(&ngr;),
D
(&ohgr;)+
L
(&ohgr;,&ngr;))
where, “D(&ngr;)” represents the distance between an origin node, namely, a current node, and a destination node, and “L(&ohgr;,&ngr;)” represents the distance between a node &ohgr; and a node &ngr;.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
An Sun Shin
Choi Eun Ho
Jeon Hong Beom
Kim Doo Seok
Yoon Young Hyun
Chin Wellington
Korea Telecommunication Authority
Merchant & Gould P.C.
Mew Kevin
LandOfFree
QoS-based routing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with QoS-based routing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QoS-based routing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306823