From owner-freebsd-isp Mon Jun 9 03:22:49 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.5/8.8.5) id DAA15713 for isp-outgoing; Mon, 9 Jun 1997 03:22:49 -0700 (PDT) Received: from agora.rdrop.com (root@agora.rdrop.com [199.2.210.241]) by hub.freebsd.org (8.8.5/8.8.5) with ESMTP id DAA15697; Mon, 9 Jun 1997 03:22:45 -0700 (PDT) Received: from labinfo.iet.unipi.it (labinfo.iet.unipi.it [131.114.9.5]) by agora.rdrop.com (8.8.5/8.8.5) with SMTP id DAA13613; Mon, 9 Jun 1997 03:19:11 -0700 (PDT) Received: from localhost (luigi@localhost) by labinfo.iet.unipi.it (8.6.5/8.6.5) id IAA04408; Mon, 9 Jun 1997 08:57:32 +0200 From: Luigi Rizzo Message-Id: <199706090657.IAA04408@labinfo.iet.unipi.it> Subject: Re: ETinc's Bandwidth limiter To: dennis@etinc.com (Dennis) Date: Mon, 9 Jun 1997 08:57:32 +0200 (MET DST) Cc: hackers@freebsd.org In-Reply-To: <3.0.32.19970608115040.006b1a80@etinc.com> from "Dennis" at Jun 8, 97 11:50:31 am X-Mailer: ELM [version 2.4 PL23] Content-Type: text Sender: owner-isp@freebsd.org X-Loop: FreeBSD.org Precedence: bulk [moved to -hackers, Bcc to -isp] > At 03:46 PM 6/8/97 +0100, you wrote: > >>> There is no "fair routing" in a web farm unless everyone pays the same > >>> price, which is ridiculous. Charge based on their bandwidth access ... > >>Dennis, this sounds like an overstatement. Fair does not necessarily > >>mean 'all equals', there can be different weights for different > >>users depending on how much they pay for, and the fairness is in > >>making everyone get what he pays for. Hard limiting the bw for ... > The BurstManager takes care of that aspect....but with heavy usage > hard limits are the only way to guarantee "fairness". Otherwise you > just have a crapshoot. The thing I am currently working on is a replacement for the IF_ENQUEUE/IF_DEQUEUE macros used in the lowest layers of the networking code (see http://www.iet.unipi.it/~luigi/newifqueue.h for an incomplete implementation, just to get the idea) These modified macros store packets in per-flow queues (where classification can be done in several different ways, but basing on the source IP and possibly source port seems one of the most practical ways), which are then handled with round robin policy. The above is adequate if all flows are allowed to use the same share of the output BW, and the code doing the above thing only takes constant time (and probably a very small overhead like 1us/packet on a reasonably modern machine -- although I don't have data). If implemented at a router driving a bottleneck, it would solve some problems. On top of this you can add all sorts of manipulations, e.g. implement a leaky bucket on each queue so as to implement BW management. If you actually modify the leaky bucket algorithm, by removing packets from queues not at a fixed rate, but once per round of the RR queue, then you have a form of adaptive rate limitation where the relative weight of each flow is preserved, but the bw limitation is not hard. I think (although have not implemented it yet) that this can be implemented in small constant time as well. If someone is interested on working on this I will be glad to exchange ideas/code. Given the clean interface between network stack and drivers, it seems an easy task from the implementation point of view (the only difficulty being in developing a suitable user interface to program flow weights and flow classification policies). All the above is mostly useful in a router, and almost useless in a end-user node (unless you want to implement the hard BW-management only). Cheers Luigi -----------------------------+-------------------------------------- Luigi Rizzo | Dip. di Ingegneria dell'Informazione email: luigi@iet.unipi.it | Universita' di Pisa tel: +39-50-568533 | via Diotisalvi 2, 56126 PISA (Italy) fax: +39-50-568522 | http://www.iet.unipi.it/~luigi/ _____________________________|______________________________________