Colin Davis wrote:
> It seems like some sort of "in network" solution, such as a variation of
> a tit-for-tat measurement.. Inserting file A with 100X redundancy is
> approximately the same as inserting file B which is 100X the size.. If
> we enforce fairness on accepting traffic unless they've "earned" it, a
> user can then decide how to "spend" that bandwidth.. One mostly lossy
> 10M file, or 10X redundancy on your 1M file.
In principle I think this is a great idea. In practice I've spent a lot
of time working on tit-for-tat-ish incentive mechanisms for multi-hop
networks, without much success. That probably just means I should find
another line of work, but it might also mean the problem is harder than
it looks.
In a single-hop network such as BitTorrent, the value provided by a
neighbouring node is directly related to how much it spends on you: if
it spends 1MB of bandwidth uploading to you, you receive 1MB of data (or
some fixed fraction of 1MB, allowing for overhead), all of which is
directly useful to you. That makes it easy to design strategies that
reward cooperative neighbours and punish uncooperative neighbours. (It
turns out that TFT isn't actually a very good strategy in this context,
but the point is that good strategies can be found.)
But in a multi-hop network the relationship between cost and benefit is
more complicated: assuming all nodes allocate bandwidth to cooperative
neighbours, if you receive a request from neighbour A, should you
forward it to neighbour B? First, will you get a response or will you
spend the bandwidth and have nothing to show for it? Second, if you get
a response and return it to A, will the cooperation you earn from A be
worth more than the cooperation previously earned from B and spent on
A's request?
I've been banging my head against this problem for a while, and I can't
come up with a model where it makes sense for selfish nodes to forward
requests. It makes sense to answer requests locally if you can, to earn
cooperation from your neighbours, but it doesn't make sense to forward
them. Unfortunately if everyone behaves like that, the network doesn't
function.
Doubtless someone else can solve this problem, but at this stage I'm
just hoping they won't solve it before my thesis is written up. ;-)
Cheers,
Michael
