Packet delay estimation in high speed packet switches

Details Packet delay estimation in high speed packet switches Packet delay estimation in high speed packet switches

1998-03-16

2001-03-13

Rao, Seema S. (Department: 2661)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S252000, C370S412000

Reexamination Certificate

active

06201793

ABSTRACT:

BACKGROUND
In packet-switching communications networks, user information is carried in packets which are routed from the source towards the destination via switches or routers. The switch buffers each packet received from the upstream direction until a decision is made when and on which outgoing link the packet would be forwarded. The time that a packet takes to reach the destination after it leaves the source is called end-to-end packet delay. Different packets travelling between the same source/destination pair may experience different delays which depend on traffic conditions and level of congestion in different switches, scheduling and management policy, and other deterministic and/or random factors.
The end-to-end delay accumulates the link transmission delays, propagation delays and switch processing delays along the route. Whereas the transmission delays and propagation delays are determined by the packet size and the fixed link parameters (capacity, length and signal propagation speed in the medium) and therefore are predictable with small error, the switch processing delays are subject to much larger random deviations. The single main contributor to the switch processing delay is the queuing delay in a switch's buffer.
In-service measurement of packet delay in a switch is an important source of network management information. It allows the switch to monitor the existing level of congestion, to provision a selected quality-of-service, as well as to support other management functions, including admission of a new connection, path selection and load balancing.
The in-service measurements are required on a per-flow basis, i.e., with respect to specific spatial source-destination pairs and to specific packet loss and service priorities. Since the delays of individual packets are experienced at arbitrary moments of time and are, therefore, random variables, the values arrived at in the course of measurement are merely samples from a stochastic process, and therefore require an estimation procedure.
Conventional direct measurements are based on timestamping. When a packet is enqueued, it is assigned a numerical value associated with the current time or clock cycle number. This value is stored with the packet. When the packet is dequeued, the difference between the new current time or clock cycle number and the value stored with the packet constitute a sampled queuing delay. However, packet timestamping in a high-speed packet switch where the number of the simultaneously buffered packets is significantly large incurs significant overhead associated with the buffer space allocated for the timestamps. Therefore, in high-speed packet switches, the direct measurement methods may be unavailable or undesirable.
SUMMARY
Unlike prior art timestamping techniques, the disclosed packet delay estimation method is indirect, as it is based on sampling the queue lengths and measuring the traffic load.
In accordance with the present disclosure, a complex system of queues sharing the same constant rate server, i.e., a switch or a router with associated fixed capacity transmission link, and driven by a sophisticated, albeit known, scheduling scheme is split into logical clusters of queues. The disclosed method estimates packet delay based on a two-level approximation. On the first level of approximation, effects of the fact that the server is shared by other clusters is approximated by an equivalent reduction of the service rate (a concept of effective service capacity). On the second level of approximation, the sampled individual queue lengths within a cluster, coupled with the knowledge of the scheduling discipline, are used to obtain the upper and lower bounds on the occupancy of the equivalent FIFO buffer (a concept of effective buffer occupancy).
Estimate of the delay is then found based on the effective buffer occupancy, and the effective service capacity.


REFERENCES:
patent: 5450394 (1995-09-01), Gruber et al.
patent: 5796719 (1998-08-01), Peris et al.
patent: 5848056 (1998-12-01), Meurisse et al.
patent: 5999534 (1999-12-01), Kim

Affiliated with

Also associated with

Rating

Packet delay estimation in high speed packet switches does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2492749