Bram Cohen ([info]bramcohen) wrote,
@ 2004-11-07 21:31:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Car Emissions

There are two concepts in car pollution which people generally get mixed up. Some exhaust gases are simply stinky and noxious, most notably particulate carbon and carbon monoxide. Those do direct damage to the humans near them and crops which grow nearby and are clearly bad. Pollutants are clearly bad and there isn't much direct economic disincentive for any one person to make their car produce less of them.

The other troublesome kind of exhaust is greenhouse gases, mostly carbon dioxide. The amount of damage caused by these is much less clear, and there's a straightforward economic disincentive to produce them, because they correspond pretty much directly to the amount of gas your car consumes. Carbon dioxide also happens to be produced in mass quantities by respiration.

If you really want to know how clean a car is, look it up on the EPA web site. There are some surprises, for example the honda civic hybrid with a manual transmission has mediocre pollution ratings.

Erasure Codes

People keep asking me about using erasure/rateless/error correcting codes in BitTorrent. It isn't done because, quite simply, it wouldn't help.

One possible benefit erasure codes is that when sending data to a peer there are so many potential pieces that you can send any random one you have and it won't be a duplicate. The problem is that the peer may already have gotten that same piece from another peer, so that benefit is destroyed, and on top of that the overhead of communicating and remembering which peer has what is increased tremendously.

Possible benefit number two is that erasure codes increase the chances that your peers won't already have the pieces which you've downloaded. But simply downloading pieces which fewer of your peers have first handles that problem quite nicely, so a vastly more complicated solution is unwarranted.

Possible benefit number three is that if there's no seed left erasure codes increase the chances that the entire file will be recoverable. In practice, when a file becomes unrecoverable it's because there was only one seed and several downloaders started from scratch, then the seed disappeared after uploading less than the total length of the file. Erasure codes obviously would not help out in that case.

There are other possible benefits and corresponding rebuttals, but they get more complicated. The short of it all is that the possible benefits of erasure codes can be had with much more straightforward and already implemented techniques, and the implementation difficulties of such codes are quite onerous.

While I'm pissing on everyone's parade, I should probably mention another scenario in which everyone wants to use erasure codes and it's a bad idea: off-site backup. If you store everything straightforwardly on each backup site, and each site has two nines (99%) uptime (if it doesn't you shouldn't be using it for backup) then the overall reliability will be six nines (99.9999%). Engineering for more than six nines is nothing but intellectual masturbation, because unforseeable problems completely dominate failure at that point. Therefore one-of-three gets great reliability with unreliable backup sites in exchange for having to store three times the amount of data you're backing up.

With erasure codes, you could make it so that each backup site only had to store half as much stuff, but that two of them would still need to be up to recover data. If you then have four backup sites, there's a savings of 1/3 of the storage versus the much more straightforward approach. This is a pretty small reduction given that the price of mass storage is very small and plummeting rapidly. It also comes at great expense: you have to deal with four backup sites instead of three, and the software is much more complicated. In systems like this, the recovery software not working is a significant part of the chances of the system as a whole failing. Also, any economic benefit of savings on disk space must be weighed against the costs of the software system which runs it. Given the ludicrous prices of backup systems these days, a much simpler albeit slightly less efficient one would probably be a great value.

ECC of course has some great uses, for example data transmission of noisy mediums and storing data on media which can get physically corrupted, and recent developments in it are very exciting, but it's very important to only use sophisticated tools when clearly warranted.



(Post a new comment)


[info]graydon
2004-11-08 04:33 pm UTC (link)
the civic hybrid manual is a curious case. as you can see by its summary page, the 5HNXV01.33A6 model did have average particulate pollution, but the 5HNXV01.3YCV (presuably a newer model?) now has near-top marks. only the prius automatic is beating it now.

(Reply to this) (Thread)


[info]bramcohen
2004-11-08 04:43 pm UTC (link)
It appears that the difference is with sales region, not production time. It's very puzzling, because the stinky one is in california, and california is known for its smog checks. Perhaps the california tests are completely borked and encouraging worse overall emissions by hyperfocusing on certain exhaust gases?

(Reply to this) (Parent)(Thread)

All well now
(Anonymous)
2004-11-18 01:40 pm UTC (link)
Not sure how the EPA site looked before, but as of now, all the Civic Hybrid models (both US-wide and California) score in the top5 (with only Prius beating it) and only the conventional Civic is listed in the medium range.

http://www.epa.gov/autoemissions/all-rank-05.htm

(Reply to this) (Parent)

(Deleted post)
Re: just discovered your lj and added you
[info]bramcohen
2004-12-07 06:29 am UTC (link)
If I didn't want people to read what I wrote, I wouldn't post it to the internet.

(Reply to this) (Parent)


[info]kragen
2004-11-11 11:09 pm UTC (link)
It's true that one-of-three gets great reliability with 99%-reliable backup sites, and I agree that it's probably not worth it to build an ECC backup system for this case. But I don't agree that 99%-reliable backup sites are the only ones worth considering.

However, the point of ECC backup is that you can get great reliability with 50%-reliable backup sites, such as DSL-connected machines in Seoul or Comcast subscribers in Ohio. Being able to tolerate 10 failures out of however many backups gives you 99% reliability; 30 gives you your "overkill" six nines. Tolerating 30 failures by duplicating data gives you a 31x cost multiplier; tolerating 30 failures by spreading your data across 300 peers with an error-correcting code that can tolerate 30 failures only increases your cost by 11%, which is noticeably less than 3000%.

In many cases the dominant cost will be data transfer rather than storage. Disks now cost $1 a gigabyte, and they can be erased and used again, but my DSL line costs about $0.15 a gigabyte, and every gigabyte of bandwidth used is used forever.

I agree with your point that simpler and working trumps theoretically superior but unimplemented or broken every time, though. And you would, I suppose, be the person to ask whether HiveCache fits in that elusive third category: superior but working.

Do you suppose Zooko's going to ship MNet any time soon?

(Reply to this) (Thread)


[info]bramcohen
2004-11-23 03:53 am UTC (link)
With less than 99% reliable sites the reliability analysis is completely untrustworthy. More to the point, the failures are likely to be very highly correlated. Perhaps 95% is worth considering, but with triple redundancy that still gets you five nines, which isn't worth engineering past.

I don't expect either hivecache or mnet to be usable in a corporate setting any time soon.

(Reply to this) (Parent)


(Anonymous)
2004-11-29 06:43 am UTC (link)
I totally agree that we have to justify the use of redundancy on error correction, error detection and data loss. But on BitTorrent, we may overlook a very important factor, the data volume.

Suppose the undetectable error rate for one piece is x% with x is a very small number. If we have 1TB (1GB files downloaded by 1000 people or 4GB files downloaded by 250 people), with average 1MB piece size, transmitted between peers, we have 1,000,000 * x% cases undetected but in error. If x% is 0.0001%, i.e. 99.9999% reliable. We expect to have 1 undetectable error piece. Not bad!

But if the files are still sharing, the error will spread amongst people and no one can tell which file is corrupted. Another 1000 downloaders will add another error piece and it is cumulative.

For some files, it may not be a problem to contain small error in them. Say, in MPEG file, it may affect the movie for a fraction of second. Who notice it and who care? But some files may not allow error at all, .rar file with password may not be opened in such case.

It may be a good idea if BitTorrent can consider special cases like huge number of people share some files or sensitive files to provide optional extra error detection with extra expense in the sharing, not necessary by ECC.

(Reply to this) (Thread)


[info]bramcohen
2004-11-29 06:57 am UTC (link)
BitTorrent checks data integrity using secure hashes. It isn't susceptible to undetected errors in redistributed data.

Hashes for detecting error and re-requesting are clearly valuable, and are used in TCP as well. The question is whether adding codes which can fix, and not just detect, the errors is worthwile, and the answer is apparently no.

(Reply to this) (Parent)(Thread)


(Anonymous)
2004-11-30 02:11 am UTC (link)
Totally agree that data correction by redundancy is meaningless in any environment request for re-send is not a problem and the error rate is not high. Why fix it when it costs little to request again and the likelihood is small?

I haven't go into the detail of the data integrity checking algorithm for BitTorrent. But my understanding is: no error correction and detection algorithms can reach 100%. Here we have 3 cases we may have to pay attention to:

1. While most of the transmission links in the world are highly reliable, we cannot rule out the possible that someone using error-prone link with BitTorrent. It doesn't matter if the one use error-prone link has a lot of re-send and slow, he/she deserve it. But if it introduces error to the shared copy on the Internet, we do not deserve this!

2. As data transmission volume is increasing rapidly, who can tell a few years later the reliable of the current detection is enough or not to ensure no undetectable errors goes redistributed. Today 100TB per day may be a safe estimation, but who know when GB will becoming outdated like MB. Someday later we may have such kind of error noticeable.

3. The worst thing may be if someone intentionally "inject" error data that can pass the current error detection algorithm in order to destroy the shared files. If I were people from Hollywood or record companies, I may try to hire someone to write a clever program to modify data pieces in this way and redistribute them to other peers. It could be a way to stop people from sharing!

I am actually concern about the flexibility on the error detection. If BitTorrent or better say, the protocol, can allow people to add their own integrity checking, the undetected-but-in-error rate can easily be reduced to any level if needed.

(Reply to this) (Parent)(Thread)


[info]bramcohen
2004-11-30 02:29 am UTC (link)
my understanding is: no error correction and detection algorithms can reach 100%

Your understanding is incorrect. That's the whole point of secure hashes. BitTorrent uses sha-1.

(Reply to this) (Parent)(Thread)

(no subject) - [info]ciphergoth, 2004-12-20 05:55 pm UTC
Error detection vs error correction - [info]ka9q, 2005-06-21 10:41 pm UTC
Re: Error detection vs error correction - [info]ciphergoth, 2005-06-21 10:56 pm UTC
Re: Error detection vs error correction - [info]ka9q, 2005-06-22 01:22 am UTC
Re: Error detection vs error correction - [info]_scorp, 2005-06-22 03:13 am UTC
Re: Error detection vs error correction - (Anonymous), 2005-08-17 10:39 am UTC
Re: Error detection vs error correction - [info]_scorp, 2005-08-19 03:32 am UTC

[info]_scorp
2005-06-22 03:16 am UTC (link)
Why not use this idea ?

You probably are already aware of Justin's findings - but it would be interesting to know your opinion on that ...

(Reply to this) (Parent)

Erasure Codes
[info]lionkingwf
2004-12-07 03:59 am UTC (link)
hi Bram,

I partly agree with your comments on Erasure Codes.

Yes, as what you have said an encoding block maybe have been downloaded from other peers. So at this time erasure codes are no better than BT swarming. And because of redundant recovery scheme, erasure codes can't recover files either, when not enough blocks be get.

However, on some other sides I can't get consistent with your views.

1. Most ECCs are better when be implemented simply than be implemented complicated. But not all ECCs are like that. A kind of erasure codes is very suitful for multipoints downloading with large scale peers, called Luby Codes, which using UDP as its transmitting protocol. It has good scalability and high efficiency of recovery, based on XOR operation with data blocks, so it needs only few computing resources and can be simply implemented on usual personal computers.

2. High Storage consumption. Because there are some applications which highly desired of seriously high reliabilty on current unreliable Internet. Compared to bandwidth costs, storage costs are much lower. So the tradeoff between storage and bandwidth exists, people will choose one of the twos.

Most over above all, Luby Codes can get ride of traditional re-request of TCP transmitting. When receivers find error in encoding blocks, these blocks will be discarded without re-requesting. This can improve its efficiency. Because TCP transmission is affected by RTT value, this limited efficiency of TCP protocol.

As discussed above, I think that erasure codes really can help improving swarming efficiency.

Do you agree with me? Any comments of you are welcome.

(Reply to this) (Thread)

Re: Erasure Codes
[info]bramcohen
2004-12-07 06:28 am UTC (link)
Internet data transfer algorithms require acks for congestion control anyway. Adding some information to those acks about what packets didn't make it adds no overhead. Under some conditions increasing the window size and massaging some other parameters can increase performance, but such tweaking will always perform just as well as and be a lot more utilitarian than transfer algorithms based on ECC.

(Reply to this) (Parent)(Thread)

Re: Erasure Codes
[info]lionkingwf
2004-12-07 07:17 am UTC (link)
TCP protocol changes the window size according to RTT value changing. If RTT value is changing larger, it will be considered that there must be congestion happened. However, in fact there are two cases for RTT value turning larger, one is that when congestion really happened, another is that if the distance of connection two sides turning longer, RTT value also will turn larger.

So, although there is enough bandwidth left, the TCP transmitting efficiency isn't high. The rather that the condition of connections between peers is much worse than servers.

Erasure codes help swarming work well on bad connection condition. Not is it?

(Reply to this) (Parent)(Thread)

Re: Erasure Codes
[info]bramcohen
2004-12-07 07:26 am UTC (link)
What you're talking about here isn't really swarming, but much more straightforward data transfer between two machines, which is used in swarming, but isn't made significantly different in a swarming architecture.

TCP is designed assuming that there's a very low rate of packet loss between machines, and when a packet is lost, that's generally due to the link getting saturated, and if backoff is done properly the link well become un-saturated and packet loss will drop to 0% again. If you're transferring over a connection which gets a significant rate of packet loss even when there is no congestion, then a fundamentally different protocol may work better, although the internet solution is to simply engineer the links to not have such problems. ECC is extremely applicable at the link level to get packet loss there to the levels which are necessary to satisfy the internet's engineering assumptions, but end to end it's hard to justify.

(Reply to this) (Parent)(Thread)

Re: Erasure Codes - [info]lionkingwf, 2004-12-07 08:14 am UTC
Re: Erasure Codes - [info]bramcohen, 2004-12-07 03:25 pm UTC
Re: Erasure Codes - (Anonymous), 2005-06-21 06:04 pm UTC
Re: Erasure Codes - [info]ka9q, 2005-06-22 01:30 am UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 03:21 am UTC
Re: Erasure Codes - [info]ka9q, 2005-06-22 06:17 am UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 07:21 am UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 03:28 am UTC
Re: Erasure Codes - [info]ka9q, 2005-06-21 10:55 pm UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 03:24 am UTC
Re: Erasure Codes - [info]ka9q, 2005-06-22 06:20 am UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 07:24 am UTC
Re: Erasure Codes - [info]bramcohen, 2005-06-26 06:16 pm UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 03:19 am UTC
Re: Erasure Codes - [info]ka9q, 2005-06-22 06:37 am UTC
Re: Erasure Codes - [info]_scorp, 2005-06-22 07:27 am UTC
Good point
(Anonymous)
2004-12-08 04:30 pm UTC (link)
(from Federico Sacerdoti)

Excellent points about using complex software and algorithms for diminishing gains. Its great to see someone being honest about the difficulty and reliability of real software, and factoring into the N-nines calculations.

Until we can prove implementations correct, we had better think long and hard about getting fancy. (I should take this advice myself occasionally).

-Federico

(Reply to this)


[info]_scorp
2005-06-22 03:33 am UTC (link)
I think the network bandwidth maintenance requirements for data correction are playing a major role.

Here is one paper from Berkeley praising the erasure codes: http://classes.eclab.byu.edu/601/wiki/plugin/attachments/CourseCalendar/Reperasure.pdf

And here's another paper from MIT looking at costs of replication vs erasure: http://www.pmg.lcs.mit.edu/~rodrigo/p2p-2ec-final.pdf

It would be interesting to discuss that.

(Reply to this) (Thread)

why are we worrying about those particualar ideas?
(Anonymous)
2005-06-22 05:10 am UTC (link)
isn't the whole reason bittorrent works better than its predecsorrs, mostly because instead of trying to invent ways to add a few bits here and there to download speed, but rather to add new sources. i think a better topic to pursue would be the ability to remember peers you encountered in the past, even for different downloads. this could speed up bittorrent transfers by reducing 'leeching' even more, particularly because it would tend to favor users who shared more data over time than those who didn't; perhaps ranking remembered users by age of last connection, number of times met, and how 'profitable' it was for the current user to have them as a peer.

(Reply to this) (Parent)(Thread)

Re: why are we worrying about those particualar ideas?
[info]_scorp
2005-06-22 07:18 am UTC (link)
What you're saying is true for content that is wanted by many different people.
Assuming that the content is non-private and/or popular.
Imagine it's a video of your baby making first steps.
And you want it to stay in the network for a long time.

(Reply to this) (Parent)

ARQ vs FEC
[info]ka9q
2005-06-22 06:54 am UTC (link)
Working in the digital radio business as I do exposes you to a lot of coding theory. The basic tradeoff between FEC and ARQ is very simple. Both are forms of error control coding, and each has a regime in which it works better than the other.

FEC tends to beat ARQ when 1) bit error rates are very high and errors are randomly distributed; 2) latencies are very high; 3) you have many listeners to one transmitter (e.g., in broadcasting); 4) you can tolerate non-negligible residual error rates.

ARQ tends to beat FEC when 1) error rates are low and errors occur in long bursts; 2) latencies are small; 3) you're running a point-to-point link where requesting a retransmission is no big deal; 4) you need a very low residual error rate.

ARQ and FEC are often used in combination, but when they are you invariably have ARQ on top of FEC, not the other way around. You take a noisy channel and reduce the error rate to a low but nonzero value, often changing the statistics of those errors from random bit errors to relatively long bursts of erasures, and then you clean up those erasures by requesting retransmissions. In practice, FEC is most often implemented down in modems, and you rarely see it at the level of an Internet protocol.

That doesn't mean FEC is never a good idea in an Internet protocol, it's just very unusual for it to be. One important exception is reliable multicast because of the inherent advantages of FEC in a broadcast environment. Bit Torrent can be thought of as providing a multicast service, but since it is implemented on a set of point-to-point links, ARQ on those links is the preferred method.

Now if we actually had a ubiquitous IP multicast network, we either wouldn't need Bit Torrent, or it would look very different than it does.

(Reply to this) (Parent)(Thread)

Re: ARQ vs FEC
[info]_scorp
2005-06-22 07:32 am UTC (link)
latencies ... IMHO we are within a factor of 2 of speed of light (in fiber which is 60% of the one in vaccum) for most connections ... and I would love to see coast to coast latencies less than 50 ms - but I doubt its possible short of quantum entanglement stuff

and think about the previous comment - switches have finite buffers (cisco: 40 input, 70 output packets) which are extremely small ...

(Reply to this) (Parent)(Thread)

Re: ARQ vs FEC - [info]bramcohen, 2005-06-26 06:23 pm UTC
Re: ARQ vs FEC - [info]_scorp, 2005-06-27 05:34 pm UTC

[info]ciphergoth
2006-03-23 12:52 pm UTC (link)
Just found myself back here due to a random mail trawl. I'm sure you're right that erasure codes aren't worth it for BitTorrent, but there's a slight error in your argument it's probably worth correcting. You say
The problem is that the peer may already have gotten that same piece from another peer, so that benefit is destroyed, and on top of that the overhead of communicating and remembering which peer has what is increased tremendously.
I think you've misunderstood the point of erasure codes. If you generate a random piece, the probability that a peer already has it (or sufficient information to reconstruct it) is practically zero, unless that peer already has the whole file. So you don't have to keep track of your peer's state of knowledge at all; you just send them new pieces until they have as many as the size of the file, in which case (with overwhelming probability) they will be able to reconstruct it. This isn't hard to prove; it's based on the probability of a random set of vectors in GF(2^k)^n being linearly independent.

(Reply to this) (Thread)


[info]bramcohen
2006-03-23 06:51 pm UTC (link)
That would be true if only peers which had complete files uploaded pieces, since they're capable of generating random new ones. However, a peer which doesn't have a complete file is stuck re-uploading pieces it already received (or recombining them - I don't know of much academic work indicating what the possibilities are for that) and so you do have to worry about having seen a piece already.

(Reply to this) (Parent)(Thread)


[info]ciphergoth
2006-03-23 08:47 pm UTC (link)
You can re-combine pieces as soon as you have more than one. Even if you don't have the complete file, it's still incredibly unlikely that a piece you generate will tell a peer something they already know, except where their knowledge is a superset of yours.

(Reply to this) (Parent)(Thread)

(no subject) - [info]bramcohen, 2006-03-24 06:18 am UTC

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…