Back To Lawrence Roberts Home Page

ATM Forum / 96-1104

_______________________________________________________________________

TITLE: Request for Coordination of Cells In Frames Specification

 _______________________________________________________________________

 SOURCE: Lawrence G. Roberts

ATM Systems Division, Connectware

989 E. Hillsdale Blvd. #290

Foster City, CA 94404

Phone: (415)358-1300

Fax: (415)358-0592

Email: lroberts@atmsys.com

 _______________________________________________________________________

 DISTRIBUTION: ATM Technical Group Members

Plenary

 _______________________________________________________________________ 

DATE: August 19, 1996 Baltimore

 _______________________________________________________________________

 ABSTRACT: The Cells In Frames Alliance requests the ATM Forum to examine the attached specification of the Cells In Frames (CIF) Protocol with respect to its interoperability with the ATM Forum’s latest specifications. If it is determined that the CIF specification will inter-operate correctly, then it is requested that the ATM Forum so notify the CIF Alliance.

_______________________________________________________________________

NOTICE: This document has been prepared to assist the ATM Forum. It is offered as a basis for discussion and is not binding on the contributing organization, or on any other member organizations. The material in this document is subject to change in form and content after further study. The contributing organization reserves the right to add, amend, or withdraw material contained herein.

 _______________________________________________________________________

Introduction

Cells in Frames (CIF) has been specified by the Cells In Frames Alliance in order to extend ATM protocol end-to-end to the desktop, even where it is uneconomic to install a new NIC card for the end-station on the desktop or even to open its case. All that is necessary with CIF is to downline load some additional software into the end-station and to connect it to a CIF Attachment device with ATM uplinks. The terminal will then operate functionally identically to an end-station connected directly to an ATM switch with an ATM NIC card. Running CIF, the end-station is in fact operating with ATM signaling and ATM ABR flow control over the legacy line protocol. ATM cells are packed into frames so as to permit the legacy protocol to operate as efficiently as it can. A CIF header before the cells includes the ATM cell header so that segmenting or reassembling ATM cells back and forth into CIF frames in the CIF Attachment device is rather simple. The benefit of using CIF for the final link to the desktop is that ATM can be extended far more economically to the desktop, a critical step if the benefit of ATM QOS and ABR flow control are to realized for the majority of users.

Motivation For CIF

Recent news stories have suggested that "ATM has Lost the Desktop". This story is based on the extremely low cost of switched Ethernet compared to ATM for the link to the desktop. Unfortunately, the story will turn out to be true unless far more economic access to the desktop is achieved for ATM. And, if the majority of the desktops connect with switched Ethernet, both the excellent and well defined QOS and ABR flow control of ATM will not be available end-to-end. Neither is useful unless it is end-to-end. Thus, unless RSVP is translated into ATM SIG 4.0 and TCP is depended upon instead of ABR flow control, there will be no need for ATM in the LAN backbone. But if TCP and RSVP are sufficient, then why translate at all? Under that assumption, switched Ethernet at 10 Mbps, 100 Mbps and 1Gbps would be quite sufficient for most LAN’s and might also be less expensive.

ATM at one time was the only way to achieve high speed switching due the advantage a fixed cell length had in building hardware switches. But today, this advantage has evaporated with the progress in ASIC’s and one can build a chip which switches Ethernet frames as easily as one to switch ATM cells. Thus, ATM cannot hold an advantage based on fast switching. Its only real advantage today is the Anchorage Accord protocol stack.

The truth is that the ATM Forum’s SIG 4.0, PNNI 1.0 and TM 4.0 are such a powerful and important protocol suite that the IP community will require many years to duplicate it. The IETF has been working on RSVP to substitute for SIG 4.0 but they have no work planned to upgrade TCP to achieve the capability of ABR explicit rate flow control and they also do not have any capability planned which will be as effective as PNNI 1.0. Both capabilities are critical to future network operation and without them the Internet probably will have serious troubles in the near future. The ATM Forum protocol suite is complete, well documented and will be deployed well within the next year. Thus, if the ATM protocol can be used to connect all the way to the end-station, even over legacy facilities if that is more economic, then the LAN and the Internet stability and functionality will be greatly enhanced and ATM’s role in the LAN backbone will be greatly increased. If we cannot find a way to reduce the cost of access using ATM protocol to the desktop to a level close to switched Ethernet very quickly, then ATM’s potential utility and usage will be seriously undermined. CIF is a very simple way to permit the use of ATM protocol to the desktop economically in the near future. As such, CIF will be of major benefit to the advancement of ATM in preserving the use of ATM in the LAN backbone, and then with time, the desktop as well, as users need to upgrade and ATM interfaces get less expensive.

The need for End-to-End Quality Of Service

QOS is necessary to achieve delay or bandwidth guarantee requirements. Voice and video are clear cases where QOS must be signaled if one wants any reasonable quality. Less understood is the need for QOS on data calls to obtain a guaranteed responce time. But in all these cases, the QOS must be signaled completely from end-to-end. Also, all network elements like routers, bridges, and switches must implement multiple queues for packets with weighted fair queuing. Thus, to achieve QOS in a network, all network components must be upgraded or replaced to incorporate QOS signaling and weighted fair queuing with multiple queues. If one segment of the path is not upgraded, QOS can be totally lost. Ethernet switches, being typically hardware switching systems, will need to be totally replaced to introduce QOS. CIF attachment devices (CIF-AD’s) are much the same as Ethernet switches which have already been upgraded to incorporate multiple queues and weighted fair queuing to support QOS. With these CIF-AD’s, just like ATM switches, voice and video can be supported with quality.

The need for End-to-End Explicit Rate Flow Control

The second major addition which is supported in ATM is Explicit Rate Flow Control. Flow control is used to control the traffic sources so that they do not send too much data into the network at any moment. If a trunk in the network is overloading, all the sources using that link must be told to slow down. This is absolutely necessary for a data network because the self-similar characteristics of data traffic are such that simply under-loading the network will not work. The critical difference between flow control techniques is the time it takes to tell the source about congestion and to get it under control. Today, LAN’s typically use TCP to control the data flow. TCP was created 15 years ago when networks were much slower. It operates a binary rate flow control between the two end-stations, slowing down the data flow if the return path indicates that data was lost. If data is not being lost, it speeds up the flow. Thus, it oscillates with a period of 1-2 seconds on the Internet, losing data each cycle and under-using the network on the other part of the cycle. Its characteristic time is about one second, that is the time it takes TCP to stop the data flow due to increased congestion.

TM 4.0 has now completely specified a new generation of flow control, explicit rate flow control, which operates from 100-1000 time faster than binary rate, in-band flow control protocols like TCP. Explicit rate flow control operates with RM cells being sent around the network to convey the flow control information back to the source. A higher priority path can be used for the RM cells so that they do not need to be delayed by the data. When a switch sees a RM cell it marks it with the highest data rate it can currently support for the associated source. This way, when congestion occurs, the switch can quickly mark RM cells with a new rate which will eliminate the congestion and these cells can move at the speed of light back to the sources telling them exactly how fast to send data. Thus, compared to today’s TCP the delay comparison is:

• Priority for RM cells over data. - Typically in Internet today a factor of 10
• Explicit rate rather than oscillation - Typically oscillation adds another factor of 5
• Switch to source distance vs round trip - Anywhere from a factor of 2 to 10

Thus, explicit rate can stop the source 100-500 times faster than TCP. This means that the buffer storage at the switch can be reduced by the same factor, 100-500. This is shown graphically in Figure 2.

Even though there tends to be statistical smoothing of the data transients at a switch for both techniques, the reduction of delay is directly reflected in reduced buffer size. This is critical because high speed hardware switches like ATM switches and 100 Mbps Ethernet switches cannot afford the same memory as the old software switches and routers had. A 100 Mbps router often has about 1 second of buffering at full input rate. A 10 Gbps ATM switch typically has about 20 ms of storage at full input rate and could not afford to increase it to 1 second since for the very fast SRAM memory needed in hardware switches, the cost would be unreasonably high. Thus, with memory of 50 times less a flow control delay gain of at least 50 is needed to make high speed hardware switches work. Explicit rate flow control has even more delay gain, which may help us fix the current brownouts and overloads in the Internet if it can be incorporated into the Internet.

As with QOS, explicit rate flow control is only useful if the RM cells flow end-to-end and all the congestion points arrange to mark the RM cells with the correct rate. If a current day router or bridge is in the path, the RM cells will be delayed behind data and no marking will be done. This will not have a major effect if the device is always significantly under-loaded, but if it ever becomes overloaded then TCP will need to be operated on top of the explicit rate flow control. Further, both end-stations must participate in the explicit rate flow control in order for it to work. If one or both do not support explicit rate, TCP will be required and much of the benefit of explicit rate will be lost.

If a VC has established explicit rate flow control from one end of the network to the other, end station to end station, then TCP can be controlled so as to only send data when a new block of data is needed. Updating TCP at the same time as the ATM signaling and CIF driver are downloaded is straightforward. Thus, TCP flow control would be used if ABR flow control was not available end-to-end, and would not be used otherwise, so as not to interfere with the explicit rate operation.

The need for QOS based Routing

One of the major problems today in the Internet is caused by the lack of bandwidth sensitive routing. TCP/IP has no current capability to route packets any way but the shortest operating route. The result of this is major outages during peak hours when one trunk is under provisioned. As peak hour approaches the trunk gets overloaded and slow. The router feeding it loses many packets and TCP slows all the users down and down. The retransmission load increases and increases. Soon no-one gets anything through. They try again, but the same route is selected. The paths routed over that trunk are inaccessible. With the fast growth of the Internet, this type of problem occurs frequently.

This problem would not exist with ATM because of PNNI 1.0. As soon as the data gets to the CIF-Attachment Device, it enjoys the benefits of ATM routing. This is another reason why using ATM protocol through CIF is far superior to hoping that TCP/IP will someday fix all its problems.

CIF Design

The CIF design is to operate software in the end-station which:

• Accepts the QOS request from Winsock2 and uses ATM signaling to request that QOS.
• Accepts data form either an ATM null stack, IP, IPX, etc
• Puts that data into multiples queues based on their QOS
• Assembles up to 31 cells of data into a packet along with the CIF header (See Figure 3)
• Sends the most time critical data first to the driver using weighted fair queuing
• Receives packets from the driver, removes the CIF header, and sends them on
• Controls TCP’s flow control activity based on if end-to-end ABR flow control is active

Figure 4 shows the components of software in a Windows end-station. The ATM signaling stack, the CIF Shim, and the modified TCP need to be downline loaded to the end-station. The end-station driver and the NIC card are not changed. The CIF Attachment Device in this case is an ATM-Ethernet Edge Switch with CIF capability. It must have multiple queues in hardware as well as RM cell marking for ABR flow control. The packet format is a standard Ethernet packet with an eight byte CIF header and then up to 31 ATM size (48 byte) cell bodies. The CIF header contains the ATM cell header (5 bytes) as well as 3 bytes of CIF control information.

CIF ABR Flow Control

CIF Attachment devices may act as VS/VD’s, reducing the number of RM cells flowing at the end-station by changing Nrm from 32 to something like 128 as shown if Figure 5. This insures that the interrupt and processing rate for RM cells in the end-station is about 3% of the packet rate, just as RM cells are 3% of the cell rate. The end-station Shim performs the RM cell processing and rate determination as specified in TM 4.0 for ABR source/destinations in software. Thus, the end-station is a proper ATM source/destination according to TM 4.0, but is all done in software.

CIF protocol can be used on both sides of an switch, in which case there is a need for the CIF switch to mark RM cells based on it’s congestion or available throughput.

With the reduced RM cell rate, the processing overhead for the end-station is only about 3% higher than in an end-station without CIF. However, depending on the design of the driver, there could be some extra overhead in keeping the queues short and going to the Shim for each new packet so as to optimize QOS.

The scheduler in the end-station Shim uses the data rates from the RM cells to set the flow rate for each queue in the same manner set forth in TM 4.0 for source/destination processes. It is also valuable to pass the VC rate on the application so that it can determine how much data to send to the user where guaranteed responce time is desired.

CIF Performance

For half duplex Ethernet, the majority of the installed base (130 million end-stations), the maximum delay variation incurred due the use of the Ethernet is 2.4 ms, 1.2 ms if one has to wait for a full packet going out and then, since the line is half duplex, another 1.2 ms if the other end has a full packet ready to send. For voice, the most time critical application currently being considered, an extra 2 ms is no problem even if it occurs at both ends since the delay tolerance for voice is about 20 ms when going to an analog phone with echo without echo cancelers, and 100 ms if both ends are full duplex, on the network. In neither case is a 5 ms delay variation for the full round trip a problem. In fact, operating system delay variation will far exceed the 2.4 ms from Ethernet for most operating systems. Therefore, the actual operating performance of CIF over Ethernet will be virtually identical to that experienced with a direct 25 Mbps ATM connection. The only difference will be the maximum throughput rate, 10 or 100 Mbps and 1 Gbps for Ethernet vs 25 , 155 Mbps and 622 Mbps for ATM NIC’s.

For Token Ring, it appears to be possible to achieve good QOS performance with a multiple (N) end-stations on a shared 16 Mbps ring and one CIF-AD. Token Ring has dual priority which can be utilized to reduce the delay variation for voice. The maximum delay variation would be (N+1)*.75 ms on the low priority but with packet size constraints on the high priority it would far less. Thus the cost per port for upgrading a Token Ring installation to CIF could be extremely low depending on the number of stations that prove to work effectively.

Conclusion

CIF provides a way to economically extend ATM protocol end-to-end, from end-station to end-station. There is a major cost saving because a new Network Interface Card is not required in the end-station nor does the end-station’s case need to be opened. CIF allows ATM to be extended over any frame based legacy protocol like Ethernet and Token Ring. Once a CIF capable switch is installed , the end-station only needs to download some software to obtain ATM quality QOS and explicit rate flow control. It should then be able to obtain quality voice and video over its current Ethernet or Token Ring NIC card.

By lowering the cost of connecting end-stations with ATM protocol to about the same cost as other non-ATM options like switched Ethernet, CIF makes it possible to make available to the mass market the full power of ATM; it’s QOS signaling, QOS routing, and Explicit Rate flow control, none of which are useful unless end-to-end. As a result, the availability of CIF should greatly expand the acceptance and installation of ATM.

Coordination Process

The CIF Alliance, in meetings with over 30 organizations working together, has completed the attached specification of CIF which defines the details for using ATM over Ethernet and Token Ring. The Alliance desires to work with the ATM Forum to insure that the CIF specification is fully inter-operable with the ATM Forum’s specifications. The working groups of the Forum which would be most impacted are the TM, Signaling, and ILMI groups. Of course if other groups feel they need to review the CIF specification, that would be fine. The Alliance wishes to follow the example of the WINSOCK 2 coordination and will quickly respond to questions. If any incompatibilities are found between CIF and ATM the Alliance will strive to quickly modify it’s specification to fix the incompatibility. When the Forum is satisfied that the CIF specification is inter-operable with the Forums specifications, then the Alliance would like to receive a notification of such.

Time is critical due to the high speed of the marketplace. It is critical for both CIF and ATM that this coordination be completed as rapidly as possible. Therefore, it is requested that the schedule for this coordination process be as fast as possible. As part of speeding the coordination process, please include the CIF Alliance on Email which it is appropriate that they be included by adding the following address on such Email :

Attachment - CIF Specification____________________________

1. Introduction

2. CIF Formats

3. CIF Layer Procedures

4. Signalling

5. Management

6. Acknowledgments

7. References

Appendix A: CIF Format Identifiers

Appendix B: Pseudocode for CRC Generation

Appendix C: Pseudocode for RM cell management

Appendix D: CIF MIB

Appendix E. Token Ring Implementation

Annex I: Discussion

Introduction

This document specifies the mechanisms by which ATM traffic is carried across a media segment and a network interface card conforming to the Ethernet Version 2 specification, IEEE 802.5 Token Ring, or IEEE 802.3. The mechanisms are collectively known as "Cells In Frames," or "CIF." ATM cells can be carried over many different physical media, from optical fiber to spread spectrum radio. ATM is not coupled to any particular physical layer. CIF defines a new pseudo-physical layer over which ATM traffic can be carried. It is not simply a mechanism for translation between frames and cells; neither is it simple encapsulation.

The concept of carrying cells in legacy LAN frames is not new [Armitage90, Armitage93, and Armitage94]. The methods proposed for CIF have some unique features that enhance performance and adaptability. The definition of a protocol between CIF end system software and a CIF attachment device ("CIF-AD") makes it possible to support ATM service, including multiple classes of service, over an existing LAN NIC, just as if an ATM NIC were in use. This document specifies how the ATM layer protocols can be made to work over the existing LAN framing protocols in such a way that operation is transparent to an application written to an ATM compliant API. Unless specifically stated otherwise, all aspects of this specification apply equally to any LAN type.

The addition of the CIF functionality to an existing LAN-attached workstation extends the functionality of the LAN to include the ATM capabilities for priority scheduling, leaky bucket traffic shaping, and end-to-end protocol independent flow control when using the Available Bit Rate (ABR) services.

An ATM end system possesses an ATM Signalling module, an ILMI module, and the ability to process multiple AAL types. Together these are the "ATM processing layer." In order to provide a generic solution that works with the existing LAN driver on the CIF end systems, a "shim" bridges between the ATM processing layer and the existing LAN drivers. Legacy applications have access to the AAL layers via a LAN Emulation module [LANE], MPOA [MPOA], or classical IP over ATM [RFC1483, RFC1577, RFC1755], just as with other end system ATM implementations.

The CIF-AD receives groups of cells from the end system and forwards them to an ATM backbone switching fabric. The CIF-AD might be implemented as a multiplexor or, more likely, an ATM switch. To be compliant with CIF functionality, the CIF-AD may but is not required to implement LANE, MPOA, or Classic IP. Figure 1 shows a single end system attached to point-to-point 10BASE-T or other LAN wiring. This is expected to be a common configuration.

Note: Not all possible shared LAN configurations involving multiple CIF-ADs have been considered in this specification and some may not function correctly. The case of multiple CIF-ADs on a single shared LAN segment has been considered and is supported by this specification.

Note: A CIF-AD implementation may optionally support both CIF and non-CIF frames from a CIF end system. Alternatively, this traffic may be handled with existing LAN equipment on the same shared segment if desired.

One of the goals of the mechanisms described in this specification is to ensure that the CIF end system is not unduly burdened by ATM processing requirements. Thus CIF offers options to move some of the ATM processing from the CIF end system to the attachment device. There are three ATM functions that may impair performance if implemented in software in a CIF end system: ABR traffic management (especially RM cell management), AAL5 CRC calculation, and the actual generation of cells by the ATM layer.

CIF functionality includes: specification of the framing for carrying cell payloads on the LAN; the generation and interpretation of the frames and action to be taken based on the contents of the frames; control; and management. The following sections of this document are purely specification, and are intended as a guide to implementation. Additional useful information, considered informative (i.e., not a mandatory part of the specification), is included as appendices. Informative discussion and analysis then follows in Annex I.

CIF Formats

General

On an Ethernet, CIF frames shall have a standard Ethernet Version 2 header and trailer. CIF devices may be configured to support 802.3 as well, but there is no mechanism defined in CIF for negotiating framing. If the CIF-AD and CIF end systems support it, it may be configured manually.

CIF Ethernet frame headers shall use an Ethernet type value of hexadecimal 8821 (decimal 34829).

CIF frames shall be encapsulated in 802.5 Token Ring and 802.3 (LLC class-1) by the use of a SNAP header. This is identified in the 802.2 protocol by the prefix of X'AAAA03' followed by a five byte SNAP header. The value of the SNAP header shall be X'0000008821' . See Appendix E for other requirements specific to Token Ring.

The first 8 octets of the frame payload shall contain the CIF header. The CIF header carries the information that is passed as parameters from the AAL layer to the ATM layer as well as CIF-specific information. The first bit of each of the first three octets (bits 0, 8, and 16, labeled "p") are even parity bits for the octets of which they are a part. For example, for CIF format type 0, octet 0 is binary "00000000". For CIF format type 1, octet 0 is binary "10000001". For CIF format type 2, octet 0 is binary "10000010".

p: Even parity bit for octet

CIF fmt: CIF format identifier

ff: CIF format independent flags

fmt flags: CIF format-dependent flags (2 fields)

GFC: Generic Flow Control

VPI: Virtual Path Identifier

VCI: Virtual Channel Identifier

PT: Payload Type

C: Cell Loss Priority

HEC: Header Error Check

CIF Format Identifier

In the CIF header, bits 1-7 of octet 0 are used as the CIF frame format identifier. The defined CIF frame formats are discussed in the following sections.

The CIF Format Identifier Authority assigns CIF format identifiers. See Appendix A.

Only three format types are defined. Formats 0 and 1 are used for CIF Signalling. Format 2 is the default format for carrying user traffic.

Formats 112-127 are designated for use in experimentation and for pre-standard CIF implementations. Every CIF implementation must support format types 0, 1 and 2.

CIF Format Independent Flags

Bits 9-10 (ff) in octet 2 contain flags that are independent of any CIF format type. The uses of bits 11-15 in octet 1, and bits 17-23 in octet 2, depend on the CIF format type (octet 0).

The CIF format-independent flags are reserved. They shall be set to 0 when sent and shall be ignored when received

Cell Header Template

The structure and semantics of octets 3-7 in the CIF header are the same as those of an ATM UNI cell header. These octets are collectively known as the "CIF cell header template."

The sender of a LAN frame shall always calculate and fill in the HEC field. The receiver may either rely on the LAN CRC to detect errors in the frame, and not validate the received HECs, or it may check the correctness of the HEC. The procedure to be followed on detecting an incorrect HEC is outside the scope of this specification.

CIF Format Dependent Flags

The format-dependent flags differ depending on the CIF format type, and are described under each format.

The content of the rest of a CIF LAN frame, after the CIF header, depends on the CIF format type, and is discussed under the individual format types.

Format Types 0 and 1

Formats 0 (binary 00000000) and 1 (binary 10000001) are used by CIF end systems and access devices for CIF-layer to peer CIF-layer communications. Format 0 is used for messages from the CIF end system to the CIF-AD. Format 1 is used for messages from the CIF-AD to the CIF end system. Formats 0 and 1 are the same except for the format type field, which is different to allow for flexibility and easier protocol analysis.

For format 0 the CIF header is as follows:

Format 1 differs from format 0 only in the first octet, which shall be binary "10000001".

In formats 0 and 1, bit 23 is a format-dependent flag, the "link activated" flag, which is used to declare whether the sender of the format 0 or 1 frame believes the link to be active or not (see CIF Activation Procedures for details). The CIF cell header template fields are unused and reserved.

Following the CIF header, a format 0 or 1 frame shall carry a 128-bit mask indicating the CIF format types the sender is willing to send and wishes to receive, with format type 0 represented by the most significant bit and format type 127 represented by the least significant. Every CIF implementation shall support at least format types 0, 1, and 2, and the corresponding bits of the mask shall always be 1. The receiver of this format 0 or 1 frame shall use only the intersection of the format types listed in this message and the format types that its peer has indicated its willingness to support.

Following the format types bitmask, 16 bits are used for options that can be represented as bit flags. The following flags are defined in this version of CIF. All other bits are reserved and shall be sent as 0 and ignored upon receipt.

C: Proxy AAL5 CRC generation and validation

M: Multiple CIF headers in CIF frame

Following the bit flags are one or more variable-length elements in {type, length, value} triplets. First is the total length of all of the variable-length elements, and then the elements themselves. If there are no TLV elements the total TLV length shall be 0.

The format for each element shall be:

0 1 2

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

|C|0| Type | Length | [Value...]

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

C (bit 0)

0 (bit 1)

Type

Length

Value

Variable length elements may be included in any order. Any particular element (except for the vendor-private element) may occur only once in a frame. The vendor-private element may occur multiple times in a frame in order to allow for vendor-private elements that do not share the same vendor ID to be present.

If the total length of the CIF payload, including the CIF header and the format 0 or 1 payload, is less than 56 octets, it shall be padded with 0s to a minimum total length of 56 octets (CIF header plus 48 octets, or 74 octets including the Ethernet header and trailer).

The variable length elements are as follows:

Element 0: List termination. Compulsory.

Element 1: Desired Nrm value for Available Bit Rate Service. Non-compulsory.

Element 63: Vendor-private. Non-compulsory.

Format Type 2

In CIF format 2 (binary 10000010), the LAN frame payload shall consist of one or more groups, comprising a CIF header followed by one or more 48-octet cell payloads (SAR-PDUs, ATM-SDUs), placed contiguously in the frame, without cell headers. Multiple groups are allowed only if both ends of a CIF link indicate willingness to support multiple groups by setting the M flag in the format 0 or 1 header.

ATM cell payloads are packed in CIF frames along with CIF headers which contain parameters that describe the cell payloads' ATM headers. In CIF frames sent from the CIF end system to the CIF-AD, the CIF header is used to specify parameters for cell headers that shall be constructed for those cell payloads by the CIF-AD. In frames sent from the CIF-AD to the CIF end system, the parameters describe the contents of the cell headers that were received from the ATM network with the payloads. In addition, CIF format type 2 offers options that permit functions to be provided by the CIF-AD to assist the CIF end system.

Within each of these groups of CIF header plus cell payloads, all of the cell payloads shall be destined to the same VC. Cell payloads shall be complete (e.g. the AAL1 SAR-PDU header octet shall be calculated and inserted). A frame shall contain no partial cell payloads.

The minimum CIF Format 2 LAN frame, carrying one cell payload, shall consist of 14 octets of Ethernet header, 8 octets of a single CIF header, 48 octets of cell payload, and 4 octets of Ethernet trailer, for a total of 74 octets. The maximum single header CIF format 2 frame carries 31 cell payloads or 1488 octets. CIF frames with multiple headers shall not exceed 1496 octets. If each cell had an associated header the frame would consist of 26 cells and headers with a total length of 1456.

r: Reserved, must be 0

p: octet parity bits (even parity)

CCCCC: Cell payload count for this CIF header (0

indicates that the header applies to the

remainder of the CIF frame.)

T: Payload type toggle indication

V: AAL5 CRC validity indication

SSSS: PDU Sequence Number

GFC: Generalized Flow Control

VPI: Virtual Path Identifier

VCI: Virtual Channel Identifier

PTI: Payload Type Indicator

C: Cell Loss Priority

HEC: Header Error Check

CCCCC (count field)

T (payload type toggle flag)

V (AAL5 CRC flag)

SSSS (PDU sequence number)

Format Types 112-127

Format types 112 through 127 inclusive are reserved for experimentation and for pre-standard implementations of ATM over LANs.

CIF Layer Procedures

CIF Activation Procedures

When either the CIF end system or the CIF-AD is starting up, it does not require knowledge of the other system's MAC address. Until it gains this knowledge, the CIF link to the other system is considered down.

The CIF end system shall initialize the CIF link by sending a CIF format 0 frame (described above) with the Link Activated flag set to zero. It shall send this frame to a MAC-layer multicast address that is assigned specifically for this purpose. Its value is xxxxxxxxxx (to be assigned).

A CIF-AD shall not send any CIF format 1 frames if it considers the link to be down. The CIF-AD only sends CIF format 1 frames when it considers the CIF link to be in the up state. A CIF-AD waits to receive a CIF format 0 frame, either multicast or unicast, from a CIF end system. When it receives one, it learns that CIF end system's individual MAC address, as well as the CIF options the CIF end system requests and is willing to support. The CIF-AD declares the CIF link to that end station to be in an up state, and sends CIF format 1 frames to this CIF end system, using the CIF end system individual MAC address as the destination address.

CIF end systems receive only unicast frames. CIF-ADs receive either multicast or unicast frames, but send only unicast frames to CIF end systems from which they have received frames.

Upon receipt of a CIF format 1 frame, the CIF end system learns the MAC address of the CIF-AD, as well as what CIF options the CIF-AD requests and is willing to support. From that time on it sends only point-to-point unicast frames destined to the CIF-AD's individual MAC address. It also places the CIF link into the up state and sets the Link Activated flag to 1 in its next Format 0 frame.

Bringing a link up is thus a three step process. First the end system searches for a CIF-AD to communicate with. Then the CIF-AD responds that it is willing to do so. Finally, the end system confirms that it will be accepting the CIF-AD's services, and in the process the link is declared up by both parties.

When there are multiple CIF-ADs on the same LAN segment, an end system may receive CIF format 1 frames from more than one CIF-AD. The CIF end system shall choose a CIF-AD from among the those that respond to its multicasts. After the choice is made, following the above rule, the CIF end system shall send CIF frames, of any type, only to that CIF-AD. Messages from that CIF-AD shall be accepted, but messages from any other MAC address shall be ignored. Subsequently, if the CIF end system declares the link to the CIF-AD down again, it again sends CIF format 0 frames to the multicast address, accepts messages from any CIF-AD, and chooses one to which to send further CIF frames.

When there are multiple CIF end systems on the same LAN segment, a CIF-AD may receive messages from more than one CIF end system. If the CIF-AD supports multiple CIF end systems on a segment (optional), it shall respond to each as it if had a point-to-point connection to it, i.e. with unicast point-to-point frames. If it does not support multiple CIF end systems it is an implementation option as to how it should respond.

A CIF end system may receive a CIF frame from the CIF-AD when it has declared a CIF connection down but before it can send a multicast frame, or a CIF-AD may receive a unicast frame whose contents are not appropriate for the state of the connection. In that case it may assume connectivity is established, place the CIF link in the up state and save the message's source MAC address.

CIF Link Maintenance Procedures

CIF provides pseudo-physical connectivity detection and maintenance between the CIF end system and the CIF-AD, using CIF format 0 and 1 frames. A CIF end system or CIF-AD shall send a format 0 or format 1 frame every 5 seconds in the up state. When in the down state, a CIF end system shall send a format 0 frame every 1second.

If either the CIF end system or the CIF-AD does not receive a CIF frame from a peer in 15 seconds then it shall place the link into the down state.

Format 2 Frame Generation and Processing

In CIF format 2 frames, the cell header template portion of the CIF header is used to generate or infer cell headers for the cell payloads associated with that CIF header. All fields in the ATM cell header portion of the CIF header are used as defined in the ITU specification for the ATM cell header [ATM] with the following exceptions.

If the format 2 Payload Type Toggle Indication flag is set in the CIF header:

• When the CIF end system receives a CIF header from the CIF-AD in which the CIF format 2 T (Payload Type Toggle Indication) flag is 1, the CIF end system shall consider the cell payloads associated with that CIF header to all have an associated payload type that is the same as the payload type in the CIF header PTI field, except that the payload type for the last cell payload associated with the CIF header shall be considered to be the inverted value of the ATM-user-to-ATM-user indication bit.
• When the CIF-AD receives a CIF header in which the format 2 T flag is 1, the CIF-AD shall set the payload type for all cells generated from the cell payloads associated with that CIF header to be the same as the payload type in the CIF header PT field, except the last one, where it shall be set to the opposite of the value of the ATM-user-to-ATM user indication in the CIF header PT field.
• When the CIF-AD is generating a CIF frame from cells received on another interface, and adds a cell payload to it from a cell whose payload type indicated a different ATM-user-to-ATM user indication than that of the first cell payload, it shall set the CIF format 2 Payload type toggle indication flag in the frame's CIF header to be 1 and add no more cell payloads to the group associated with that CIF header.

These rules are true for all AALs. Only the last cell payload in a group associated with a CIF header can be for a cell where the payload type differs from that of the first cell. The ATM payload type field PTI is defined for all AAL types in ITU Recommendation I.361 as follows:

AAL5

General

In VCs using AAL5 the cell payloads associated with a particular CIF header shall all belong to the same CPCS-PDU, and the last cell payload of the CPCS-PDU may be included in the same group as cell payloads that are not the last by using the format 2 Payload Type Toggle Indication flag.

For traffic from the CIF end system to the network, processing of the AAL-SDU starts in the CIF end system and is completed at the CIF-AD where the ATM cells are created. On the send side the AAL-SDU is the basic unit. CPCS processing is performed, adding any header or trailer, and the resulting CPCS-PDU is broken up into 48 byte payloads at the SAR layer. A CIF header and then a LAN header are prepended to up to 31 of the 48 byte SAR-PDUs (the most that fit in a single Ethernet frame), and a LAN trailer is appended to the end of the set. (Multiple groups of CIF header and SAR-PDUs may be included in a LAN frame.) The resulting frame is then sent to the CIF-AD. This process is repeated as necessary until the entire CPCS-PDU has been transmitted. In the CIF-AD the LAN header and trailer for each LAN frame are discarded and the CIF header is used to construct an ATM Cell header for each of the ATM cell payloads within a group.

For traffic from the network to the CIF end system, the CIF-AD places one or more cell payloads in a frame with an appropriate CIF header. The CIF-AD stops filling a particular frame whenever:

the number of cell payloads placed in the frame reaches a maximum for that VC (31 or less). A CIF-AD may choose a value less than 31 to improve latency; however, this must be traded against increased processing load placed on the CIF end system through forwarding a larger number of smaller CIF frames.

the cell payload from a cell is placed in the frame where the new cell's payload type differs from the payload type of the first cell placed in the group of cell payloads and CIF header.

Traffic from CIF end system to CIF-AD

The CIF end system shall provide a complete CPCS-PDU to the CIF-AD in one or more CIF frames. The CIF end system shall add the appropriate amount of padding and an AAL5 trailer to create a complete CPCS-PDU. The trailer length field and UUI shall be filled in correctly.

The CIF end system shall segment an AAL5 CPCS-PDU into groups containing 1 to 31 cell payloads. Each group shall begin with a CIF header. The PDU sequence number field in the CIF header shall be filled in for frames that contain appropriate PDUs. In CIF format type 2, frames may contain cells from more than one CPCS-PDU if this capability has been agreed to at CIF activation. If the frame contains more than one cell from a PDU, and includes the last cell of the PDU, then the payload type in the CIF header shall be set to indicate ATM-user-to-ATM user indication 0 and the format 2 Payload type toggle indication flag in the CIF header shall be set to 1.

Figure 2: An example of an AAL5-SDU in multiple LAN frames

The format 0 and 1 Proxy AAL5 CRC generation and validation flag works with the format 2 AAL5 CRC validity indication flag to determine how AAL5 CPCS-PDU CRCs are managed. The exchange of the Proxy AAL5 flag with format 0 and 1 frames determines which system is responsible for AAL5 CRCs. If the CIF end system is responsible for AAL5 CRCs, the CIF-AD gives AAL5 CRCs no special treatment and the format 2 AAL5 CRC validity indication flag is never used. If the CIF-AD has assumed responsibility for AAL5 CRCs, then the following are true:

The format 2 AAL5 CRC validity indication flag may be set by the end system in a CIF header that is associated with the cell payload containing the end of an AAL5 CPCS-PDU and thus the CRC-32 field. The format 2 AAL5 CRC validity indication flag is used whenever the CIF end system does not provide a valid CRC-32 field and the CIF-AD is to calculate it on its behalf.

Upon receipt of the last cell payload of an AAL5 CPCS-PDU (the Payload type toggle indication being 1), the CIF-AD shall:

• fill in the AAL5 CRC field before sending the last cell of the PDU into the network.
• check the PDU sequence number and the AAL5 length field. If either of these tests fail, the CIF-AD shall modify the last cell of the PDU to indicate an abort by modifying the AAL5 length and CRC fields to be zero.

Traffic from CIF-AD to CIF end system

Similarly, if the CIF-AD has not taken responsibility for AAL5 CRC management, neither the CIF-AD nor the CIF end system give AAL5 cells special handling with regard to CRCs. However, if the CIF-AD has taken responsibility, the following shall be done:

In each CIF frame being sent to the CIF end system for an AAL5 CPCS-PDU the CIF-AD shall set the PDU sequence number as described in section 3.3.1.4

The CIF-AD shall validate the CRC for an AAL5 CPCS-PDU arriving from the network. In the CIF header associated with the last cell payload of an AAL5 CPCS-PDU being sent from the CIF-AD to the CIF end system (the cell payload that contains the CRC), the CIF-AD shall set the format 2 AAL5 CRC validity indication flag to 1 to indicate that the AAL5 CRC field does not contain an actual CRC but rather an indication of validity.

If a valid CRC was received from the network, the CIF-AD shall set the AAL5 CRC field to all 1s. If the CRC validation failed, it shall set both the AAL5 length field and the AAL5 CRC field to all 0s to indicate an AAL5 abort.

After the CIF end system has received the entire AAL5 CPCS-PDU, it shall check: the PDU sequence number in the last received CIF header s described in section 3.3.1.4, the CRC validity, and the AAL5 length field. The length must be a value greater than or equal to the actual received length minus 40, and less than or equal to the received length minus 8 (because of variable AAL5 padding to fill out the final cell). If the PDU fails any of the 3 tests, it shall be delivered to the client layer as if it had been received in error.

The PDU Sequence Number

The PDU sequence number field in the CIF Format 2 header is an unsigned 4-bit integer that is used for error detection. Senders (both CIF end system and CIF-AD) shall insert a valid PDU sequence number specific to each virtual channel for which they are relevant. As discussed in Section 2.3, the PDU sequence number shall be used in CIF headers applying to user data cells and AALs where an AAL CPCS PDU can be span more than one CIF LAN frame.

When a virtual channel becomes active, the first CPCS-PDU sent on that VC by each source shall set the sequence number field in the CIF header of the PDU to 1, and shall hold the sequence number at 1 through the last CIF header associated with cell payloads for that PDU. The PDU sequence number is incremented by 1 for the first CIF header of the next PDU and (again) remains the same for all CIF headers associated with cell payloads containing that PDU. Sequence number 15 is followed directly by sequence number 0. PDU sequence numbers are independent for the two different directions of traffic flow between the CIF end system and the CIF-AD.

The receiver of frames for an AAL5 VC must at least check the PDU sequence number on the last CIF header of every AAL5 CPCS-PDU it receives. It should check the PDU sequence number on every frame, in order to avoid dropping some frames unnecessarily (discussed in Annex I.5).

The CIF end system shall check PDU sequence numbers in every appropriate CIF header. If the CIF end system receives a CIF header whose PDU sequence number does not directly follow that of the previous CIF header received for that VC, and if the previous CIF header was not associated with a cell payload containing the end of an AAL5 CPCS-PDU, the PDU previously being accumulated is treated as if it were aborted and the current CIF header and associated cell payload are considered the start of a new PDU. This procedure avoids unnecessary discarding of PDUs. See Annex I.5 for more discussion.

For traffic from the CIF end system to the CIF-AD, the CIF-AD behavior is the same with one exception. As above, if the CIF-AD receives a CIF header whose PDU-sequence number does not match that of the previous CIF header but the previous CIF header's cell payloads did not contain the end of a PDU, the PDU received so far shall be treated as aborted. However, since the CIF-AD is forwarding cells to the network, in this case it shall generate a new cell, on its own, containing the end of an AAL5 PDU, with length and CRC fields set appropriately for an AAL5 abort.

Other AALs in CIF Format 2

While AAL0, AAL1, and AAL5 are the only AALs that have been considered in this specification, there are no known restrictions in CIF that would cause other new AALs not to work.

AAL1 is only expected to be used in the "simplified" form for voice interworking [I.363.1].

Available Bit Rate Support

Based on the capabilities of the CIF-AD and the Nrm value exchanged in the format 0 and 1 frames, the CIF-AD may provide VS/VD support for ABR, i.e., the CIF-AD must include a non-zero Nrm TLV element in its format 1 frames.

For all VCs using ABR traffic management, the CIF-AD optionally may act as an ABR virtual source and virtual destination (VS/VD), sending and receiving RM cells on behalf of the CIF end system, in which case it shall communicate with the CIF end system as described here. If the CIF-AD does not support VS/VD behavior then it shall pass RM cells either transparently or, optionally, set the congestion indication, no increase bits, or explicit rate fields in the RM cells flowing through it.

If the CIF-AD supports VS/VD behavior, it shall maintain a value for its available cell rate (ACR) in conformance with the ABR specification, and shall indicate to the CIF end system the rate at which the CIF end system may generate cells by creating a response RM cell and encoding its current ACR rate into the explicit rate field of that RM cell. The CIF-AD may optionally set the congestion indication and no increase bits in this cell and may restrict the explicit rate further if it is currently congested.

An RM cell shall be generated by the CIF-AD to the CIF end system whenever either the ACR on an ABR VC changes significantly from the last time the ACR was sent, or periodically at a rate consistent with the Nrm value indicated in the CIF-AD format 1 frames.

The CIF end system shall act as a compliant source/destination as defined by the ATM Forum’s TM 4.0 specification. The Pseudocode for this is included in Appendix C. It shall send forward RM cells at a rate consistent with the Nrm value indicated by the CIF-AD format 1 frames and shall turn around all forward RM cells received and send out backward RM cells.

Signalling

It is intended that ATM Signalling functionality be fully supported without change. The specific version(s) of Signalling supported, at the CIF end system or in the CIF-AD, is vendor-dependent.

The CIF link connecting the end system with the attachment device may be considered an ATM user-network interface (UNI). As with other UNI implementations, it is necessary to define one end of the UNI as the "user" side of the link and one end as the "network" side of the link. While CIF does not require any specific mapping to function, it is recommended that, by default, the end of the link at the attachment device be defined as network-side and the end of the link at the end system be defined as user-side.

In configurations where multiple CIF end systems share a single LAN segment to access an attachment device, each association between an end system and an attachment device may be considered a separate UNI.

Management

ILMI support

It is intended that all ATM ILMI functionality be fully supported without changes. The specific version(s) of ILMI supported, in the CIF end system or in the CIF-AD, is vendor-specific.

The CIF MIB is contained in Appendix D. All implementations shall this MIB.

OAM Support

It is intended that OAM be supported as per any other ATM interface. Specifically, this means that OAM cells (payload types 4 and 5) are supported across the LAN via the standard CIF framing, and may be sent to the network by the CIF end system and/or received by the CIF end system from the network. The actual level of OAM support, at the CIF end system or in the CIF-AD, is vendor-specific.

CRC-10 generation for both OAM and RM cells shall be performed by both CIF-AD and CIF end system. The CIF end system shall ignore CRC-10 fields on receipt. The CIF-AD shall validate the field on all RM and OAM cells and discard without forwarding any cells in error.

Acknowledgments

Editing was done by Scott Brim (Cornell University). Comments can be addressed to him at <swb1@cornell.edu> Major individual contributions to this specification were made by: Robert Amy, Andrew Chittenden, Richard Cogger, Roy Dixon, Kingston Duffie, Jim Grace, Greg Hill, Sanjay Kumar, Vernon Little, Drew Perkins, Larry Roberts, Raphael Rom, David Singer, Michael Sobieski, and John Yang.

In addition, the following organizations contributed to this specification's development: 3COM Corporation; 3M Corporation; AMD; Allied Telesyn; Apple Computer Inc.; ATM Inc.; Bell Atlantic; Bellcore; Cirrus; Com21 Inc.; Connectware ATM Systems Division; Digi International; First Virtual Corporation; Fore Systems; Fujitsu Microelectronics; Future Communications Software; IBM Corporation; Integrated Device Technology; Lynx; MMC; Madge; Microsoft; National Science Foundation; Northern Telecom; Novell; Olicom; PMC-Sierra; Siemens; Stratacom, Inc.; Sumitomo Electric USA; Sun Microsystems; Texas Instruments; University of California, Davis; Whitetree; Zeitnet.

References

[AAL5] ITU-T. "AAL Type 5, Draft Recommendation text for section 6 of I.363." TD-XVIII/10. 29 January 1993.

[AAL5-CP] T1S1. "Proposed Procedures, Detailed Service Interface, and Layer Management Interface Description for AAL-5 Common Part." 92-285. May 1992.

[Armitage90] Armitage, G.J., and K.M. Adams. "Architecture of a Multimedia Desktop Workstation." Proc. Australian Video Communications Workshop, Melbourne, pp. 76-85. July 1990.

[Armitage93] Armitage, G.J., and K.M. Adams. "Using the Common LAN to Introduce ATM Connectivity." Proc. IEEE Computer Society 18th Conference on Local Computer Networks, Minneapolis, MN. September 19-22, 1993. See also ftp://ftp.bell core.com/pub/gja/mu/gja.18th.LCN.slides.ps.Z.

[Armitage94] Armitage, G.J. "The Application of Asynchronous Transfer Mode to Multimedia and Local Area Networks." PhD Thesis, Department of Electrical and Electronic Engineering, University of Melbourne, Australia. January 1994.

[ATM] ITU-T. ATM Layer Specification. I.361. 1993.

[Cogger94] Cogger, Richard. "IEEE802.1 Looking for Guidance - Cells in Frames." Rem-Conf Internet mailing list (rem-conf@isi.edu). 21 July 1994.

[Ethernet2] Digital Equipment Corporation, Intel Corporation, and Xerox Corporation. "The Ethernet - A Local Area Network: Data Link Layer and Physical Layer Specifications, Version 2.0." November 1982.

[I.361] ITU-T., SG13. "B-ISDN ATM layer specification." I.361.

[I.363.1] ITU-T., SG 13. "B-ISDN ATM Adaptation Layer (AAL) Specification, Types 1 and 2." I.363.1. 10-21 July 1995.

[ILMI4.0] The ATM Forum Technical Committee af-ilmi-0065.000. "ATM Forum Interim Local Management Interface (ILMI) Specification 4.0."

[LANE] The ATM Forum Technical Committee. "LAN Emulation over ATM, Version 1.0." January, 1995.

[MPOA] The ATM Forum Technical Committee. "Baseline Text for MPOA." 95-0824.

[RFC1483] Heinanen, Juha. "Multiprotocol Encapsulation over ATM Adaptation Layer 5." RFC 1483. July, 1993.

[RFC1577] Laubach, Mark. "Classical IP and ARP over ATM." RFC 1577. January, 1994.

[RFC1755] Perez, M., Liaw, F., Mankin, A., Hoffman, E., Grossman, D., Malis, A. "ATM Signalling Support for IP over ATM." RFC1755. February 1995.

[Partridge95] Partridge, Craig, and Hughes, Jim. "Performance of Checksums and CRCs over Real Data", ACM CCR 25:4, pp. 68-76. October, 1995.

[SIG4.0] The ATM Forum Technical Committee af-sig-0061.000. "ATM Forum User-Network Interface (UNI) Signalling Specification Version 4.0."

[TM4.0] The ATM Forum Technical Committee af-tm-0056.000. "ATM Forum Traffic Management Specification Version 4.0."

[UNI3.1] The ATM Forum Technical Committee. "User-Network Interface (UNI) Specification, Version 3.1." September, 1994. Available by FTP from ftp.atmforum.com.

[8802-5] ISO/IEC 8802-5 ANSI/IEEE Std 802.5 Second Edition 1995-12-29 Information technology - Telecommunications and information exchange between systems -- Local and metropolitan area networks -- Specific requirements Part 5: Token ring access method and physical layer

Appendix A: CIF Format Identifiers

Requests for CIF format identifiers should be e-mailed to cif-format-request@cif.cornell.edu.

Appendix B: Pseudocode for CRC Generation

There are a number of references to the generation of CRCs available at the Cell Relay site.

All the code fragments and examples that appear in this appendix are provided with the kind permission of Charles Micheal Heard and Angie Tso.

B.1 HEC generation

As the ATM cell header does not change from one frame to the next for a given VC, the HEC only needs to be calculated and saved when a given VC is set up. This value is then inserted into the ATM Cell header on every frame sent for a given VC. On receipt of a CIF frame, the HEC requires checking only if the receiver does "cut-through" as, in this case, the receiver doesn't know whether the media CRC is correct at the time the HEC is received.

There is an excellent tutorial on the theory of the HEC checksum available on the Cell Relay site. The following code, that also appears on that page, can be used to generate the HEC efficiently.

/********************************************************************/

#define HEC_GENERATOR 0x107 /* x^8 + x^2 + x + 1 */

#define COSET_LEADER 0x055 /* x^6 + x^4 + x^2 + 1 */

static unsigned char syndrome_table[256];

void gen_syndrome_table()

/* generate a table of CRC-8 syndromes for all possible input bytes */

{

register int i, j, syndrome;

for ( i = 0; i < 256; i++ )

{

syndrome = i;

for ( j = 0; j < 8; j++ )

{

if ( syndrome & 0x80 )

syndrome = ( syndrome << 1 ) ^ HEC_GENERATOR;

else

syndrome = ( syndrome << 1 );

}

syndrome_table[i] = (unsigned char) syndrome;

}

return;

}

void insert_hec(cell_header)

unsigned char cell_header[5];

/* calculate CRC-8 remainder over first four bytes of cell header */

/* exclusive-or with coset leader & insert into fifth header byte */

{

register unsigned char hec_accum = 0;

register int i;

for ( i = 0; i < 4; i++ )

hec_accum = syndrome_table [ hec_accum ^ cell_header[i] ];

cell_header [4] = hec_accum ^ COSET_LEADER;

return;

}

#define NO_ERROR_DETECTED -128

#define UNCORRECTIBLE_ERROR 128

static int err_posn_table[256];

void gen_err_posn_table()

/* Generate the error position table as a function of the syndrome. */

/* A negative value indicates that there is no error to correct. */

/* A value of 40 or greater indicates that an uncorrectible error */

/* has occurred, i.e., that the syndrome either indicates a double */

/* error pattern or points to a single-bit error position that is */

/* outside the header. Finally, a value between 0 and 39 indicates */

/* that a single-bit error occurred in that position (bit 0 being */

/* the header bit which was transmitted first). */

{

register unsigned char hec_accum;

register int i, j, k;

/* mark the NO_ERROR_DETECTED position */

err_posn_table[0] = NO_ERROR_DETECTED;

/* default remaining positions to UNCORRECTIBLE */

for ( i = 1; i < 256; i++ )

err_posn_table[i] = UNCORRECTIBLE_ERROR;

/* override w/err posn for syndromes indicating other single-bit errors */

for ( i = 0; i < 5; i++ )

{

for ( j = 0; j < 8; j++ )

{

if ( i < 4)

{

hec_accum = 0;

for ( k = 0; k < 4; k++ )

if ( k == i)

hec_accum = syndrome_table [ hec_accum ^ (0x80 >> j) ];

else

hec_accum = syndrome_table [ hec_accum ];

}

else

{

hec_accum = (0x80 >> j);

}

err_posn_table [ hec_accum ] = (i * 8) + j;

}

}

return;

}

int correct_header_err(cell_header)

unsigned char cell_header[5];

/* return HEC value calculated over first four bytes of cell header */

{

register unsigned char syndrome;

register int i, err_posn;

syndrome = 0;

for ( i = 0; i < 4; i++ )

syndrome = syndrome_table [ syndrome ^ cell_header[i] ];

syndrome ^= cell_header[4] ^ COSET_LEADER;

err_posn = err_posn_table [ syndrome ];

if ( err_posn < 0)

{

return NO_ERROR_DETECTED;

}

else

if ( err_posn < 40)

{

cell_header [ err_posn / 8 ] ^= (0x80 >> (err_posn % 8));

return err_posn;

}

else

{

return UNCORRECTIBLE_ERROR;

}

}

static unsigned char prototype_hdr[5] = { 0x0f, 0xff, 0xff, 0x02, 0x75};

void main ()

{

int i, j, k;

unsigned char cell_header[5];

gen_syndrome_table();

gen_err_posn_table();

for ( i = 0; i < 5; i++)

cell_header[i] = prototype_hdr[i];

insert_hec (cell_header);

printf("cell header w/inserted hec = %02x, %02x, %02x, %02x, %02x \n",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

j = correct_header_err(cell_header);

printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

printf("err posn = %d \n", j);

for (k = 0; k < 40 ; k++ )

{

for ( i = 0; i < 5; i++ )

{

if ( i == k / 8 )

cell_header[i] = prototype_hdr[i] ^ ( 0x80 >> ( k % 8) );

else

cell_header[i] = prototype_hdr[i];

}

printf("cell header w/inserted err = %02x, %02x, %02x, %02x, %02x \n",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

if ( (j = correct_header_err(cell_header)) != UNCORRECTIBLE_ERROR )

{

printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

printf("err posn = %d \n", j);

}

else

{

printf("err posn = %d => UNCORRECTIBLE ERROR \n", j);

}

}

for (k = 0; k < 40 ; k++ )

{

for ( i = 0; i < 5; i++ )

{

if ( i == k / 8 )

cell_header[i] =

prototype_hdr[i] ^ (( 0x181 >> ( k % 8) ) & 0xff);

else

cell_header[i] = prototype_hdr[i];

}

printf("cell header w/inserted err = %02x, %02x, %02x, %02x, %02x \n",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

if ( (j = correct_header_err(cell_header)) != UNCORRECTIBLE_ERROR )

{

printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",

cell_header[0], cell_header[1], cell_header[2], cell_header[3],

cell_header[4]);

printf("err posn = %d \n", j);

}

else

{

printf("err posn = %d => UNCORRECTIBLE ERROR \n", j);

}

}

return;

}

B.2 AAL5 CRC generation

There are a number of things to be wary of with the generation of CRCs using the code in this Appendix:

The initial value of crc_accum which you pass to update_crc is 0xFFFFFFFFL, not zero. This is true whether the code is used for CRC generation or checking.In order to generate the AAL5 CRC you must first run update_crc over the whole CPCS-PDU, including PADS, CPCS-UU, and all other trailer fields except the CRC field itself. You must then append the ones complement of the output from update_crc as the CRC field of the CPCS-PDU.

In order to check the AAL5 CRC you must run update_crc over the whole CPCS-PDU including the CRC field and check that the remainder is 0xC704DD7BL, as specified in recommendation I.363.

Note that update_crc has been designed to allow for incremental calculation one cell at a time should you wish to do so. All that you need to do is to save the return value from one invocation of update_crc and pass it as the crc_accum argument to the next invocation of update_crc.

The following code can be used to generate the AAL5 CRC.

B.2.1 CRC-32 Code

/* crc32h.c -- package to compute 32-bit CRC one byte at a time using */

/* the high-bit first (Big-Endian) bit ordering convention */

/* */

/* Synopsis: */

/* gen_crc_table() -- generates a 256-word table containing all CRC */

/* remainders for every possible 8-bit byte. It */

/* must be executed (once) before any CRC updates. */

/* */

/* unsigned update_crc(crc_accum, data_blk_ptr, data_blk_size) */

/* unsigned crc_accum; char *data_blk_ptr; int data_blk_size; */

/* Returns the updated value of the CRC accumulator after */

/* processing each byte in the addressed block of data. */

/* */

/* It is assumed that an unsigned long is at least 32 bits wide and */

/* that the predefined type char occupies one 8-bit byte of storage. */

/* */

/* The generator polynomial used for this version of the package is */

/* x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0 */

/* as specified in the Autodin/Ethernet/ADCCP protocol standards. */

/* Other degree 32 polynomials may be substituted by re-defining the */

/* symbol POLYNOMIAL below. Lower degree polynomials must first be */

/* multiplied by an appropriate power of x. The representation used */

/* is that the coefficient of x^0 is stored in the LSB of the 32-bit */

/* word and the coefficient of x^31 is stored in the most significant */

/* bit. The CRC is to be appended to the data most significant byte */

/* first. For those protocols in which bytes are transmitted MSB */

/* first and in the same order as they are encountered in the block */

/* this convention results in the CRC remainder being transmitted with */

/* the coefficient of x^31 first and with that of x^0 last (just as */

/* would be done by a hardware shift register mechanization). */

/* */

/* The table lookup technique was adapted from the algorithm described */

/* by Avram Perez, Byte-wise CRC Calculations, IEEE Micro 3, 40 (1983).*/

#define POLYNOMIAL 0x04c11db7L

static unsigned long crc_table[256];

void gen_crc_table()

/* generate the table of CRC remainders for all possible bytes */

{ register int i, j; register unsigned long crc_accum;

for ( i = 0; i < 256; i++ )

{ crc_accum = ( (unsigned long) i << 24 );

for ( j = 0; j < 8; j++ )

{ if ( crc_accum & 0x80000000L )

crc_accum =

( crc_accum << 1 ) ^ POLYNOMIAL;

else

crc_accum =

( crc_accum << 1 ); }

crc_table[i] = crc_accum; }

return; }

unsigned long update_crc(unsigned long crc_accum, char *data_blk_ptr,

int data_blk_size)

/* update the CRC on the data block one byte at a time */

{ register int i, j;

for ( j = 0; j < data_blk_size; j++ )

{ i = ( (int) ( crc_accum >> 24) ^ *data_blk_ptr++ ) & 0xff;

crc_accum = ( crc_accum << 8 ) ^ crc_table[i]; }

return crc_accum; }

B.2.2 Angie Tso's Test Cases

Here are the examples of valid AAL-5 CS-PDU in I.363: (There are three examples in I.363)

/* 40 Octets filled with "0" */

/* CPCS-UU = 0, CPI = 0, Length = 40, CRC-32 = 864d7f99 */

char pkt_data[48]={0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

0x00,0x00,0x00,0x28,0x86,0x4d,0x7f,0x99};

/* 40 Octets filled with "1" */

/* CPCS-UU = 0, CPI = 0, Length = 40, CRC-32 = c55e457a */

char pkt_data[48]={0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,

0x00,0x00,0x00,0x28,0xc5,0x5e,0x45,0x7a};

/* 40 Octets counting: 1 to 40 */

/* CPCS-UU = 0, CPI = 0, Length = 40, CRC-32 = bf671ed0 */

char pkt_data[48]={0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,

0x0b,0x0c,0x0d,0x0e,0x0f,0x10,0x11,0x12,0x13,0x14,

0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,

0x1f,0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,

0x00,0x00,0x00,0x28,0xbf,0x67,0x1e,0xd0};

Here is one out of my calculation for your reference:

/* 40 Octets counting: 1 to 40 */

/* CPCS-UU = 11, CPI = 22, CRC-32 = acba602a */

char pkt_data[48]={0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,

0x0b,0x0c,0x0d,0x0e,0x0f,0x10,0x11,0x12,0x13,0x14,

0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,

0x1f,0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,

0x11,0x22,0x00,0x28,0xac,0xba,0x60,0x2a};

B.3 Code for CRC-10 Generation

The attached test cases and C program show how to implement a reasonably efficient software algorithm for generating and checking the CRC-10 in AAL 3/4 cells or OAM cells. It computes the CRC on such a cell one byte at a time using the generator polynomial x^10 + x^9 + x^5 + x^4 +x + 1

Unlike the AAL 5 CRC-32 code from which it was derived, the CRC update routine in the attached C program combines the input data with the CRC accumulator after the accumulator is shifted via the table lookup algorithm. This is done so that the CRC bit positions are included in the accumulation; if they were excluded then byte alignment problems would arise since the CRC length is not an integral number of bytes. The test cases below have zeroes in the last two bytes of the cell, but the code which inserts the payload CRC does not in fact depend on this; arbitrary values could be stored in the last two bytes and the resultant CRC would still be correct. In particular, an AAL 3/4 payload length field could be included in the 6 MSBs of the next-to-last byte. Of course, if any of the other bits—i.e., those in the CRC positions -- were non-zero then the final value of crc10_accum would no longer be equal to the cell's CRC, and the printf statements in the C program would be incorrect.

B.3.1 CRC-10 Test Cases

(All values in hex)

Test cell #1:

Test cell #2:

Test cell #3:

Test cell #4:

AIS OAM cell:

RDI OAM cell:

Loopback OAM cell:

B.3.2 CRC10 code

#include <assert.h>

#include <stdio.h>

#define PAYLOAD_SIZE 48

#define POLYNOMIAL 0x633

typedef struct{

char *name;

unsigned char *cell_payload;

} TCASE_STRUCT;

static char test_cell_1_name[]="Test cell #1";

static unsigned char test_cell_1_payload[PAYLOAD_SIZE]={

0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};

static char test_cell_2_name[]="Test cell #2";

static unsigned char test_cell_2_payload[PAYLOAD_SIZE]={

<