Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-03
2003-11-25
Hsu, Alpus H. (Department: 2739)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S232000, C370S235000, C370S413000
Reexamination Certificate
active
06654345
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to routing packets in a communication network, and, more particularly, to scheduling routing of packets through nodes of the network to guarantee a data transfer rates and delay bounds between data sources and destinations.
2. Description of the Related Art
Packet networks, such as asynchronous transfer mode (ATM) networks, commonly schedule processing and forwarding of data packets (or “cells” in ATM networks) received at each intermediate node. Such scheduling may be employed to reduce or prevent excessive delay experienced by packets of each user's data connection, termed a virtual circuit connection (VC-connection), as the packets are routed through the node. Scheduling allows network providers to guarantee data transfer rates and bounds for delay through the node and the network. Network providers may then offer these rates and bounds for the VC-connections as a guaranteed service. Minimizing implementation costs for a per-virtual-circuit connection (per VC-connection) scheduling algorithm is a performance objective for designers of packet networks. Such algorithms for scheduling packets may achieve excellent delay and fairness properties by approximating an ideal scheduling discipline, known as a Generalized Processor Sharing (GPS) scheduling algorithm. One exemplary GPS scheduling algorithm is described in A. K. Parekh and R. G. Gallagher, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,”
IEEE/ACM Trans. Networking
, pp. 344-357, June 1993 (hereinafter “Parekh”).
Among GPS scheduling algorithms used by a scheduler of the node, the class of packet-by-packet rate-proportional servers (P-RPS) is known in the art for near optimal delay properties. The schedulers of this class compute, for each packet, or group of packets, queued in the node, a “timestamp” value (the timestamp is also known as the “virtual finishing time”). The timestamp specifies when the packet(s) should be routed (transmitted) relative to packet(s) of the other VC-connections in the node. Several such P-RPS scheduling algorithms well-known in the art are: Packet-by-packet Generalized Processor Sharing (P-GPS), Virtual Clock, Frame-based Fair Queuing (FFQ), Self-Clocked Fair Queuing (SCFQ), and Starting-Potential Fair Queuing (SPFQ). These algorithms differ in the specific measure or function used as the system potential (predefined service time reference that may be calculated on an ongoing basis) to compute the timestamps. These algorithms are described in, for example, Parekh; D. Stiliadis and A. Varma, “Design and Analysis of Frame-based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,”
Proc. SIGMETRICS
'96, pp. 104-115, May 1996; L. Zhang, “Virtual Clock A New Traffic Control Algorithm for Packet Switching,”
ACM Trans. Comp. Syst
., pp.101-124, May 1991; D. Stiliadis and A.Varma, “Efficient Fair Queuing Algorithms for ATM and Packet Networks,”
Tech. Rep
. UCSC-CRL-95-59, December 1995; and S. J. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications,”
Proc. INFOCOM
'94, pp. 636-646, April 1994 (hereinafter “Golestani”).
In addition to delay properties, another measure of scheduling algorithm performance is the “fairness” of the scheduling discipline. Fairness is generally used to characterize the priority or distribution of delay that the scheduler assigns to servicing packet(s) of each connection in the queues when the node is backlogged (i.e., when the queues are not empty while servicing or completing service of a connection). Two measures of fairness are commonly employed in the art. The first fairness measure is the service fairness index (SFI, described in Golestani) that measures the distance (as mathematically defined, such as the Euclidean distance) of the particular scheduling discipline from the ideal fairness of GPS in distributing service to VC-connections that are simultaneously backlogged.
The second fairness measure is the worst-case fairness index (WFI) that measures the maximum amount of time that packets of a backlogged VC-connection may have to wait between two consecutive services (e.g., processing and routing of two separately received groups of packets). WFI is described in J. C. R. Bennett and H. Zhang, “WF
2
Q: Worst-case Fair Weighted Fair Queueing,”
Proc. INFOCOM
'96, pp. 120-128, March, 1996. Schedulers with minimal WFI are known in the art as worst-case-fair schedulers and are desirable, since the distribution of service to competing connections in a scheduler with small WFI is much less bursty than in a scheduler with a large WFI.
A P-RPS worst-case fair scheduler may employ “smallest eligible virtual finishing time first” (SEFF) packet-selection. With SEFF, the scheduler grants the next service to the packet of a VC-connection having the minimum timestamp among those packets satisfying an “eligibility condition.” The eligibility condition may be that the packet of a VC-connection have a starting potential (or virtual starting time) that is not greater than the current value of system potential. For each VC-connection, the eligibility condition needs to be verified only for the packet at the head of the corresponding queue, since this is the packet with the minimum starting potential among all packets in that queue. Depending on the specific P-RPS algorithm employed, the scheduler with SEFF selection may be work-conserving (e.g., P-GPS and SPFQ algorithms) or non-work-conserving (e.g., Virtual Clock and FFQ algorithms). A P-RPS scheduler employing SEFF selection may have optimal delay bounds, be worst-case fair, and have an SFI close to the theoretical lower bound in packet-by-packet servers. SEFF selection is described in J. C. R. Bennett and H. Zhang, “Hierarchical Packet Fair Queueing Algorithms,”
Proc. SIGCOMM
'96, pp. 143-156, August 1996; and D. Stiliadis and A. Varma, “A General Methodology for Designing Efficient Traffic Scheduling and Shaping Algorithms,”
Proc. INFOCOM
'97, April 1997.
Four factors contribute to a total implementation cost for a P-RPS worst-case fair scheduler. The first factor is the complexity of calculating or maintaining the system potential, which factor is generally specific to the particular scheduling algorithm (e.g., for a scheduler supporting V VC-connections, this complexity is O(V) for the P-GPS algorithm, O(logV) for the SPFQ algorithm, and O(1) in Virtual Clock and FFQ algorithms, where O(*) is the mathematical relation “on the order of *”) The other three factors, common to all P-RPS worst-case fair schedulers, are: (i) the complexity of identifying the eligible packets, (ii) the cost of handling and storing the timestamps, and (iii) the complexity of sorting the timestamps of the eligible packets in order to select the one with minimum timestamp for the next service. The complexity of implementing SEFF is a considerable burden when the scheduler's implementation is based on conventional priority queues, since a worst-case of O(V) packets may become eligible for service at the same time.
Discrete-rate scheduling may be used instead of conventional priority queues when the scheduler is only required to support a relatively small discrete set of guaranteed service rates at any time. In the discrete-rate scheduler, backlogged VC-connections with the same service rate are grouped together in a First-In-First-Out (FIFO) rate queue, and only packets for VC-connections at the head of each FIFO rate queue are scheduled for service. Thus, the number of VC-connections for which the eligibility condition must be determined and the number of corresponding timestamps to be sorted are significantly reduced (equal to the number of supported service rates). Consequently, the complexity of implementing the SEFF policy is considerably decreased. In the case of P-RPS worst-case fair schedulers, discrete-rate scheduling yields negligible degradation in delay bounds when compared to conventional priority queues
Chiussi Fabio M.
Francini Andrea
Agere Systems Inc.
Hsu Alpus H.
Hughes Ian M.
Mendelsohn Steve
Stevens Robert
LandOfFree
Single-bit timestamps for data transfer rate and delay... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single-bit timestamps for data transfer rate and delay..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-bit timestamps for data transfer rate and delay... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3147143