US 5,706,288 A · 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.

Claims19

Dependent claims

A method of scheduling available bit rate cell transmission over an asynchronous transfer mode communication network characterized by a system clock frequency f and by a plurality of virtual circuit communication channels, each of said virtual circuits characterized by an allowed cell rate ACR expressed by mantissa and exponent portions, said virtual circuits further characterized by a next cell time and a current cell time, said method comprising:

(a) selecting those of said virtual circuits for which said ACR exponent portion is an exact power of two and grouping said selected virtual circuits into a set of p profiles, each of said profiles corresponding to one or more of said selected virtual circuits for which said ACR exponent portion is the same power of two;
(b) for each of said profiles, further grouping said selected virtual circuits into subprofiles, each of said subprofiles corresponding to one or more of said selected virtual circuits for which said ACR mantissa portions are linearly partitioned;
(c) prioritizing said profiles by reference to said ACR exponent portions, allocating highest priority to said profile corresponding to said selected virtual circuits for which said ACR exponent portion is highest, allocating lowest priority to said profile corresponding to said selected virtual circuits for which said ACR exponent portion is lowest, and allocating sequentially intermediate priorities to said profiles corresponding to said selected virtual circuits for which said ACR exponent portions are intermediate said highest and lowest exponent portions;
(d) servicing said profiles in priority sequence by referencing a profile having a given priority twice for each referencing of a profile having priority immediately lower than said given priority, said servicing further comprising comparing said prioritized profiles' next and current cell times to identify profiles corresponding to virtual circuits which are ready for transmission;
and,
(e) transmitting to an output queue said profiles identified as corresponding to virtual circuits which are ready for transmission.

3 more elements

An available bit rate scheduler for asynchronous transfer mode communication of a plurality of cells over a communication network characterized by a system clock frequency f and an allowed cell rate ACR, each of said cells characterized by a virtual circuit communication channel, each of said virtual circuits characterized by one or more profiles, said scheduler comprising:

(a) a profile generator for iteratively generating a number p of said profiles by:
(i) outputting a k*modulo 2.sup.i th one of said profiles during each kth iteration of said 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 said iterations;
(iii) dispatching said profiles from said profile generator to said a 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 said particular profile;
(b) said profile queue coupled to said profile generator for receiving and sequentially storing said generated profiles;
and,
(c) a virtual circuit processor for sequentially receiving said profiles from said profile queue and, for each one of said received profiles, dispatching to an output queue all of said virtual circuits characterized by said one received profile.

4 more elements

(a) selecting those of said virtual circuits for which said ACR exponent portion is an exact power of two and grouping said selected virtual circuits into a set of p profiles, each of said profiles corresponding to one or more of said selected virtual circuits for which said ACR exponent portion is the same power of two;
(b) for each of said profiles, further grouping said selected virtual circuits into subprofiles, each of said subprofiles corresponding to one or more of said selected virtual circuits for which said ACR mantissa portions are linearly partitioned;
(c) for each one of said profiles:
(i) if said one profile is non-zero and if one or more of said subprofiles are allocated to said one profile, then for each one of said subprofiles allocated to said one profile:
(1) selecting a next highest one of said subprofiles allocated to said one profile;
(2) determining said selected subprofile's next cell time;
(3) if said selected subprofile's current cell time is greater than or equal to said selected subprofile's next cell time, then dispatching said selected subprofile to an output queue;
(4) incrementing said next cell time by f/ACR;
(ii) if none of said subprofiles allocated to said one profile have a current cell time greater than or equal to said subprofile's next cell time, then dispatching a null pointer to said output queue;
(iii) incrementing said current cell time by an amount equal to the time required to process one of said subprofiles during said steps (c)(i)(1) through (c)(i)(4);
(iv) if none of said subprofiles are allocated to said one profile, then:
(1) dispatching a null pointer to said output queue;
(2) incrementing said current cell time by an amount equal to the time required to process one of said subprofiles during said steps (c)(i)(1) through (c)(i)(4);
(v) if said one profile is zero, then:
(1) dispatching a null pointer to said output queue;
and,
(2) incrementing said current cell time by an amount equal to the time required to process one of said subprofiles during said steps (c)(i)(1) through (c)(i)(4).

14 more elements

Dependencies are inferred from the claim text.

Available bit rate scheduler

Life of this patent

Available bit rate scheduler

Life of this patent

Abstract

Claims19