Available bit rate scheduler

Abstract

An available bit rate scheduling method and apparatus for asynchronous transfer mode communication of a plurality of cells over a network characterized by a system clock frequency f and an allowed cell rate ACR. Each cell belongs to an assigned virtual circuit communication channel which is defined by a set of negotiated traffic parameters. The invention partitions the ACR's of the virtual circuits into a smaller subset of profiles/sub-profiles and conducts a deterministic search to service them. The scheduler incorporates a profile generator for iteratively generating a number p of the profiles by (i) outputting a k*modulo 2.sup.i th one of the profiles during each kth iteration of the profile generator, where 1.ltoreq.i.ltoreq.p and 1.ltoreq.k.ltoreq.p-1; (ii) outputting a null profile during each 2.sup.p th one of the iterations; and, (iii) dispatching the profiles from the profile generator to the profile queue such that a particular profile is dispatched at a time T=T.sub.0 +(1/ACR)*f, where T.sub.0 is the dispatch time of a profile dispatched immediately prior to the particular profile. A profile queue coupled to the profile generator receives and sequentially stores the generated profiles. A virtual circuit processor sequentially receives the profiles from the profile queue and, for each one of the received profiles, dispatches to an output queue all virtual circuits which are characterized by the one received profile.