Adaptive time slot scheduling apparatus and method for end-points in an atm network

Abstract

A scheduling mechanism for satisfying specified Quality of Service guarantees for each VC of an end-point host in an ATM network and for satisfying low latency requirements of certain VCs while maintaining high throughput. The scheduling mechanism includes at least one time slot ring, a VC table and at least two pending queues. The time slot ring is an array of time slots grouped into clusters. Each slot contains a pointer which contains the virtual channel identifier to be serviced. The VC table is an array of all the VC descriptors. The pending queues are used for queuing a new VC and when the scheduler is unable to find a time slot for a VC it is queued in the pending queue. One pending queue is restricted to VCs requiring low latency and thus need to be serviced prior to servicing other VCs not sharing the same low latency requirements. A second pending queue is used for VCs with a less critical latency requirement. 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 multiple cluster pointers. The scheduler first processes all low latency VCs, and then circularly reads and processes one cluster at a time at the maximum speed allowed by the physical link, and a current slot pointer points to the slot being serviced. For the current time slot, the scheduler first services the VC waiting on this slot, then schedules a new target time slot for this VC after marking the current slot empty.