Slashdot Mirror
New Router Manages Flows, Not Packets
An anonymous reader writes "A new router, designed by one of the creators of ARPANET, manages flows of packets instead of only managing individual packets. The router recognizes packets that are following the first and sends them along faster than if it had to route them as individuals. When overloaded, the router can make better choices of which packets to drop. 'Indeed, during most of my career as a network engineer, I never guessed that the queuing and discarding of packets in routers would create serious problems. More recently, though, as my Anagran colleagues and I scrutinized routers during peak workloads, we spotted two serious problems. First, routers discard packets somewhat randomly, causing some transmissions to stall. Second, the packets that are queued because of momentary overloads experience substantial and nonuniform delays, significantly reducing throughput (TCP throughput is inversely proportional to delay). These two effects hinder traffic for all applications, and some transmissions can take 10 times as long as others to complete.'"
Damn right, they manage flows. It keeps the tubes from clogging.
Duuuurrrrrr.
Sent from your iPad.
It just makes the packet switching faster. But really, we're talking about the same idea here: datagram networks. Congestion avoidance has been known to be a difficult problem in datagram networks for a long time.
TCP's congestion control algorithm, which causes congestion and then backs off is the real culprit here, and this router does nothing to fix that. The way to fix that is to dump TCP's congestion control and replace it with real flow control in the network layer. That requires lots of memory on intermediaries, because you need all the hosts along the data path to cooperate with each other to communicate about flow control, and that means keeping state. At which point, we're not talking about datagram networks anymore. And that means dumping the other desirable thing about datagram networks: fault tolerance. Packets are path-independent.
Anyway: getting back to TCP's congestion control: his article even says that "During congestion, it adjusts each flow rate at its input instead." Wait, what? "If an incoming flow has a rate deemed too high, the equipment discards a single packet to signal the transmission to slow down." That's how it works right now! The only difference that I can see is that he's being a little smarter about which packets to discard, unlike RED, which is what he's comparing this to. If so, that's an improvement, but it doesn't solve the problem. It will still take awhile for TCP to notice the problem, because the host has to wait for a missed ACK. TCP can only "see" the other host-- it does not know (or care) about flow control along the path. Solving the problem requires flow control along that path, i.e., in the network layer, but IP lacks such a mechanism.
a router tampon?
Can you explain a little more? I just RTFA and I'm not convinced this is revolutionary either, but it's hard to say because this seems more like marketing than actual research. However, I'm hesitant to say he's full of shit without hearing a bit more of the debate around his ideas.
One question I was hoping would be answered is what this flow routing buys you that something like SCTP wouldn't?
I'm disabling ads until because I choose not to reward redesigns that are less usable than "view source".
Definitely not new.
"The router recognizes packets that are following the first and sends them along faster than if it had to route them as individuals."
Where have I heard this before...oh hay...
http://en.wikipedia.org/wiki/Cisco_Express_Forwarding
It manages flow of traffic, recognizing when one packet belongs with the others. This sounds wonderful, at least for people trying to inject packets.
I hope these things recognize the evil bit.
Check out my sysadmin blog!
The main players in the routing industry have been working on flow-aware routing for years.
(I'm in the hardware side of our company so I'm not sure where how many and which of the features built on the flow-based architecture are already in the field. But I'm willing to bet a significant chunk of change that that the full bore will be deployed on more than one name-brand company's product line and be the dominant paradigm in routing long before these guys can convince the telecoms and ISPs to adopt their product. No matter how many big names they have on staff - or how good their box is. Breaking into networking is HARD.)
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
What you describe (packet inspection and prioritizes traffic based on internal rules) is QoS. No one in their right mind is against that. The net neutrality debate is about ISP's throttling some traffic in order to extort money from both their customers and content providers that otherwise have no other relationship with the ISP. The debate is that all ISP's should be are the tubes the content is delivered over, not gate keepers of content.
That an ISP may prioritize services like VOIP over http or bittorrent is not what net neutrality is about and quite frankly is something that a good network engineer would look into and would probably implement.
"I use a Mac because I'm just better than you are."
First, routers discard packets somewhat randomly, causing some transmissions to stall.
While it is true that whether or not a particular packet will be discarded is the result of a probabilistic process, it is unfair to call it "random". Based on a model of the queue within the router and estimation of the input parameters the probability of a packet being discarded can be calculated. In fact, that's how they design routers. You pick a bunch of different situations and decide how often you can afford to drop packets, then design a queueing system to meet those requirements. Queueing theory is a well-established field (the de-facto standard textbook was written in 1970!) and networking is one of the biggest applications.
Second, the packets that are queued because of momentary overloads experience substantial and nonuniform delays
You wouldn't expect uniform delays. A queueing system with a uniform distribution on expected number of customers in the queue is a very strange system indeed. Those sorts of systems are usually related to renewal processes and don't often show up in networking applications. That's actually a good thing, because systems with uniform distributions on just about anything are much more difficult to solve or approximate than most other systems.
"Substantial" is the key word here. Effectively the concept of managing "flows" just means that the router is caching destinations based on fields like source port, source IP address, etc. By using the cache rather than recomputing the destination the latencies can be reduced, thus reducing the number of times you need to use the queue. In queueing theory terms you are decreasing mean service time to increase total service rate. Note however that this can backfire: if you increase the variance in the service time distribution too much (some delays will be much higher when you eventually do need to use the queue) you will actually decrease performance. Of course assumedly they've done all of this work. In essence "flow management" seems to be the replacement of a FIFO queue with a priority queue in a queueing system, with priority based on caching.
Personally, I'm not sure how much of a benefit this can provide. Does it work with NAT? How often do you drop packets based on incorrect routing as compared to those you would have dropped if you had put them in the queue? If this was a truly novel queueing theory application I would have expected to see it in a IEEE journal, not Spectrum.
And of course, any time someone opens with "The Internet is broken" you have to be a little skeptical. Routing is a well-studied and complex subject; saying that you've replaced "packets" with "flows" ain't gunna cut it in my book.
Exactly how is this different from what we currently have?
Consider a conventional router receiving two packets that are part of the same video. The router looks at the first packet's destination address and consults a routing table. It then holds the packet in a queue until it can be dispatched. When the router receives the second packet, it repeats those same steps, not "remembering" that it has just processed an earlier piece of the same video.
Uh, no. This is called process switching. It hasn't been used in anything but the most low-end routers for quite some time. CEF (Cisco Express Forwarding) and MPLS (Multiprotocol Label Switching) use flow control. The perform a lookup on the first packet, cache the information in a forwarding table and all further packets which are part of the same flow are switched, not routed, at effectively wire speeds. MPLS adds a label to the packet which identifies the flow, so it isn't even necessary to check the packet for the five components which define the flow. Just look at the label and send it on its way.
QOS (Quality Of Service) has multiple modes of operation and multiple queue types which address the issues of which packets to drop. It may or may not include deep packet inspection to attempt to determine the type of packet.
Perhaps they've come up with some new innovations that aren't obvious in the write-up because it's written at a relatively high level, but there's nothing here that isn't already implemented and that I don't already work with on a daily basis in production networks.
"The legitimate powers of government extend only to such acts as are injurious to others." Thomas Jefferson.
Yippee.
Cisco (and probably several others) have done this by default for many many moons now. By way of practical demonstration, notice that equal weight routes load balance per flow, not per packet. What it allows is subsequent routing decisions to be offloaded from a route processor down to the asics on the card level. And don't try to turn CEF off on a layer 3 switch - even a lightly loaded one - unless you want your throughput to resemble 56k.
Among the innovations:
no ram for buffering flows to cope with any temporary overcommitments. Instead it does this:
"Even more significant, the FR-1000 does away entirely with the queuing chips. During congestion, it adjusts each flow rate at its input instead. If an incoming flow has a rate deemed too high, the equipment discards a single packet to signal the transmission to slow down."
Um, discarding a random packet in the middle of my session will indeed slow the flow down, much in the same way as if you shoot me in the knee it will slow me down.
No, it doesn't break net neutrality in and of itself, any more than a traffic light or a roundabout breaks road neutrality. The idea of routing flows, rather than packets, permits more packets to get through for the same bandwidth.
So long as all flows are treated fairly, this will actually BOOST network neutrality as network companies will have less justification to throttle back protocols which take disproportionate bandwidth - as they will no longer do so. Users will also have less cause to complain, as the effective bandwidth will move closer to the theoretical bandwidth.
The only concern is if corporations and ISPs use this sort of router to discriminate against flows (ie: ensure unfair usage) rather than to improve the quality of the service (ie: ensure fair usage).
The belief by ISPs that you cannot have high throughput unless you block legitimate users is nothing more than FUD. It has no basis in reality. It is possible, by moving away from best-effort and towards fair-effort, to get higher throughput for everyone.
Congested networks can be modeled as turbulent flow in a river. Blocking streams is like damming up some of the tributary streams. It causes a lot of grief and isn't really that effective.
On the other hand, smoothing out the turbulence will improve the throughput without having to dam up anything. QoS services are intended as smoothing mechanisms, not dams. For the most part, at least.
Most "net neutrality" advocates would be advised to focus only on the efforts to build gigantic dams, rather than to be unkind or unfair on those merely smoothing the way, with no bias or discrimination intended.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Routing/Switching based on flows is highly flawed. The article claims that the benefit is due to reduced table lookup based on individual packet content. Instead if the 5 tuple is hashed to a flowid. then the presence of flowid indicates that the flow is already active and will be treated preferentially during a congestion. First of all, if the number of flowids are large then there is no way to store all the different flowids in a scalable and cost effective manner. Which means you associate an eviction clause which can hurt you more with all these complexities. Secondly, there is concept of hardware caching which works better than hashing flowids. Finally, all the classes of flow which are really important, can be protected with class based queuing.
Why?
It would be bad.
I'm fuzzy on the whole good/bad thing. What do you mean, "bad"?
Try to imagine all the packets on your network stopping instantaneously and every router on the Internet exploding at the speed of light.
Total TCP reversal!!
Right, that's bad. Important safety tip. Thanks, Egon.
"TCP throughput is inversely proportional to delay"
Absolutely wrong, 2Mb/s at 1ms delay gives the same throughput as 2Mb/s at 10ms delay
As long as the window is large enough
He has re-invented the layer 3 switch... now with less jitter and latency because:
The FR-1000 does away entirely with the queuing chips. During congestion, it adjusts each flow rate at its input instead. If an incoming flow has a rate deemed too high, the equipment discards a single packet to signal the transmission to slow down. And rather than just delaying or dropping packets as in regular routers, in the FR-1000 the output provides feedback to the input. If thereâ(TM)s bandwidth available, the equipment increases the flow rates or accepts more flows at the input; if bandwidth is scarce, the router reduces flow rates or discards packets.
So we are going to implement WRED on a per flow basis, get rid of the queuing, and force the tcp stream to scale back it's window size when we run out of bandwidth by dropping a packet out of that conversation...
I mis-spoke, this is a layer 2 and a half switch!
I'm hesitant to say he's full of shit without hearing a bit more of the debate around his ideas.
There really isn't a debate around his ideas, at least not any more.
The hitch is management overhead. Managing a flow requires remembering the flow. That means data structures and stateful processing. It's expensive and no one has demonstrated hardware accelerators that do a good job of it. On the other hand, devices like a TCAM can accelerate stateless packet switching a couple orders of magnitude past what's possible with a generic PC.
At low data rates where DRAM latency is not an issue (presently around the 500mbps range), flows can work and accomplish much of what he claims. At higher data rates (like the 10-100gbps links on the backbone) we simply can't build hardware capable of managing flows for any kind of reasonable price.
Beyond that, Larry has really missed the boat. The next routing challenge isn't raw bits per second. That's pretty much in hand. Rather the next challenge is the number of routes in the system. If you want two ISPs for reliability (instead of one), you currently have to announce a route into the backbone that is processed by every single router in the backbone even if it never sees your packets. That currently costs about $8k per route per year, the cost is falling a lot more slowly than the route count is climbing and the lack of filtering and accounting systems mean that each one of those $8k's is an overhead cost to the backbone networks rather than a cost directly recoverable from the user who announced the route.
Flow based routing doesn't help us solve that challenge in the least. If anything, it makes it worse.
If you're interested in routing theory and research, I recommend the Internet Research Task Force Routing Research Group (IRTF RRG). They're chartered by the IETF to perform basic research into Internet routing architectures and anyone interested can participate.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
What do you mean? 99% of the internet's packets are pretty girls.
I prefer rogues to imbeciles because they sometimes take a rest.
All older cisco equipment worked this way. This was nice, and worked very well for the first router(s) closest to the end customer. However for routers meant to route for large numbers of users this turned out to be a disaster.
Just to give you an idea, this was EOS (end of support) before I turned 10 (look for "netflow routing")
There are a number of very problematic properties :
-> trivial to ddos (just generate too many flows to fit in memory, or generally increase the per-packet lookup time)
-> not p2p compatible (p2p will cause flow based routers to perform at a snail's pace, because they open so much connections)
-> possible triple penalty for every new flow (first a failed flow lookup, followed by a failed route lookup, going to default route)
-> very hard to have a good qos policy this way. A pipe has a fixed bandwidth, and you almost always oversubscribe. Therefore useful policies are very hard to formulate per-flow.
-> if you divide bandwidth per-flow over tcp then a large overload will "synchronize" everything. So let's explain what happens if 3 users are happily surfing about and another user starts bittorrent. Bandwidth gets divided over all the flows, and *every* connection closes, due to timeouts.
There are a number of advantages
-> easy, very extensive QOS is trivial to implement
-> stateful firewalling is almost laughably easy to implement, and very advanced firewalling can be done (e.g. easy to block ssh but not https, just filter on the string "openssh" anywhere in the connection. Added bonus : hilarity ensues if you email someone the text "openssh", and his pop3 connection keeps getting closed)
Here's the deal : a router has to lookup in a table of about 300.000 entries in per-packet switching (excepting MPLS P routers). My PC is, at this moment, opening 331 flows to various destinations, each sending an average of 5 packets (probably a lot of DNS requests are dragging this number down), but you have to keep in mind that a flow-based router has to look up first in the "flow table" AND in the route table (which still has 300.000 entries).
As soon as a flow-based router services more than 1000 machines (in either direction, ie. 100 clients communicating with 900 internet hosts = 1000 machines serviced), it's performance will fail to keep up with a packet-based router. That's not a lot. If a single client torrents or p2p's you will hit this limit easily, resulting in slower performance. 2000 machines and packet-based switching is double as efficient.
So : flow-based routing ... for your wireless access point ... perhaps. For anything more serious than that ? No way in hell.
He's doing it *without* custom ASICs and without TCAM. TCAM is very expensive. I'm not sure this is faster than CEF or the like, but it may very well be cheaper.
"Where quality is like a dead stinking rat - you just can't miss it."
QoS isn't a bad thing, but the user should be in control of it
Exactly! That way MY packets (not some of them, ALL OF THEM) need to be prioritized.
Kind of reminds me of the good old days when I had access to print queue priorities. No-one ever understood why my printouts always came out first...I maintained I was just lucky.