End-to-end delay estimation in high speed communication...

Details End-to-end delay estimation in high speed communication... End-to-end delay estimation in high speed communication...

1997-10-07

2001-05-01

Nguyen, Chau (Department: 2739)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S252000

Reexamination Certificate

active

06226266

ABSTRACT:

TECHNICAL FIELD
The present invention relates to high speed communication networks and more particularly to a method to efficiently estimate the end-to-end delay of a path between an origin and a destination node in a high speed packet switching network.
BACKGROUND ART
The emergence of high speed/bandwidth networking technologies now makes possible the integration of multiple types of traffic like speech, video and data over the same communication network. The end user applications that generate such different types of traffic, while using the same transmission media of the network, i.e. nodes and transmission links, have different requirements regarding the transmission characteristics over the network. These applications requirements, commonly called quality of service (QoS) requirements, are taken into account during the path selection process.
The role of the path selection process is to determine optimum paths for user applications across the network each time a connection is requested, commonly referred to as call setup. This implies the allocation of network resources to users in order to guarantee their QoS requirements while optimizing the overall throughput within the network. This function may take place entirely within the origin node. Various QoS parameters may be specified by the users, some of them in order to satisfy real-time delivery constraints, others related to non real-time data traffic transfer. The origin node computes a path to the destination node that is capable of carrying the new connection and providing the level of service required by the new connection. The path selection algorithm uses data describing the current traffic load in the entire network. Such data are stored in a topology database located in each input node of the network. If no suitable paths can be found that meet all the requirements, the connection is rejected. Once the origin node has found a suitable path, a setup message is generated which traverses the selected route, updating the resource allocations for each link visited by the setup message.
The quality of service can be defined as a set of measurable quantities that describe the user's perception of the service offered by the network like the connection setup delay, the connection blocking probability, the loss probability, the error probability, the end-to-end transit delay and the end-to-end delay variation also referred to as jitter.
The present application focuses on end-to-end transit delay (hereinafter referred also to as EED) estimation. At each connection setup, during path selection, an estimation of the EED is computed for each path selected. The precision of the end-to-end delay estimation is important since the acceptance or the rejection of a connection may depend on whether or not the computed EED violates the QoS specification. If the EED computed is too “optimistic”, the path for which it applies can be accepted and the connection granted while the QoS specifications of the connection may not actually be guaranteed. In the other hand, if the EED estimation is computed in a too “pessimistic” way, a connection can be rejected because no paths can be found that satisfy the QoS EED requested by the connection.
Consequently, an accurate method for computing an EED estimation of a path from an origin node to a destination node in a communication network, is required in order to make a precise screening of paths regarding the QoS end-to-end transit delay specification of a connection being set up.
In many products of the prior art and particularly in the standard defined by the ATM Forum which applies to high speed packet switching networks, the current method for computing an EED estimation of a path is based on the mere addition of the maximum delays per hop along the path. A hop defines a node associated with the link that connects that node to the next node of the path.
Moreover the maximum delay per hop along the considered path is specified as being the maximum time that a packet/cell can wait in a switching node (queuing time) in addition to the fixed propagation delay of the link that connects that node to the next one.
This common approach can be summarized by the following equations:
the connection is granted if:
Tqos>Tmax   (1)
with
Tmax
=
∑
i
=
1
N
⁢
(
Qmax
⁡
(
i
)
+
P
⁡
(
i
)
)
(
2
)
where:
Tqos is the maximum end-to-end delay specified by the connection Qos.
Tmax is the EED estimate of the selected path.
N is the number of nodes in the selected path.
Qmax(i) is the maximum queuing time of node i.
P(i) is the propagation time of the link that connects node i to node i+1.
The disadvantage with the common approach (illustrated by formulas (1) and (2)) resides in that experience, which is mathematically corroborated, shows that the probability for one to observe in reality the delay estimated Tmax for the considered path is negligeable. Tmax is a “worst case” delay which implies that most of the time the connection will be rejected unless the customer specifies very high Tqos.
Referring to equation (2) above, the maximum queuing time of node i, Qmax(i) can be expressed as follows:
Qmax
⁡
(
i
)
=
X
⁡
(
i
)
S
⁡
(
i
)
(
3
)
where:
X(i) is the buffer size of node i of the selected path;
S(i) is the speed of the link that connects node i to node i+1.
Qmax(i), P(i) and X(i) are specified in the topology database.
if &egr; denotes the engineered loss probability on the links of the network then delay Tmax of equation (2) is observed with a probability of &egr;
N
(considering that a packet/cell transmitted over the selected path observes the maximum queuing time at each node of the path). For example, considering the network of the preferred embodiment of the invention, &egr; is a network constant whose value is 5.10
−8
. If N=5 (the path comprises five nodes), then the probability to observe an estimated end-to-end delay Tmax according to formula (2) is 3.10
−37
. This negligeable probability value clearly shows that it is absolutely unrealistic to use formula (2) for estimating the EED in order to check the conformance of the selected path with the delay specified in the connection QoS as with formula (1).
This problem raises the need to have an estimation of the EED which is more accurate than the common Tmax estimation, for the relation (1) to be realistically usable.
SUMMARY OF THE INVENTION
The object of the present invention is to improve the estimation of the end-to-end delay of a path from an origin node to a destination node in a communication network.
In brief, according to the invention this object is achieved by providing a network node for a packet switched communication network, the node having at least one input and at least one output with a queuing delay associated with passage of a packet from one input to one output. The node is characterised in that it comprises logic arranged to provide an estimation of the queuing delay for use in connection routing or other purposes, the estimated queuing delay being such that there is a selected probability for packets to experience a queuing delay larger than the estimated queuing delay based on an approximated probability distribution for packet transmission times through the node.
Another aspect of the invention provides a method for estimating the end-to-end delay of a path comprising N nodes from an origin node to a destination node in a communication network. The method is characterised in that it comprises the following steps of:
a) computing for each node along said path an estimated queuing delay;
b) combining for each node of the path said estimated queuing delay with the propagation time of the link that connects said each node to the next node of said path to provide a second delay value associated with said each node;
c) combining all said second delay values to provide an estimation of the end-to-end delay of said path.
The method of the invention is much more accurate than the common approach of “sum of max delay per node”, because it relies on a probabilistic appro

Affiliated with

Also associated with

Rating

End-to-end delay estimation in high speed communication... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with End-to-end delay estimation in high speed communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and End-to-end delay estimation in high speed communication... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2529337