Every few months, there is a new press release from Fujitsu or Hitachi about their new Internet Core Routers and the ungodly number of packets per second that it can forward. They seem to expect to sell only tens or hundreds of these monstrous devices, and they tend to have truly absurd configurations: for example, an ``off-the-shelf'' million-dollar ATM switch routes the actual traffic, but this piece is readily-available and doesn't take smart people to build it. The PR-worthy Fujitsu or Hitachi brain sniffs the traffic, and then commands the ATM switch over an out-of-band channel about how to route it. Why? I don't know. The brain is implemented in silicon, not software, and the next release promises active optical components.
IPv6, the next-generation low-level Internet protocol, includes a
whole bunch more addresses. A machine address is 128 bits, up from
the current 32. This, we are told, is because there are just that
many computers on the Internet. Hogwash. Current predictions suggest
the planet will hold 1.5 * 10^10 people, but 128 bits is
3.4 * 10^38 addresses. That may well be enough for every
atom on the planet---but I don't really know. The purpose of
all these addresses is routing aggregation. The rightmost
(least-significant) 48 bits of the address is enough to uniquely
identify every piece of equipment ever made, but the IPv6 spec leaves
64 bits anyway. While the leftmost (msw) 32 bits is a routing
zipcode. The 32 bits in between is divided into 16 bits to enumerate
an ISP's customers, and 16 bits assigned to each customer for its leaf
network's topology. This way, addresses which are near to each
other---addresses in the ``default-free zone''---will be numerically
similar, allowing routing decisions that currently occupy many tuples
in the routing tables of core routers to be replaced with a single
tuple. Huge unaggregateable core routing tables are the
less-discussed Internet expansion catastrope, but this is also an
important motivator for IPv6.
Queueing algorithms like HFSC require routers to keep per-flow state. With the pseudocode published in the HFSC paper, this means that each high-quality service (phone call, videoconference) must have state stored on every router that it passes through. For core routers, this is unworkable.
HFSC is only workable after some trick appears to implement the algorithm in a distributed way, for example by attaching the necessary state to each packet rather than storing it in a lookup table, and doing some precomputation of queueing decisions before packets reach the core routers. This is not an unreasonable expectation. It presumes the existence of a trusted-untrusted boundary somewhere far downstream from the highest-capacity core routers: machines on the trusted side of the boundary must not act to unfairly priviledge certain flows or subvert billing mechanisms. I think the Internet already includes such boundaries. In the early days, presumably the entire network was ``trusted.'' I have read papers which attempt to do this, but when I last read about queueing algorithms, HFSC had just replaced H-PFQ, and the papers about the core routing problem all used third, even older, fairness algorithms. That was three years ago---who knows what's going on now. Perhaps if there were more interest in and use of the algorithms, the work would continue.
As packet-switched networks begin to bend the rules by keeping per-flow state on routers, or forwarding packets after the header is received but before the body is received, they begin to eerily resemble circuit-switched networks. Ultimately, I think the distinction will become meaningless. The victory of packet-switched networking will not be a purely theoretical one. Rather, it will be this: packet-switched networks will adopt and assimilate circuit-switched tricks, and not the other way around. You will see Hui Zhang's name again, but I think the designers of X.25 and SS7 (excursions of the circuit-switched camp into packet switching) will not resurface under any flattering light.
Another problem
Most scheduling algorithms are for routers. Routers, as imagined by
these algorithms, have some interesting characteristics which we must
not take for granted:
In these days of gluttanous MIS budgets and overuse of disgusting ``switched'' equipment, it's possible, perhaps even the norm, for an end-to-end wired connection to obey this model. However, the good old broadcast medium still exists to some extent with wireless networks.
It's considerably more complicated, though. Even in the old days of wireless, it wasn't the same as Ethernet because there were a multiplicity of ``channels'', and each channel was an independent broadcast medium. First-generation Ricochet obeyed this model. I believe it had 160 channels of 100Kbit/s each. A wired access point typically had eight independent-and-identical radios, so it could receive or transmit on eight channels at once.
Now that everyone agrees CDMA works (cough, Motorola, cough), the broadcast network model (like Ethernet, or Alohanet) fits non-legacy radio technology (all of which is CDMA) even worse because some small number of stations can transmit simultaneously without interfering with each other, and without assigning stations to ``channels'' before they start transmitting.
Radio is not a ``broadcast medium'' like Ethernet, but it doesn't agree with the simplified ``router'' model I introduced, either.
Since radio is not the same as ``routers,'' unaltered HFSC will not work to mediate the transmissions of large numbers of radios on congested bands. However, that doesn't mean we need to go back to assigning high-quality services to fixed-bandwidth circuits. HFSC could potentially help between small numbers of short-range radios like Ricochet's repeaters, and other scheduling algorithms will have something to say about wireless networks.