Subject: RE: QDIM issue: the SchedulingService classes

From: Walter Weiss <[email-masked]>
Date: Fri, 18 Aug 2000 11:27:13 -0400

> 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.  A priority scheduler
> services queues based on static priority values
> associated with each queue.

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.

> But the QDIM-01 model
> can't represent these priorities:  it has only a
> single-valued Priority property on the
> PrioritySchedulingService object itself.
> 
> What's needed is the ability to have one priority
> value per queue that a priority scheduler is
> servicing.  There are two ways to do this:
> 
What is wrong with what we have now with the property in the
PriorityScheduler?

>   a. Move the Priority property from
>      PrioritySchedulingService to the association
>      SchedulerUsed that sits between a scheduler
>      and each of the queues it services.
> 
>   b. Move the Priority property from
>      PrioritySchedulingService to the class
>      QueuingService.  Note that this is an
>      option only because the cardinality at the
>      PacketSchedulingService end of the
>      SchedulerUsed association is 0..1, which
>      says that a given queue can by serviced
>      by at most one scheduler.
> 
Actually there is also alternative c: Keep the Priority property in the
PrioritySchedulingService. The semantics of a priority scheduler are
distinctly different from bandwidth and packet schedulers. In fact, the
semantics for priority don't exist in bandwidth schedulers at all. Since the
SchedulerUsed association is used for all present and future Schedulers, the
property does not really belong there. Further, as queues can also schedule
packets in a non-priority fashion, putting a property in the queue means
that in many cases the property will be inappropriate or ambiguous.

The final reason for preserving the concept of a priority scheduler is that
there are many implementations of priority schedulers that are actually rate
limiters. In other words, each scheduler has an upper bound on the bandwidth
that that priority is entitled to. Since this is a derivation of a basic
priority scheduler, it makes sense to preserve the distinction between
priority schedulers and other types of schedulers like bandwidth schedulers
(CBQ, WFQ, etc.) and Round Robin schedulers. 

<snip> 
>   - Once we move Priority up to SchedulerUsed,
>     there's no need any more for the class
>     PrioritySchedulingService.  A priority
>     scheduling service is now represented as
>     a PacketSchedulingService whose
>     SchedulerUsed associations all have the
>     Priority property on them.

See comment above for why priority scheduler needs to stay.

>   - Similarly, we no longer need the class
>     PriorityBandwidthSchedulingService:  this
>     is just a BandwidthSchedulingService whose
>     SchedulerUsed associations all have the
>     Priority property.

Interestingly, there is a huge difference between a Priority Service with a
bandwidth limit and a bandwidth service with a priority. It would be a
mistake to combine them because this would lead to semantic ambiguities.

>   - WeightedRoundRobinPacketSchedulingService
>     has a problem similar to the one we just
>     fixed for PrioritySchedulingService.  It
>     has a WeightingFactor property that needs
>     to be one per queue, not one for the whole
>     scheduling service.  The way to fix this
>     problem is to move the WeightingFactor to
>     the associations, just as we did with
>     Priority.  To do this, we need to subclass
>     the SchedulerUsed association to a new
>     association class WRRSchedulerUsed, so we
>     can add the new property to the association.
>     On the scheduler side, this new association
>     goes to WeightedRoundRobinPacketScheduling
>     Service rather than to its superclass
>     PacketSchedulingService.

Again, you are suggesting generalizing properities that are specific to
unique type of scheduler. The whole reason for seperating out these
schedulers was to use inheritance hierarchies to clearly distinguish between
various classes of schedulers. It seems to me that what you are really
suggesting is that we only need one scheduler class and that we create
derivations of the SchedulerUsed association to describe the parameters for
each scheduler. Since I don't think you have proved your case for the first
change, I don't see a good reason to discuss these other cases yet.

>   - Applying the same trick a third time, we
>     define another subclass of SchedulerUsed,
>     BandwidthSchedulerUsed, so that we can
>     move the per-queue property
>     BandwidthAllocation from the class
>     BandwidthSchedulingService up to the
>     association.  This time the class on the
>     scheduler side of the new association is
>     BandwidthSchedulingService.
> 
Ditto.

> Finally, one more change to the scheduler classes,
> which is independent of all the changes we've
> discussed up to this point:  we need to move
> the Boolean property WorkConserving from the
> class BandwidthSchedulingService up to its
> superclass PacketSchedulingService.  The reason
> for doing this is to align with the treatment
> of work-conserving and non-work-conserving
> schedulers in the Diffserv Conceptual Model.
> 
Work Conservation is not applicable to either priority or round robin
schedulers. Therefore, if the conceptual model suggests this, we should fix
the conceptual model.

regards,

-Walter

---

From: [email-masked]
Date: Mon, 21 Aug 2000 12:44:34 -0400

Walter,

Here's the fundamental issue we need to resolve:

--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)

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.

Regards,
Bob

Bob Moore
IBM Networking Software
+1-919-254-4436
[email-masked]

---

From: [email-masked]
Date: Mon, 21 Aug 2000 16:05:43 -0400

Andrew,

This is confusing.  You start out stating that Walter
is correct, but then you go on to demonstrate that
he's not.  Walter is saying that schedulers and their
upstream elements are one-to-one.  If we model it this
way, then there won't be any schedulers with multiple
inputs.  Yet this is exactly what you're talking about
throughout your posting:  scheduler instances with
multiple upstream inputs.

What you've done with the MIB is a reasonable data-model
compromise that does not contradict the information
model I've proposed.  Using the model I've suggested,
instances of the SchedulerUsed association are always
one-to-one with instances of queues feeding the
scheduler.  So you're free to optimize your mapping to
SMI by placing properties from the associations in the
table entries that represent the queues.

Walter's approach would move these same properties not
into the queues' table, but into the schedulers' table.
This is why he makes the schedulers one-to-one with
the queues, that is, restricts a scheduler instance to
servicing only one queue.  This is what I have said is
very different from the Diffserv Conceptual Model,
where one scheduler instance services multiple queues.
You've also demonstrated that it's very different from
the Diffserv MIB:

   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.

Regards,
Bob

Bob Moore
IBM Networking Software
+1-919-254-4436
[email-masked]

Andrew Smith <[email-masked]> on 08/21/2000 03:14:45 PM

To:   "Weiss, Walter" <[email-masked]>
cc:   Robert Moore/Raleigh/IBM@IBMUS, [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,
> > >> 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
> 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.
> I already said that it is better to fix a problem at the source than
> perpetuating the problem.
>
> regards,
>
> -Walter

---

From: [email-masked]
Date: Tue, 22 Aug 2000 13:16:08 -0400

I am re-posting this to the list, because it bounced on the first try.(Ed E.)

Date: Mon, 21 Aug 2000 15:12:00 -0700
From: Andrew Smith <[email-masked]>
Subject: Re: QDIM issue: the SchedulingService classes
To: [email-masked]
Cc: "Weiss, Walter" <[email-masked]>, [email-masked]
Message-Id: <[email-masked]>
Mime-Version: 1.0
X-Mailer: Mozilla 4.6 [en] (WinNT; I)
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Accept-Language: en
References: <[email-masked]>

Bob,

I think I agree 99% with what Walter just wrote in his message of Mon, 21 Aug
2000 15:48:33 -0400. Everything except that where he wrote "My thinking is that
a scheduler contains a table ... that ... is indexed by the queue number." he
should have written "My thinking is that a scheduler contains a table ... that
... is indexed by the *input* number.". It is up to the external plumbing
mechanisms to make the association between any upstream element (e.g. a queue)
and the scheduler input number. See further comment below.

[email-masked] wrote:
> upstream elements are one-to-one.

I don't see where you get this from - he's saying that, for each scheduler
instance, there is a table inside it that is indexed by some "input identifier".
That's not the same as saying that schedulers and their upstream elements are
one-to-one.

The rest of your disagreements with Walter stem from this so I'll leave those
for now.

Andrew

---

From: "Weiss, Walter" <[email-masked]>
Date: Tue, 22 Aug 2000 13:23:27 -0400

John,

Consider a bandwidth scheduler that determines what packet is sent based on
bandwidth allocations associated with queues. Some of the algorithms include
CBQ and WFQ come to mind, although there are many others. The idea is to
maintain fair distributions between queues. However, there may be instances
in these schedulers where their is a tie in which queue should get serviced.
In most cases the order of the queue decides. This is an implicit ordering.
A priority provides an explicit order.

Consider in contrast a simple priority scheduler. In this scenario, the
highest priority queue is drained before the next priority queue may have
access to the link. While this is a very desirable behavior for a PHB like
EF, there is a subtle problem of starvation of the other queues. To prevent
starvation, a rate limiter is introduced into the scheduler to prevent one
or more queues from stealing all the bandwidth.

On the link, the two systems exhibit very different behaviors. The most
notable distinction is that the highest priority queue has the lowest jitter
provided that the traffic does not exceed the limit, whereas in the first
algorithm, the contents of all queues always affects all the queue's delay
variation. Hope that helps.

regards,

-Walter 

> -----Original Message-----
> From: John Schnizlein [mailto:[email-masked]]
> Sent: Monday, August 21, 2000 9:29 PM
> To: Weiss, Walter
> Cc: [email-masked]
> Subject: RE: QDIM issue: the SchedulingService classes
> 
> 
> At 01:40 PM 08/21/2000 -0400, Weiss, Walter wrote: 
> >
> > ... How do you propose to distinguish priority bandwidth 
> scheduling from
> > bandwidth priority scheduling? 
> 
> 
> Could you please specify the distinction you mean here?
> 
>

---

From: [email-masked]
Date: Tue, 22 Aug 2000 14:15:15 -0400

Andrew,

>That's not the same as saying that schedulers and their upstream elements
are
I agree that he's saying this *now*.  I was responding to
the following statement from Walter's 8/18/2000 note:

    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.

Regards,
Bob

Bob Moore
IBM Networking Software
+1-919-254-4436
[email-masked]

---

From: Keith McCloghrie <[email-masked]>
Date: Tue, 22 Aug 2000 14:25:01 -0700 (PDT)

I missed the original message, which is quoted in the below, so I may
have missed some of the context, but:

> I would like to "modelize" Andrew's words since he is working from the
> perspective of the "Informal/Conceptual" Model.  Here goes ...
> 
> 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.
> 

If I understand the need correctly, it would seem fairly straightforward
to represent it "cleanly" in the MIB:  if each input of the multi-input
scheduler has a set of parameters, you just need to add a scheduler-input
table, indexed by scheduler-id and input-id.  The set of parameters would
then be columnar objects in the scheduler-input table.

Keith.

---

From: "Weiss, Walter" <[email-masked]>
Date: Tue, 22 Aug 2000 18:17:34 -0400

Replace <1>  and <2> with table rows and columns of your choice and tell me
how the scheduler is different:
 
<1>                          <2>
InputPort            FilterTable Row
Connection        Security Association
DestIPAddr        Routing Table Entry
Queue               SchedulingTable Entry
 
Please 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 <1> and <2>.  The data at the intersection of
the row and column is specific to BOTH the <1> and the <2> - so, it is best
modeled as an association.

How any of these concepts are implemented is up to the data model.  In the
data model, you make the determination whether you use associations, tables,
arrays or something else.
 
<Walter> Which is why a table entry is usually implemented in a class,
logically indexed using an association.
 
regards,
 
-Walter

---

From: John Schnizlein <[email-masked]>
Date: Wed, 23 Aug 2000 14:35:34 -0400

Walter,

Since your intention that the second word modify the first word,
which is opposite the order of Engish adjectives, you should
consider using non-compound noun-phrases for this distinction.

Referring to priority schedulers or bandwidth-share schedulers 
would be much clearer than confusing people with your subtle 
semantics of reversed-terms labels. The details that you suspect
 each of these needs parameters associated with the other
(which we might not all agree with) could be described elsewhere.
This is especially the case when you are asking someone how they 
handle this distinction.

John

At 09:35 AM 08/23/2000 -0400, Weiss, Walter wrote:
>
>> Which, of priority scheduler and bandwidth-share scheduler, 
>> is which of the types you asked to be distinguished: 
>> priority bandwidth or bandwidth priority scheduling? 
>
>If I understand your question correctly, I was assuming that the 
>first word represented the primary mode of the scheduler (is it 
>fundamentally a bandwidth scheduler or fundamentally a priority 
>scheduler), and the second word to specify any special extensions 
>to the scheduler.
>...
>If my clarification was insufficient, let me know. If you would like to 
>propose a different term for each example (rate limiting priority 
>scheduler), please propose it. I have been using those terms mostly because 
>that was the way the classes were originally named (my fault), and because 
>the real point is that both schedulers use the same set of attributes with 
>distinctly different semantics and results.
>
>> > >scheduling from bandwidth priority scheduling? 
>> >

---

From: "Weiss, Walter" <[email-masked]>
Date: Wed, 23 Aug 2000 19:10:33 -0400

John,

I agree that the terms are important for clearly distinguishing the
different operational characteristics of each type of scheduler. The names
of the schedulers are largely a hold-over from previous iterations of the
model where the distinction was discussed, if not in the draft, then at
least amoung the authors (otherwise we would not have put both in :)

The question of whether the types of parameters for each type of scheduler
is immaterial to the original point of the discussion. If the parameters are
different, then seperate classes are needed.  If they are the same set of
parameters, then you need seperate classes because the meaning  of the
attributes to the scheduler (behavioural semantics) is different.

regards,

-Walter

> Sent: Wednesday, August 23, 2000 2:36 PM
> To: Weiss, Walter