================================================================== RNA METAPROTOCOL (v1.0) http://www.isi.edu/rna $Revision: 1.16 $ $Date: 2009/01/05 23:38:46 $ ================================================================== This is the README for the source release of RNA Metaprotocol software. See http://www.isi.edu/rna for more information on RNA. RNA Metaprotocol is a stem cell-like protocol that adapts to a given context of operation. The aim of RNA Metaprotocol software is to take a step in that direction. This implementation of RNA Metaprotocol extends Click modular router software with additional modules and runtime composition capabilities. CONTENTS ========= 1 DISTRIBUTION Summary of the files that are part of this distribution 2 INSTALLATION & EXECUTION Instructions on installing RNA-extensions and execution 3 CONFIGURATION Discusses configuration file format 4 CODE 4.1 FILES 4.2 DESCRIPTION OF MODULES Summary of the code in the various files 4.3 MODIFICATIONS TO CLICK Changes made to Click router 5 METAPROTOCOL PATTERN LANGUAGE AND COMPILATION: Description of the language of the metaprotocol template and the parser written in Perl 6 INSTRUCTIONS FOR DEVELOPERS 7 BUGS/LIMITATIONS 8 FUTURE WORK Possible extensions ======================================================================= 1. DISTRIBUTION --------------- RNA is distributed a set of new files and modifications to Click modular router (http://read.cs.ucla.edu/click). CLICKDIR/LICENSE.RNA USC/ISI Licence for RNA-specific code CLICKDIR/Makefile.RNA Build Click to use RNA CLICKDIR/README.RNA This file CLICKDIR/CHANGES.RNA Changes since the last revision CLICKDIR/elements/rna/ RNA elements and metaprotocol CLICKDIR/conf/rna* Click configuration files that use RNA capabilities This release has been tested only on FreeBSD though it should work without minor modification on other UNIX platforms. ======================================================================= 2. INSTALLATION & EXECUTION --------------------------- Download the click source (version 1.5.0) and apply the metaprotocol match. Click source may be downloaded from the cvs site or from the standard distribution. $ fetch http://read.cs.ucla.edu/click/click-1.6.0.tar.gz $ tar zxvf click-1.6.0.tar.gz $ fetch http://www.isi.edu/rna/rna-metaprotocol-v1.0.patch $cd $patch -p1 < ../rna-metaprotocol-v1.0.patch $ make -f Makefile.RNA configure-rna $ make -f Makefile.RNA compile Execution is simple: $cd $./userlevel/click ./conf/ Often multiple configuration files may have to run to simulate multiple stacks. Most examples have a "right" and "left" click configuration files. The left process initiates the communication to the right. So [Terminal 1] $./userlevel/click ./conf/rna-XXX-right.click [Terminal 2] $./userlevel/click ./conf/rna-XXX-left.click Note the testing has been limited and that this is experimental capability. ======================================================================= 3. CONFIGURATION FILE --------------------- The configuration files use the same language as that of Click but with minor modifications.A fragment of the configuration file is shown below: ~~~~~~~~~ b1 :: Buffer(NAME 'B1 MODULE'); b2 :: Buffer(NAME 'B2 MODULE'); d1 :: Demultiplexor(NAME 'DEMUX 1'); m1 :: Multiplexor(NAME 'MUX 1'); r1 :: Metaprotocol(NAME 'MP1', ELEMENTS b1 b2 d1 m1, CONN false, PATTERN 'MIN', AUTONEGOTIATE true); ... -> [0] r1 [1] ->.... ~~~~ Several modules of various kinds are instantiated and provided to the Metaprotocol. The Metaprotocol may compose any subset or none of the element provided. The elements are not explicitly connected using the language provided by Click except the metaprotocol. The Metaprotocol has several parameters some of which are module-independent. These parameters are supported by the base class RNAElement and supported by all modules. They include: NAME : String - Human readable name for each module DEBUG : Bool - Enable debug messages for this module (default is true) PROCESS: Bool - Should initiate the composition process True by default with metaprotocol, false by default for other modules CONN : Bool - Mark this protocol as being connection-oriented (helps mostly with testing) ELEMENTS: Element list - Elements available for composition UPSTREAM: Element list - Upstream elements DOWNSTREAM: Element list- Downstream elements Helpful when there are loops (caused by the composition) and compound elements. Beyond these each module supports modules-specific parameters. Some of these are listed below. >> Metaprotocol: Basic implementation of the metaprotocol PATTERN: String - Initial pattern AUTONEGOTIATE: Bool - Enable automatic negotiation The PATTERN parameter specifies the initial pattern that must be executed by the metaprotocol. It does not, however, specify a particular final composition that must be reached. So this metaprotocol instantiates a subset of patterns selected from the many based on some internal strategy. The autonegotiate parameter tells the metaprotocol to negotiate with the peer once the protocol is instantiated. >> Buffer: Multi-purpose buffering module COPIES Send packet copies repeated? DELAY Enable delayed send (default = false; each packet delayed for a random time < some max ) MANAGEMENT Enable sending management packets (default = false) SKIP The number of packets between successive management packets (default = 5) >> Crypt: Symmetric cryptographic module KEY Symmetric key (32 characters in Hex with optional "0x" at the beginning) >> Multiplexor: Distribute incoming message from upstream into several streams STRATEGY Algorithm for distribution of packets >> FlexLink: Simulates a link with a specific loss ratio; can be used as a stand alone module or as part of a meta-protocol composition. LOSSRATE Fraction of packets lost >> Rexmit: Reliable ordered delivery service ======================================================================= 4 CODE ------ RNAElement is the base class from which most modules are derived. RNAElement itself is derived from the Element class of Click. In addition there are helper class to enable storage and retrieval of link and node state, and track the status of the composition. Metaprotocol and the modules that are composed by the metaprotocol are subclasses of RNAElement. Metaprotocol uses a template that consists of the pattern language and state objects. 4.1 FILES This section lists various files in the elements/rna directory and summarizes the content of each. // Basic RNA Element rnaelement.hh - Specifies the RNAElement class (derived from Click's Element class) rnaelement.cc - Main file that includes other RNA Element files rnaelement_links.cc - Management of creation and deletion of connections between modules rnaelement_messages.cc - Handle incoming messages (both data, control and management) rnaelement_neighbors.cc - Discover upstream and downstream elements rnaelement_parse.cc - Parse the input parameters rnaelement_handlers.cc - Call backs from Click router. rnaelement_control.cc - Control interface between modules (effectively between the protocol layers) rnaelement_ctlmsg.cc - Data structure passed between module while performing the control operations. rnaelement_linkstate.cc - Stores state associated with each link from a particular module instance has to other modules. This is internal to each module. The link may be intra-layer or cross layer. rnalement_connstate.cc - Connection state that is exchanged between layers and included in messages // Metaprotocol metaprotocol.cc - Metaprotocol implemented as a class derived from RNAElement class metaprotocol_state.cc - Stores and retrieves patterns metaprotocol_patterns.cc- Implementation of patterns metaprotocol_patterns_db.txt - Stored patterns file metaprotocol_patterns_db.cc - Output of the patterns file parser patterns_parser.pl - Patterns file parser (written in perl) // Modules that are composed by the metaprotocol shared_namespace.txt - Enums containing namespaces that are shared between protocols and across hosts. modules_crypt.cc - Implements a module that encrypts and decrypts traffic. Assumes a symmetric key and key specified using configuration interface. modules_buffer.cc - Implements a simple buffer that can optionally delay packets and generate management packets to the layers below modules_reorderbuffer.cc- Buffer extended with support for sequence numbers in header modules_multiplexor.cc - Multiplexor and demultiplexor of packets based on the modules_demultiplexor.cc packet header. Demultiplexor that supports registration of the demux patterns from the downstream modules. Mux can support multiple strategies for muxing (in theory) modules_pktsrc.cc - Wrapper around the packet generator that adds a RNA message header modules_flexlink.cc - Flexible link. A primitive module that can be configured to be lossy at a certain level modules_rexmit.cc - Reliable ordered packet delivery service. 4.2 DESCRIPTION OF MODULES -------------------------- This section summarizes the structure and function of various classes in the elements/rna directory. RNAElement: ---------- The RNAElement is the base class from which the metaprotocol and other modules are derived. It implements the shared functionality. RNAElement is a wrapper around the basic element structure provided by Click Element class. RNAElement adds: * Type - type of RNA element (e.g., BUFFER) * Configuration - parses commonly used parameters and arguments * Control interface - to communicate between RNAElements for discovery and state modification * Link management - addition/deletion of the links on the fly * Message flow - default algorithms to move data across modules; do pre and post processing of the messages. * Element management - maintain the list of elements * Template - the state and pattern management. Only metaprotocols use this capability. RNAElement supports an explicit control interface within and across protocols. The purpose is to allow discovery and coordination across layers. The coordination could be locally driven or driven by an entity performing the coordination. There are two control interfaces - synchronous and asynchronous. The synchronous interface is useful when the programming environment for the protocol is shared across layers. The asynchronous interface based on messages is useful when the programming environment is not shared. It provides a message based abstraction. Both are equivalent. The synchronous control interface consists of a generic control() function. Each control request consists of a message type (command and reply), operation type (configuration, connection, discover etc.), operation (link add, connection close etc.), and optional data. If the default control handler in RNAElement cannot handle the request, the request is handled by module-specific control handler. Link State: ---------- Each RNAElement, including the metaprotocol, maintains a list of links to other elements. This is necessary to foward message within and across protocols. A LinkState object is instantiated upon addition of a link during initialization period or later. The datastructure maintains information about the following: * Ports - the local and remote Click element ports * Element - a pointer to the element structure at the remote end of the link * Direction - the direction of traffic flow because Click links are unidirectional (they flow from the output port of a given element to the input port of another element) * [Optional] Linktype - which tells whether the link from the module goes to the metaprotocol element or another data processing element. * [Optional] Connection-orientedness : Whether the next layer is connection-oriented or not and if yes, whether the connection state has been obtained or not * Connection state - exported connection state from the next layer. Ideally this should be per-connection and not per-link. May be this should be an array. Messages: -------- There are three kinds of messages - data, control and management. Data messages flow between peers within the same layer. Control messages also flow across hosts between endpoints within the same layer but the data is intended for control and coordination purposes. Management messages flow within a single host between layers. The management messages are used to implement the asynchronous control interface between layers. There is no explicit new class associated with the messages. The Packet class of Click is reused. The header in the packet is used to carry the message type information. The header of each metaprotcol message includes the type of message (control, data or management), the sub-type (e.g., test and normal for data messages), and sub-type specific content such as length and pattern name. Packet annotation is used to convey connection state information across layers. The connection state is structured as a set of (variable, value) tuples that is discovered across layers. Metaprotocol: ------------ The Metaprotocol class is derived from RNAElement class and uses all of its capabilities. The main code rests in two files (metaprotocol.cc/hh). The metaprotocol implements: * Composition - execution of a selected pattern * Negotiation - exchange of control messages with a peer * Testing - testing the outcome of a composition The content of the negotiation (patterns) are managed by the metaprotocol state object (metaprotocol_state.cc/hh). The pattern functionality is implemented by a separate object (metaprotocol_patterns.cc/hh). State: This should be rightly called pattern manager. This state specifies: * Initial pattern * Possible next patterns given a position * Execute or cleanup an executed pattern * Tests the feasibility of a specific pattern The state is populated during compile time (for now). The patterns are specified in a separate file (metaprotocol_patterns_db.txt) that are precompiled (metaprotocol_patterns_db.cc) and incorporated into the state object at compile time. The objective of the negotiation process is to enable two endpoint within the same layer to agree upon a composition. This is achieved incrementally adding one feature at a time. The patterns are organized as DAG (directed acyclic graph) and the negotiation process walks down the patterns DAG in a synchronized fashion. The negotiation might result in backtracking as well. Undoing a pattern may be necessary in addition to doing. This in general requires several round trips but a production implementation may be able to make larger functional jumps. The main file (metaprotocol.cc/hh) implements the negotiation (initiate_negotiation(),negotiate_request(), and negotiate_reply()). In future the negotiation will be separated out because multiple negotiation strategies may have to be supported over time. 4.3 MODIFICATIONS TO CLICK -------------------------- Click is a powerful framework and the modifications are minimal. They are in two basic classes. First, click assumes that once the modules loaded and connected to each other, they remain unmodified with respect to internal structure. Click has extra tools to manipulate compositions once made but do not have that support in the core code. Minor changes were necessary to enable one module to be 'disconnected' from another module. A second function was written that tries to update the internal state of all the modules so that the modifications of the composition are 'committed'. This poses an interesting problem in that the composition is being modified by the composed elements. This naturally creates recursion and potential problems. Ideally Click should provide an interface to control the composition process but until then this is a stop gap arrangement. The files modified include lib/router.cc, lib/element.cc, include/click/element.hh and include/click/router.hh. Some changes to lib/* and elements/userlevel/* are intended to fix compilation issues that arose when the Click code is compiled without 64-bit support. 5 METAPROTOCOL PATTERN LANGUAGE AND COMPILATION ----------------------------------------------- A key challenge is to deal with the semantics of the inter-connection between modules. This information is specified in the patterns file provided to the meta-protocol. Why a certain protocol should be connected a particular way is related to the question of function and semantics that is beyond the scope of the pattern language. The pattern language specifies the patterns that are accepted by the metaprotocol. : # There are multiple namespaces and each namespace is a collection of # patterns. You can choose a given pattern as a starting point. COMMAND: NAMESPACE_CMD NAMESPACE_CMD: 'NAMESPACE' IDENTIFIER START_CMD: 'START' IDENTIFIER PATTERN_CMD: 'PATTERN' IDENTIFIER RULES COMMENT: ( /#/ | /^$/ ) # Rules form a given pattern RULES: RULE(s?) RULE: ( REQ_CMD | FOLLOWS_CMD | RENAME_CMD | CONF_CMD | CAPABILITY_CMD ) # Various types of rules REQ_CMD: 'REQ' ('MUST') IDENTIFIER VALUE(?) OP(?) FOLLOWS_CMD: 'FOLLOWS' IDENTIFIER CAPABILITY_CMD:'CAPABILITY' CAPABILITY_CHECK CAPABILITY_VAR TEXT CONF_CMD: ('CONFIG' | 'UNCONFIG') (ARG_CMD | LINK_CMD | CAPABILITY_CMD ) ARG_CMD: 'ARG' IDENTIFIER VALUE(?) TEXT TEXT LINK_CMD: 'LINK' ('ADD'|'DEL') IDENTIFIER VALUE(?) VALUE(?) IDENTIFIER VALUE(?) VALUE(?) KEYWORD(s?) CAPABILITY_CHECK: ( 'PRESENT' | 'ABSENT' | 'MATCH' | 'PROVIDE' | 'NOTPROVIDE' ) RENAME_CMD: 'RENAME' IDENTIFIER VALUE TEXT # Misc OP: ('>='|'<='|'='|'<'|'>') LOGICAL_OP: ('XOR'|'AND'|'OR') CAPABILITY_VAR:IDENTIFIER IDENTIFIER: /[A-Za-z_][A-Za-z0-9_]*/ KEYWORD: (SIMPLE_KEYWORD|RANGE_KEYWORD) SIMPLE_KEYWORD:('BIDIRECTIONAL'|'ALL') RANGE_KEYWORD: 'RANGE' VALUE '-' VALUE TEXT: /\S+/ VALUE: /\d+/ The perl script CLICKDIR/elements/rna/process_patterns.pl implements a simple recursive descent parser for the pattern language. This process may be invoked through the Makefile.RNA $ make -f Makefile.RNA patterns module namespace | | V metaprotocol_patterns_db.txt ----> patterns_parser.pl---->metaprotocol_patterns_db.cc The output is included during the initialization process of the metaprotocol template state. metaprotocol_state.cc: ... State::State(RNAElement *control_in, ....) { ... #include "metaprotocol_patterns_db.cc" ... } ... ======================================================================= 6. INSTRUCTIONS FOR DEVELOPERS ------------------------------ In order to understand/extend the code: 1. Experiment with basic Click (1.6.0) 2. Apply the 1.6.0 patch 3. Configure and compile the code again - this time using Makefile.RNA itself as mentioned above 4. Look through the rnaelement which is the base class for all other modules and metaprotocol. It handles the default control and data path functions of the modules. 5. Next look at metaprotocol.c, metaprotocol_state.cc and metaprotocol_patterns.cc 6. The patterns are stored in metaprotocol_patterns.db.txt that is processed by patterns_parser.pl. The result is metaprotocol_patterns_db.cc that is included in the metaprotocol_state.cc 7. Once the compilation is done, run an instance of click with 'right' and 'left' click configuration files from conf 8. The output will track the packets as they go up and down the metaprotocol. Some are control packets and other are data. It allows you to follow the activity as it is happening. You can map the output entries to specific modules and specific actions being taken. This is useful mostly for debugging purposes. The application is still under development. 9. A new module can be added by copying and editing the code from an existing module. Make sure that the name is also added to the shared_namespace.txt and rnaelement_ctlmsg.c. 10. Follow the composition process closely - to the debug messages that indicate how one module is linked to another module. The message forwarding logic also prints out the incoming and outgoing links between modules. Thats the place to look. 11. Edit metaprotocol_patterns_db.txt if you would like options for composition. If multiple compositions are feasible, note that there is no way in the existing system to force one path being picked. ======================================================================= 7. BUGS/LIMITATIONS ---------------- >> Error message: ::class_name method malformed This warning is printed by click-buildtool that parses the files for sanity check. It assumes that class_name() method returns a fixed string. RNA elements call the default_class_name() function in the base class. This is not a critical error. The work around is to try compiling again. >> The compilation process terminates with "*** Error code 2" Workaround: Try compiling again. $make -f Makefile.RNA compile >> Only push interface supported Only push interface is supported right now. Pull interface is not fundamentally different in terms of the functionality except the RNAElement structure must be generalized a little more. >> When I execute ./click ./conf/ I see >> messages like this: [MP2] RNAElement::push: 29 | b02000b0 2000b020 00080000 00b02000 b02000b0 2000aaaa aaaaaaaa aa [MP2] Metaprotocol::push_data - received a data message [MP2] Metaprotocol::push_data - Normal data. Pushing to intra-layer module. [MP2] RNAElement::push_data(port = 1) [LINK] <> [MP2 local, 1 port] <- [UNKNOWN remote, -1 port]] [MP2] RNAElement::push_data inter-layer message [MP2] RNAElement::select_outgoing_link (upstream, layer sensitive, intra-layer, agnostic remote, remote unknown, conn state not required) [MP2] open_connection Entry [LINK] <> [RNAElement::open_connection local, 3 port] -> [B2 MODULE remote, 1 port]] [MP2] open_connection: Found 0 downstream elements [MP2] open_connection Exit [12] Sending packet to: [LINK] <> [MP2 local, 3 port] -> [B2 MODULE remote, 1 port]] The current release has debug messages enabled mostly because the runtime construction of the metaprotocol and message flow is being debugged. This is not a "production" release in that sense. >> Static template Patterns are included during compilation. Future work will make the patterns loadable at runtime. >> Explicit specification of upstream/downstream nodes The nodes may require an explicit specification of upstream and downstream elements. This is useful because the metaprotocol may create loops - depending on the programming framework. >> Limited wild card support Only one wild card is supported in any pattern. Support for multiple wild cards will be added in future. For example if multiple buffers must be incorporated into a mux-demux system, then the meaning of the following line is that two buffers must be connected to the multiplexor. CONFIG LINK ADD MULTIPLEXOR 0 BUFFER 0 2 On the other hand, the following instruction means that first two buffers must be disconnected from the multiplexor. UNCONFIG LINK DEL MULTIPLEXOR 0 BUFFER 0 2 Fine grained control and multiple wildcards will be supported in future. >> UNCONFIG ARG not effective UNCONFIG supports only LINK commands for now. UNCONFIG ARG will be added in future. >> When sending test reply and intra-layer links are found, the message is sent on the cross-layer links. A check is required to see if the protocol has not composed any elements at all or if that composition has failed for some reason. >> When the patterns specifies a prerequisite but does not use it, in the example shown below, negotiation fails. PATTERN MIN REQ MUST BUFFER 1 CAPABILITY PRESENT CONNECTION_LESS The test messages look for intra-layer path through the buffer. When no such path is found, the packet is dropped. A sanity check must be added to the parser to check for the consistency of the pattern specification. The same consistency check must be performed while loading in the pattern. ======================================================================= 8. FUTURE WORK -------------- 1. Runtime parsing. The parsing of the patterns is currently a compile-time operation. The parser has been written in Perl. Making this process a runtime operation by embedding a parser into the metaprotocol enables dynamic loading of the patterns file and learning of the patterns across hosts. 2. Extensions to the language The language described above is still primitive. Possible extensions include more expressive patterns with support for notions such as atleast or atmost, a language for testing, 3. Context-driven composition A decision process is required to bridge the information about the context of operations and the final goal of the protocol. 4. Multiple host configurations Multiple peers e.g., any kind of algorithm that involves multiple parties such as routing, filtering etc. In this case the design point is obtained from the peer and it is relatively fixed. New design points may be propagated accounting for disruption. 5. Check multiple possible compositions Exchange a set of possible next compositions instead of one at a time. This is a simple extension and should be supported in future. 6. Support for multiple negotiation strategies Currently the metaprotocol supports only one kind of negotiation style (simple two-way negotiate + test). Others may be necessary/interesting such as those with multilevel backtracking and with memory. 7. Dynamic instantiation of modules This enables further simplification of the configuration files but requires modifications to the Click core. 8. Add consistency checks in the pattern parser as discussed in the bugs section. Also add consistency checks across patterns. If a previous pattern does not have the links that are being manipulated by a given pattern, an error should be flagged. The parser must have an internal model of protocol and verify the model as it parses the modules. 9. Patterns learnt from peers are not stored. For now, the metaprotocol patterns are incorporated into the metaprotocol during the compile time. Patterns can be transferred during negotiation or later but 10. Negotiation in each instantiation is inefficient. The result of past exchanges may be stored and retrieved to improve the efficiency of the exchange. 11. Support for multihop For now the implementation supports only two protocol endpoints. It can be extended to add support for multiple hops. There are two challenges in multi-hop. First, the metaprotocol becomes multiported making the outgoing link selection dependent on the content. Second, endpoints will be at different starting points during negotiation.