Modeling and SimulationSoftware DevelopmentWhitepapers

Common Code Simulation Architecture for Embedded Wireless Routing Protocols

Abstract

When developing networking algorithms for embedded communications devices, the use of a common code architecture greatly reduces the complexity of the development cycle and increases the reliability of the end product.  The use of an operating system abstraction layer provides the ability to run a high percentage of the embedded code directly in both the OPNET simulation environment and the target hardware.  Executing the same code in both simulation and implementation assures that the simulation results are relevant to the target’s performance, and that updates are quickly reflected in the performance results under both environments.  Here we present the development of a Linux abstraction layer, which was used to verify a MANET routing protocol code base simultaneously in both the OPNET environment and a wireless router.

Introduction

Introducing a network routing algorithm into a network communications device is a challenging effort.  Applications such as public safety and Military communications systems are becoming increasingly reliant on Ad Hoc wireless systems for decentralized communications.  Analysis and simulation efforts are required to verify the effective operation of the protocol and its implementation in firmware prior to its use.   The development of a network simulation model separate from the embedded target firmware presents certain logistics and configuration concerns when attempting to match functionality.  Abstracting the higher layers of the routing protocol and then using them as a single base for both simulation and firmware development results in an efficient approach which mitigates most of the dual code base approach.

 

novaroam

Figure 1 – MANET Routing in Public Safety Applications

The widespread use of Linux as a operating system for wireless networking has increased in recent years.   One area in which this use of Linux is prevalent is in the development of Mobile Ad Hoc Routing Network (MANET) algorithms.  The target for much of this research and development effort centers around algorithms running on Linux platforms and simulation of the algorithms in OPNET or NS2.   In the late 90’s, NS2 was the predominate tool in used within the research community.    Increasing support for the evaluation of MANET algorithms in OPNET has grown as both commercial and research organizations searched for a more mature platform.   The use of OPNET in this area was underpinned first by the release of the wireless support package followed by the release of the MANET Manager extensions to the IP process model in the OPNET release 10.5. 

 

Figure 2 – MANET Routing in Military Applications

In the development arena the advantage of using an open source operating system such as embedded Linux has found its way into many communications devices in development today.

Internally at Nova the NovaRoam platform has been upgraded  from a proprietary only Operating System to one which enables support for Linux.    This enhancement enables the use of MANET protocols developed for the Linux environment.   As a method of supporting this and other MANET radio efforts an OPNET simulation model for an embedded Linux environment was developed.  The abstraction layer which makes this possible and the use of the common code base is covered in this paper with respect to the implementation of the AODV routing protocol.

MANET Protocols Requirements

The MANET working group of the Internet Engineering Task Force (IETF) is chartered to standardize IP routing protocol functionality suitable for wireless routing application within
both static and dynamic topologies with increased dynamics due to node motion or other factors.  Two basic classes of protocols referred to as reactive and proactive have emerged from the working group.

The proactive protocols have the same concept as the traditional routing protocols for the wired internet in that the attempt to establish all routes prior to use is performed.   These protocols are well behaved in that they require minimal support from the protocol stack in which they operate.  Their needs are often limited to opening a communications socket and sending updates to the IP routing table when new information is determined.

The reactive protocols which constitutes much of the working groups focus require several additional interface areas with the supporting IP stack.

Requirements of both Proactive and Reactive Protocols

  1. Receiving routing control packets
  2. Sending routing control packets
  3. Update routing table entries

Requirements of Reactive Protocols

  1. Notification of containing a packet which has no route
  2. Re-injecting queued packets when route is found
  3. Status of route usage when IP stack forwards a packets

When simulating routing protocols in OPNET the IP process model  must support these requirements.   In OPNET this  support  is provided by the both the MANET manager and other hooks into the IP dispatch process.

OPNET MANET Manager

The OPNET MANET Manager provides the features (a), (d) and (f) listed above.   Features (b), (c) and (e) are supported with specific calls into the IP routing process.   In the common code framework the MANET Manager operates the same as before only that it does not communicate directly to the routing protocol but rather it communicates with an operating system abstraction task as shown in Figure 3.

Figure 3 – MANET Manager Child Processes

The Linux OS interface task acts as a bridge between the Linux interface processes of the routing protocol and the OPNET system calls.

OPNET MANET Common Code Architecture

In the new common code architecture, the implementation of the routing protocol which in this cases would be the AODV_RTE process is replaced by two processes and a shared memory block as shown in Figure 4.

 

Figure 4 – MANET Manager Common Code Interface

The OS interface task converts OPNET formatted packets into the structure required by the routing process.  In the case of the Linux implementation the OPNET packets are converted into the skbuff structure which is expected by the socket calls of the routing protocol.

AODV Linux Implementation Methods

Several methods of providing the functionality of the reactive AODV protocol are possible and are described in greater detail in [3]. The following are some of the  AODV approaches which have been implemented:

  • Snooping
  • Kernel Modification
  • Netfilter Interface

The Snooping method is a brute force method of intercepting all incoming and outgoing packets from the interface.   This method relies on the use of the ARP protocol and its associated limitations.

The Kernel Modification method allows the insertion of the protocol directly into the IP forwarding agent process.  Though this method provides the ultimate control, it comes with maintenance and portability issues which makes it a less than optimal approach for most applications.

The Netfilter approach uses hooks at various points inside the Linux protocol stack.  This interface as shown in Figure 5 allows the redirection of the packet flow through user defined processes.  The protocol running in user space uses the Netfilter interface to redirect the packet flow by examining, dropping, discarding, modifying or queuing the packet received by the IP stack.

Figure 5 – Net Filter TAP Points

Kernel AODV Common Code Implementation

Given the flexibility of this method of interfacing the reactive AODV protocol we selected this as the approach for the development.

An implementation of an AODV protocol which uses this interface is available from the National Institute of Science and Technology (NIST) [1].    The NIST AODV protocol is shown within the common code framework in Figure 6 and requires the following basic support features to run in the OPNET environment:

  • Device interface structure
  • Send and receive sockets for control messages
  • Net Filter packet queue receive
  • Net Filter packet received with no route
  • Net Filter re-inject packet
  • Ioctl calls for route table updates
  • Timer and memory allocation

 

Figure 6  –  Kernel AODV in Common Code Framework

Common Code Linux Interface

The shared memory interface between the Linux OS interface and the common code defines a set of mailbox structures and queues to pass routing objects between the OPNET simulation and the Linux IP API as shown in Figure 7.   An example of the operation of these processes is when a packet is received by the MANET manager.  The MANET manager then invokes the Linux Interface child process and passes the OPNET formatted packet.  The Linux interface coverts the packet to a sk_buff format and invokes the common code based routing protocol process.

 

Figure 7  –  OPNET to Linux Interface

In some cases packets and control information is required to flow in the reverse direction from the child process back to the Parent process.  An example of this is when a route is established and packets which are queue by the routing process are required to re-injected into the IP stack.  When this occurs the packets are placed in the native sk_buff format on the shared memory interface and the routing protocol invokes the Linux OS process.  After converting the packet back into the native OPNET format the Linux OS process re-injects the packet back into the IP process.

 Common Code Process Model

The common code routing protocol which is built using a high level OPNET process is shown in Figure 8.  The process model includes files from the embedded target source code directory during the build process.

Figure 8  –  Common Code Process Model

A configuration control tool is used to resolve update issues between the embedded production build and the OPNET simulation environment during development.

The common code process responds to four types of events as shown.  The internally generated timer events are independent of the events received from the Linux OS Process.  An example of a timer event would be the sending of a Hello messages, which would be formatted and then passed through the shared memory interface to the Linux OS Process.   The TX Packet state is entered when the routing protocol has a packet to send to the Linux OS interface as a result of a self interrupt.  The self interrupt allows the routing protocol to invoke the Linux Interface Process to receive the outgoing packet.  Similar to the TX Packet state the RT update is entered as a result of a self interrupt which requires a modification of a IP route table entry.  Lastly the RX Packet state is called when a packet has been passed through the Linux OS process from the MANET Manager.

Linux OS Process Model

The Linux OS process model has two event types to which it must respond to.  A packet from the MANET manager will invoke this task as a child process with an OPNET packet stored in the MANET routing interface structure memory.   Any activity from the child process which requires external servicing will result in an invocation from the common code routing protocol and a transition to the Process Linux Interface state.

Figure 9 – Linux Interface Process

Conclusion

Simulation of network routing protocols are essential for the effect development and deployment of these complex communications systems.  Creating a suitable abstraction layer which allows the embedded code to execute in a form which is highly correlated with the end product is possible by employing a common code development environment within OPNET.  The end result is a product which is much more reliable and has a higher probability of meeting the customers needs when deployed.  The common code base also reduces maintenance issues which result when OPNET and embedded network routing applications are develop separately.

References

[1] L. Klein-Berndt. Kernel AODV from National  Institute of Standards and Technology (NIST).

[2] Nova Engineering. NovaRoam.

[3] AODV Protocol Implementation Design, Ian D. Chakeres, Elizabeth M. Belding-Royer,   June 1997.  http://people.cs.ucsb.edu/ebelding/sites/people/ebelding/files/publications/ijwmc05.pdf

[4] C. E. Perkins, E. M. Belding-Royer, and S. Das. Ad hoc On-Demand Distance Vector (AODV) Routing. RFC 3561, July 2003.