Alternative BitSwap strategies

[ghost]

There is room for more Bitswap strategies.

This one prefers the peer with the best debt ratio, while still seeding to peers with a worse ratio, if there is no better peer to seed to.

larsg, couple of relatively obvious things i see re implementation details 1: when you decide not to send a block, you do so by introducing a 10s delay before retry. this is possibly the worst possible thing to do 2: slightly related (since it triggers 1, especially when just connecting to someone for the first time... at least on paper), it tries way too hard to be "fair" and invents the wrong 0-sum game from an optimal throughput standpoint larsg, i was actually planning to hang out in #ipfs if/when things settle down a bit it's the closest thing to usable content-addressable-networking that i've come across you are very much invited to (i'm reading up what you mean about the 0-sum game) i haven't gotten very close to bitswap yet oh the ledger and debt ratio? basically, you try to be fair by keeping upload/download ratio per peer at close to 1.0 (and enforce it with the stupid delay noted before) ah yep total data transferred isn't a terribly good metric to use if your goal is moving bits as fast as possible better would be to send blocks to peer with the most favorable ratio until you've saturated your upload if the only person who wants something has a terrible ratio, they still get it. so they can't hurt other people's chances of getting data from you so that the peer's ratio gets worse and we start letting another peer leech? right, or another peer who already had a better ratio decides they want a new block yeah that sounds simple enough that it could actually work :P mind if i hand that on? you are encouraged to great it's vaguely similar in end result to how cjdns's QoS is supposed to work that is, the way to get higher priority is to ask for less it self-corrects without depending on any constants that might be picked wrong (see: the 10s timeout)

[jbenet]

@arceliar thanks for the thoughts. i'll address a few points below. But either way, come hang out in #ipfs and help think about these things.

important to note a few things first:

• bitswap is far underspecified at the moment. it's perhaps the weakest link in DRAFT3 static.benet.ai/t/ipfs.pdf -- much more has come up that we will be adding. including, for example protocol upgrades (to recognize strategies and other mediums of exchange, probably using mss), and query notation (#12).
• Bitswap is inspired by several papers, including Propshare, which presents BitTorrent as a round-based auction and shows much more fair + robust relationships emerge from disributing upload bandwidth proportionally to download bandwidth contributions. I'll let the paper speak for itself.
• The 10s time delay is not in the protocol, and it is a dirty hack that works well atm. the bitswap game (like bittorrent's) is best modeled as a series of rounds (auctions in PropShare) than per-peer optimistic accounting (random unchoking). In practice, bittorrent clients do not implement "rounds across all peers", but instead assume optimistic per-peer adjustments will approximate "rounds across all peers", (which is not a terrible assumption and vastly simplifies implementation). However, to be correct and fair, from a protocol standpoint, bitswap must be implemented as rounds, even if we process requests as they come in (i.e. per-peer event responses).

@arceliar I'm curious about

1: when you decide not to send a block, you do so by introducing a 10s delay before retry. this is possibly the worst possible thing to do

Can you expand on this? I'm not seeing what you're seeing. Why is this "possibly the worst possible thing to do" -- discounting the hyperbole, this is still a strong claim that I'm not understanding. While the 10s delay is definitely a very poor simulation of rounds, it is a simulation of rounds.

Please note it is very important to keep re-rolling (randomly chosing whether to send to someone else) periodically or decisions will stick too hard. The period here (whether to reroll per-round, or re-roll according to some other function) is important to the performance of the swarm, but I don't havestrong arguments nor meaningful data on what to chose. I'm sure thinking about it more will show functions that vastly outperform others in all the metrics we care about.

better would be to send blocks to peer with the most favorable ratio until you've saturated your upload

1. No. Propshare proves this is incorrect for healthy swarms. It is favorable to send to peers proportionally to the ratio. This is proportionally in the limit, so one could opt to dedicate bursts of bandwidth entirely to strong relationships, as the latency of data is often very important. But it is critical not to dedicate all the bandwidth to the strongest relationships (cartels).
2. This is not going to build healthy swarms (where newcommers with little to contribute can still participate), it's going to build strong cartels with a very strong historical bias. Newcommers will find it extremely hard to be considered suitable by peers (except perhaps if they're in the same datacenter or LAN). It will seldom reform. This is why it is critical that the decision be probabilistic and (like simulated annealing) have a chance to find better optima.
3. As a sidenote, because it is relevant, "saturating your upload" is not straightforward. Bandwidth is usually modeled as a "per host" thing because most p2p models assume all connections move across one pipe. this is obviously wrong, bandwidth is per-connection (not even per-peer, as peers could have multiple connections across multiple routes), and per-conection / time at that. The upshot of this is that nodes in a datacenter or a LAN will have much larger bandwidth limits than across other peers, and that those bandwidth limits will change (possibly drastically) over time. The way to do it is with good per-connection bandwidth estimators. The good news is there's a lot of great work on cheap estimators. :)

if the only person who wants something has a terrible ratio, they still get it. so they can't hurt other people's chances of getting data from you so that the peer's ratio gets worse and we start letting another peer leech? right, or another peer who already had a better ratio decides they want a new block

This is already accounted for in the trivial basic bitswap send probability. It is designed to tolerate leechers to a given threshold ratio (hence the logistic probability of sending).

One important thing not accounted for in the DRAFT3 paper is that the debt ratio must be combined with the magnitude of the data transferred. (i.e. drastically different ratios when talking small (<5MB) dont matter much). (reminder to self: don't open the door wider for sybils.)

[jbenet]

Also, we'll soon be able to put these to the test! @heems is making a bssim that we'll use to do basic bitswap simulations, and we'll expand that to run across real connections over real networks.

We should make our own planet lab to test across the real internet.

[Arceliar]

Thanks for the response @jbenet

First off, I'm glad to hear about bssim. I'm too lazy to formally prove most of what I say, so I'm looking forward to playing with the sim to test.

Secondly, it's entirely possible that I could be mistaken about the bitswap implementation in go-ipfs. I realize the specification in the paper doesn't include the 10s delay, but the go implementation is still the de-facto standard so I feel it warrants criticism when if I see an apparent issue. Feel free to correct me or point-and-laugh if I've made any mistakes in my arguments.

No. Propshare proves this is incorrect for healthy swarms. It is favorable to send to peers proportionally to the ratio.

Using propshare's definition of "fair", you are of course completely right. I didn't think through my explanation very well in the IRC convo; I was mostly thinking about performance for users with low ratios when the sources of a block have unused bandwidth. Instead of dwelling on how to fix the thing I'm baselessly asserting is a problem, I'll just focus on describing the apparent issue the 10s delay before reroll causes, and I'll come back to potential workaround later.

Let me start by illustrating with an example. Suppose that I have a website and I want to use ipfs to deliver any static files. This node is strictly a server, so it's not looking to download any blocks right now. Now suppose you visit my site and try to download a relatively large file--streaming a video, perhaps. I don't run a particularly popular site, so you're the first person to request this file, and I'm the only source of the blocks in the network at this time. I begin sending you blocks, but since there's nothing that I want from you, your ratio becomes poor. Eventually I fail a roll to send you a block, and this introduces a 10s delay. These delays get progressively more common as your ratio continues to fall, but I would still send the entire file to you given enough time (give or take any rounding or precision errors in the rolling function, and "enough time" might still be unreasonably long if the delays happen to aggressively).

Now, if I'm not doing anything else with my bandwidth, what does introducing the delay accomplish? It seems like all I've done is degrade performance for you, by introducing a delay before sending blocks that I was going to have to send anyway. It would be better for the user if I had just sent the file via http as usual.

A bittorrent seed does not normally stop sending data just because their peers' ratios are low. They might change who they send data to, depending on the clients seeding strategy, but they still endeavor to utilize as much available bandwidth as possible.

That's really the crux of the issue that's bothering me. Looking at ratios, and using them to introducing delays, may have the effect of keeping things "fair" as measured by data sent, but it does at the cost of failing to utilize all available bandwidth at that moment in time. Bandwidth is the actual finite resource, so anything I fail to utilize is wasted from my perspective.

So coming back to Propshare, I agree that it's fine to send data at a rate proportional to ratio (give or take the case where exactly 0 bytes have been sent), but only if renormalized to use all available bandwidth (that is, if someone isn't using their share of my bandwidth, I want to reallocate it fairly among the subset of peers for whom I have blocks to send). Most bittorrent clients manage to bypass this with optimistic unchoke, which helps keep things flowing in the rare cases where everyone's ratio is terrible w.r.t. the peers that have pieces they want. Or they just stop caring about ratios entirely once they become seeds. If my understanding of Bitswap's implementation is correct (big if), then it currently has no mechanism in place to mitigate the kinds of problems like in my example above.

All that being said, I realize that actually implementing something that can utilize all available bandwidth is not trivial. A 10s delay is fine if it's just used until something better can be written, or to help with debugging, but it's still one of those things that keeps shouting in the back of my head that it needs to be fixed.

[iskradelta]

@Arceliar I believe FairTorrent algorithm would solve those problems, it is generally better than PropShair. Though I do not know if FairTorrent can be implemented as a Bitswap strategy.