Packet delay estimation in high speed packet switches
First Claim
1. A method of packet delay estimation in a switch having a plurality of input links which may be assigned to clusters, where each cluster is serviced differently by a scheduler of said switch but all links in a cluster are serviced similarly, and where each link has an associated buffer for storing incoming packets until they are outputted by said switch onto output-links of said switch, the method comprising the steps of:
- for each cluster, measuring buffer load of said cluster, which corresponds to the number of packets that await servicing by said scheduler which are stored in buffers of links assigned to said cluster;
for at least one cluster (cluster i), determining a reduction in service rate for said cluster i by said scheduler because of service provided by said scheduler to clusters other than cluster i, to obtain thereby an effective service capacity for said cluster i;
for said cluster i, determining an effective buffer occupancy of said cluster i to be less than or equal to the measured buffer load of said cluster i and greater than or equal to a measure that accounts for clusters that are serviced in a manner that empties those clusters more quickly than the servicing of said cluster i would empty cluster i, and that accounts for buffer load of clusters having a higher priority than that of said cluster i; and
evaluating an estimated range of packet delay through said cluster i based on said effective service capacity of said cluster i and said effective buffer occupancy of said cluster i.
5 Assignments
0 Petitions
Accused Products
Abstract
An improved packet delay estimation method results from an indirect measurement method that employs an estimation method based on sampled lengths of queues and measured traffic. A complex system of queues sharing the same constant rate server and driven by a non-trivial scheduling scheme is split into logical clusters of queues. The 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. On the second level of approximation, individual queue lengths within a cluster are sampled and, based on the knowledge of the scheduling discipline, used to obtain the upper and lower bounds on the occupancy of the equivalent FIFO buffer. Estimate of the delay is found based on the effective buffer occupancy, and the effective service capacity.
82 Citations
8 Claims
-
1. A method of packet delay estimation in a switch having a plurality of input links which may be assigned to clusters, where each cluster is serviced differently by a scheduler of said switch but all links in a cluster are serviced similarly, and where each link has an associated buffer for storing incoming packets until they are outputted by said switch onto output-links of said switch, the method comprising the steps of:
-
for each cluster, measuring buffer load of said cluster, which corresponds to the number of packets that await servicing by said scheduler which are stored in buffers of links assigned to said cluster;
for at least one cluster (cluster i), determining a reduction in service rate for said cluster i by said scheduler because of service provided by said scheduler to clusters other than cluster i, to obtain thereby an effective service capacity for said cluster i;
for said cluster i, determining an effective buffer occupancy of said cluster i to be less than or equal to the measured buffer load of said cluster i and greater than or equal to a measure that accounts for clusters that are serviced in a manner that empties those clusters more quickly than the servicing of said cluster i would empty cluster i, and that accounts for buffer load of clusters having a higher priority than that of said cluster i; and
evaluating an estimated range of packet delay through said cluster i based on said effective service capacity of said cluster i and said effective buffer occupancy of said cluster i. - View Dependent Claims (2, 3, 4, 6, 7, 8)
where ρ
i is the load of cluster i, and the summation is taken over clusters with higher service priority π
(i) than that of queue j, π
(j).
-
-
6. The method of claim 1 where said scheduler provides different service to different ones of said clusters because said different ones of said clusters are serviced with different priority designations.
-
7. The method of claim 1 where said scheduler provides different service to different ones of said clusters because said different ones of said clusters are serviced with different bandwidth reservation.
-
8. The method of claim 1 where said scheduler provides different service to different ones of said clusters because said different ones of said clusters are serviced either with different priority, or with different bandwidth reservation, or both.
-
5. The method of claim I where the step of determining a reduction of service for cluster i develops a measure for the effective service capacity of cluster i, ci, by the equation
-
{ ( ∑ { π ( i ) > π ( j ) } ρ i + ∑ { λ ( i ) < π ( j ) } min { ρ i , w i } ) , ( 1 - w j ) } , , where ρ
i is the load of cluster i, π
(i) is the priority of cluster i, and ω
i is a reserved bandwidth for cluster i.
-
Specification
-
- Resources
-
Current AssigneeWSOU Investments, LLC (WSOU Holdings, LLC)
-
Original AssigneeLucent Technologies, Inc. (Nokia Corporation)
-
InventorsKhotimsky, Denis Andreyevich, Chen, Xiaoqiang
-
Primary Examiner(s)RAO, SEEMA SRINIVAS
-
Application NumberUS09/039,699Time in Patent Office1,093 DaysField of Search370/230, 370/231-237, 370/412, 370/417, 370/418, 370/252, 370/238, 710/60, 711/151US Class Current370/238CPC Class CodesH04L 2012/5649 Cell delay or jitterH04L 2012/5681 Buffer or queue managementH04Q 11/0478 Provisions for broadband co...
