An Asynchronous Transfer Mode Receiver

An Asynchronous Transfer Mode Receiver[1]

Martin Hill
Antonio Cantoni
Tim Moors[2]

Networking Research Laboratory
Department of Electrical and Electronics Engineering
University of Western Australia,
Nedlands, WA, 6009; Australia.

Facsimile +61 9 380 1065
Telephone +61 9 380 3047

13 March, 1992

Abstract

Asynchronous cell based transmission is the preferred transmission mode for
emerging high speed network standards such as the IEEE 802.6 MAN standard
and the CCITT BISDN. These networks are envisaged to operate at bit rates
in excess of 100 Mbps. The high bit rate and the cell based mode of
transmission pose challenging requirements on memory buffer management and
the reassembly of packets from constituent cells. This paper describes
hardware architecture and memory management techniques developed to achieve
the required packet reassembly functions and buffer memory management for a
node operating in a high speed ATM based network. The paper also discusses
a number of major generic issues addressed during the development.

Keying words: Networks, Packet, Memory Management, MAC, Reassembly

Introduction


Asynchronous cell based transmission is the preferred transfer mode for
emerging high speed network standards such as the IEEE 802.6 Metropolitan
Area Network (MAN) standard and the CCITT Broadband Integrated Services
Digital Network (BISDN). Asynchronous cell based transport offers the
possibility of supporting a wide variety of services in an integrated
manner on the one network.

The networks are envisaged to operate initially at bit rates in excess of
100 Mbps. At these high bit rates it is likely that the processing
functions required in the lower layers of the protocol stack, (physical
layer and much of the Medium Access Control (MAC) layer), will have to be
performed by specialised processors custom built for specific protocols.
At 155 Mbps the octet data rate will be close to 20 Million octets per
second and the cell rate will be close to 0.4 Million cells per second.

Data packets to be sent over an Asynchronous Transfer Mode (ATM) network
are segmented into cells by the transmitter and need to be reassembled by
the receiver. Packets may occupy from one to a large number of cells, e.g.
in IEEE 802.6 there may be up to 210 cells in a packet. Furthermore, the
arrival of packets at a particular node can be interleaved requiring the
MAC receiver to provide a number of packet reassembly machines able to
operate at the peak cell rate to avoid excessively high packet losses.

The MAC receive processor needs to provide a buffer for received packets,
to match the high speed of the output of the MAC processor to the lower
performance of the upper protocol layers. This buffer, referred to here as
the MAC Buffer, may, in connectionless networks without flow control, needs
to be large to ensure that the probability of packet loss due to
unavailability of buffering resources is sufficiently low [1]. As discussed
in a subsequent section of the paper, the need to pipeline sections of the
receiver in order to achieve high performance may add to buffer
requirements in the receiver.

Memory management is required to allocate memory efficiently in the MAC
Buffer. For high performance systems the MAC Buffer may be physically
indistinct from the buffers used by the upper layers of the protocol stack.
Since much of the data may be invariant as it traverses the protocol
stack, the processors implementing the upper protocol layers would access
the MAC buffer directly and use buffer cut through techniques to avoid
copying of data [2],[3],[4]. However, there are applications in which the
MAC needs to interface to a processor running existing higher layer
software that interfaces to a specific operating system and makes use of
the operating system's buffer pool management. In this case, it is quite
likely that packet data must be transferred to the processor's system
memory in which the operating system maintains its buffer pools and also
may need to be stored in contiguous locations.

This paper describes a MAC receive processor developed for an ATM cell
based connectionless data network. The paper also discusses the major
issues that were addressed in the development since many of these issues
are considered to be generic in nature. The target network is a QPSX
Metropolitan Area Network [5] that operates with bit rates up to 140Mbps
and is a precursor to the IEEE 802.6 and SMDS,[6], based networks. The
design of a receiver for only one bus of the dual bus QPSX network is
considered in this paper. The MAC processor was designed to address the
problems of high physical layer data rates, the provision of a large number
of packet reassembly machines, the provision of a large MAC buffer to hold
both fully and partially reassembled packets, random access and the high
speed transfer of packet data out of the MAC buffer if required. In
particular, the paper describes the use of Video RAM technology to provide
the MAC buffer located between the MAC processor and upper layers. The
paper also describes an architecture suitable for the implementation of the
MAC receiver functions. While a hardware solution to packet reassembly has
been adopted, others have proposed [7] that this function can be performed
in software and still achieve acceptable performance.

The paper is organised as follows: The basic functions that must be
implemented in the MAC receive processor are briefly reviewed. The
architecture of a MAC receive processor which can process cells in real
time at the peak cell rate is then outlined. Next, the method used to
handle a large number of concurrent reassemblies is discussed. Then, an
efficient memory management scheme for MAC buffer management is described.
The scheme supports a large number of reassemblies and also the buffering
of many reassembled packets in the one MAC buffer. The implementation of
the reassembly machine and the memory management is then outlined. The
requirements of the MAC Buffer are identified and the choice of Video RAM
technology to realise the MAC buffer is justified and some aspects of the
implementation of the buffer are discussed. The performance achievable
with the design is noted in each section as appropriate.



The MAC Receive Processor


The node protocol architecture we wish to consider and the position of the
receive MAC processor within the node architecture is illustrated in Figure
1.

The Physical Layer Processor handles line decoding, synchronisation, serial
to parallel conversion and supplies the MAC processor with a continuous
stream of octets at a rate dependent on the medium bit rate.

Data is passed from the MAC receive processor to the processor implementing
the Logical Link Control layer through a buffer. For most end station
nodes the average rate of data flow across this interface is only a
fraction of the medium bandwidth, and the unit of data transferred is a
packet, whereas cells are the data unit transferred across the Physical
Layer Processor-MAC interface. In the receiver described in this paper,
buffer cut through is used to provide an area to perform reassembly of
packets and an elastic buffer to hold reassembled packets in a common
physical memory.

The MAC receive processor also has an interface through which it can be
managed. Management may be performed by a microprocessor responsible for
initialisation and supervision or as part of the tasks of a processor
implementing one or more of the upper layers.



The Target Network Cell Format and Reassembly Protocol


In this section we briefly describe the essential characteristics of the
target network packet and cell format and the basic receive functions that
must performed by the MAC receive processor operating in this network.

A cell in the QPSX MAN consists of a five octet header and sixty four
octets of payload as shown in Figure 2. Information can be written into
cells by nodes via the DQDB medium access protocol, [5], that uses the
Access Control Field in the cell header.

Packets to be sent over the network are first segmented by the transmitting
node into cells which are then sent on the network using the DQDB access
protocol. To enable reassembly of a packet from its constituent cells at
the receiving node, a Message Identifier (MID) field in the cell header is
used to logically link cells together. In the QPSX MAN the MID is fifteen
bits long. The first cell in a packet to be sent is assigned a Beginning
of Message (BOM) cell type and contains the packet's destination address.
The receiving node's MAC processor must recognize its address in the BOM.
If the BOM is destined for the node, the MAC processor must temporarily
store the MID and also accept the BOM payload. Subsequent cells belonging
to the same packet are labelled as Continuation of Message (COM) cells and
are sent with the same MID as the BOM. Since the MID is unique to a
specific source and sources do not interleave packets with the same MID,
the receiving node's MAC processor can use the MID to recognize and link
cells belonging to the one packet. The last cell sent for a packet is
labelled as the End of Message (EOM). On receipt of the EOM the receiving
node's MAC processor removes the corresponding MID from its list of known
MIDs, so that no further COMs and EOMs with the same MID but not destined
for the node, are accepted. A new BOM with the MID causes the MAC
processor to register once again the particular MID. Fig