Cows, Cars, and the Internet

[iago]

I'm curious what people think of this essay/report:

Cows, Cars, and the Internet
by Suzanne Ross

What do cows and the Internet have in common?

In the days when hunter-gatherers first decided to stay put and become farmers, they often stuck together in villages for protection from marauding gangsters known alternately as Huns, Vikings, Celts, or "them." As a result, cow grazing areas were limited to common lands that could be easily defended.

The only problem with this scheme (now called the Tragedy of the Commons) was that everyone thought their own cows had more right to graze the common lands then their neighbors' cows, and no one wanted to think about how cow congestion led to poorer grazing and thinner cows for everyone. If one person added another cow, even though it would increase the load on the grazing lands and reduce overall quality, it would still give that individual a higher percentage of cows.

The same is true for the Internet. More and more users want more and more bandwidth, they want it now, they want it fast, and they won't tolerate a few seconds delay. Their streaming video is more important than the next guy's executable file download. The resulting congestion is annoying to everyone, yet no one is willing to give up their piece of turf. How can we get everyone to share?

One of the solutions is to add more pipes, more servers, and more technology. But, as any one who has ever retired or tried to build a freeway knows, tasks and cars expand to fill whatever time or space you have. The same is true of bandwidth. Technology users will probably always expand to fill the available bandwidth, and we'll still have the same congestion.

Peter Key, Richard Black and other researchers from Microsoft Research in Cambridge, UK, have implemented a model to reduce network congestion that follows an economic model developed to avoid the tragedy of the commons. It's called "congestion pricing" or "resource pricing."

This model, which several researchers have thought about applying to networking since the early nineties, is more needed than ever before. The proposal is to add feedback signals to network communications, allowing a weighted fair sharing of resources. Congestion pricing is often used by city planners (for cars instead of cows) to prevent freeway gridlock. Under this model, car owners have to pay to drive their cars at peak hours. The hope behind this system is to motivate drivers to take to the roads at non-peak hours, or to ride-share or take public transportation.

The network model doesn't demand a monetary return for peak access, but could give greater weight to a pre-determined set of applications or users that would change depending on need. For instance, if streaming videos accessed by person A had preference over Web surfing by person B, it would receive a proportionally greater bandwidth share, but if person A wasn't accessing a video, then person B's surfing might get a greater share of the bandwidth over A's file download. Or, on an individual machine, Windows updates could be given a lower value than email traffic or Web surfing. That way, the update would automatically run when the user was not engaged in those activities; say, at two in the morning.

The Problem with TCP
Black explains the problem with the current network protocol. "TCP is a very good protocol in many respects, but it reacts to network behavior mostly by driving the network to the point where the network is congested, and then it's able to observe that congestion and that causes it to reduce the loads it puts on the network."

While the network is observing the congestion, something happens that reduces the quality of customer service. Queuing delays lead to lost packets, which leads to lost data. For some applications this isn't a big problem. For others, such as streaming video, it means that the picture will break up or freeze.

"The basic idea is that if there is a resource that becomes overloaded then you can think of that as its 'price' going up," explains Key, "because if a lot of people share a resource then they have an effect on each other, and they've then got an incentive to cooperate, so that you can share that resource out fairly. The resources can be elements of a computer system, it could be memory, it could be battery power, but we're particularly looking at networks and bandwidth. How can you get applications that run across the network to share bandwidth? By telling them about the current price, and then letting them react accordingly."

"One of the advantages of a system like this is that once you have sort of bought into the economic model it becomes easier to understand how to do relative shares of the network so you can say that this particular activity should have approximately twice as much weight or access to the system," says Black.

"It turns out you can get the network to behave like a smart market, in a rather simple way," says Key.

Making It Work
Though Key originally envisioned this system as a cure for Internet delays, Black and his colleagues, Paul Barham and Neil Stratford started using it on a smaller scale.

"You don't have to change the whole network all at once. You can look at a very restricted environment where it's much clearer who is in a position to set the rules of the game. If you were to try to change the whole Internet into a congestion pricing model you'd have the difficulty of who would police the economic worth of the various users on the Internet. Because, who is to say one user is worth more or less than another? Even if you did come up with such a scheme, how would you police it given the number of different companies, different network service providers, and so on. It's a difficult problem," adds Black.

However, in a constrained environment, such as a home or a private company, users could benefit from having an underlying economic model to control bandwidth access.

In the company, the powers that be could decide that a video conference that included the company's top brass would get precedence over a video conference between single users, or even network email. They might be willing to trade some company-wide ability to access certain applications in favor of a smooth conference with major customers.

In the home, the parents could decide that their applications and use of the Internet had a greater value than their children's online game play. Or, in the case of a former Cambridge researcher, Derek McAuley, the parent might be a game player who can't have any delay in the time it takes for his data to travel across the network, called latency, or he'll lose the game. McAuley became interested in the model that Key and Black are developing when he was playing the game Counterstrike. His opponent took out his character before he could get in his own hit because his children's nanny was surfing the Web at the same time, causing high latency. If he'd had a congestion pricing system in place, he could have assigned more value to online game play over Web surfing.

Black has created a prototype system to test Key's economic model. "We're trying to get to the engineering level -- it's fine to think about the math and write the paper, but then you come to build it and it's a bit harder. Real nuts and bolts engineering often is quite difficult," says Black.

Recently Key and Dinan Gunawardena, a software developer at MSR, have applied the congestion pricing theory to network aware applications. Prototype versions of popular applications such as Windows Media and Windows Messenger adapt dynamically to the varying congestion price. The audio and video quality changes transparently when network conditions vary, giving a much better user experience.

The commons is an ancient organizing principle that worked well when the world was small, but failed with the advent of the agricultural revolution and larger populations. Once the Internet increased network traffic, it too became prone to the tragedy of the commons. Black and Key's research suggests a way to allocate bandwidth fairly in the face of fluctuating user demands.

[iago]

Since nobody has taken it up, i'll point out my two favorite lines:

Queuing delays lead to lost packets, which leads to lost data. For some applications this isn't a big problem. For others, such as streaming video, it means that the picture will break up or freeze.

Or, in the case of a former Cambridge researcher, Derek McAuley, the parent might be a game player who can't have any delay in the time it takes for his data to travel across the network, called latency, or he'll lose the game. McAuley became interested in the model that Key and Black are developing when he was playing the game Counterstrike. His opponent took out his character before he could get in his own hit because his children's nanny was surfing the Web at the same time, causing high latency.

Any opinions about those two quotes?

[GameSnake]

What does it mean exactly, iago? The internet isn't going to die is it? We have enough bandwidth for everyone, except that it is running out? Whats the problem here?

[CrAz3D]

People are greedy, thats the problem.

People need more cows, they need more cars, they need more bandwidth.  We all have probably more than enough to get by decently, but we want more.  So we just keep making more...its getting crowded as far as cows & cars go

[Sidoh]

I actually read the whole thing! :D

It's a very good article.  As long as high-bandwidth connections are available at reasonable prices, I don't see any sort of small change being able to fix the problems we're experiencing.  This is actually a really interesting subject, I think.

The last article I read said that code theorists had developed a new algorithm that was very close to the Shannon Limit.  I wonder if that will have any affect on upcoming network protocols?

[iago]

See, here's my take.  I think the person who wrote it is an idiot.  It's hard to respect somebody who makes so many factual errors.  What's left doesn't really matter.

For example, if you were making a list of stuff that is OKAY to lose packets, video and sound would be it.  Video and sound are designed around the principle that stuff will get lost, so make recovery possible. 

And for the second quote, do you really think that a nanny browsing the web will cause enough lag to kill him in counterstrike?  That's just bull. 

[Sidoh]

See, here's my take.  I think the person who wrote it is an idiot.  It's hard to respect somebody who makes so many factual errors.  What's left doesn't really matter.

I must've skipped a paragraph or two.  I thought the economy-based network was a pretty neat idea, but you're right, there are definitely a lot of errors...

For example, if you were making a list of stuff that is OKAY to lose packets, video and sound would be it.  Video and sound are designed around the principle that stuff will get lost, so make recovery possible. 

Yes, but there is downtime due to that?  I was under the impression that most lost packets were because of bad checksums, but I guess those would be "corrupted" packets, haha.

And for the second quote, do you really think that a nanny browsing the web will cause enough lag to kill him in counterstrike?  That's just bull. 

Skipped over that paragraph or sentence for sure.  I don't even remember reading anything about counterstrike, haha.

[CrAz3D]

See, here's my take.  I think the person who wrote it is an idiot.  It's hard to respect somebody who makes so many factual errors.  What's left doesn't really matter.

For example, if you were making a list of stuff that is OKAY to lose packets, video and sound would be it.  Video and sound are designed around the principle that stuff will get lost, so make recovery possible. 

And for the second quote, do you really think that a nanny browsing the web will cause enough lag to kill him in counterstrike?  That's just bull. 

Depends what the nanny is browsing.
Side note: shouldn't she be watching the kids?

[iago]

I must've skipped a paragraph or two.  I thought the economy-based network was a pretty neat idea, but you're right, there are definitely a lot of errors...

:)

Yes, but there is downtime due to that?  I was under the impression that most lost packets were because of bad checksums, but I guess those would be "corrupted" packets, haha.

There are 3 ways to lose it.  First of all, almost all video/audio traffic is sent over UDP.  This is because TCP has a lot of overheard/built-in delays, and most audio/video traffic is time sensitive.  If UDP gets lost, it's not transmitted.  So the 3 ways to lose a packet are: gets lost due to too much traffic, corrupted so checksum fails (as you said), or takes too long (usually there's a threshold, for example any packet that takes over 450ms might be dropped).  So yeah, there are many ways.  Generally, video is interlaced.  That means that each packet contains the data of a few packets before it, compressed more.  So you might have:

Packet: [[Frame 4 compressed] [Frame 5 compressed] [Frame 6]] 
Packet: [[Frame 5 compressed] [Frame 6 compressed] [Frame 7]]
Packet: [[Frame 6 compressed] [Frame 7 compressed] [Frame 8]]

Of course, the compression is very lossy, which is why it looks crappy when packets get lost.  But realistically, audio and video are very tolerant of lost frames. 

(can you tell what chapter we're on in Networks class?  Go Multimedia Networking!)

Skipped over that paragraph or sentence for sure.  I don't even remember reading anything about counterstrike, haha.

:)

Depends what the nanny is browsing.
Side note: shouldn't she be watching the kids?

Yeah, but they give the definite impression that she's not doing anything spectacular.  Also, I have never met a nanny, but I doubt they look after kids 24/7.  I'm sure they get some time off. :P

[Sidoh]

There are 3 ways to lose it.  First of all, almost all video/audio traffic is sent over UDP.  This is because TCP has a lot of overheard/built-in delays, and most audio/video traffic is time sensitive.  If UDP gets lost, it's not transmitted.  So the 3 ways to lose a packet are: gets lost due to too much traffic, corrupted so checksum fails (as you said), or takes too long (usually there's a threshold, for example any packet that takes over 450ms might be dropped).  So yeah, there are many ways.  Generally, video is interlaced.  That means that each packet contains the data of a few packets before it, compressed more.  So you might have:

Packet: [[Frame 4 compressed] [Frame 5 compressed] [Frame 6]] 
Packet: [[Frame 5 compressed] [Frame 6 compressed] [Frame 7]]
Packet: [[Frame 6 compressed] [Frame 7 compressed] [Frame 8]]

Of course, the compression is very lossy, which is why it looks crappy when packets get lost.  But realistically, audio and video are very tolerant of lost frames. 

(can you tell what chapter we're on in Networks class?  Go Multimedia Networking!)

Neat!  Do you know the percentages that make up the total loss?  That'd be interesting to see, especially if there was data collected on multiple years.

[iago]

Neat!  Do you know the percentages that make up the total loss?  That'd be interesting to see, especially if there was data collected on multiple years.

I seem to remember her saying that the connections can typically handle a loss of up to 10% and a jitter (that's the difference from when a packet is supposed to arrive to when it does arrive) of 150 - 400ms.   

[Joe]

Or, in the case of a former Cambridge researcher, Derek McAuley, the parent might be a game player who can't have any delay in the time it takes for his data to travel across the network, called latency, or he'll lose the game. McAuley became interested in the model that Key and Black are developing when he was playing the game Counterstrike. His opponent took out his character before he could get in his own hit because his children's nanny was surfing the Web at the same time, causing high latency.

And that, my friends, totally sums up why I hate trying to play World of Warcraft on 56k while my brother is on his computer using LimeWire and MSN (the official client, I just want to kill him sometimes).

[iago]

See, you shouldn't be using LimeWire on 56k anyways.  I doubt that using MSN would affect your gameplay much, though, it uses almost 0 bandwidth. 

[iago]

Incidentally, the original source on the paper is http://research.microsoft.com/displayArticle.aspx?id=355.  I didn't want to say so earlier because I didn't want this to turn into a Microsoft debate.  I really do think the person who wrote the article is an idiot :)