Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-06-22
2001-03-20
Ton, Dang (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
C370S395430
Reexamination Certificate
active
06205118
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of telecommunications systems, and more particularly to an adaptive time slot scheduling scheme for end-points in ATM networks and particularly suited for providing low latency to a lock manager function in distributed processing systems.
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) networks allow a large number of data flow paths or Virtual Channels (VCs) to be statistically multiplexed over a common link. A high speed ATM connection allows a host end-point device, for example, a computer, to have a large number of simultaneous virtual channels sharing bandwidth of the common link. A challenge in implementing the large number of virtual channels is to achieve specified Quality of Service (QOS) for each virtual channel independent of other virtual channels. The challenge is compounded when a mix of virtual channels with differing requirements for the QOS have to be satisfied.
In order to efficiently accommodate the differing QOS requirements of multiple virtual channels, a scheduler in an end-point device should be able to respond quickly to changes in transmission rates on the individual virtual channels. This is required, for example, for the Variable Bit Rate (VBR) and the best effort or Available Bit Rate (ABR) classes of service. The scheduler should also be able to dynamically adjust the scheduling when new virtual channels are added or old ones are removed or existing virtual channels stop or start sending data temporarily. In addition, the scheduler should also minimize the jitter, that is, changes in cell rate. This is important because ATM switches, which receive streams of cells generated by the scheduler, continuously monitor each VC using a leaky bucket algorithm or Generic Cell Rate Algorithm (GCRA) to check if the switch is adhering to the traffic contract. In the event the leaky bucket overflows, the cells can potentially be dropped by the switch. Accordingly, the scheduler should protect against this by minimizing the jitter. In case of constant bit rate (CBR) channels, a buffer is required at the receiving end to remove the jitter and smooth the incoming flow of cells. Increased jitter will then require a larger buffer.
Scheduling schemes have been proposed in the prior art for scheduling VCs within a switch and within an end-point. Heretofore, these schemes have been unable to meet the requirements necessary for efficient implementation of multiple virtual channels having various transmission rates and differing QOS guarantees. Accordingly, there is a need for a scheduling mechanism capable of implementing specified transmission rates for each virtual channel independent of other virtual channels, wherein the virtual channels include a mix of differing QOS requirements. U.S. patent application Ser. No. 08/580,470, the parent of the present application addresses this need.
A scheduler in an end-point device should also be able to accommodate a low latency QOS requirement of an individual virtual channel. One application where low latency is of concern is the use of an ATM network to build a parallel processing system where individual workstations act as nodes and the ATM network functions as the fabric for inter-processor communication. In this ATM network application it is necessary to have a lock manager, whose messages are typically short and infrequent, for locking a resource when it is accessed by one processor, thereby preventing access to the resource to more than one processor at a time. Since a principal objective for using the ATM network for parallel processing is the potential for increased throughput, the ATM network is a stable fabric. However, the increased throughput is achieved at the expense of high latency. With respect to the lock manager, this cost is very serious as end points are prevented from accessing a resource until it is released by the lock manager operation. Thus reducing latency for the lock manager is critical to realizing high throughout.
SUMMARY OF THE INVENTION
The present invention discloses an apparatus and method for realizing low latency while maintaining high throughput for high priority operations such as lock manager, conveyed in a specific virtual channel (VC) generated by an end-point host in an ATM network. In order to satisfy the specified low latency requirement for the specific VC, the present invention uses a scheduler which utilizes a time slot ring. As the VC's with the less critical latency requirements have specific rates in terms of cells per second, the time slot ring is only defined for these VC's. The scheduler dynamically fills in the various slots of the time slot ring with different VCs to be serviced, and services them only after first servicing all VCs having a low latency requirement.
In one preferred embodiment of the present invention, the scheduler includes a time slot ring, a VC table and at least two pending queues. The time slot ring is an array, wherein each element represents a time slot. The size of the time slot ring is determined by the ratio of the highest rate to the lowest rate to be supported. The VC table is an array of all the VC descriptors. The pending queues are used for queuing a new VC. At least two pending queues are used; one for those VCs requiring low latency and therefore need to be serviced first and the other or others for VCs with less strict latency requirements so that they can be serviced after the first pending queue is empty. Where more than two pending queues are used, service of various levels of latency is possible.
The size of the ring and consequently the memory required to store the ring can be reduced by combining a fixed number of consecutive time slots. Each cluster nominally holds a “Cluster-Size” number of slots. The ring contains cluster pointers which point to the first VC to be serviced. The rest of the VCs in the cluster are linked to the first VC. In order to accommodate different classes of service, each entry in the ring holds two cluster pointers: the High Priority Pointer (HPP) which services the VBR/CBR traffic classes and a Low Priority Pointer (LPP) which services VCs belonging to the ABR/VBR classes.
In calculating the target slot, the scheduler calculates the target cluster. This acts to decrease the memory requirements, but at the expense of reduced accuracy in calculating the target slot since it has to be approximated to the nearest cluster. A variable called the CCTP (Current Cell Time Pointer) is used in all the timing calculations. The CCTP increments every time slot without regard to the cluster size and ensures accuracy of time delay calculations. A Current Cell Time Pointer (CCTP) increments every cell time and points to the cell position which will be sent if the scheduler is not backlogged. A set of Current Slot Pointers (CSHPP and CSLPP) point to the current slot which is being serviced. In a second embodiment of the present invention, a plurality of time slot rings are used to accommodate multiple classes of traffic as defined by the ATM Forum Traffic Management Specification 4.0, hereby incorporated by reference as if fully set forth herein. Multiple time slot rings allow different traffic classes to have different priorities dependent on how the scheduler services the time slot rings. One example of this embodiment uses two rings: a high priority ring for VBR/CBR traffic, and a low priority ring for ABR/VBR traffic.
REFERENCES:
patent: 5751709 (1998-05-01), Rathnavelu
patent: 5914934 (1999-06-01), Rathnavelu
patent: 5914935 (1999-06-01), Saito
Lucent Technologies - Inc.
Ton Dang
LandOfFree
Adaptive time slot scheduling apparatus and method for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive time slot scheduling apparatus and method for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive time slot scheduling apparatus and method for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514460