Subject: RE: QDIM issue: the SchedulingService classes

From: "Weiss, Walter" <[email-masked]>
Date: Mon, 21 Aug 2000 15:48:33 -0400

Andrew,

I think I heard you agreeing with both Bob and I. I think you agree with Bob
that there is only one scheduler. I think you also agree with me that
scheduling parameters are part of the scheduler and not the queue. The
question here is what does the scheduler do and how should it be
represented. In my mind the scheduler contains a set of table entries one
per input. These entries determine how that input is drained relative to the
other inputs and external constraints such as bandwidth over time
(non-work-conserving).

The easiest way I can think of to represent this is as some variant of a
table of union structs. It is a union because it is possible to have very
dissimilar scheduling rules (priority and bandwidth) within the same
scheduler. Combining all possible properties for all possible schedulers
makes interoperable interpretation of the table next to impossible. Further,
it makes it difficult to expand as new algorithms are defined.

This table constitutes the essence of the scheduler. Further each row has an
implicit or explicit effect on other rows. For example, the collective
bandwidth allocation may not exceed 100% of the link utilization. Excess
capacity in one queue may only be allocated to a specific set of other
queues. The enabling or disabling of one queue can influence the weights,
priorities, or bandwidth allocations of other queues.

My thinking is that a scheduler contains a table or potentially diverse
structures that collectively represent a scheduler. The table is indexed by
the queue number. Therefore, I would preserve all the scheduler classes,
their properties, their associations to the queuing service, and the
association for excess capacity scheduler, but rename all the classes to
indicate that they are not a scheduler, but entries in a scheduler table.
Then create a scheduling service that aggregates the various entries. If
there are any properties global to the service (I can't think of any off
hand), then they can be placed there.

regards,

-Walter

> -----Original Message-----
> From: Andrew Smith [mailto:[email-masked]]
> Sent: Monday, August 21, 2000 3:15 PM
> To: Weiss, Walter
> Cc: [email-masked]'; [email-masked]
> Subject: Re: QDIM issue: the SchedulingService classes
> 
> 
> I think Walter is right on this one although it's not clear 
> to me what he thinks
> needs fixing in the Model draft. The Model authors struggled 
> with this one too.
> The most "correct" model (I think) is that the scheduler has 
> multiple inputs:
> each input has a set of parameters associated with it that 
> describe how the
> scheduler will handle traffic arriving on that input. This has nothing
> whatsoever to do with the elements that are upstream from the 
> scheduler - they
> could be queues, they could be whatever you choose. So, the 
> model ought to allow
> for a multi-input scheduler with multiple sets of parameters.
> 
> Unfortunately, with the SMI syntax available to us, there was 
> no way to
> represent this cleanly in the MIB: the indexing does not work 
> well. So we chose
> to move any "per-input" scheduler parameters back (upstream) 
> to a "queue table".
> To quote diffserv-mib-04:
> 
> "The Scheduler Table represented in this MIB module contains entries,
> each of which represents the algorithm in use for servicing the one or
> more queues that feed it. The [MODEL] section 7.1.2 describes a
> scheduler with multiple inputs: this is represented in the MIB by
> including the scheduling parameters associated with a 
> scheduler input in
> the Queue Table entry that feeds it and having that point at one
> particular Scheduler Table entry. In this way, sets of Queues can be
> grouped together as inputs to the same Scheduler.  This table 
> serves to
> represent the example scheduler described in the [MODEL]: other more
> complex representations might be created outside of this MIB."
> 
> I don't see a big problem with this. The QDIM might also have 
> to make similar
> concessions in clarity to work with whatever syntax 
> limitations you have there.
> 
> Andrew
> 
> 
> > "Weiss, Walter" wrote:
> > 
> > Bob,
> > >
> > > Here's the fundamental issue we need to resolve:
> > >
> > > -- Bob:
> > > >> An instance of any of the scheduling service classes
> > > >> represents a scheduler, which is a component that
> > > >> services a set of queues according to the parameters
> > > >> of some scheduling algorithm.
> > 
> > This is where the real problem is. All the parameters for 
> the scheduler apply
> > to specific individual instances of particular queues. 
> However, they are
> > parameters of the scheduler, not the queue, and not the 
> binding of the queue
> > and scheduler.
> > 
> > > >> A priority scheduler
> > > >> services queues based on static priority values
> > > >> associated with each queue.
> > > >
> > > --Walter:
> > > >This is a slightly inaccurate description. Each 
> Scheduling Service
> > > instance represents >the scheduling parameters associated
> > > with a single
> > > queue. The bandwidth scheduler >determines that a single
> > > queue is entitled
> > > to. This is why the cardinality for >SchedulerUsed is 0..1.
> > >
> > > Let's drop the names for a minute, and just look at
> > > a picture:
> > >
> > >
> > > Q1 --- A1 ---+     B1
> > >              |   +----+
> > >              +-->|    |
> > > Q2 --- A2 ------>|    |----> outbound link
> > >              +-->|    |
> > >              |   +----+
> > > Q3 --- A3 ---+
> > >
> > > This figure shows three queues, some A's that are
> > > one-to-one with the queues, and a B that takes
> > > the packets from the three queues and places them
> > > on the outbound link.  If this is priority
> > > queuing, then the priorities must be in the A's:
> > > the one B doesn't have the right cardinality,
> > > and you've already argued (correctly, I think)
> > > that the priorities don't belong on the queues
> > > themselves.
> > >
> > > If *appears*, then, that our disagreement is
> > > really one of semantics / terminology:
> > >
> > > Bob:
> > >   A = SchedulerUsed association
> > >   B = PacketSchedulingService
> > >
> > > Walter:
> > >   A = PacketSchedulingService
> > >   B = (not explicitly modeled)
> > >
> > In your proposal, is it possible to model a multi-queue 
> environment where some
> > of the queues use one scheduling discipline and other 
> queues use a completely
> > different one? If you have only a single 
> PacketSchedulingService, but you have
> > moved all the parameters to the association, what is the 
> Service modeling.
> > What are the local properties? How do you propose to 
> distinguish priority
> > bandwidth scheduling from bandwidth priority scheduling? 
> How do you propose to
> > address excess capacity scheduling for bandwidth schedulers 
> when the excess
> > capacity could be allocated either using priorities, packet 
> ratios or
> > bandwidth ratios? This particular issue was solved rather 
> elegantly with the
> > old model.
> > 
> > > If this is really the crux of our disagreement,
> > > then I think that the Diffserv Conceptual Model
> > > very clearly supports my interpretation rather
> > > than yours.  Look specifically at Figure 7, but
> > > also, more generally, at all of the text that
> > > talks about the multiple inputs of a scheduler.
> > 
> > I already said that it is better to fix a problem at the source than
> > perpetuating the problem.
> > 
> > regards,
> > 
> > -Walter
>

---

From: "Andrea Westerinen" <[email-masked]>
Date: Mon, 21 Aug 2000 21:38:42 -0700

RE: QDIM issue: the SchedulingService classesPlease note that modeling using
a table is not "good" OO practice.  Tables exist either because you have
multiple instances of something (best done as a class with instances) or
because you want to relate the rows and columns and put some data at the
right spot in the table.  The latter is really an implementation dependent
way of modeling an association.  There are always two perspectives to a
"relate the rows and columns" table - in this case, the rows and columns
represent queues and schedulers.  The data at the intersection of the row
and column is specific to BOTH the queue and the scheduler - so, it is best
modeled as an association.

I would like to "modelize" Andrew's words since he is working from the
perspective of the "Informal/Conceptual" Model.  Here goes ...

> The most "correct" model (I think) is that the scheduler has multiple
inputs:

Modeled as an association to the Scheduler from all the classes that could
be inputs.

> each input has a set of parameters associated with it that describe
> how the scheduler will handle traffic arriving on that input.

Modeled as properties on the association.

> This has nothing whatsoever to do with the elements that are upstream from
the
> scheduler - they could be queues, they could be whatever you choose.
> So, the model ought to allow for a multi-input scheduler with multiple
sets
> of parameters.

This argues to generalize the SchedulerUsed association and move it up to
ConditioningService in QDIM.  In this way, any of the ConditioningServices
(meters, markers, queues, etc.) could be an input to a scheduler.

> Unfortunately, with the SMI syntax available to us, there was no way to
> represent this cleanly in the MIB: the indexing does not work well. So we
chose
> to move any "per-input" scheduler parameters back (upstream) to a "queue
table".

If you have to use the word, "unfortunately", this means that you are
compromising the semantics to fit the syntax.  This is ok - but makes the
info model more valuable since it describes the semantics correctly.  Also,
another data model that supports a different syntax is not compromised by
the syntax constraints of the first data model.  Note that I am not saying
that the MIB is wrong - it is just a syntax specific rendering of what we
have tried to capture in the info model.  What matters is that the mapping
is reasonable and valid - not that an association MUST map to an
association.  Info models are about achieving consistent and correct
semantics.

> more queues that feed it.

In QDIM, this is the SchedulerUsed association.

> The [MODEL] section 7.1.2 describes a scheduler
> with multiple inputs: this is represented in the MIB by including
> the scheduling parameters associated with a scheduler input in
> particular Scheduler Table entry.

In QDIM, "scheduling parameters" are modeled as properties on the
association between a SchedulingService and a QueuingService
(SchedulerUsed).  The words, "the scheduling parameters associated with a
scheduler INPUT" imply that these parameters are NOT specific to the Queue
or the Scheduler but the relationship between the two.

> In this way, sets of Queues can be grouped together as inputs to the same
> Scheduler.  This table serves to represent the example scheduler described
in the
> [MODEL]: other more complex representations might be created outside
> of this MIB."

In QDIM, an instance of the SchedulerUsed association ties a specific Queue
to a specific Scheduler.  All the associations to an instance of the
SchedulingService class describe the "set of Queues ... grouped together as
inputs to the same Scheduler."

> to make similar concessions in clarity to work with whatever
> syntax limitations you have there.

I actually don't think that we have to make any concessions, related to
modeling this, in QDIM.

HTH,
Andrea

 -----Original Message-----
From: [email-masked] [mailto:[email-masked]]On
Behalf Of Weiss, Walter
Sent: Monday, August 21, 2000 12:49 PM
To: 'Andrew Smith'
Cc: [email-masked]'; [email-masked]
Subject: RE: QDIM issue: the SchedulingService classes

Andrew,

<snip>