home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / dcom / cellrel / 492 < prev    next >
Encoding:
Text File  |  1992-09-04  |  3.2 KB  |  93 lines
  1. Newsgroups: comp.dcom.cell-relay
  2. Path: sparky!uunet!stanford.edu!ames!sgi!rigden.wpd.sgi.com!rpw3
  3. From: rpw3@rigden.wpd.sgi.com (Rob Warnock)
  4. Subject: Re: AAL5-CRC32
  5. Message-ID: <pee6ubc@sgi.sgi.com>
  6. Sender: rpw3@rigden.wpd.sgi.com
  7. Organization: Silicon Graphics, Inc.  Mountain View, CA
  8. Date: Fri, 4 Sep 1992 18:30:18 GMT
  9. Lines: 82
  10.  
  11. de@fokus.gmd.de (Dirk Elias) writes:
  12. +---------------
  13. | I've got some questions and comments concerning AAL5-CRC32 calculation.
  14. | 
  15. | 1. Does anybody know something of fast software algorithms to compute CRC32?
  16. | The fastest I know is based on look-up tables and will take 16 instructions
  17. | per 32 bit. This results in about 70 MIPS for a bitrate of 150 Mbps!
  18. +---------------
  19.  
  20. Well, the fastest byte-at-a-time method I know (with a 1024-byte table) is:
  21.  
  22.     for (i = 0; i < size; ++i)
  23.         crc = (crc >> 8) ^ table[ (crc & 0xff) ^ data[i] ];
  24.  
  25. That's about 9 cycles/byte (or more), or 36 cycles/word. I suppose you could
  26. cut that in half if you used a 256 KB table and did it 16 bits at a time.
  27.  
  28. +---------------
  29. | Definitely to slow. So, if there is no possible software solution, let's 
  30. | take a look on the hardware, exclusively for AAL5-CRC32. You will need a
  31. | CRC-chip and glue-logic, consuming "lots" of board space and wasting power
  32. | for almost nothing!
  33. +---------------
  34.  
  35. Why do you say "lots" of board space? A similar parallel algorithm can be
  36. done is a small gate array, in less space than the buffers to drive the
  37. host bus.
  38.  
  39. +---------------
  40. | ...there are two major ways to calculate CRC by hardware. One is "on-the-fly"
  41. | while receiving a cell from the ATM layer... I just want to point out that
  42. | "context-switching" after every cell is lots of work, just to calculate CRC.  
  43. +---------------
  44.  
  45. BUT YOU HAVE TO DO IT ANYWAY! You have to extract a *lot* more "context" per
  46. cell than just the previous CRC. You need the buffer pointers & counts (or
  47. limits), descriptor-ring pointer (for some architectures), etc. The 32 bits
  48. for the CRC is "just" another pair of "by 16" SRAMs, indexed the same way
  49. as all the rest.
  50.  
  51. +---------------
  52. | Has anybody knowledge of CRC hardware, performing "context-switching" on
  53. | it's own? (something with integrated memory and some kind of control
  54. | interface)
  55. +---------------
  56.  
  57. Again, you have to do it anyway. Tacking the CRC task on the side is a fairly
  58. small thing...
  59.  
  60. +---------------
  61. | the other is "fly-by" upon transmitting a reassembled packet from the AAL
  62. | layer to the next higher layer... If I would like to have about 100 VC's
  63. | using AAL5 and I had to store every packet till it's completed, I would
  64. | have to allocate 64 KBytes for every VC.
  65. +---------------
  66.  
  67. Memory's cheap.
  68.  
  69. +---------------
  70. | Since there is still no CPCS-PDU header defined for AAL5, where a packet-size
  71. | information could be transmitted, I have to assume the maximum CPCS-PDU size!
  72. +---------------
  73.  
  74. Not necessarily. You could allocate "chunks" of buffer as the cells arrive
  75. (a simple linked list).
  76.  
  77. +---------------
  78. | This would result in several MBytes of interface-board memory. (Sometimes
  79. | I remember that S-BUS card size in my nightmares)
  80. +---------------
  81.  
  82. It's small, but so is "several MBytes" of RAM.
  83.  
  84.  
  85. -Rob
  86.  
  87. -----
  88. Rob Warnock, MS-9U/510        rpw3@sgi.com
  89. Silicon Graphics, Inc.        (415)390-1673
  90. 2011 N. Shoreline Blvd.
  91. Mountain View, CA  94043
  92.  
  93.