[jandrewrogers]

Designing networking protocols that are robust in mathematical sense is unbelievably difficult. In fact, we humans have only found optimal solutions in a few cases if you dig through the mathematics literature. Many real-world networking protocol design scenarios do not have a known non-pathological implementation. Furthermore, there is a large number of decentralized protocol designs that we can prove to have many poor qualities. To bludgeon the equine, people that can significantly advance our understanding of such things tend to win Nobel prizes and similar. It is that difficult.

That said, TCP is not the best we can design given everything we know about designing network protocols. It was good enough for the people that designed it at the time, and possibly (my chronology is fuzzy) was approximately as good as the mathematics would have reasonably allowed when it was developed. We can make it work well enough in many cases -- the economics of inertia. Other narrow use cases are better solved differently but are not general solutions.

It is one of those problems that sounds like it should be easy to solve on the surface but turns into a bloody epic challenge once you start to dig into it. I am not offering a solution, just noting that very few people can.

[paulsutter]

Hold on a minute

> possibly (my chronology is fuzzy) was approximately as good as the mathematics would have reasonably allowed

Just because Van Jacobsen's papers spew forth great volumes of mathematics, doesn't mean there is any robust mathematics behind TCP. Read to the end of his paper "Congestion Avoidance and Control". Read past all of the impressive plots graphs and equations. Read to the conclusions.

"The 1-packet increase has less justification than the 0.5 decrease. In fact, it’s almost certainly too large."

This statement shows how little formal consideration went into the entire algorithm. The 1-packet increase is not simply too big or too small, it just doesn't make any sense. For starters, how big is the packet? Oh, it isn't defined anywhere. Even if we just go with the de facto internet packet size of 1542 bytes (you know, the old limit for 10Mbit Ethernet)...

Could that one packet increase per roundtrip make equal sense for a 10Gbit path to India with a 400ms round trip time, as it does for a 56Kb link between Berkeley and MIT (his test case)? Of course it doesn't make sense. And it gives lie to any notion that there is a formal underpinning for TCP. They tweaked it until it worked, and then put on a nice mathematical show to feel better about it.

Quoth Van Jacobsen: "We have simulated the above algorithm and it appears to perform well". Oh now I feel better.

Second point, which Braham is covering: TCP makes the assumption that router queue lengths are reasonable. TCP says, fill up the router queues until they drop packets. But router queues have been getting longer and longer as memory gets cheaper. These queues can create additional seconds of delay to layer on top of the 10ms-400ms speed of light delays we see on the internet itself.

EDIT: In that 10Gb to India example, it takes TCP literally DAYS to fill up the pipe because of that "1 packet per roundtrip" window increase. Days, by the way, of no incidental packet loss, because it all gets reset on a loss.

EDIT: I spent 5 years of my life working on the fact that latency was never really factored into the design of most network protocols.

[bramcohen]

Did you even read the article?

[paulsutter]

One thing you have to realize about Hacker News is that people can accumulate pretty good karma points for postings that have a definitive/authoritative tone blended with some truisms. Not to bludgeon the equine or anything, but I think people find them comforting.

[scott_s]

I don't think his comment in any way contradicts your post. I thought it added to it; his point is that not only are good protocols hard in practice (which you covered), they are theoretically hard (which you did not cover, hence adding to your point).

[its_so_on]

To people who don't know what the parent is talking about.

Take a simple example.

http://en.wikipedia.org/wiki/Two_Generals_Problem

My summary:

The two generals problem proves that, if there exists any nonzero probability of packet loss, two people cannot even coordinate to both have a state 1 at sunrise tomorrow (attack!!!) or both have the state 0 if it is not 100% mathematically guaranteed that they both believe this has been coordinated (since an uncoordinated attack will be a catastrophic loss for them).

(In other words, the guarantee must be such that by sunrise tomorrow state 0-1 or 1-0, in other words one general thinking the attack has been coordinated with certitude and attacks, but the other general thinking the attack has not been confirmed with certitude and does not attack, must be a mathematical impossibility.)

Take a simple approach. The following packets are all encrypted, but any or all may be lost.

1) first general sends: "Let's both be in state 1 tomorrow (coordinated attack). Since an uncoordinated attack is so catastrophic to us, I will only enter state 1 if I receive your reply. Please include the random number 25984357892 in your reply. As soon as I get this the attack is ON. If I don't get such a packet within the hour I will assume this post was intercepted (lost), and I will send another. I will remain in state 0 until I receive that packet."

2) second general sends: "Got your packet with 25984357892. This is my acknowledgment! I will attack as well. In case you don't get this, I know you won't attack thinking I didn't get your message, so I am sending this message continuously."

Great. But what if all messages from the second to the first are intercepted. Now the first thinks all of HIS were intercepted (has received no acks) and doesn't attack, but the second one does. Failure.

So, we have to emend 2) to:

2) second general sends: "Got your packet with 25984357892. This is my acknowledgment! I will attack as well. In case you don't get this, I know you won't attack thinking I didn't get your message, so I am sending this message continuously. In case you don't get any of THESE messages, however, I will not attack. Therefore acknowledge ANY of them with random number 458972984323..."

Ooops. What if all the first general's ack's of the acks are intercepted or lost? (Perhaps the first general is able to send messages until receiving (2), but just as the first general gets 2) conditions change and the general no longer has any of his messages delivered.)

Now the first general thinks he has acknowledged the ack, but the second general doesn't even know if his ack-(cum-request-for-an-ack-back) message was even delivered...

and so it goes...

Of course, in practice you can simply say: "Let's do this for a certain number of acks of acks of acks, 3 let's say, and then just keep sending the same ack to each other, assuming that if the connection was reliable enough to get to three deep, then it will be reliable enough for one of the final acks to make it through." That's a false assumption (mathematically - what guarantee do you have that if 3 of your encrypted messages made it across, at least one of the next 217 that you send by sunrise all with the same message will), but a reasonable one.

So it is not a practical problem. This is a mathematical problem. Although you cannot even do something as simple as "let's agree to both be in state 1 (or neither if we fail to agree), OK?" over a less than guaranteed reliable connection, if the connection has any reliability at all you can get to within a practical level.

once you reliaze that, PROVABLY, you can't even do the most mundane things no matter what, the mathematics the parent is talking about do not seem all that interesting anymore. :)

[paulsutter]

While it's true that network protocols are neat challenging puzzles with nontrivial solutions, the hardest parts end up being the mundane: how does any given protocol change interoperate with all the existing implementations out there, especially changes to congestion control, and across the range of optional protocol features.

Uncertainties introduced by packet loss are actually pretty easy to work past.

[romaniv]

Shouldn't there be mathematically solid probabilistic solution? Start at 50% certainty, increase it with every positive message, decrease it with every unit of time. Stop when you're close to 100% or 0%.

[scotty79]

You could still prove some estimates of probabilities of the outcomes given reliability of the connection and such. It still can be mathematically interesting.