Overview of MAGICIAN

System Architecture

The two principal components of an active network are the active nodes and the SmartPackets. The prototype active network, whose topology is shown in Figure 1, is a collection of individual active nodes and a single Information Server (see Four11 FAQ) each running on a separate Java Virtual Machine (JVM). Active nodes exchange SmartPackets by encapsulating them inside UDP packets and sending them on UDP ports 3322-3325 of the host on which a neighboring active node is running. The Information Server maintains the configuration of the network. At startup, nodes in the active network contact the Information Server to determine adjacent nodes. This information is useful to provide a basis for developing the infrastructure necessary for routing SmartPackets in the active network. We provide a brief overview of the structure of a SmartPacket and the role of active nodes in the active network before describing the architecture of an active node in detail.
 
 

Figure 1. An Example Virtual Active Network Topology

Magician is implemented in JavaTM.The Java Virtual Machine environment supports machine-independent programs and the language is quickly becoming a standard for object-oriented programs that can be compiled into bytecodes. We opted to implement the system using version 1.1 of the Java Development Kit (JDK) for two principal reasons:

Since SmartPackets are executable entities, their state has to be preserved when they are transported from one active node to the next. Object serialization is one technique for preserving and transporting state. The state of an executing object is written out as a byte array in a particular format. The byte array is then transported across the network to the neighboring active node where the bytes in the array are used to re-create the SmartPacket. There is an added advantage in using object serialization. Since Java is being becoming increasingly popular in the active networking community, we expect most active nodes to support object serialization. This permits widespread integration of the different active network architectures.

SmartPackets

In an active network, data packets are information entities. These entities, which we call SmartPackets, contain a destination address, user data, and methods that can be executed locally at any node in the active network. Since architectures like the x-kernel and Horus allow us to compose complex protocol stacks from single-function protocols, we can think of SmartPackets as carrying customized protocols that are fitted in with protocol modules at the network nodes.

The code in the SmartPacket can be in any executable format and it is executed at the node if the node has the correct processing environment. In our implementation, the code of the SmartPacket is actually a Java class that describes the methods that act on the user data. Each SmartPacket has a 128-bit type identifier, which is used to identify the protocol that is carried by the SmartPacket. The type identifier is a MD-5 message digest of the structure of the SmartPacket.

The idea is that any composer of a SmartPacket (user, application, router etc.) wanting to define a new type sends the SmartPacket definition to a local Type Authority (currently built into the kernel at the host node). This Type Authority authenticates the composer, checks the structure of the SmartPacket and converts the SmartPacket definition to canonical form. The canonical form is then hashed (using a standard hash algorithm) into a 128-bit number that is returned as the type identifier for the SmartPacket. This prevents spoofing because the signature is a one-way function and the contents of the packet can be verified against the signature.
 
 

Figure 2. On-The-Wire Format of SmartPacket

The overall structure of the SmartPacket conforms to the Active Network Encapsulation Protocol (ANEP). ANEP was created to enable members of the Active Networking community to implement their own execution environments at all member sites and still be able to interchange SmartPackets. The ANEP structure (Figure 2) consists of a fixed header that describes, among other things, the environment in which this SmartPacket executes, and a series of optional type/length/value (TLV) tuples. Some of the TLVs defined in the ANEP proposal are source definition TLV, destination definition TLV and authentication TLV.

Members are free to add their own TLVs to the overall structure except that they will not processed at nodes which do not understand them. We defined a class definition TLV to carry the Java class definition of the user code. We also defined an object definition TLV to carry the serialized object and a Type definition TLV that carries the type identifier of the SmartPacket.

Active Nodes

Active nodes perform the functions of receiving, scheduling, executing, monitoring and forwarding SmartPackets. When a SmartPacket arrives at an active node, the type identifier and the user-defined code inside the SmartPacket is extracted. The type identifier is used to de-multiplex the SmartPacket to its correct processing environment. The SmartPacket is then scheduled for execution. A separate environment is required for each invocation to prevent undesirable interactions and malicious access to node resources.

Active nodes export a set of resources and primitives that can be used by the user programs contained inside SmartPackets. This not only provides a consistent view of the network but also enforces constraints on the actions that can be performed by user code. Thus an active node enforces a time limit on the execution of SmartPackets to prevent runaway user programs. It also imposes a limit on the total memory that can be requested by a SmartPacket. In terms of primitives, user code has restricted access to certain internal information such as the routing tables, buffer space information and available link bandwidth on the node's interfaces. The user can utilize this information to develop application specific strategies to combat congestion or implement a new routing policy for its packets.
 

Active Node Architecture

The model of an active node is shown in Figure 3. An active node is made up of (possibly) multiple processing environments such as a PLAN execution environment or an ANTS environment. Each environment is controlled by its node manager. When an active node boots up, it starts a set of port managers, a demultiplexer, and the node managers of all the environments that the active node supports. There is one Port Manager per UDP port that the active node listens to and on which the active node communicates with other nodes. The list of ports that the active node listens to is obtained from the Information Server (see Four11 server FAQ) at boot time. Incoming SmartPackets are queued at the Demultiplexer (class Demultiplexer). The Demultiplexer verifies that the packet conforms to ANEP standard and then attempts to demultiplex the packet to its correct processing environment based on the environment identifier field in the header. This is accomplished by using the environment identifier to index into a table to find the Node Manager for the environment. The byte stream constituting the packet is then handed over the environment's node manager.
 
 

Figure 3. Model of an Active Node

Node Manager

In this approach, the Node Manager starts other managers such as the resource manager (class ResourceMgr), the routing manager (class RoutingMgr), the network event reporting manager (class NetLoggerEventManager) and the port interface manager (class PortInterface). The resource manager is involved in the management of node resources including scheduling and is discussed in the next section. The routing manager provides the interface for installing routing protocols and also provides a default routing mechanism for those SmartPackets that do not implement their own. More details about the routing manager are discussed later.

The port interface manager controls the assembly and disassembly of SmartPackets and their transmission and reception over the wire. The port interface manager receives a SmartPacket as a byte stream. The ANEP header is peeled off first. The TypeID TLV describes the type of the SmartPacket. If the node is receiving a packet of that type for the first time, a new SmartPacket loader is created (class SmartPacketLoader). The SmartPacket loader extends the normal Java Virtual Machine class loader by allowing new classes to be loaded from packets received over the network. The SmartPacket loader is then assigned to that type and is used whenever packets of that type are received or need to be transmitted. This also presents a separate environment for each type so that there are no name conflicts between SmartPackets of different types. Name conflicts between packets of same types are treated as errors.

To construct an incoming SmartPacket, the SmartPacket loader reads the bytecodes representing the class definition and the serialized object. After reading the SmartPacket, the classes, if any, in the SmartPacket are loaded and verified by the SmartPacket loader. The serialized object is de-serialized and checked for the presence of resource information. This resource information includes resource requirements like maximum processing time, which are passed to the Resource Manager along with the de-serialized object for processing.

The port interface manager reverses the process when transmitting SmartPackets. When it receives the SmartPacket object and information about its next hop, the object is serialized and placed in the Object Definition TLV, the ANEP header and other appropriate TLVs are added and the byte stream is transmitted on the appropriate link.

Serialization of a Java object is an expensive operation. Therefore, when a SmartPacket is received a hash is computed on the extracted data object and the object is cached. This hash is used when the same SmartPacket is ready for forwarding to determine if the entire object needs to be re-serialized. If nothing in the object has changed, simply re-sending the original cached object can save time.

Resource Manager

When a SmartPacket arrives at an active node, the Node Manager verifies, loads, and defines the embedded class to the execution environment as described earlier. The Node Manager then forwards the de-serialized code object to the Resource Manager for execution. The Resource Manager provides an interface to resources at the node. The code in the SmartPackets is run in a thread. All requests for resources are made by the thread on behalf of the code. This is similar to the path abstraction used in the Scout operating system. Having a single thread per SmartPacket simplifies resource management because it is easy to track the resources allocated for a given thread.

Most SmartPackets arriving at an Active Node do not require sophisticated resource models. Some of the basic resources are CPU cycles, memory and I/O bandwidth. This list can be extended by including storage in which SmartPacket can leave small state at a node after its execution environment expires.

Memory for Short Term Storage

During its execution, a SmartPacket may have to create objects which need to be stored in the local memory. The active node must limit the size of storage used by a SmartPacket and the lifetime of the storage. It is not always possible to perform such low level monitoring without incurring a serious overhead. Therefore, we have not imposed any limitations at this time.

Resource Sharing and Control

Since the resources in an active node are shared by different SmartPackets, the Resource Management entity must ensure safe resource assignment to SmartPackets. Firstly, the node must maintain its state integrity by limiting the resources to which SmartPackets have access. Secondly, the node must provide safe sharing of resources between different SmartPackets.

Access to resources is limited by imposing static maximum allocation of each resource. In this implementation, the Active Node Manager imposes static limits on some of the resources. The resources are:

At startup, the Resource Manager starts a Scheduler (class Scheduler) for scheduling SmartPacket threads and a Resource Monitor (class ResourceMonitor) that keeps track of per thread resource consumption. Resource information (such as CPU and memory requirements), which is extracted from the incoming SmartPacket, is checked against the static limits imposed by the Node Manager. If the resource requirements are more than the maximum allowed, then an exception is raised and the SmartPacket is rejected. Otherwise, a new thread is allocated to run the code in the SmartPacket and it is passed to the scheduler. As mentioned earlier, the scheduler uses feedback scheduling with dynamic priority to schedule the threads. To ensure timely execution, the scheduler allows only a fixed number of threads to start execution in any given interval of time. The Scheduler also runs periodically to revoke threads that have finished their execution time, or to lower the priority of a long running thread, or to schedule new threads.

The Resource Monitor runs as a separate thread and monitors the activities of the SmartPackets at the node. It periodically checks the current level of resource utilization for each thread. Any threads that have exceeded their pre-stated resource requirements are stopped immediately and the associated SmartPackets are discarded.

Small State Management

In traditional networks, packets cannot exchange information with each other as they pass through the network. However, in our implementation, we allow SmartPackets to leave information in the form of data at the nodes they traverse. The cache in which this information is stored is called as Small State. A variety of information can be stored as Small State. For example, a SmartPacket may leave behind the name of the next hop it is traversing. Trailing SmartPackets can potentially use this information. The interface to manipulate small state is currently provided directly by the Node Manager. Details about how to use the interface are described in the annotation for the class ActiveNodeManager. Note: This interface will likely be rolled into the KUSmartPacketV2 class interface in the next version. Users are cautioned to use the current interface with discretion.

Routing

The Routing Manager (class RoutingMgr) maintains the interfaces for various routing protocols to be implemented. The default routing protocol that is installed at all active nodes is the RIP routing protocol (class RIPRouting). The RIP routing protocol creates and maintains its own routing tables and provides the interface for manipulating these tables. The routing table is a simple vector of 4-tuples that describes other active nodes in the network and how to get there. But instead of sending routing table updates as data, the active routing protocol sends SmartPackets that carry code to modify, add or delete table entries at the destination. Figure 4 shows the idea of our routing protocol where the updates are sent as SmartPackets. The routing protocol sends these SmartPackets after specified intervals of time (say, every 30 seconds).

Figure 4. Routing Manager

Users can install their own routing protocol for their SmartPackets. To do so, they have to install it at the node by using the interface provided by the RoutingMgr class. Next the GextNextHop() method of the base SmartPacket class (class KUSmartPacketV2) must be overridden to return the name of the active node that serves as the next hop towards the destination.
 

Four11 Service FAQ

What is Four11?
The Four11 server (class Four11) is an information service that maintains information about named, virtual active networks. The idea is that the physical network of active nodes can be overlaid by a virtual network of nodes. Thus a physical active network can contain multiple virtual active networks (VAN). Information about each VAN is maintained by the Four11 server. Any active node can query the Four11 server through a specific API to obtain information about a VAN or its constituent nodes. Information such as the names of the active nodes in a VAN, the physical nodes on which they reside, the interface addresses, their neighbors in the VAN can be easily determined.

How is the network configuration specified?
The topology of the VAN and its member active nodes are described as lists attribute value pairs. Each pair is of the format attribute: value. An attribute must be a single name. The value can either be a name by itself or a list. The list can itself have sublists. Attribute-value pairs of all member nodes of a VAN are grouped into a list. It is thus possible to describe multiple VANs in a single configuration file. The configuration file is located in the magician/Four11 directory. It is possible to describe any attribute of the active node using this method. New attributes can be added at any time. The only restriction is that the name of the attribute must not match the name of a value.

What is the ports attribute?
The ports attribute has as its value a list that describes the UDP ports on which the member active node receives SmartPackets. The port numbers given in this list must match the port numbers listed in the nbors entry of the active nodes that are neighbors to this node.

What is the gateway attribute?
The gateway attribute is used to describe the active node(s) that form the gateways of the VAN. The default behavior of the active nodes is that if a destination address does not resolve to a valid VAN address, then the SmartPacket is shipped to the gateway node. It is the responsibility of the user to provide the logic for dealing with the packet once it reaches the gateway node.

How are neighbor interfaces specified?
Since a physical active network can have multiple VANs, the neighbors of each member node have to be explicitly described. Neighbors are described using the nbors attribute. The value of this attribute is a list of lists. Each sublist describes a neighboring node. The description includes: the virtual name of the neighboring node, its interface address, the UDP port number on which SmartPackets must be sent and the bandwidth of the link connecting the neighbors. If the neighbor is more than 1 hop away, the bandwidth value is the minimum of the link bandwidth of all the hops.

How do nodes interact with Four11 server?
Active nodes interact with the Four11 server using freeform lisp-like messages. Each message must match the format of the attribute-value pair's description in the configuration file. Only the first match is returned. The interface for sending the messages is implemented by the methods described in the Four11Stubclass.
 

Operation FAQ

How to start up an Active node?
Active nodes can either act as hosts (i.e. they inject SmartPackets into the network) or they can act as intermediate nodes (i.e. they process and forward SmartPackets). While the underlying architecture is the same in both cases, the startup interfaces are different. We have provided a generic command-line interface for injecting any user SmartPacket. If the interface is insufficient, the user can write his/her own interface. See Starting the Network  section in the Setup and Configuration document for exact details on how to start active nodes/hosts.

How to specify the topology of an active network?
The topology of the network is specified giving a configuration file to the Four11 server. An overview of the Four11 server and its working are described in the Four11 FAQ. Details of the layout of the configuration file are available in the Four11 Server and Network Setup section in the Setup and Configuration document.

How is a SmartPacket defined?
The KUSmartPacketV2 class implements the definition of the SmartPacket. It implements the interface between the user code and the active node kernel. Its public methods expose the functionality of the kernel that is available to the user. The type of the SmartPacket is given by a 128-bit type identifier that is automatically generated when the SmartPacket is created. This type identifier is used to identify the packet in the network and to protect its integrity and the integrity of other packets at the node. Forcing the user to interact with the node only through the interface provided by the SmartPacket's methods ensures safety of the node's resources.

How does an user create a new, simple SmartPacket?
The user creates his own SmartPacket definition by extending the class KUSmartPacketV2. The functionality of the SmartPacket is described by overriding the exec() method of the KUSmartPacketV2 class. Using this interface enables the user to use the default routing, unguaranteed delivery characteristics. See the SmartPing class for an example.
For guaranteed delivery, extend the ReliableCommFW class and override its exec() method for implementing user functionality. The ReliableCommFW class provides a framework that uses a simple Send and Wait for Ack protocol (class StopAndWaitAck) for reliable delivery and RIP routing protocol for routing. See the SmartAckPing class for reference.
If the user wishes to create more complex underlying frameworks, he must override the build() method of the KUSmartPacketV2 class and implement the framework there.

How is a SmartPacket injected into the network?
A Smartpacket is injected into the network in one of two ways. The user creates his own SmartPacket definition by extending the class KUSmartPacketV2 as described earlier. If the logic described in the exec() method does not terminate the execution of the SmartPacket (i.e. call halt() etc.) and the destination of the packet has been set by setting the instance variable Destination_Address then the default execution path takes over after the code in the exec() method is executed and the SmartPacket is automatically routed to its destination.
It is possible to create a new SmartPacket belonging to the group of the parent SmartPacket. In this case, the new SmartPacket can be injected into the network by calling the SendSmartPacket() method of the newly created SmartPacket.

How to create new, complex SmartPackets that are part of a group?
In most complex applications, a single SmartPacket cannot provide all the functionality. In this case, one needs to use many classes of SmartPackets, each implementing a piece of the functionality but are part of the same application framework. By default, when a user creates a new Smartpacket, it's type is derived by generating a cryptic hash of its structure. So if there are multiple Smartpackets that a part of the same application, then each SmartPacket will get a unique type. The problem with this is that these SmartPackets will not be able to interact with each other in the network because they have different types. (Actually they can but it will be in a unsafe manner because they have to use insecure global small state). One way to handle this is to create a base class that extends the KUSmartPacketV2 class or the ReliableCommFW class or whichever new framework class that the user has created. The base class then defines all the application SmartPackets as transient private members of the class. Override the writeObject() method in the base class and call the describeComponents() method to describe the members to the system. This enables all the SmartPackets belonging to the application to have the same type.


Send comments to Amit Kulkarni

1