CERF@A.ISI.EDU (10/10/87)
I found this note of considerable interest; fast packet switching (FPS)
is become an important focus of attention in several places - Bell Labs,
Bellcore, Univ Washington, and elsewhere. I believe it has the potential
to become the principal switching technology of the 90's and at the speeds
shwon in the laboratory (aggregate switching rates in the tens of gigabits
per second) could handle voice, data and possibly video (especially if
compressed).
Vint Cerf
Begin forwarded message
Received: from LF-SERVER-2.BBN.COM by A.ISI.EDU with TCP; Tue 6 Oct 87 17:13:19-EDT
Date: Tue, 06 Oct 87 16:31:43 -0400
From: John Robinson <jr@LF-SERVER-2.BBN.COM>
Reply-To: jr@BBN.COM
To: CERF@A.ISI.EDU
Subject: Re: TCP performance limitations
Return-Path: <jr@LF-SERVER-2.BBN.COM>
It is interesting that the Bell&al switching fabrics are, at a lower
level, hardware packet switches. This comparison was in fact the seed
of the Butterfly idea in Crowther's head. Reduce the routing decision
to something simple enough, and then speed the whole thing up by doing
it in hardware (1976). I was intrigued when Luderer's (Bell Labs)
presentation on fast packet switching at ISS87 last March alluded to
the Butterfly as a commercial realization of FPS technology to build a
multiprocessor. Computing and communications are tending to merger
here, as has often been said at other levels. Conservative
projections of Buterfly technology we have done make 45mbs trunks and
FDDI LANs look entirely feasible for next-generation IP switching.
The phone application of packet switching isn't concerned about
end-end integrity too much, but they naively assume that plentiful
bandwidth and high speeds together mean that error detection and
recovery and, more importantly, resource management, won't ever be
necessary. I think the current difficulties the Arpanet is having
under heavy load are a consequence of a similar attitude in the early
Arpanet days. When peak utilizations are 20%, you don't have to try
very hard to control resource utilizations. So the only question is,
will the supply of phone trunking bandwidth keep enough ahead of
demand come FPS. Right now, I'd guess it will for at least long
enough for FPS to get accepted, due to rapid deployment of fiber and
deregulation. This depends on possible shakeouts in the IECs, I
suppose. This doesn't apply to the non-US world.
As for silicon doing IP or CLNS, I'd expect that this is entirely
within reason already. I would probably opt for a more powerful
header checksum, in fact, but this choice may already be moot. Too
bad that CRC is so easy in hardware and hard (compared to simple sum)
in software. Since only the header is checksummed, however, the check
can overlap reception of the user data and need not add any processing
delay at all.
I am not calibrated on what tcp-ip considers worth airing; please
redistribute this note if you find it interesting enough.
/jr
jr@bbn.com or jr@bbn.uucp
--------------------
End forwarded message
LAWS@rsre.mod.UK (John Laws, on UK.MOD.RSRE) (10/11/87)
Vint, I guess this reply should be to the John Robinson portion of your msg - but my mailer is not that smart. Concerning CRC checksum computation. More than 17 years ago I read a paper on this topic which used matrix algebra to construct look-up tables. You took your choice - one large table and a simple one line equation, or more smaller tables and more complicated equations. I could still remember enough maths then to follow the algebra through and did a single table version for the CRC-16 checksum. I used it in EIN and passed it around the European centres (there was no chips then for this and most folks were having to do it in one-off hardware of the day). My code implementation for a CTL Modular-One (a UK m/c with some interesting inovations that were to appear in DEC PDP 11) ran at 10 micro-secs per byte and only a little longer in Corai-66. My only export of this to the US was Ed Cain about 2/3 years ago. What does suprise me is the steady rain of papers on this topic which often propose less effective solutions (and also get the algorithm wrong) and never reference this old paper. Just a mo...... ....found it - P E Boudreau and R F Steen (IBM Corp, Research Triangle Park, N.C.) Cyclic Redundancy checking by program. AFIPS Conf Proc Vol.39 1971, pp 9-15 and the latest I just found this week and in my briefcase waiting to be read Georgia Griffiths and G Carlyle Stones The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32. Comms of the ACM July 1987 Vol.30 No.7 pp 617-620 typos: tbles = tables, Corai-66 = Coral-66 John