Route selection method

Details Route selection method Route selection method

1998-08-03

2001-07-10

Chin, Wellington (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S351000

Reexamination Certificate

active

06259673

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a route selection method for selecting a route satisfying a condition with regard to a plurality of Quality of Service (QoS) out of routes each connecting a start point to an end point, and in particular to a route selection method, responsive to an approximation proportion of cost specified beforehand, for selecting a route satisfying a condition with regard to a plurality of QoSs a low cost within the approximation proportion.
2. Description of the Related Art
For high utilization of a network, a route selection technique simultaneously satisfying a desired condition with regard to a plurality of QoSs, such as the bandwidth, transmission delay, and error rate, of a communication route at a low cost is necessary and indispensable. Also in ATM (Asynchronous Transfer Mode) spreading in recent years, a QoS such as cell delay variation tolerance, cell transfer delay, and cell loss ratio are defined. The importance of the communication route selection technique capable of satisfying a desired condition with regard to a plurality of QoSs is increasing. According to their properties, a QoS can be classified broadly into the following three kinds.
(1) Additive property
It is such a property that the QoS value of a route becomes the sum of QoS values of respective links forming the route. For example, the transmission delay and the cell transfer delay come under the property.
(2) Multiplicative property
It is such a property that the QoS value of a route becomes a function of product of QoS values of respective links forming the route. For example, the error rate and the cell loss ratio come under the property.
(3) Concave property
It is such a property that the QoS value of a route becomes the minimum value among QoS values of respective links forming the route. For example, the bandwidth comes under the property.
As a conventional technique for selecting a low cost route satisfying a condition with regard to a plurality of QoSs, “rule-based route selecting system” will now be described by referring to a flow chart of FIG.
8
. It is now assumed on a network having ten nodes (A to J) as shown in
FIG. 9
that a route satisfying all desired QoS conditions from a node A (start point) to a node J (end point) and requiring the lowest cost is selected. In addition, it is now assumed that the link cost, bandwidth, transmission delay, and error rate between nodes have values as shown in
FIG. 10
, and QoS conditions to be satisfied are the following three conditions.
QoS condition
1
—The bandwidth should be at least 3.
QoS condition
2
—The transmission delay should be at most 16.
QoS condition
3
—The error rate should be at most 0.05.
At step S
71
, links which do not satisfy the desired conditions with regard to the bandwidth which is the concave QoS are excepted. In the present implementation form, the bandwidth between D and J is “2” and hence it does not satisfy the QoS condition
1
. Therefore, the route DJ is excepted from the subjects of the route selection. At step S
72
, the other QoS conditions to be satisfied are provided with priorities, and a maximum number of times of trial N described later in detail is determined. The present implementation form will be described, assuming that the QoS condition
2
(transmission delay) is provided with a priority higher than that of the QoS condition
3
(error rate) and the maximum number of times of trial N is set to 2.
At step S
73
, the cost function or one of the QoS conditions is selected. At first, however, the cost function is always selected. At step S
74
, the condition selected at the step S
73
, i.e., at first a route P
0
minimizing the cost function is selected regardless of other QoS conditions. In the example shown in
FIG. 10
, the route P
0
of the start point A→G→H→I→the end point J is selected. At step S
75
, it is determined whether the route P
0
satisfies all of the QoS conditions. In the route P
0
, the transmission delay becomes “28” and hence the QoS condition
2
is not satisfied. Therefore, the processing proceeds to step S
78
.
At the step S
78
, it is determined whether the number of times of trial n (=1) has exceeded the maximum number of times of trial N (=2). Since n is not yet exceeded in this case, the processing proceeds to step S
77
, where the number of times of trial n is increased by one, and the processing returns to the step S
73
. At the step S
73
, the QoS condition
2
(transmission delay) having a higher priority is selected this time. At the step S
74
, a route P
1
minimizing the transmission delay is selected regardless of other QoS conditions.
In the present implementation form, the route P
1
of the start point A→E→H→I→end point J is selected. At the step S
75
, it is determined whether the route P
1
satisfies all other QoS conditions simultaneously. In the present implementation form, the error rate in the route P
1
becomes at most 0.05 and consequently the QoS condition
3
is satisfied. Since all other QoS conditions are thus satisfied, the processing proceeds to step S
76
. At the step S
76
, the route P
1
is output as an optimum route. If the decision at the step S
75
becomes negation repeatedly and the number of times of trial n has exceeded the maximum number of times of trial N at the step S
78
, then information representing that there is no route satisfying the conditions is output at step S
79
.
The above described conventional technique had the following problems.
(1) The approximation precision depends upon the empirical law.
At the step S
72
, each QoS condition is provided with a priority on the basis of the empirical law of the user. According to the priority, it is successively determined whether there is a route satisfying each QoS condition. Without the knowledge concerning the kind and property of each QoS condition, an optimum route or a route having a high approximation precision cannot be selected.
For example, contrary to the foregoing description, it is now assumed that the QoS condition
3
(error rate) is provided at the step S
72
with a priority higher than that of the QoS condition
2
(transmission delay) . At the step S
73
, in this case, a route represented as the start point A→B→C→F→the end point J is represented as the minimum error rate route P
2
. This route P
2
has a transmission delay of “14”, and satisfy all QoS conditions. And the sum of the link costs of the route P
2
is “26”, and it becomes less than the cost “32” of the route P
1
.
Since the selected route thus differs depending upon how QoSs are provided with priorities, the approximation precision depends upon the empirical law. If the number r of the QoS conditions increases, the number of ways of providing QoSs with priorities increases as represented by r!=r×(r−1)× . . . 2×1. Therefore, the approximation precision furthermore depends upon the empirical law.
(2) The approximation precision is fixed.
The approximation proportion is fixedly determined by the network configuration such as the number or cost of nodes and links, bandwidth, transmission delay, and error rate. There occurs such a situation that network resources satisfying QoS conditions desired by the network provider or the network users cannot be flexibly assigned.
For example, in the above described conventional system, a route A→E→H→I→J minimizing the transmission delay irrespective of the cost is selected. However, the sum of link costs of this route is “32”, whereas the sum of link costs of the optimum solution is “14”. The approximation ratio is 32/14, i.e., approximately 2.3. Therefore, the maximum value of the approximation ratio, i.e., the approximation proportion of the conventional technique in an arbitrary network becomes at least 2.3.
In the above described conventional technique, the approximation proportion is fixedly determined by the network configuration such as the link cost. Even if it is

Affiliated with

Also associated with

Rating

Route selection 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 Route selection method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route selection method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2447525