Slashdot Mirror
ARPANET Co-Founder Calls for Flow Management
An anonymous reader writes "Lawrence Roberts, co-founder of ARPANET and inventor of packet switching, today published an article in which he claims to solve the congestion control problem on the Internet. Roberts says, contrary to popular belief, the problem with congestion is the networks, not Transmission Control Protocol (TCP). Rather than overhaul TCP, he says, we need to deploy flow management, and selectively discard no more than one packet per TCP cycle. Flow management is the only alternative to peering into everyone's network, he says, and it's the only way to fairly distribute Internet capacity."
Oh, from his company of course.
I'm not big on networking but if I'm sending data to someone and some "flow management" dumps one of the packets, won't my computer or modem just resend it? Seems like not such a good idea to me.
Google's Super Secret Search Algorithm: SELECT @search_results FROM internet WHERE @search_results = 'good'
ANy device sophisticated enough to do the flow fairness described can also do "user" fairness by averaging behavior across multiple flows from the same soure, and the behavior of the source over time.
This solves the P2P problem, and has a bunch of other advantages.
Note, also, you only need to do this at the edges, as the core is pretty overprovisioned currently.
Test your net with Netalyzr
I couldn't help but laugh a bit at his solution. He talks about "flow management" being put into the core of the network to solve TCP's unfairness problem, but at the end of the article he says:
So, in other words, his solution to the "P2P problem" is just a fancy version of a token bucket.
It immediately kills any worries that this could be used for "evil" as stallman wouldnt stand up for anything that could be used for censorship. Big-names can be useful sometimes, even in nerd circles.
Can someone explain why this hasn't already been implemented?
It has been implemented and abandoned already because it doesn't scale. Serious routers today use the concept of interface adjacency: for a given inbound packet there are only a few possible destinations: they are each of the interfaces on the router.
When a route is installed into the FIB, you can recursively follow that route until you find the egress interface and the layer 2 address of the next hop - those will typically never change! So long as the router always keeps this adjacency information up to date, individual packets never need to have a route lookup performed - the destination prefix is checked in the adjacency table, the layer 2 header is rewritten, and the packet is queued for egress on the appropriate interface.
This allows for substantially higher throughput (in packets per second) than other methods because the adjacency table can be cleverly stored in content-addressable memory that provides constant time answers. A prefix will be installed in a content-addressable memory circuit as a lookup key. The value associated with that key is a pointer into the adjacency table that holds the interface and layer 2 information for that prefix.
By reconsidering the routing problem, and by using some smart circuits, the route lookup for a single packet has been reduced from O(k) to O(1), where k is the length of the longest prefix. For IPv4, that's up to 32-bits - so that means you do a single fetch and lookup instead of 32 or so comparisons for each packet. At a million packets per second, that's a huge difference.
Traditional flow-based routing requires creating in-memory structures for each flow, collectively called the flow cache. Each packet requires an initial full route lookup, which builds the structures for that flow. Then, subsequent packets in that flow can be matched against the cache and switched directly to the egress interface. This operation is much closer to that of a contemporary firewall. The good thing about this method is that it gives you a lot of visibility into the traffic. The bad side is that it requires a very large amount of memory for all of these structures. When that memory is exhausted, you can't route anymore flows!
This comparison is a bit apples to oranges - the adjacency table described above is pretty much state-of-the-art for off the shelf gear, while the flow cache architecture is highly dated. But without some substantial advances in the ways flows are created, tracked, and expired, no flow router is going to reach the number of packets per second that are required for very large installations in the Internet.
Maybe because as far as your rights go in relation to privacy, copyright, and computing in general, RMS is one of the few people that has dedicated their lives to defending those rights. If there is a problem that might infringing upon fair equal access to public information, who do you want to comment? Should those that make a buck off of charging you to get to said information be the only ones that have a right to comment or someone that is dedicated to preserving his and your freedom? I personally thing both have equal credit speaking on the subject.
wonder if routing algorithms themselves aren't contributing to the problem.
BGP and the intra-domain routing protocols assume there is at most one correct route from a given source address to a given destination address. That assumption could give rise to unnecessary congestion. For example, suppose the source wants to use bandwith of 100 units and the destination is capable of keeping up. But between them there are two routers, in parallel, each of which can supply only 50 units. If there's exactly one path, source and dest can't talk any faster than 50 units because everything has to go through one of the two routers. (There are mechanisms to share bandwith in some situations, like the simple parallel routers one I described, but they dont' work for arbitrarily complex routing topologies across multiple BGP domains.)
It's possible, though, to imagine a network that routes in such a way that data could use both routers. For instance, in circuit switched networks the preestablished path tends to hang around even as the current "best" route changes, so in the earlier example two 50 unit connections between source and dest might end up being spread across both routers.
Rather than taking the congestion as a given, and figuring out work-arounds, I wonder if someone's done some research into why it exists and whether it's due to hot spots forming in the traffic flow.
The multi-flow problem is already solved with the level of management he has proposed. It equates the total bandwidth coming from one IP, not just a specific flow.
'Your websurfing, he's got 6 torrents downloading. He is going to have at least 24 active flows, running full bore, and you will have 1 or 2 (which are bursty even). Thanks to how TCP works, without traffic shaping, you will receive 1 packet for every 24 he gets.'
As things stand now, yes. But under the scheme he is suggesting my flows would be slowed down while yours would not.
This slows the rate at which the P2P user transmits packets from a given IP (regardless of how many flows are used) so that whether I am using one or 200 connections, you and I will receive packets at the same rate while we are both requesting them.
At the end of the day the P2P user used more bandwidth, and received more data. But that is well and good, there is nothing wrong with utilizing your connection. The surfer (or any other type of user) never had to wait longer because of how the P2P user used their connection.
Too many people want to punish the people who use their connection regularly because light users experience congestion. Network admins in particular begin seeing high bandwidth users as evil.
I have a lot of respect for Larry Roberts. The idea of only discarding a single packet per flow on a congested interface in order to slow things down is a good one.
If WRED didn't exist on every production-grade router made in the last 10+ years then there would certainly be a need for this technology. However, I'm not really sure how much benefit the "multi-flow fairness" concept would provide vs. just configuring WRED to discard only payload packets & not TCP control traffic. The tradeoff is the added complexity of the congestion avoidance mechanism having to be flow-aware, which increases cost, time to market, heat & power consumption, etc.
Such a technique combined with microflow policing would come closer to what he describes. In fact one could probably refer to the congestion avoidance technique described in the article as "adaptive microflow policing".
A pretty standard config used with OpenBSD's PF firewall is to prioritize ACKs in both directions so that a line congested in one direction is still useful in the other.
BTW, TCP has already been re-engineered; it's called SCTP. If you've got a custom high-bandwidth point-to-point application where you have complete control over both ends (mostly research stuff at this point), check it out.
A different approach to bandwidth management that is being developed by the major router vendors is the application-aware network. Imagine if the router was smart enough to read a field in an XML stream that indicates that this particular flow requires 64kbps or it should be dropped, it should have 256kbps to work well, and giving it more than 1mbps is not useful and you start to get the idea. That's just the tip of the iceberg.
Anyway, congestion control is useful & necessary, but "quality of service is no substitute for quantity of service"...
Why is there an "insightful" mod and why isn't it "-1"? If I wanted insight, I wouldn't be reading
In other words, if such a model were to be adopted, every company would adopt each a different pricing model for metering usage. One provider would have free minutes of internet between 2 am and 7 am. Another provider would have free/partially discounted minutes of internet between the hours of 7 pm and 10 pm. And another provider still would provide some functionality free with some other functionality that's purposefully crippled.
The end result would be a potpourris of confusion and annoyance for the consumer, just like the cell phone market is right now for the American consumer. And I guarantee you, the end result wouldn't make sense. Pricing schemes are not optimized to enlighten and save money for the consumer. Pricing schemes are optimized to confuse the consumer and take away money *from* him.
And if you go back far enough, you'll find that Compuserve, AOL, Prodigy, and/or the Minitel did charge for the internet in a metered fashion. They just didn't do it in the same ways, and often they didn't provide the same services -- for the exact reasons I described. AOL for instance didn't give full access to the World Wide Web, it tried to have a marketing partnership with every content provider its users connected to. And it didn't charge by the month, it charged by the minute -- often charging exorbitant $300 bills per month -- while its uncrippled competitors ended up charging much less for unlimited access.
Did you look at the date?