Process for the arrangement of equitable-loss packets

Details Process for the arrangement of equitable-loss packets Process for the arrangement of equitable-loss packets

1998-03-04

2002-01-22

Vu, Huy D. (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S468000

Reexamination Certificate

active

06341134

ABSTRACT:

The invention relates to a process for the arrangement of equitable-loss packets. Such a process is particularly applicable in a high-volume integrated services network using the ATM (Asynchronous Transfer Mode) technique. In such a network, which is of the packet switching type, the packets have an interacting connection with the packets from other connections at each node at which a switching element would normally be located.
BACKGROUND OF THE INVENTION
Such networks are designed to allow for communications between applications which call for performance values from the said networks which are becoming constantly more demanding in terms of routing times, jitter (service time variation), packet loss, minimum volume etc.
Traditional packet switching networks are of the type known as best effort; that is to say, they do not provide guarantees of service. The philosophy behind this type of network is that the intelligence is concentrated in the applications, while the network itself is as simple as possible. The result is that, in the event of the network being overloaded, performance values may deteriorate to a substantial degree, which may lead to a significant loss of packets. In addition to this, the joint presence of applications requiring different qualities of service calls for their having a homogeneous type of behavior with regard to congestion, in other words, they are required to obey a rule of reduction in their volume, at the risk of leading to situations in which certain more “aggressive” applications are accordingly favoured, and take up the larger part of the bandwidth, to the detriment of more conservative applications (those which tend more to obey the behavior rule). There is the risk of this phenomenon becoming all the greater, the greedier the applications become in the bandwidth. It accordingly appears unlikely that several audio and video applications are capable of existing together in harmony.
To resolve these problems, a number of arrangement procedures have been applied which allow for a command to be implemented to determine the order in which the packets deriving from different connections will be served. These procedures are referred to as “equitable”, because, when linked to conformity and admission checks, they make it possible to guarantee that a given fraction of the bandwidth of a node is explicitly dedicated to a particular connection. Such a guarantee of volume, extended to all the nodes of a give channel, forms the essential basis for the provision of more sophisticated service guarantees with regard to service time, jitter, or even losses. In a similar way, its relaxation provides the opportunity to improve the use of the network by providing a statistical commitment with regard to the quality of the service supplied.
Accordingly, during the establishment phase of the call, a request relating to the characteristics of the anticipated traffic and performance values is issued. A group of admission check conditions for the connection is tested at each node in the network. The new connection is then accepted by the network if the network resources available are sufficient to satisfy the request for the connection without disturbing existing connections. The network accordingly guarantees that the performance values required will be respected, provided that the subscriber respects the traffic characteristics.
A process for establishing of order is implemented at each node in the network, and consists of determining which packet is to be served for transmission by discriminating between the packets on the basis of the traffic characteristics of their performance requests.
A first establishing of order process known under the service name of “First In, First Out ” (FIFO) makes use of a queue for each output link of a network node, in which the incoming flows are multiplexed.
In the context of the FIFO process used in the traditional manner, Demers et al and Parekh and Gallager have jointly proposed another process known as Generalised Processor Sharing Discipline, or GPS discipline. Descriptions of this process have been given, on the one hand, in the article which appeared in the Journal of Internet Working Research and Experiment, October 1990, pages 3 to 26, and entitled “Analysis and simulation of a fair queuing algorithm”, and, on the other, in another article which appeared in the journal Proceedings of IEEE of Infocom, pages 914 to 924, 1992, entitled “A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks - The Single Node Case”. The basic principle of this process is summarised hereinafter.
Given a collection of weightings r
1
. . . r
N
associated with the flows 1, . . . N. A node implements the GPS discipline, being given two instants s and t, if the quantities of data W
i
(s,t) and W
j
(s,t) serving for two flows i and j active between s and t are such that:
W
i
⁡
(
s
,
t
)
W
j
⁡
(
s
,
t
)
=
r
i
r
j
(
1
)
A flow is active between s and t is at least one packet o the said flow is present in the queue or is in the course of service between the instants s and t.
The weightings r
1
to r
N
are directly proportional to the quantities allocated respectively to the connections 1 to N. Such an establishing of order process may also be considered as equitable in the sense that it allows for the division of the output capacity in precise proportion to the weightings and therefore of the quantities allocated to the different flows.
It is likewise considered that the relationship indicated above defines a fluid model. In fact, if the hypothesis of fluid flow is adopted, it is possible to serve traffic units as small as may be desired, or, likewise, to serve all the flows in parallel. As a result, it is possible to divide the service into precise proportions of the weightings of the flows, at any time. Nevertheless, the problem posed by a fluid model is that of its implementation in the context of flows consisting of packets.
Equation (1) may be rewritten in the form:
W
i
⁢
(
s
,
t
)
r
i
=
W
j
⁢
(
s
,
t
)
r
j
=
q
⁢
(
s
,
t
)
The quantity q(s,t) is referred to as the normalised quantity. For a flow k, this quantity is generally annotated.
w
k
⁢
(
s
,
t
)
=
W
k
⁢
(
s
,
t
)
r
k
.
This can be written as q(s,t)=v(t)-v(s)
The function v(t) represents the development over time of the function q(s,t), and is known as the virtual time function of the system. The virtual time defined in this manner increases in step with the growth of service in the system. It can be shown that v(t) is an incrementing string function, linear in the form of fragments, of which the slope at any moment t is inversely proportional to the sum of the weighting of the flows which are then active.
In current networks, one single flow is served at a given moment, and this service corresponds to the transmission, which cannot be pre-emptied, of a data packet of variable size. As a result of this, it is necessary to approximate the fluid model described above by a mechanism which manipulates the final entities such as the packets, while still approaching as closely as possible to the “ideal” equability of the fluid model. The general principle of known forms of implementation, referred to as fair queuing, and known without distinction as PGPS (Packetized Generalized Processor Sharing) or WFQ (Weighted Fair Queuing) is based on the marking of the packets entering with the aid of the virtual time function of the server, and their insertion in a queue which is selected on the basis of the incrementing markings. The packet selected for transmission is then the first packet in the queue.
SUMMARY OF THE INVENTION
The objective of the invention differs from that of the fluid model described above. It is in fact possible to distinguish between three types of guarantees which must be offered to the user of an adaptive application. The first guarantee relates to the volume. In fact, for the adaptation threshold reasons indicated earlier, it is essential to supply a minimum volume limit which is reserved for the flow under consider

Affiliated with

Also associated with

Rating

Process for the arrangement of equitable-loss packets does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Process for the arrangement of equitable-loss packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for the arrangement of equitable-loss packets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2861527