Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/17/84; site ittvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!crsp!pesnta!qumix!ittvax!hagouel
From: hagouel@ittvax.UUCP (Jack Hagouel)
Newsgroups: net.mail
Subject: Re: Line costs used in pathalias
Message-ID: <1611@ittvax.UUCP>
Date: Mon, 21-Jan-85 13:58:33 EST
Article-I.D.: ittvax.1611
Posted: Mon Jan 21 13:58:33 1985
Date-Received: Wed, 23-Jan-85 05:00:58 EST
References: <1605@ittvax.UUCP> <424@down.FUN>
Distribution: net
Organization: ITT-ATC, Stratford Ct.
Lines: 69

From Peter (...!down!honey):
>         ... Even if I know ihnp4's capacity, how much of it am I
> entitled to take?  I can't ask ihnp4 to assign me some fraction, since
> that would require n-squared messages...

It is true that the burden of every node in the network allocating
capacity for every other node in the network is too large. Not
to mention the messages needed to implement such a scheme. There
are ways though to realistically implement the fairness algorithm
I suggested with considerably less cost.

The total capacity in ihnp4 is broken down into assigned slots 
and a common pool. Nodes that do not consume more than a (predefined)
small portion of ihnp4's capacity are all allocated capacity from
the common pool with minimal tracking (to be described in a later
paragraph). Nodes with higher consumption are allocated a slot with
predefined capacity which diminishes with usage. 

When the capacity
allocation expires ihnp4 nacks subsequent messages causing the
remote node to recalculate the path blocking ihnp4 from becoming
an intermediate node. Based on the allocation period, each node
recalculates all its paths (say the 1st of each month) with no
blocking restrictions. Based on usage ihnp4 may reduce the allocation
of any node. Allocations may be increased by demand from the remote
node: it may decide that the delay characteristic of the second
best path is considerably higher than going through ihnp4 (say
there is a network wide-rule that requests will only be generated
if the delay more than doubles). If the nack scheme is used then
the information of increased/decreased allocation need not be
transmitted at all.

Finally, let's touch on the subject of how ihnp4 manages its
own resources in terms of keeping track of allocations: ihnp4
defines the threshold that differentiates between nodes in the
pool and nodes in assigned slots. If that threshold is high enough
then there are no assigned slots: ihnp4 would not keep track
of any node and it would never generate nacks.

Depending on its storage capacity ihnp4 defines the threshold
so that it can handle the resulting data base (some trial and
error may be required). The threshold may change at any time
without affecting any other node (other than impose a restriction).

It is easy to see how a node may lose a slot (through an allocation
bellow the threshold). To gain a slot the node must use more than
the current threshold. But this information is not available since
its usage is lumped into the common pool.

A possible answer to the above problem is to keep short term
statistics (i.e. daily, weekly or otherwise) and identify new
candidates for slots. If the allocation is monthly, then a 
possible candidate would be a node that consumed a quarter of
the allocation per week. These are offline calculations which
can happen at system time as opposed to the slot calculations
which need to happen online. Of course some cap for capacity
usage per day should exist online (i.e. if a node exceeded
the threshold in one day then it is reasonable to send a nack).

So, to conclude, there are ways for allowing a flexible
implementation of the fairness algorithm. Each node may decide
to use it or not use it and still coexist with nodes that use
it. Pathalias would need to change slightly to implement
blocking, and it may have to run a little bit more often.
Furthermore, participating nodes may define their own
granularity of participation. 

Jack Hagouel
..!ittvax!hagouel