EXHIBIT F

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 1 of 18
US006018527A 

United States Patent (19) 11 Patent Number: 6,018,527 

Yin et al. (45) Date of Patent: *Jan. 25, 2000 

54) QUEUE SERVICE INTERVAL BASED CELL OTHER PUBLICATIONS 

SCHEDULER WITH HIERARCHICAL Mercankosk, Guven et al., “Multiplexing Spacer Outputs on 

QUEUING CONFIGURATIONS Cell Emissions," IEEE Infocom 1995, Boston, Apr. 1995, 

pp. 49-55. 

J. Rexford et al., “Hardware-Efficient Fair Queueing Archi 

tectures for High-Speed Networks”, IEEE Infocom'96, Mar. 

1996, pp. 638-646. 

J. Hyman et al., “Real Time Scheduling with QOS Con 

stranits”, IEEE J. on Selected Areas in Comm. Vol. 9, Sep. 

1991, pp. 1052–1063. 

Office Action for application Serial Number 08/792,624 

mailed on Jan. 5, 1998, 5 pages. 

75 Inventors: Nanying Yin, Newton; Marty Borden, 

Littleton, both of Mass.; Shiping Li, 

Los Altos, Calif.; Michael Hluchyj, Wellesley, Mass. 

73 Assignee: Nortel Networks Corporation, 

Montreal, Canada 

* Notice: This patent issued on a continued pros 

ecution application filed under 37 CFR Primary Examiner William Luther 

1.53(d), and is Subject to the twenty year Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor & 

patent term provisions of 35 U.S.C. Zafman LLP 

154(a)(2). 57 ABSTRACT 

21 Appl. No.: 08/696,272 To determine when to service a cell queue in an ATM 

network, a cell Scheduler can use an ideal Service interval 

22 Filed: Aug. 13, 1996 time. The ideal Service interval time of each cell queue is the 

51 Int. Cl." ................................ H04L 12/56, H04J 3/16 reciprocal of the bandwidth assigned to that cell queue. An 

52 U.S. Cl. ........................... 370,412; 370/395, 370/468 interval based cell Scheduler is then initialized by Setting a 

58 Field of Search ..................................... 370/235, 236 time reference to Zero and Setting a next Service time for 

370/375, 378, 389, 395,399 412. 415. each queue to the queue's ideal Service interval. The cell 

46.45.426 Scheduler then enters a repeating loop. During each iteration 

s as of the loop, the first nonempty cell queue having the Smallest 

56) References Cited next Service time value is Selected. The Selected queue is 

Serviced and its next Service time is updated by adding its 

U.S. PATENT DOCUMENTS ideal Service interval. The time reference value is also 

4,979,165 12/1990 Dighe et al. .............................. zoo updated. If all the queues are empty, then an idle time slot 

5,268,900 12/1993 Hluchy et al. .. ... 370/94.1 is allowed to pass. The cell queues may consists of queue 

5,463,620 10/1995 Sriram ....................................... 370/60 groups. For example, Several queues can be gathered into a 

5,500.858 3/1996 Mckeown. queue group that assigned a single ideal Service time. Within 

5.533,020 7/1996 Byrnet al.. this queue group, each queue may be Serviced equally using 

5,577,035 11/1996 Hayter et al.. a fair queuing System. 

5,629,918 5/1997 Calvignac et al. ...................... 370/237 

5,640,389 6/1997 Masaki et al. ....... ... 370/418 14 Claims, 11 Drawing Sheets 

CBR 

WBR 

MULTIPLE OOS ABR 

QUEUES AND/OR PER VC SHAPING UBR 

PER VC SHAPING (VSIVD) PER VC OUEUES 

MQOS WCSHAPING WCSHAPING FAIR OUEUES 

QUEUES GROUPS 

SERVICE INTERVAL-BASED SCHEDULER 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 2 of 18
U.S. Patent Jan. 25, 2000 Sheet 1 of 11 6,018,527 

\VI Ioso)|H 

`N BIWISEnEnD ||||| Tyap?9 

 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 3 of 18
U.S. Patent Jan. 25, 2000 Sheet 2 of 11 6,018,527 

OUEUE OUEUE QUEUE 

2 

NOOS 

QUEUES 

SERVICE INTERVAL-BASED SCHEDULER 

OUTGOING 

PORT 

FIG 2 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 4 of 18
U.S. Patent Jan. 25, 2000 Sheet 3 of 11 6,018,527 

ASSIGNANINTERVAL TIMEI()TO 310 

EACH OUEUE OR OUEUE GROUP 

315 INITIALIZE SCHEDULER 

TR = 0 

FOR i = 1 TON 

T(1) = (i) 

330 

DLE TIME 

—> 

SLOT 

ALL 

YES QUEUES 

EMPTY 

? 

SELECT ANONEMPTY QUEUE WHERE: TG)= MINIMUM (T(k) FOR ALLk) 

333 

SERVICE QUEUEC) 

Tprev=TC) 

TC) = MAX(TR, Tprev) + () 

IFTR < Tprev THENTR = Tprev 

FG 33A 

 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 5 of 18
U.S. Patent Jan. 25, 2000 Sheet 4 of 11 6,018,527 

I(2) = 6 --> T(2) = 6 ANDTR - O 

4 

1 10 6 4 

2 

3 

4 

5 

6 

7 

8 

9 

FG 33B 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 6 of 18
U.S. Patent Jan. 25, 2000 Sheet S of 11 6,018,527 

O 10 6 4 4 4. OUEUE 3 

2 6 EMPTY 

3 

4 

5 OUEUE 3 

6 NON-EMPTY 

7 

8 

9 

O 

FIG BC 

 

 

 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 7 of 18
U.S. Patent Jan. 25, 2000 Sheet 6 of 11 6,018,527 

410 

FOR ANN QUEUE SYSTEM, 

ASSIGN AN INTERVAL (i) WHERE 

FORj= 1 to Ns' 

Rmin = 0 

Rnext = oo 

FOR = 1 TON 

RC)= Max(RC) - Rmin, 0) IF(RC) < Rnext) AND (QUEUEC)7EMPTY) THEN 

Rnext = R() ("Save queue Service time "I i=j f" Save queue ID "l 

} 430 

DLE TIME SLOT 

Rmin Rnext 

TRANSMIT CELLFROMQUEUEC) R(i) = Rmin+1() 

FIG 4 

 

 

 

 

 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 8 of 18
U.S. Patent Jan. 25, 2000 Sheet 7 of 11 6,018,527 

#. 

ETTETTO 

Sc}(\OH0/SETTEÑO SOON 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 9 of 18
U.S. Patent Jan. 25, 2000 Sheet 8 of 11 6,018,527 

BTE] [E]GIOA 

9) o£DIIQH 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 10 of 18
U.S. Patent Jan. 25, 2000 Sheet 9 of 11 6,018,527 

READ VIRTUAL CONNECTION OUEUEID 

FROM HEAD OF QUEUE LIST. 

TRANSMITA CELL FROM THAT OUEUE 

THE OUEUE 

NOW EMPTY 

? 

730 

REMOVE THE ENTRY FOR THIS 

OUEUE FROM THE QUEUE LIST 

MOVE THIS ENTRY TO THE 

TAL OF THE OUEUE LIST 

WAIT FOR NEXT SERVICE 

OF THIS QUEUE GROUP 

FIG 7 

 

 

 

 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 11 of 18
U.S. Patent Jan. 25, 2000 Sheet 10 of 11 6,018,527 

SETETTO OAHEIdSE(TETTO HIVHET 

HETOOJEHOS OESW/8-TWAHHINI BOIAHES 

43 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 12 of 18
U.S. Patent Jan. 25, 2000 Sheet 11 of 11 6,018,527 

PER VC OUEUES 

WCID 

CALENDAR so VCD 930 

o 930 

f O o 930 ve 930 

-> --TIME INTERVAL A 

INDEX 910 

CALENDAR SIZE 

FG 9) 

 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 13 of 18
6,018,527 

1 

QUEUE SERVICE INTERVAL BASED CELL 

SCHEDULER WITH HIERARCHICAL 

QUEUING CONFIGURATIONS 

FIELD OF THE INVENTION 

The present invention relates to the field of computer networking. In particular the present invention discloses a 

cell Scheduling System for an Asynchronous Transfer Mode 

(ATM) network. 

BACKGROUND OF THE INVENTION 

Asynchronous Transfer Mode (ATM) is a digital commu 

nication Standard for transmitting information. In the ASyn 

chronous Transfer Mode system, the information to be 

transmitted is divided into fifty-three byte units known as 

“cells.” The fifty-three byte cells of information are trans 

mitted from a Source node to a destination node through an 

ATM network constructed of communication lines and ATM 

Switches. 

In an ATM System, information is communicated from a 

Source node to a destination node through a defined path 

known as a “virtual circuit'. The virtual circuit is set up 

when a connection is needed and later torn down when the 

connection is no longer needed. Each Virtual circuit is 

defined by Several parameterS Such as Quality of Service 

(QOS) parameters and traffic parameters, the latter of which 

may include a required bandwidth. Once a virtual circuit has 

been established, all cells will travel along the Same Set of 

intermediary nodes between the Source node and the desti 

nation node until the virtual circuit is torn down. However, 

when a Subsequent Virtual circuit is established between the 

same source node and destination node, the Subsequent Virtual circuit may not consist of the same intermediary 

nodes. 

Within each ATM node, the ATM node must Switch ATM 

cells from incoming communication lines to outgoing com 

munication lines. Since a virtual circuit may have a defined 

required bandwidth amount, the ATM node must carefully 

Schedule cell Servicing Such that the Virtual circuit receives 

its required bandwidth and QOS requirements. To perform 

this function, a cell Scheduler is implemented for each 

outgoing communication line. The cell Scheduler allocates 

the bandwidth of its associated communication line to the 

Virtual circuits or groups of Virtual circuits that are assigned 

to use that communication line. Then the cell Scheduler must 

Schedule cells from queues associated with each Virtual 

circuit or virtual circuit group Such that each receives its 

allocated bandwidth. 

SUMMARY OF THE INVENTION 

It is therefore, an object of the present invention to Service 

a Set of quality of Service queues Such that each queue 

receives its allocated bandwidth and unused bandwidth is 

shared fairly among active queues. This and other objectives 

are achieved by the interval based cell scheduler of the 

present invention. 

In the interval based cell scheduler of the present invention, each cell queue is assigned an ideal Service 

interval time. The ideal service interval time of each cell 

queue is the reciprocal of the bandwidth assigned to that cell 

queue. The Scheduler is then initialized by Setting a time 

reference to Zero and Setting a next Service time for each 

queue to the queue's ideal Service interval. The cell Sched 

uler then enters a repeating loop. During each iteration of the 

loop, the first nonempty cell queue having the Smallest next 

1O 

15 

25 

35 

40 

45 

50 

55 

60 

65 

2 

Service time value is Selected. The Selected queue is Serviced 

and its next Service time is updated by adding its ideal 

Service interval. The time reference value is also updated. If 

all the queues are empty, then an idle time slot is allowed to 

pass. The cell queues may consists of queue groups. For 

example, Several queues can be gathered into a queue group 

that is assigned a single ideal Service time. Within this queue 

group, each queue may be Serviced equally using a fair 

queuing System. 

Other objects, features, and advantages of present inven 

tion will be apparent from the accompanying drawings and 

from the following detailed description that follows below. 

BRIEF DESCRIPTION OF THE DRAWINGS 

The objects, features and advantages of the present inven 

tion will be apparent to one skilled in the art, in view of the 

following detailed description in which: 

FIGS. 1a and 1b illustrate a block diagram of a shared 

memory ATM Switch. 

FIG. 2 illustrates a conceptual diagram of a Scheduler that 

must Service N quality of Service queues. 

FIG. 3a illustrates a generalized flow diagram of the cell 

Scheduling method of the present invention. 

FIG. 3b illustrates a first example of the cell scheduling 

method of the present invention in operation. 

FIG.3c illustrates a second example of the cellscheduling 

method of the present invention in operation. 

FIG. 4 illustrates a flow diagram of one embodiment of 

the cell Scheduling method of the present invention for 

Systems with a limited number of queues. 

FIG. 5 illustrates cell Scheduling System that uses hierar 

chical queues. 

FIG. 6 illustrates a conceptual diagram of a fair queue implemented using a linked list. 

FIG. 7 illustrates a flow diagram that describes how a fair 

queue can be implemented using a linked list. 

FIG. 8 illustrates cell scheduling system that uses hierar 

chical queues with VC Shaping and interval based cell 

Scheduling. 

FIG. 9 illustrates cell scheduling system that uses VC 

Shaping. 

DETAILED DESCRIPTION OF THE 

PREFERRED EMBODIMENT 

A method and apparatus for implementing an interval 

based cell Scheduling mechanism is disclosed. In the fol 

lowing description, for purposes of explanation, Specific 

nomenclature is Set forth to provide a thorough understand 

ing of the present invention. However, it will be apparent to 

one skilled in the art that these Specific details are not 

required in order to practice the present invention. For 

example, the present invention has been described with 

reference to ATM based communication networks. 

However, the same techniques can easily be applied to any 

type of packet-Switched communication network. 

FIG. 1a illustrates a block diagram of a shared memory 

ATM switch 100. In FIG. 1a a global cell buffer 110 is used 

to store ATM cells that enter the shared memory ATM Switch 

100. Each ATM cell is then referenced using a set of address 

queues that are assigned for each outgoing communication 

line. The address queues Store pointers to cells in the global 

cell buffer 110. When an ATM cell enters the shared memory switch 100 of FIG. 1a, the ATM cell is stored into the global 

cell buffer 110. Then, a cell address of cell location is created 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 14 of 18
6,018,527 

3 

for that ATM cell and is placed in one of the outgoing address queues depending on the output port address for the 

ATM cell. Note that the shared memory ATM Switch 

embodiment disclosed in the document is used for illustra 

tive purposes only, the teachings of the present invention can 

be used in other Switch architectures Such as bus type Switches with output buffers. 

FIG. 1b illustrates a conceptual diagram for an outgoing 

port. In the outgoing port in FIG. 1b there is a set of N 

queues. Each queue Stores cell addresses for ATM cells that 

need to be transmitted through the outgoing port. A Sched 

uler 120 accesses each of the address queues Such that all of 

the queues are served. Specifically, the scheduler 120 

accesses each queue at a Sufficient frequency Such that the 

queue receives its allocated bandwidth. When the scheduler 

120 Schedules a queue for Service, the Scheduler fetches an 

ATM cell from the global cell buffer 110 using the cell 

address at the head of the address queue and transmits the 

ATM cell through the outgoing port. 

FIG. 2 illustrates in detail the job that must be performed 

by a cell scheduler. In the illustration of FIG. 2, there are N 

queues that contain cell addresses to cells that need to be 

transmitted. Each of the N queues is assigned a certain 

amount of the outgoing port's bandwidth. Thus, the Sched 

uler 120 must Service each queue in a manner Such that each 

queue receives its allocated bandwidth. 

An Interval Based Cell Scheduler 

A Scheduler must perform two important functions: traffic 

isolation and Statistical sharing. Traffic isolation refers to the 

fact that each queue should receive at least its allocated 

bandwidth no matter what the traffic load conditions are in 

other queues. Thus, an overload of one or more of the queues 

should not affect other non-overloaded queues. Statistical 

Sharing is the technique of allowing the unused bandwidth of 

certain queues to be made available to other queues. For 

example, if one or more queues becomes empty, then the 

other nonempty queues will receive the bandwidth that was 

allocated to the empty queues. The allocation of unused 

bandwidth may be proportional to the bandwidth allocated 

to each queue. 

To properly Schedule each queue, the present invention 

uses a Service interval assigned to each queue. The Service 

interval is an interval time that may pass between each time 

the queue is Serviced. The Service interval is the inversion of 

the assigned bandwidth. To best illustrate the interval based 

Scheduling System of the present invention, an example is 

provided wherein: 

BW=the total bandwidth reserved for the cell Scheduler 

out of the output port physical bandwidth in cells per 

Second. 

N=the number of queues that will be sharing the output 

port. 

B(i)=For i=1 to N, B(i) is the allocated bandwidth for ith 

the queue in cells per Second. 

The allocated bandwidth B(i) is an important parameter 

that defines the transmission bandwidth for a virtual circuit 

or a group of Virtual circuits in an asynchronous transfer 

mode network. The allocated bandwidth B(i) is used by a 

call admission control unit to admit or reject a call depend ing on the required bandwidth. AS previously Stated, the 

present invention uses the inverse of the allocated 

bandwidth, known as the ideal service interval I(i), as the 

primary variable which determines when cell Scheduling 

will occur. The ideal Service interval defines a maximum 

amount of time in Seconds that may elapse between cells for 

a given queue being Scheduled. Specifically: 

15 

25 

35 

40 

45 

50 

55 

60 

65 

4 

I(i)=1/B(i)=the ideal service interval for the ith queue. The scheduler creates a service time variable T(i) for each 

queue i where i=1 to N. The service time specifies a “time” 

when the queue should be serviced next. The service time 

variable T(i) is first initialized with the assigned service 

interval I(i). The Scheduler then begins Servicing the queues by Starting with the queuei having the Smallest Service time 

TG). This queue j is serviced and the Service time T() is 

incremented using the Service interval IG). Then the queue jhaving the Smallest Service time T() is again Serviced Such 

that the Scheduler repeats this pattern. 

FIG. 3a illustrates a generalized flow diagram of the cell 

Scheduling method of the present invention. At the first Step 

310, a cell interval time I(i) is assigned to each queue will 

be served. AS previously mentioned, the interval time IG) is 

equal to the inverse of the bandwidth B(i) allocated to a 

particular queue j. At Step 315 the cell Scheduler is initial 

ized. Specifically, at step 315 a time reference variable TR 

is set to Zero and a Service time TG) for each queue 1 through 

N is set to the queue's interval time IG). After the initial 

ization Step 315, the cell Scheduling method is ready to begin Servicing cells from queues. 

If all of the queues are empty at step 325 then the method 

proceeds to step 330 where an idle time slot is allowed to 

pass. After the idle time slot of step 330, the scheduling 

method returns to Step 325 again. 

At step 320, the scheduling method selects the first non 

empty queue j, where T() is the Smallest T(k) where k=1 

through N. 

After having Selected a nonempty queue j with the Small 

est Service time TG), then that queue j is serviced at Step 333. 

Next, at step 335 the next service time TG) for that queue j is determined. Specifically, a temporary variable Tprev is set 

to the currentTG) in order to store the previous Service time. 

Then, the service time TG) is set to the maximum of the time 

reference TR and the previous service time TG) and this is 

added to the Service time interval I(i) for that queue. Finally, the time reference value TR is updated. Specifically, if the 

time reference value TR is less than the previous service 

time Tprev of queue j, then the time reference value TR is 

set to the previous service time Tprev. The method then 

proceeds back to Step 325 and repeats the same Steps again. 

FIG. 3b illustrates an example of the scheduling method 

of FIG. 3a in use. In FIG. 3b there are three connections 1, 

2, and 3 where the Service interval of connection one is Set 

to ten, the Service interval of connection 2 Set to Six and the 

Service interval of connection 3 is set to four. These service 

intervals could be in units of microseconds. However, for 

Simplicity of the example, the exact magnitude is not nec 

eSSary. 

According to the initialization Stage of Step 315, the time 

reference value TR is set to zero and the service time TG) for 

connections 1, 2, and 3 is set to the connection's respective 

interval times. Thus, the Service time for connection 1 is Set 

to ten, the Service time for connection 2 is Set to Six and the 

Service time for connection 3 is set to four. The chart of FIG. 

3b then illustrates a series of iterations of the scheduling 

method, Starting with iteration 1 where the initial Situation is 

presented. 

Referring to step 320 of FIG. 3a, the nonempty queue 

having the Smallest minimum Service time TG) is selected. 

Thus, in the first iteration of FIG. 3b, the service time T(3) 

for connection 3 is Selected Since the next Service time value 

T(3) is four. Connection 3 is therefore serviced and the next 

Service time value T(3) for connection three is incremented. 

Specifically, T(3) is set to the previous connection time plus 

the service interval time I(3) of four. Thus, the next service 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 15 of 18
6,018,527 

S 

time T(3) for connection 3 is set to eight. The time reference 

value TR is also updated. The time reference value TR is set 

to the previous service time Tprev which is four. 

Next, at iteration 2, the service time T(j) that is the 

Smallest is for connection 2 with a service time T(2) of 6 

Such that connection 2 is serviced. The service interval of 6 

then is added to the current Service time to produce a next 

Service time T(2)=12. At, the following iteration, queue three again has the earliest service time T(3) with the service 

time of 8 Such that queue 3 is Served again. The remainder 

of FIG. 3b illustrates how the algorithm would continue 

along provided that none of the queues become empty. In 

this example, tie resolution favors earlier index, but other 

resolution is also possible. 

FIG. 3c illustrates a second example of the method of the 

present invention wherein one of the queues becomes empty while the Scheduling method is operating. The example of 

FIG. 3c uses the same initial data as the example of FIG. 3b. 

In iteration one of FIG. 3c, queue 3 is selected as the first 

queue to Service Since queue 3 has the Smallest Service time 

T(3). After this iteration it is assumed that queue 3 becomes 

empty. In the next iteration, queue 2 is Selected Since it has 

the smallest service time T(2)=6. The service time T(2) for 

queue two is updated Such that T(2)=12 after the update. 

In iteration 3, queue 3 has the smallest service time with 

T(3)=8. However, since queue 3 is empty, the next smallest 

Service time is Selected. In this case, the Smallest Service 

time for nonempty queue is T(1)=10. Queue 1 is thus 

Serviced and its next Service time is updated Such that 

T(1)=20 after the update. In iteration 4, queue 3 again has 

the Smallest service time since T(3)=8. However, queue 3 is 

still empty so that the next smallest service time is that of for 

queue 2 which has a Service time T(2)=12. Thus, queue 2 is 

Serviced and its next Service time is updated Such that 

T(2)=18 after the update. In iteration 5, queue 3 is still empty 

such that the next smallest service time is T(2)=18 such that 

queue 2 is Serviced again. After iteration 5, queue 3 receives 

Some ATM cells Such that queue 3 is no longer empty. Thus, 

at iteration 6 the service time T(3)=8 for queue 3 is selected 

and queue 3 is Serviced. The next Service time for queue 3 

is set to be the current time reference TR plus queue 3’s 

interval time I(3) of 4. Thus, the next time reference service 

time for queue three is set to be 22 since 18 (TR) plus 4 (I(3)) 

is 22. 

The generalized scheduling method disclosed in FIG. 3a 

should be modified slightly in an implementation in order to 

prevent variable overflow. Specifically, the service time 

variables will wrap around after reaching a maximum value. 

One method of preventing variable overflow is disclosed in 

section 10.5 of the book “Internetworking with TCP/IP, vol. 

2", Prentice Hall, N.J., 1991 by Douglas E. Comer and 

David L. Stephens (Herein after Corner-Stephens). The 

“Sequence Space Comparison” disclosed in the Corner 

Stephens reference explains how it is unnecessary to main 

tain arbitrarily large Sequence numbers as long as the 

maximum increment is no more than % of the largest integer that can be represented. 

FIG. 4 illustrates one implementation of the scheduling 

method for Systems that have a limited number of queues to 

Service. The Scheduling method implementation illustrated 

in FIG. 4 could be appropriate for systems with limited 

number of queues (e.g., 16 queues) depending on the line 

Speed and processing Speed. 

Referring to FIG. 4, in step 410 the interval time for each 

queue is set. Next in step 415, a relative service time R() is 

Set for each queue j to the interval time IG) and a minimum 

relative Service time Rimin is set to Zero. The repeated Scheduling Steps begin at Step 420. 

15 

25 

35 

40 

45 

50 

55 

60 

65 

6 

In step 420 a variable Rnext is set to the highest value that 

the Rnext variable can hold. In FIG. 4 this value is illustrated 

as infinity, however in practice it will probably be the largest 

integer the variable can represent. Next, the Step 420 goes through a loop that examines every queue 1 through N. The 

first step of the loop reduces the relative service time R(i) for 

each queue by Subtracting off the value Rimin. In the very 

first iteration nothing will be Subtracted Since Rimin is Zero. 

A maximum value is Selected between this Subtraction and 

Zero, Such that the relative Service time for any queue is 

never less-than-Zero. This Subtraction Step ensures that the 

relative service times for the queues will not overflow. 

Next, the loop in step 420 determines if the current queue j is not empty and if the relative service time RG) for the 

current queue is Smaller than the next relative Service time 

Rnext. If the queue is nonempty and the relative Service time 

R() for the current queue is Smaller, then this relative 

Service time R() becomes the next relative Service time 

Rnext. Since Rnext is initially Set at infinity, as long as the 

queue is not empty this queue's relative Service time will 

become the next relative Service time and this queues identity will be stored in variable i. Since this comparison is 

done for all of the queues using the loop, the queue with the 

smallest relative service time will be selected by the loop. 

At step 425 Rnext is tested to see if it is equal to the 

infinity value. If Rnext is still infinity, then all the queues 

were empty such that the method proceeds to step 430 where 

an idle time slot is allowed to pass and then back to step 420. 

However, if Rnext is set to a value other than infinity then 

a queue has been Selected for Service. At Step 435, a cell is 

transmitted from the Selected queue. Rimin is Set to the 

current Rnext value Since it was the Smallest relative Service 

time. The Rimin value will be used to reduce the relative 

Service times during the next iteration Such that variable 

overflow is prevented. Finally, the relative service time for 

the Selected queue is updated. Specifically, queue i is Set to 

the current Rmin plus the interval time I(i) for that queue. The cell scheduling method then proceeds back to step 420 

where the same Steps are repeated. 

Hierarchical Queuing Configurations 

The interval based cell Scheduling System of the present 

invention can be combined with other cell Scheduling Sys 

tems to implement other hybrid queuing configurations. 

Referring back to FIG. 2, a flat queuing System is illustrated 

where N queues are serviced by the interval based scheduler. 

However, FIG. 5 illustrates an alternate hierarchical queuing 

System that uses the interval based cell Scheduling System. 

Specifically, in FIG. 5 the interval based cell scheduler 

Services a Set of individual queues and a separate Set of 

queue groupS. Specifically, in FIG. 5 there are four indi 

vidual queues labeled one through four and two queue 

groups labeled queue group five and queue group Six. The 

two queue groups, queue group five and queue group Six, are 

serviced by the interval based scheduler as if they were 

individual queues. Specifically, the entire Set of queues 

within each dotted perimeter is Serviced as a Single queue. 

Within each queue group there is another queuing method 

that Schedules cells within each group. In the illustration of 

FIG. 5, queue group five and queue group six each imple 

ment “fair queue System. A fair queue group is a simple 

round robin Scheduling System where each queue within the 

queue group receives an equal portion of the cell Scheduling. 

Thus, each time the interval based cell Scheduler Services a 

queue group, one of the queues in that queue group is 

Selected for Service. 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 16 of 18
6,018,527 

7 

FIGS. 6 and 7 illustrate how a fair queue group can be 

implemented. FIG. 6 illustrates that each queue in the fair 

queue group is assigned a virtual circuit ID value. A linked 

list 600 of active virtual circuits is then created wherein each 

entry in the linked list 600 is identified by its virtual circuit 

ID value. The linked list 600 has a head 610 and a tail 620. 

During each Service time for the queue group, the Virtual 

circuit ID value at the head 610 of the linked list 600 is 

Serviced. If the Serviced queue then becomes empty, then 

that queue is removed from the active virtual circuit linked 

list 600. Otherwise, if the queue is not empty it is moved to 

the tail of the active virtual circuit linked list 600. 

FIG. 7 illustrates a flow diagram that describes how the 

Fair queue is implemented. At step 710 the virtual circuit 

queue ID value is read from the head of the active virtual 

queue list. The cell is then transmitted from the queue with 

that Virtual circuit queue ID value. Next, that queue is tested 

to see if the queue is empty at Step 720. If the queue has 

become empty, then the queue is removed from the active 

queue linked list at step 730. If the queue has not become 

empty then the entry for that virtual circuit queue ID value 

is moved to the tail of the linked list at step 740. At step 750, 

the queue group waits until the next Service time for the 

queue group. When the next Service time arrives, the method 

moves back to step 710 and repeats the steps. 

Other types of Scheduling Systems can also be combined 

with the interval based cell scheduling system. FIG. 8 

illustrates another hierarchical queuing System that uses the 

interval based cell Scheduling System as the main Scheduler 

but also includes VC Shaping Schedulers. Specifically, in 

FIG. 8 VC shaping cell schedulers are used the schedule 

cells for a set of queue groups. 

Per VC scheduling/shaping may be needed for better 

traffic isolation as well as the implementation of Virtual 

Source for ABR. In Per VC scheduling/shaping, cells from 

each VC queue are Scheduled even if for the same 

traffic/QOS class. FIG. 9 illustrates one example of VC 

scheduling. The per VC scheduler of FIG.9 uses a “calendar 

queue” 920 that comprises a series of time slot entries. The 

time difference between each time slot entry is one Service 

interval I(i). Each active VC queue has an associated VC ID 

930 in the calendar queue 920. There is a current time index 

910 that points to the current reference time in the calendar 

queue 920. The position of each calendar time slot entry 

relative to the current index time 910 represents a relative 

number of time slots in the future. 

When the scheduler is ready to service the cell from a 

calendar queue, the cell from the first VC queue in calendar 

time slot entry pointed by the index 910 is transmitted. If this 

VC queue is non-empty after the cell transmission, then the 

VC ID for that VC queue is moved into a future entry position with a distance from the current index of the inverse 

of the VC rate (e.g., 1/(Peak Cell Rate) for a Constant Bit 

Rate Queue). Each time the calendar queue is visited, its 

reference time index is moved one slot down. There may be 

more than one VC queue Scheduled in one calendar time slot 

entry. If there are additional VCs in the calendar time slot 

entry to be scheduled, the additional VCs are moved to the 

next subsequent calendar time slot entry. The index 910 is 

then incremented and the next calendar entry is Scheduled. 

If a cell arrives at an empty VC queue, then the empty VC 

queue's VC ID is added to the calendar queue at a calendar 

entry position that is the inverse the cell rate from the current 

index 910. 

The foregoing has described an interval based cell Sched 

uler. It is contemplated that changes and modifications may 

15 

25 

35 

40 

45 

50 

55 

60 

65 

8 

be made by one of ordinary skill in the art, to the materials 

and arrangements of elements of the present invention 

without departing from the Scope of the invention. 

We claim: 

1. A method of scheduling cells from a plurality of cell 

queues, Said cell queues organized into cell queue groups, 

Said method comprising the Steps of: 

assigning an ideal Service interval time to each of Said cell 

queue groups, and all cell queues within each of Said 

cell queue groups having a Same quality of Service; 

assigning a next Service time to each of Said cell queue 

groups, 

determining a Selected cell queue group to Service from 

Said plurality of cell queue groups, Said Selected cell 

queue group having a Smallest next Service time and 

Said Selected cell queue group being nonempty; 

Servicing Said Selected cell queue group by Servicing one 

of Said cell queues in Said Selected cell queue group; 

updating Said next Service time for Said Selected cell 

queue group using Said ideal Service interval time, and 

repeating Said Steps of Selecting, Servicing, and updating. 

2. The method as claimed in claim 1, said method further 

comprising the Step of: 

initializing Said next Service times for each of Said cell 

queue groups using the respective idea Service times. 

3. The method as claimed in claim 1, said method further 

comprising the Step of: 

updating a time reference value after updating a next 

Service time, updating Said time reference value com 

prising Setting Said time reference value equal to a 

Smallest next Service time of Said cell queue groups. 

4. The method as claimed in claim 1 wherein said step of 

updating the next Service time for Said Selected cell queue 

group comprises incrementing the next Service time for Said 

Selected cell queue group by Said ideal Service interval time 

for Said Selected cell queue group. 

5. The method as claimed in claim 1, said method further 

comprising the Step of: 

allowing an empty time slot to pass if there is no non 

empty queue group during Said Step of Selecting. 

6. The method as claimed in claim 1, said method further 

comprising the Step of: 

reducing a variable associated with each said next Service 

time associated with each of Said cell queue groups 

Such that Said variable associated with each said next 

Service time associated with each of Said cell queue 

groups does not overflow. 

7. The method as claimed in claim 1 wherein at least one 

of Said cell queue groups has an available bit rate (ABR) quality of Service. 

8. The method as claimed in claim 1 wherein said cell 

queue group is Serviced Selected by Selecting one cell queue in Said cell queue group using a fair queuing System. 

9. A hierarchical queuing apparatus for Servicing cells 

from a plurality of cell queues, said apparatus comprising: 

a plurality of cell queue groups, having, each of Said cell 

queues in a cell queue group having a Same quality of 

Service level, each of Said cell queues Storing repre 

Sentations of cells, each of Said cell queue groups having an assigned ideal Service interval and a next 

Service time; 

an output port, Said output port for transmitting cells, and 

a cell Scheduler, Said cell Scheduler Selecting a cell queue 

group to Service having a Smallest next Service time, 

Servicing a cell queue in Said Selected cell queue group, 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 17 of 18
6,018,527 

9 10 

and then updating Said next Service time for Said 12. The apparatus as claimed in claim 9 wherein at least 

Selected cell queue group using Said Selected cell queue one cell queue group uses a round-robin Scheduling System. 

group's ideal Service interval. 13. The apparatus as claimed in claim 9 wherein at least 

10. The apparatus as claimed in claim 9 wherein each one cell queue group uses a VC Shaping Scheduling System. 

ideal Service interval equals the reciprocal of a bandwidth 5 14. The method as claimed in claim 1 wherein said 

assigned to each cell queue group. Selected cell queue group is Serviced by Selecting one cell 

11. The apparatus as claimed in claim 9 wherein at least queue in Said Selected cell queue group using a VC Shaping of one cell queue group comprises a group one cell group Scheduling System. 

has having an available bit rate (ABR) quality of service level. k . . . . 

Case 6:20-cv-00486-ADA Document 172-6 Filed 03/23/22 Page 18 of 18