Subject: [Diffserv] Scheduler scenarios for the MIB

From: "Weiss, Walter" <[email-masked]>
Date: Thu, 9 Aug 2001 04:56:48 -0400

As per the WG discussion today, here is some text describing some scheduler
scenarios and how the existing scheduler could be changed to support them.
Comments appreciated.

regards,

-Walter

-------------------------------------

In order to appreciate the rational behind this rather complex model for
scheduling, we must consider the rather complex nature of schedulers as well
as the extreme variations in algorithms and implementations. Although these
variations are broad we have identified four examples that serve to test the
model and justify its complexity.

A simple, hierarchical scheduler has the following properties. First, when a
scheduling opportunity is given to a set of queues, a single, viable queue
is determined based on some scheduling criteria, such as bandwidth or
priority. The output of the scheduler is the input to another scheduler that
treats the first scheduler (and its queues) as a single logical queue.
Hence, if the first scheduler determined the appropriate packet to release
based on a priority assigned to each queue, the second scheduler might
specify a bandwidth limit/allocation for the entire set of queues aggregated
by the first scheduler. Figure 1 illustrates the example and how it would be
instantiated using the model. In the figure, NextService determines the
first scheduler after the queue. NextScheduler determines the subsequent
ordering of schedulers. In addition, the ElementSchedulingService
association determines the set of scheduling parameters used by a specific
scheduler. Scheduling parameters can be bound to either queues or
schedulers. In this case of the SchedulingElement EF1-Pri, the binding is to
a queue, so the QueueToSchedule association is used. In the case of the
SchedulingElement PriSched1-Band the binding is to another scheduler so the
SchedulerToSchedule association is used. Note that due to space constraints
of the document, the SchedulingService PRISched1 is represented twice to
show how it is connected to all the other objects.

A complex, hierarchical scheduler has the same characteristics of a simple
scheduler except that the criteria for the second scheduler are determined
on a per queue basis rather than an aggregate basis. One scenario where this
could occur is when a WRR scheduler determines the relative allocations
between a set of queues. However, EF traffic is scheduled in a subsequent
priority scheduler. This works fine except that the relative priority of EF
falls in between NetworkControl traffic and BE traffic. Hence we need three
priorities bound back to the original queues rather than the first
scheduler. In order to support this scenario the BE and NetworkControl
queues must be bound to two separate schedulers. Figure 2 illustrates this
by describing an EF queue and a BE queue both pointing to a Weighted Round
Robin scheduler via the NextService association. The NextScheduler
association between the WRR scheduler and the priority scheduler in turn
define the ordering of the scheduling hierarchy. Also note that each
scheduler has a distinct set of scheduling parameters that are bound back to
each queue. This demonstrates the need to support two or more parameter sets
on a per queue basis.

An excess capacity scheduler offers a similar requirement to support two
scheduling parameter sets per queue. However, in this scenario the reasons
are a little different. Suppose a set of queues have each been assigned
bandwidth limits to ensure that no traffic class starves out another traffic
class. The result may be that one or more queues have exceeded their
allocation while the queues that deserve scheduling opportunities are empty.
The question then is how is the excess (idle) bandwidth allocated.
Conceivably, the scheduling criteria for excess capacity are completely
different from the criteria that determine allocations under uniform load.
This could be supported with a scheduling hierarchy. However, the problem is
that the criteria for using the subsequent scheduler are different from
those in the last two cases. Specifically, the next scheduler should only be
used if a scheduling opportunity exists that was passed over by the prior
scheduler.

When a scheduler chooses to forgo a scheduling decision, it is behaving as a
non-work conserving scheduler. Work conserving schedulers by definition will
always take advantage of a scheduling opportunity irrespective of which
queue is being serviced and how much bandwidth it has consumed in the past.
This point leads to an interesting insight. The semantics of a non-work
conserving scheduler is equivalent to that of a meter in that if a packet is
in profile it is given the scheduling opportunity and if it is out of
profile, it does not get a scheduling opportunity. Similarly, with meters
there are semantics that determine the next action behavior when the packet
is in profile and when the packet is out of profile. Similarly, with the
non-work conserving scheduler, there needs to be a means for determining the
next scheduler when a scheduler chooses not to utilize a scheduling
opportunity.

Figure 3 illustrates this last scenario. It appears very similar to Figure 2
with the exception that the binding between the allocation scheduler and the
WRR scheduler is using a FailNextScheduler association. This association is
explicitly indicating the fact that the only time the WRR scheduler would be
used is when there are non-empty queues that the allocation scheduler
rejected for scheduling consideration. Note that Figure 3 is incomplete in
that typically there would be several more queues that are bound to an
allocation scheduler and a WRR scheduler. 

A hierarchical CBQ scheduler is the fourth scenario to be considered. In
hierarchical CBQ, each queue is allocated a specific bandwidth allocation.
Queues are grouped together into a logical scheduler. This logical scheduler
in turn has an aggregate bandwidth allocation that equals the sum of the
queues it is scheduling. In turn, logical schedulers can be aggregated into
higher-level logical schedulers. Changing perspectives and looking top down,
the top-most logical scheduler has 100% of the link capacity. This
allocation is parceled out to logical schedulers below it such that the sum
of the allocation is equal to 100%. These second tier schedulers in turn in
turn may parcel out their allocation across a third tier of schedulers and
so forth until the lowest tier that parcels out their allocations to
specific queues representing relatively fine grain classes of traffic. The
unique aspect of hierarchical CBQ is that when there is insufficient
bandwidth for the specific allocation, schedulers higher in the tree are
tested to see if another portion of the tree has capacity to spare.

Figure 4 demonstrates this example with two tiers. The example is split in
half because of space constraints resulting in the CBQTier1 scheduling
service instance being represented twice. Note that the total allocation at
the top tier is 50 Mb. The voice allocation is 22 Mb. The remaining 23 Mb is
split between FTP and Web. Hence, if Web traffic is actually consuming 20 Mb
(5 Mb in access of the allocation). If FTP is consuming 5 Mb, then it is
possible for the CBQTier1 scheduler to offer 3Mb of its allocation to Web
traffic. However, this is not enough, so the FailNextScheduler association
needs to be traversed to determine if there is any excess capacity available
from the voice class. If the voice class is only consuming 15 Mb of its 22
Mb allocation, there is sufficient resources to allow the web traffic
through. Note that FailNextScheduler is used as the association. The reason
is because the CBQTier1 scheduler in fact failed to schedule a packet
because of insufficient resources. It is conceivable that a variant of
hierarchical CBQ allows a hierarchy for successful scheduling as well. Hence
both associations are necessary. 

+---------------+        NextService  
|QueuingService +------------------------------------------------------+ 
| Name=EF1      |                                                      |
|               | QueueTo    +-------------------+ ElementScheduling   |
|               +------------+PriorityScheduling +----------+          |
+---------------+ Schedule   |Element            | Service  |          |
                             | Name=EF1-Pri      |          |          v
                             | Priority=1        |
+--+----------+----+
                             +-------------------+       |SchedulingService
+--
                                                         | Name=PriSched1
+--
                             +-------------------+
+----------+--+----+
                             |PriorityScheduling |ElementScheduling |  ^
+---------------+            |Element            +------------------+  |
|QueuingService | QueueTo    | Name=AF1x-Pri     |Service              |
| Name=AF1x     +------------+ Priority=2        |                     |
|               | Schedule   +-------------------+                     |
|               |                                   NextService        |
|               +------------------------------------------------------+
+---------------+
 .
:

+------------------+        NextScheduler  
|SchedulingService +------------------------------------------------------+ 
| Name=PriSched1   |                                                      |
|                  |SchedulerTo +---------------------+ElementScheduling  |
|                  +------------+AllocationScheduling +--------+          |
+------------------+Schedule    |Element              |Service |          |
                                | Name=PriSched1-Band |        |          |
                                | Units=Bytes         |        |          v
                                | Bandwidth=100       |
+--+----------+----+
                                +---------------------+
|SchedulingService |
                                                            |
Name=BandSched1  |
                             +---------------------+
+---------+---+----+
                             |AllocationScheduling |ElementScheduling |   ^
+---------------+            |Element              +------------------+   |
|QueuingService |            | Name=BE-Band        |Service               |
| Name=BE       | QueueTo    + Units=Bytes         |                      |
|               |------------+ Bandwidth=50        |                      |
|               | Schedule   +---------------------+                      |
|               |                                   NextService           |
|               +---------------------------------------------------------+
+---------------+

      Figure 1: Example 1 simple hierarchical scheduler

+----------------+                     NextService
|QueuingService  +-------------------------------------------------------+
| Name=EF        |                                                       |
|                |QueueTo     +--------------------+ElementScheduling    |
|                +------------+PriorityScheduling--+------------------+  |
+----------------+Schedule    |Element             |                  |  |
                              | Name=Pri2          |                  |  |
                              | Priority=2         |                  |  |
+----------------+            +--------------------+                  |  |
|QueuingService  |                                                    |  |
| Name=NetControl|QueueTo    +---------------------+ElementScheduling |  |
|                +-----------+PriorityScheduling   +--------+         |  |
|                |Schedule   |Element              |Service |         |  |
++---+-----------+           | Name=Pri1           |        |         |  |
 |   |QueueTo                | Priority=1          |        |         |  v
 |   |Schedule               +---------------------+
+--+---------+-----+
 |   |                                                   |SchedulingService
|
 |   |      +-------------------+                        | Name=PriSched
|
 |   +------+WRRScheduling      |
+----------+-----+-+
 |          |Element            |                                   ^     |
 |          | Name=WRR1         |ElementScheduling                  |     |
 |          | Weight=20         +----------------------+            |     |
 |          +-------------------+Service               |            |     |
 |NextService                                          |            |     |
 +-------------------------------------------------- + |            |     |
                                                     | |            |     |
  NextService                                        | |            |     |
 +-------------------------------------------------+ | |            |     |
 |                                                 | | |            |     |
 |          +-------------------+ElementScheduling | | |            |     |
 |          |WRRScheduling      +--------+         | | |            |     |
 |          |Element            |Service |         | | |            |     |
 |          | Name=WRR2         |        |         v v |            |     |
 |   +------+ Weight=100        |     +--+---------+-+-+-+ Next     |     |
 |   |      +-------------------+     |SchedulingService +----------+     |
 |   |                                | Name=WRRSched    | Scheduler      |
 |   |                                +------------------+                |
 |   |QueueTo                                                             |
 |   |Schedule               +---------------------+                      |
 |   |                       |PriorityScheduling   |ElementScheduling     |
+---------------+            |Element              +----------------------+
|QueuingService |QueueTo     | Name=PriBE          |Service
| Name=BE       +------------+ Priority=3          |
|               |Schedule    +---------------------+
+---------------+

      Figure 2: Example 2 complex hierarchical scheduler

+----------------+          
|QueuingService  |
| Name=EF        |
|                | 
|                |
++---+-----------+ 
 |   |
 |   |QueueTo
 |   |Schedule
+------------------+
 |   |                                                   |SchedulingService
|
 |   |      +---------------------+                      | Name=WRRSched
|
 |   +------+AllocationScheduling |
+------------+---+-+
 |          |Element              |                                   ^   |
 |          | Name=BandEF         |ElementScheduling                  |   |
 |          | Units=Bytes         +----------------------+            |   |
 |          | Bandwidth=100       |Service               |            |   |
 |          +---------------------+                      |            |   |
 |NextService                                            |            |   |
 +-----------------------------------------------------+ |            |   |
                                                       | |            |   |
  NextService                                          | |            |   |
 +---------------------------------------------------+ | |            |   |
 |                                                   | | |            |   |
 |          +---------------------+ElementScheduling | | |            |   |
 |          |AllocationScheduling +--------+         | | |            |   |
 |          |Element              |Service |         | | |            |   |
 |          | Name=BandwidthAF1   |        |         | | |            |   |
 |          | Units=Bytes         |        |         v v |            |   |
 |   +------+ Bandwidth=50        |     +--+---------+-+-+-+ FailNext |   |
 |   |      +---------------------+     |SchedulingService +----------+   |
 |   |QueueTo                           | Name=BandSched   | Scheduler    |
 |   |Schedule                          +------------------+              |
 |   |                                                                    |
 |   |                       +---------------------+                      |
+---------------+            | WRRSchedulingElement|                      |
|QueuingService |QueueTo     | Name=WRRBE          +----------------------+
| Name=BE       +------------+ Weight=30           |
ElementSchedulingService
+---------------+Schedule    +---------------------+

      Figure 3: Example 3 excess capacity scheduler

+---------------+        NextService  
|QueuingService +------------------------------------------------------+ 
| Name=Web      |                                                      |
|               | QueueTo  +---------------------+ ElementScheduling   |
|               +----------+AllocationScheduling +----------+          |
+---------------+ Schedule |Element              | Service  |          |
                           | Name=Web-Alloc      |          |          v
                           | Bandwidth=15        |
+--+----------+----+
                           +---------------------+       |SchedulingService
+--
                                                         | Name=CBQTier1
+--
                           +---------------------+
+----------+--+----+
                           |AllocationScheduling |ElementScheduling |  ^
+---------------+          |Element              +------------------+  |
|QueuingService | QueueTo  | Name=FTP-Alloc      |Service              |
| Name=FTP      +----------+ Bandwidth=8         |                     |
|               | Schedule +---------------------+                     |
|               |                                   NextService        |
|               +------------------------------------------------------+
+---------------+
 .
:

+------------------+        NextFailScheduler
|SchedulingService +------------------------------------------------------+ 
| Name=CBQTier1    |                                                      |
|                  |SchedulerTo +---------------------+ElementScheduling  |
|                  +------------+AllocationScheduling +--------+          |
+------------------+Schedule    |Element              |Service |          |
                                | Name=LowPri-Alloc   |        |          |
                                | Bandwidth=23        |        |          v
                                +---------------------+
+--+----------+----+
 
|SchedulingService |
                                                            | Name=CBQTop
|
                             +---------------------+
+---------+---+----+
                             |AllocationScheduling |ElementScheduling |   ^
+---------------+            |Element              +------------------+   |
|QueuingService | QueueTo    | Name=BE-Band        |Service               |
| Name=Voice    +------------+ Bandwidth=22        |                      |
|               | Schedule   +---------------------+                      |
|               |                                   NextService           |
|               +---------------------------------------------------------+
+---------------+

      Figure 4: Example 4 hierarchical CBQ scheduler

_______________________________________________
diffserv mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www2.ietf.org/mail-archive/working-groups/diffserv/current/maillist.html

---

From: Muneyb Minhazuddin <[email-masked]>
Date: Thu, 9 Aug 2001 20:02:55 +1000 (EST)

Following the discussion in the working group meeting I would appreciate
if people could post any diffserv implementation that they can disclose
about, to the diffserv implementation list.

http://www.tip.csiro.au/dsimplementation

I will try to consolidate the responses in the form of a report.

Regards
Muneyb

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 09 Aug 2001 13:31:14 -0500

Walter, can you indicate exactly where in draft-ietf-diffserv-model-06.txt
you propose to insert your text?

Thanks
    Brian

> scenarios and how the existing scheduler could be changed to support them.
<snip>

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 09 Aug 2001 13:33:21 -0500

Or maybe you intend it for the MIB text, in which case the same question
applies - but it seems to me that this sort of rationale belongs more
in the informal model.

   B

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 29 Aug 2001 15:40:03 -0500

I've seen no real discussion on this. If you think this should, or should
not, be included in the MIB text - please speak up now! Absent support,
it won't go in.

    Brian Carpenter
    diffserv co-chair

-- 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Brian E Carpenter 
Distinguished Engineer, Internet Standards & Technology, IBM 
On assignment for IBM at http://www.iCAIR.org 
Board Chairman, Internet Society http://www.isoc.org

"We shall need a number of efficient librarian types 
 to keep us in order." - Alan Turing, 1947.