hagouel@ittvax.UUCP (Jack Hagouel) (01/18/85)
Given the interest in the meaning of the DAILY, HOURLY, ... designations I thought that this excerpt of a message I sent to Mark Horton may be of interest to this newsgroup. I believe that a more rigorous approach to defining the line costs used by pathalias is possible if the optimization objectives are more clearly defined. The syntax of expressing these costs is not addressed here, although it is also important. ----- start of excerpt ----- The cost values allocated to connections appear to be arbitrary. If there was a formula that was used to compute them I would be interested to learn it. The rest of this letter deals with thoughts and sketchy suggestions on computing the cost. I think that a good definition of cost will be appreciated by both the users and the providers of Usenet service. Current cost trend appears to be that frequent connections have lower cost (but not proportionally so). Telephone charges may also be relevant. I couldn't guess any more factors. The issue to be resolved is how to achieve least cost routing (using the pathalias program). The problem arises in that the user perceives a different cost (delay) from the cost of the service provider (mostly dollars and fairness). To top it all, the "network manager" is concerned with efficient utilization of the resources, i.e. throughput. With the advent of domains the problem becomes more manageable. At least for some domains (like ATT) the domain manager and the service providers are the same; possibly even many of the users (internal traffic). Since the whole concept of Usenet is based on voluntary, non-abused, contribution of resources for the collective good, fairness appears to be the driving force. For Usenet to become useable low delay could work wonders. Throughput may have to be left in the background. Currently pathalias is not very dynamic (path computations occur infrequently). In the future that may change, I hope. It is desirable to preserve the same cost definition in both cases. Focus on fairness: I think that the best way to define it is that a site will not be asked to handle more mail than it commited to when it joined the network. Question: do sites declare their capacity constraints? If not maybe some semi-formal definition is necessary (beyond the frequency of calls). I've often seen new sites mentioning a vague "as long as we do not get a lot of transient traffic". Based on these capacity constraints pathalias should be able to do some load splitting, i.e. the optimal path is not always used since that would overutilize the "good" connections and ignore the "bad" ones. The following algorithm could be used: each node is initially allocated bandwidth through other nodes in the network. The amount allocated would depend on the topological distance of the two nodes and the total bandwidth available. Each node may allocate its own bandwidth. The allocation would last for a predetermined amount of time (say a month). Pathalias will execute based on these values. The source of traffic will monitor its bandwidth consumption. When it exceeds a limit on a node then it generates a new path based on the remaining allocation. Intermediate nodes may monitor for adherence to their limits and inhibit excess traffic. Allocations that are underutilized may be either redistributed or negotiated periodically. Bids for additional bandwidth may be automatically processed at allocation time. This becomes an organic algorithm where node bandwidth becomes a commodity and it is fairly allocated to demand. The penalty is increased bookeeping and control traffic. The advantage is that nodes can budget their Usenet contribution in some predictable and consistent fashion. Jack Hagouel ...!ittvax!hagouel (203) 929-7341 x244
spaf@gatech.UUCP (Gene Spafford) (01/20/85)
Just as a note of general interest, the mathematical model for a
network where some of the edges, and some of the combinations of edges,
have maximum flow constraints as well as edge weights (preferences,
speeds, etc), is known as a matroid. Matroid analysis can be done by
program, although optimizations are often much more complex than a
similar (directed) network. I can provide a text reference to anyone
interested, but I have no interest in implementing any such in a
pathalias-style program. I've done something similar before, and
I don't want to do it again in the very near future (at least until
after I finish my thesis!).
--
Gene "7 months and counting" Spafford
The Clouds Project, School of ICS, Georgia Tech, Atlanta GA 30332
CSNet: Spaf @ GATech ARPA: Spaf%GATech.CSNet @ CSNet-Relay.ARPA
uucp: ...!{akgua,allegra,hplabs,ihnp4,linus,seismo,ulysses}!gatech!spafhoney@down.FUN (code 101) (01/21/85)
I follow your thinking, Jack, but I see a serious problem: allocating bandwidth. 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. Is there a centralized scheme that is both fair and effective? (Read max-flow for effective.) Doesn't this require a lot of data? Incidentally, it is my understanding that the authors of pathalias had in mind an objective function that measured delay. The costs (and more importantly, their mnemonics) are an attempt, if ad hoc, to effect that goal. Peter
hagouel@ittvax.UUCP (Jack Hagouel) (01/21/85)
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