RDRN Network Control

In this section, we will present the RDRN adaptive protocols and the Network Control Program (NCP) that manages those protocols.

RDRN Wireless ATM Protocols

RDRN Protocol Stack

The RDRN protocol stack is shown in the figure. This stack is implemented in the Edge Nodes (ENs) and the Remote Nodes (RNs). On the other hand, radio link management is only implemented in the ENs. A list of the networking protocols implemented in the RDRN prototype is listed in the following table:

Protocol Management
IP IP Routing
IP over ATM Classical IP over ATM
AAL 5  
ATM Q.2931 and RDRN NCP
Radio Link RDRN NCP

RDRN protocols and management components have been implemented in the Linux operating system running on Intel x86 compatible computers. Linux provides an open development system with many contributors around the world running on a wide variety of computer architectures. The system supports applications running over both native-mode ATM as well as TCP/IP over ATM. There has been considerable development work done to support standard ATM on Linux by researchers at the Laboratoire de Reseaux de Communication (LRC) at EPFL in Switzerland. In particular, they have developed a BSD-sockets based application programming interface (API) to support native-mode ATM applications as well as support for Classical IP over ATM for TCP/IP based ATM applications.

The RDRN NCP supports applications through the standard UNIX socket interface to the networking protocols within the operating system kernel. The socket interface provides conventional TCP/IP services and ATM services. Applications can interface to the ATM service either through a framing protocol, such as AAL5, or raw ATM cells. Within the kernel, the network layer implements the Internet Protocol (IP), whose primary purpose is to provide routing between subnetworks and service for the Transmission Control Protocol (TCP), User Datagram Protocol (UDP), and other transport layers. Classical IP (CLIP) and ATM Address Resolution Protocol (ATMARP) are initial standard solutions for carrying IP traffic over the ATM links. However, it has several weak points such as requiring a router to connect separate Logical IP Subnets (LIS), even when the subnets are directly connected at the ATM level, and requiring an ATMARP server to provide address resolution for a single LIS. The non-broadcast multiple access Next Hop Resolution Protocol (NHRP) provides a better solution but it is still in draft form. The RDRN architecture implements CLIP and supports both Permanent Virtual Circuits and Switched Virtual Circuits via ATMARP.

To this base system we have added four software components in our prototype system: (1) the Bellcore Q.Port ATM signaling system, (2) an ATM driver for handling AAL5 protocols, (3) an ATM cell switch, and (4) a driver for our wireless links. The Bellcore Q.Port system provides a reference implementation of the ATM User-Network Interface (UNI). This software is used for call setup and teardown, virtual circuit management, and interoperability with wired systems. The ATM driver for AAL5 is a custom software componet that can interface to conventional ATM interfaces and/or our wireless interface at the frame level and handles the encapsulation of IP for the network layer. The ATM driver also distinguishes between virtual circuits (VCs) that carry AAL5 frames and those that carry raw ATM cells. In the case of VCs carrying AAL5 frames, segmentation and reassembly functions are handled in hardware on conventional interfaces and software for the RDRN wireless interface. Otherwise, for non-framed VCs, single ATM cells are handed to the ATM cell switch for switching to other VCs and then passed to the appropriate interface. The ATM cell switch is not present in Remote Nodes.

RDRN nodes implement an Adaptive HDLC link layer over the wireless link. ATM cells are collected into a modified HDLC frame, called the Wireless ATM frame or WATM frame, for transmission. In the case of Edge Node to Edge Node traffic, ATM cells from any VC can be included in the WATM frame. In the case of Edge Node to Remote Node traffic, ATM cells must be sorted into separate queues, one for each Remote Node. Only cells destined for a single Remote are included in the WATM frame for transmission under the TDMA media access protocol. The WATM frame consists of a Start-of-Frame flag (1 byte), a Link Identifier (1 byte), a Control Byte (1 Byte), one to nine ATM cells (53-477 bytes), and a 16-bit CRC field (2 bytes). Multiple ATM cells are included in each WATM frame to reduce the effect of encapsulation overhead necessary for addressing in the TDMA access mechanism and error control. No ATM header compression is used at this time. Likewise, we have not included forward error correction in the WATM frame. The number of ATM cells in a frame is based on resources at each end of the link and the link condition.

Radio link quality at the link level is estimated by counting the number of WATM frames received in error. This information is communicated upstream to the transmitting node. The HDLC link layer adapts to link quality in two ways. As the link quality goes down, fewer ATM cells are included in each WATM Frame. Thus, any noise burst or fade over a few tens of microseconds will cause fewer ATM cells to be dropped. The second technique, used for loss-sensitive traffic, is to transmit multiple copies of the WATM frame, for example two or three copies. Experiments have shown that WATM frame length adjustment with up to two copies of each frame transmitted is sufficient for most situations. The protocol uses a sliding window and go-back-N ARQ scheme.

Network Control Program (NCP)

The RDRN Network Control Program (NCP) is the primary control program for the system. As such, it monitors the backbone topology, locations of Remote Nodes, computes antenna beam patterns, and implements connection handoffs between antenna beams and between Edge Nodes. The NCP executes on Edge Nodes. To perform these functions the NCP monitors Remote Node locations and link quality to make decisions on configuration changes. The NCP causes antenna beams to be adjusted as Remote Nodes move and re-routes ATM virtual circuits as Remote Nodes move between beams and Edge Nodes.

Maintaining Backbone Topology

The current RDRN implementation assumes Edge Nodes remain stationary during operation of the network. However, Edge Nodes can enter or exit the system causing backbone topology changes. As mentioned above, our algorithms for determining backbone topology are based on a consistent labeling approach. In consistent labeling, constraints are expressed as pair-wise constraints, e.g. if node A transmits to node B on frequency F, then node B can transmit to node A on any frequency except F. The consistent labeling algorithm considers all pair-wise constraints and determines a consistent labeling of all links.

The consistent labeling problem is a generalization of the graph coloring problem, the cellular frequency assignment problem, and many others. Suppose one has cellular frequencies F1...F7. Further, suppose cells A and B are adjacent and cell A is assigned frequency F1. Then cell B can only use frequencies F2...F7. This constraint can be expressed as a list of 4-tuples: {<A, F1, B, F2>, <A, F1, B, F3>,...,<A, F1, B, F7>} indicating the allowable combinations of cell A, the frequency assigned to cell A, cell B and the frequencies assigned to cell B. The consistent labeling algorithm takes such a list describing the allowable combinations for all cell pairs and determines a consistent assignment of frequency to cells meeting all the constraints.

The advantage of the consistent labeling approach is that multiple criteria, such as frequency, beam direction, and spread spectrum code, can easily be included in determining the backbone topology. The disadvantage is that the labeling problem is equivalent to the graph coloring problem and, hence, is NP-complete. However, we expect that due to the limited number of Edge Nodes, the computational speed of available computers, and heurestics that can be incorporated into the implementation, that this approach is sufficient for an RDRN type system.

Monitoring Locations of Remote Nodes

The NCP at each Edge Node monitors the location of nearby Remote Nodes through either the orderwire link or inband signaling. From this information the NCP determines whether to adjust an antenna beam to accommodate Remote Node motion or to switch the Remote Node to a different beam. In the former case, the Edge Node considers the locations of all the Remote Nodes within a current beam and computes new antenna beam patterns to maximize the minimum signal-to-interference ratio across all remote nodes. In the later case, the Edge Node moves a Remote Node to a new antenna beam, re-calculates the antenna beams for the "source" and "destination" beams, and re-routes all necessary ATM virtual circuits. In the current system, the beams are re-calculated every five seconds.

We have considered a system that predicts the motion of Remote Nodes. Future positions of Remote Nodes are predicted from recent positions and computing a simple velocity vector. Using predicted positions, the RDRN system can pre-allocate resources to make smoother handoffs between beams or nodes. The modified system is described in.

Last Update: November 03, 1999 03:00pm (GMT-0600)