RE: A proposal for the improvement of the delay pools

> Not sure I understand your distinction in "simple" and "class" delay
> pools.. Why is there new "simple" pools being created?

A "simple" pool would be just that, a pool which governs some resource.
A "class" pool would be a family of simple pools. It would be fundamentally
different in terms of implementation: if a request has to be matched
to a pool class, the class definition parameter is checked against
all pools in the class and if a matching pool is found, it's used. If
not, a new one is created. This allows to adapt the search algorithm
to the parameter used and thus be very fast. Matching multiple parameters
would be more generic but harder to implement.

> If I understand you correctly then I think hierarchical delay pools
> is perhaps a better approach.
>
> A request only belongs to at most one delay pool, but this pool may
> have parents further governing the resource availability.

It's simpler but less generic. Tying to multiple pools allows
for matrices of constraints, while hierarchical allows for trees
of constraints. Maybe it can be functionally equivalent..

For instance, supposed that you want to limit by username
AND source network (the former to limit bandwidth hogs and the
latter to save WAN bandwidth for instance)
Those constraints are not hierarchical in definition. Maybe they can
be made into an hierarchy but it doesn't feel "natural".

Also, having hierarchical pools makes hierarchy defined at pool definition
time rather than at ACL match time.

> Requests are assigned to their pool by ACL matches, as is done today.
>
> Pools may be keyed on request derived information such as source
> IP, network, username or whatever one might want to limit bandwidth
> on, or no key to have a single limit for all users. Set on a per-pool
> basis.
>
> What is a L3 pool today is then described as a hierarchy of three
> Root: A keyless pool defining the global limits
> Level1: Keyed by network number
> Level2: Keyed by IP
>
> Note: While emulating the current L3 pools this would not have the
> limitation on IP network layouts.. and you can easily change the
> lower levels per request if needed without detaching from the global
> limit.
>
> Configuration:
>
> delay_pool <name> [parent=<name>] [key=<keyspec>] size=<size>
> refill=<refill>
>
> delay_access <name> <acl...>
>
>
> There should be a magic pool name for "not limited" I think..

It depends. With the approach I suggested (list of pools, matching
all ACLs) such a pool would just be a no-op. With the single-pool
first-match-decides approach it would be convenient to have such
a definition.

> Unused full delay pool entries are garbage collected every now and
> then.

Yes.

> One thing to watch out for when implementing this is the increased
> pool index size for keyed pools, but I think this will be compensated
> quite well by getting rid of all the unused entries.

It depends on the approach again. With "yours" it mostly relies on
configuration parameters, with "mine" the overhead is all in
keyed (or "class" as I called them) pools, and it means basically
an hashtable or a splaytree or whatever accessor is faster for
each defined pool.

>
> Regards
> Henrik
>
>
> On Sunday 14 April 2002 18:47, Kinkie wrote:
> > Hello everyone.
> >
> > I'll soon need to implement bandwidth control at my organization,
> > and so I finally gave an in-depth look at delay pools. While
> > they'll be sufficient at the beginning, they could be vastly
> > improved with (I hope) a not-too-vast effort.
> >
> > Here is a modest proposal on how they could be improved. I won't
> > start coding right away on this, but it might be my next project.
> > Notice, there might be gross inaccuracies in the presented facts
> > since I haven't looked at the code in-depth, just a cursory glance.
> >
> > SPECS
> > =====
> >
> > 1)
> > There should be two types of pools: "simple" delay pools and
> > "class" delay pools.
> > The former should be a single pool of a given depth, fill rate and
> > initial fill. The latter should be a group of pools that depend on
> > some requests' attribute, such as the source IP, destination IP or
> > authenticated username. All pools in the class should have the same
> > parameters. When a request comes in, the defining parameter is
> > matched against already-defined pools in the class. If a pool is
> > found, the request is subject to it. If not, a new "simple" pool is
> > defined and initialized and the request is made subject to it.
> >
> > 2)
> > Pool definition and request assignment should be separate. A pool
> > should be identified by an unique name.
> >
> > 3)
> > Pools are assigned to requests by ACL matches. Since inaccuracies
> > are acceptable in bandwidth management, fast acl matches can be
> > used thus avoiding to impact request processing flow
> >
> > 4)
> > A request can be impacted by many different pools. If so, the
> > bandwitdh it gets assigned is the least of all the pools it must
> > obey. The bandwidth it uses is subtracted by all the pools it is
> > subject to.
> >
> >
> > 5)
> > Bandwidth management need not be very strict. Granted bandwidth
> > packets could be so arranged:
> > pool <= 0: grant 0 and wait
> > pool > 0: grant a minimum value (i.e. 1 Kb) for network efficiency
> > reasons, and cause pool to go sub-zero
> > pool > minimal packet: grant whatever available.
> >
> >
> > CONFIGURATION
> > =============
> >
> > Configuration format and parameters which match the specs could be:
> >
> > -delay_pool pool_name depth fill_rate initial_fill
> >
> > defines a new pool and assigns parameters to it
> >
> > -delay_pool_class pool_name by_attribute depth fill_rate
> > initial_fill
> >
> > defines a new pool class. The namespace is shared by the simple and
> > class delay pools by_attribute can be one of "by_src", "by_user",
> > "by_dst", "by_dstdomain", "by_dstregexp" etc. Attributes can
> > initially be a subset of the acl types, and expand as development
> > proceeds.
> >
> > -delay_pool_assign pool_name acl [acl ...]
> >
> > Assigns a request matching ALL the mentioned ACLs to a given delay
> > pool. All conditions are evaluated for each request
> > enable assigning a request to multiple pools.
> >
> >
> > IMPLEMENTATION
> > ==============
> >
> > simple delay pools could come for free or almost. Only caveat is
> > that they should be refcounted to correctly handle pools undefined
> > on reconfiguration.
> >
> > class delay pools are quite more complex, but should be rather
> > modular. Optimization could lead to lots of differences in
> > implementation of the locator algorithms for the different pool
> > defining attributes. Those pools should obviously also be
> > refcounted, and pose two extra issues: garbage collection and
> > reconfiguration. A pool in a class can be garbage-collected when
> > it's completely filled and it's not referenced by any active
> > connection. Reconfiguration could be handled by moving all active
> > pools to a "temporary" and undifferentiated storage area where
> > they'll be garbage-collected when their refcount goes to 0.
> >
> > The request flow path should be altered to match acls and to
> > determine what pools it must be subject to. A request should
> > contain a list of pointers to pools it's subject to and take care
> > to properly refcount them. When sending data it should scan the
> > pools list twice: one to discover what is the bandwidth it has
> > available, and another to adjourn the pools' contents.
> >
> > Ideas? Thoughts? Am I just on too much wine?

-- 
	/kinkie