Download [WORK] Writer 39;s Odyssey Subtitle

[Clorinda Manzer]

Table of Contents

• Odyssey
• Introduction
• CANEs
• Overview of CANEs
• CANEs Packet API
• CANEs Slots
• Declaring and Exporting Slots
• Raising Slots.
• CANEs Variables.
• Declaring Shared Variables in the Parent.
• Declaring Shared Variables in the Child
• Importing and Exporting Shared Variables
• Accessing Shared Variables
• CANEs Entry
• CANEs GetID
• Sending and Receiving CANEs Packets
• Sending CANEs Packets
• Receiving CANEs Packets
• CANEs Timers
• Setting a Timer
• Prototype for Timeout Handler Functions
• Canceling a Timer
• CANEs Logging
• CANEs Store
• Bowman
• Overview
• Channels
• Overview of Channel
• Channel API
• Channel Information
• Channel Creation
• Channel Modification
• Channel Selection
• Channel Subscription
• Aflows
• State-store
• Bowman Extension Mechanism
• Odyssey Packet API
• Generic Addresses
• Threads API
• Random Numbers
• Odyssey Time
• Registry for text interfaces
• Extensions
• Overview of Extensions
• Route Table Extension
• Data Structure of Routing Table
• Interface to the routing table
• Odyssey Code Loading
• Interface to address resolution
• Heavy Weight Timers
• Node Administration
• Abstract Link Manager
• The ARP service
• Abstract Topology manager
• Routing Table manager
• CANEs Signaling and User Interface
• Command Line Interface to Bowman
• Various notes on the distribution
• Variable scoping within CANEs
• Variable Sharing
• Packet Classifier
• Overview of Packet Classfier
• Packet Classification
• Packet Classifier API
• Notes on Shared Utilities
• Notes on the Odyssey code server
• Concept Index
• Function Index
• Variables Index
• Program Index
• Data Types Index
• The Odyssey Story

@title Odyssey @subtitle Version 1.3 User's Guide @author Odyssey Code GroupMy mind is going@dots I can feel it HAL to Bowman, 2001: A Space OdysseyCopyright (C) The Georgia Institute of Technology.

Introduction
• Odyssey : Top-level ArchitectureComponents
• CANEs : Execution Environment
• Bowman : Node Operating System
• Extensions : Runtime Loadable ModulesReference
• Administration : Node Administration Applications
• Distribution Notes : Various notes on the distribution
• Index : Cross-References

OdysseyIntroductionThe Odyssey active networking environment is an implementation of theDARPA active networking architecture ArchDraft. It consists oftwo major components: the Bowman Node Operating System and the CANEs execution environment. The software structureof Odyssey is shown in the Figure. Odyssey assumes a hostoperating system over which a node operating system is built.Execution environments and generic services that are likely to beuseful across environments (e.g. routing) are built using theabstractions provided by the node operating system; user code andparticular protocols are run as part of an execution environment.The Odyssey implementation is multi-thread safe and multi-processor capableand can utilize Solaris Real-Time Scheduling Extensions. The currentimplementation uses the POSIX threads library and runs as anuser-process above SunOS 5.5.1. environment in this paper. Itspreliminary performance results have been extremely positive.CANEs

Introduction:
• CANEs Overview: Overview of Slot Model Programming.API:
• CANEs Packets: CANEs Packets.Control:
• Slots: Exposing and Utilizing Slots.
• Canes Timers: Setting and Cancelling Timers.
• Variables: Sharing Variables.Data:
• Send: Sending Packets.
• Receive: Receiving Packets.Sundries:
• Entry: Initializing the Underlying Program.
• Logging : CANEs Logging.
• GetID: CANEs Flow Identifier
• Store : CANEs Flow Store

Overview of CANEsThe second major component of Odyssey is an implementation of the CANEsexecution environment (as described in DiAN, RaANP ). The Odysseyimplementation of CANEs executes as an aflow within Bowman and providescomplete support for underlying and injected programs. Both theunderlying and injected programs are demand loaded, dynamically. Theslot processing model described in RaANP is implemented; bothunderlying and injected programs can export slots, to which multiplesub-injected programs may be bound. The CANEs implementation alsoprovides mechanisms for variable sharing between programs exporting andsharing slots. The signaling message consists of a computation part(which we ignore here), and a communication part. The communicationpart of the message identifies the routing schema and topology for theuser. This provides information for theCANEs EE to establish the input and output channel plumbing for theuser's computation. C++ Linkage for underlying and injected within Odysseyprogram is now available. The CANEs library itself is included in anextern "C" block. CANEs Packet APISee section Odyssey Packet APICANEs SlotsIn this section, we describe the slot processing model for active networking.Composition in CANEs is achieved in two steps -- first the user selectsan "underlying program" that is executed on behalf of the user. Theunderlying program is offered by the node, and may have provableproperties.Depending upon the their needs, users may choose different underlyingprograms. The users then select/provide a set of "injectedprograms", which correspond to individual code modules, that can beused to customize the underlying program on a per-user basis.We introduce the notion of a processing slot---that localizes theprocessing of injected code. In effect, slots identify specificpoints in the underlying program where injected code may be executed.Slots are also the mechanism by which the underlying program assertsproperties that hold at the node.Like in an event-driven framework, injected code is "bound" tospecific processing slots, and becomes eligible forexecution when appropriate slots are "raised". Underlying programs in CANEs define and raise specific slots, and composite services are formed by binding user-specified code tospecific slots. More than one injected program may be bound to the same slot---the order of execution of instructions belonging to different injectedprograms bound to the same slot is non-deterministic.User-supplied code may raise slots during their own execution--thiscorresponds to recursive events (i.e. events raising their ownevents). Injected code have an uniform signature, and inter-modulecommunication is achieved via the node store.Forwarding functions would be typical examples of underlying programs.Depending on the user, and the network provider, there may be severalforwarding functions available at each node, each of which woulddefine a specific set of processing slots. The underlying program andthe composition technique is designed such that we can formally reasonabout the progress and safety of the resultant computation on a network-wide basis independent of theinjected code. Declaring and Exporting SlotsSlots must be declared and exposed to injected programs with thefollowing two macros. The argument slot_name for bothdeclarations can be any valid "C" variable name, it is opaque andshould not be interpreted in any manner. Its semantics are outsidethe "C" language. The variable should not be manipulated in any way,and should only be passed as an argument to canes_raise_slot.Note that there is no analogous "import_slot" function. Injectedprograms are "bound" to slots during the canes signaling phase.#define canes_slot(s) _canes_declare_slot(s)#define canes_export_slot(s) _canes_export_slot(&s, #s)Raising Slots.This function allows programs which are bound to a slot to execute.All injected programs bound to the slot s will execute concurrently.The parameter slot_id should be the same variable as was specifiedin the corresponding canes_slot, and canes_export_slotdeclarations. As a result of preprocessing those macro's, it is nowof type canes_slot_id.#define canes_raise_slot(s) _canes_raise_slot(s)CANEs Variables.An Import/Export mechanism follows which allows variables to beshared with injected programs bound to slots. In this mechanism,the parent is referred to as the underlying or injected programwhich exports slots, and the children are injected programs whichare bound to those slots.Variables are shared with children ONLY when they are exported bythe parent AND imported by the child. No variables of a child arevisible to the parent. If more than one injected program is boundto a slot and import a shared variable exposed by the parent,multiple references to the shared variable will exist. Each ofthese references will be updated synchronously.Declaring Shared Variables in the Parent.Parents declare shared variables using the following primitives:#define canes_shared_global(t, v) _canes_shared_global(t,v)#define canes_shared_global_per_flow(t, v) _canes_shared_global_per_flow(t,v)As an example, to make the unsigned long current_timevariable shared, it should be replaced by: @result@codecanes_shared_global(unsigned long, current_time); or by @result@codecanes_shared_global_per_flow(unsigned long, current_time);In the first case, there is a single current_time sharedvariable that will be synchronously updated for each flow as anythread writes into current_time. In the latter case, thereis a per flow current_time variable, and updates to it byone flow do not affect its value in another flow.The exporting program _must_ declare each shared variable as aglobal. (The reason being that stack allocated variables are notlikely to be around when they are eventually accessed by theinjected program) There are cases when global scope is notrequired -- when the exported is sure that all usage will occurwhen the shared variables are on the stack. There is a plausible(though somewhat cumbersome) scenario (as each time these sharedvariables are allocated they have to be exported and imported akinto the shmem publish/subscribe.Declaring Shared Variables in the ChildChildren declare shared variables using the following primitives:(The per-flow predicate and the type have to match for reference calls.)The referencing program may declare shared references withinwhatever scope is deemed useful. As noted, before each use,however, each reference must be properly initialized using theappropriate canes_import_xxx call.#define canes_referenced_global(t, v) _canes_shared_reference(t, v)#define canes_referenced_global_per_flow(t, v) _canes_shared_per_flow_reference(t,v)Importing and Exporting Shared VariablesThe exporting program must declare each shared variableas a global. The reason being that stack allocated variables are notlikely to be around when they are eventually accessed by the injectedprogram. There are cases when global scope is not required, when theexported is sure that all usage will occur when the shared variablesare on the stack. There is a plausible though somewhat cumbersomescenario: as each time these shared variables are allocated they haveto be exported and imported akin to the shmem publish/subscribe. Thereferencing program may declare shared references within whateverscope is deemed useful. As noted, before each use, however, eachreference must be properly initialized using the appropriatecanes_import_xxx call.canes_boolean_t canes_export_global_per_flow (char *name, canes_generic_t p);canes_boolean_t canes_export_global (char *name, canes_generic_t p);Polymorphic forms of these functions would have been nice. Eachshared variable must be explicitly imported by the injected programs.FWIW, there may be multiple references, each will be updated synchronously,and each reference only uses up some pointer space. Each reference mustexplicitly import the shared variable before use.canes_generic_t canes_import_global_per_flow (char *name);canes_generic_t canes_import_global (char *name);Accessing Shared VariablesEach reference to shared variables must be explicitly importedbefore use. While cumbersome, this will hopefully be beneficialas it requires the programmer of the parent program to thinkabout what is being exported. The variables exported are exactlythe amount by which the sandbox is legally opened by theparent program. Obviously, current non type-safe C allows forany program to wander around in memory and munge any part of coreit pleases, but that seems to be hard to check without run-time orstatic type checking. The following macros, which should be usedjust as the variable itself would be used, provide import and exportfunctionality:/* access exported variables */#define c_Ep(v) _canes_access_shared_per_flow(v)#define c_Eg(v) _canes_access_shared(v)/* access imported variables */#define c_Ip(v) _canes_access_referenced_per_flow(v)#define c_Ig(v) _canes_access_referenced(v)CANEs EntryEvery underlying program must have a function named _entry withthe prototype canes_program_t. When dynamically linked, this willbe the function called by the flow initializer. Both underlying andinjected programs have the same entry prototype:#define canes_underlying_program_entry_point "_entry"typedef void (*canes_program_t)(canes_flow_id_t f);CANEs GetIDReturns the unique identity of the thread within the CANEs environment.Note that this id is not the same as this flow's Bowmanaflow id.int canes_getid();Sending and Receiving CANEs PacketsSending CANEs PacketsThis call sends a packet pk of length len out thechannel ch_id, and returns the length of the packet sent. Thepacket is mutated and freed by a successful canes_send. Therefore packetmanipulation or copying of the data within a packet MUST occur beforea packet has been sent.canes_packet_length_t canes_send(canes_channel_id_t c, canes_packet_t **p, canes_packet_length_t l);Caution: This is a blocking call. A non-blocking version canbe made available if need be.Receiving CANEs PacketsThis call blocks waiting for a packet to arrive on the inputchannel. Upon arrival, the call returns the length of the packetreceived, pk contains the head from the input channel queue.canes_packet_length_t canes_recv(canes_packet_t **p);Caution: This is a blocking call. A non-blocking version canbe made available if need be.CANEs TimersSetting a TimerTimers can be set within any underlying or injected program. Thecanes_timeout function can be called to set the timer. Afterat least num_ticks ticks, function timer_f(arg) willbecalled unless the timer has been successfully cancelled. Theresolution (in ticks) is likely to be near 5000 usecs. num_ticksmust be given as integer values. The function returns a handle to thetimer established which is required to cancel timer.Prototype for Timeout Handler FunctionsThis is the function prototype for all timeout handler functions:typedef void (*canes_timer_func_t) (int arg);canes_timer_handle_t canes_timeout (canes_tick_t t, canes_timer_func_t f, int arg);Canceling a TimerIf an existing timer has not gone off, the timer can be canceledusing the timer handle th.int canes_timeout_cancel (canes_timer_handle_t th);CANEs LoggingALL text output should be done with the following canes_logfunction. This will print "format string", variables, in printf styleto the canes_output_file iff b is true. If 0 is returned,nothing printed.u_int canes_log (canes_boolean_t b, "format_string", variables...);Caution: This is a blocking call. A non-blocking version canbe made available if need be.CANEs StoreEach user flow is allocated a state store during flow initialization.Datum can be added to this store by the signaling message that startsthe flow.The per-flow store is accessed via the callscanes_boolean_t canes_put (char *k, canes_generic_t v);canes_generic_t canes_get (char *k);The canes_put call adds a datum to the store. The key for thedatum is the parameter k and the value is the parameter v.The canes_get call retreives an existing value from the store. Thekey is passed as the only parameter. This call will return NULL if the specified key does not exist in the per-flow store.Bowman

Introduction
• Overview of Bowman : Top-level ArchitecturePrimary Abstractions
• Channels: Communication
• A-Flows: Computation
• State-store: Memory
• Bowman Extensions: Loadable ModulesAdditional APIs
• Threads: Threads
• Packets: Packets
• Addresses: Generic Addresses
• Random : Random Numbers
• Time: Time
• Info: Registry for text interfaceReference
• Index : Cross-References

OverviewThe Bowman node operating system is built around three keyabstractions:

• Channels. A Channel is the primary abstraction for communication in Bowman . A channel is a communication end point; it consists of a set of protocols and optionally local and remote addresses. Channels export an interface for reading and writing data onto the channel. In each case, the data is processed according to the channel protocols, i.e., the data is framed with protocol-specific headers upon a channel write and conversely, protocol-specific headers are removed upon reading from a channel. The implementation of channels encapsulates all of the protocol processing required to implement individual protocols over each channel. Channels serve to decouple user computations from exactly how the node operating system implements particular communication protocols. Bowman exports interfaces to create, destroy, query and communicate over channels. Details of Bowman channels and the protocols implemented under Odyssey are discussed in Section\ref sec:channel .
• A-flows. An a-flow (1) is theprimary abstraction for computation in Bowman . Itencapsulates a set of processing contexts and user state. Eacha-flow consists of at least one thread and executes on behalf of anidentified principal (user of the system). Bowman providesinterfaces to create, destroy and run a-flows. Further, multiplethreads may be active within a Bowman a-flow -- the level ofconcurrency is user-selected. Execution environments may createa-flows per-user or may just create one a-flow (and not expose itsinternal per-user state to Bowman ; in such a case, the EE itself isjust one user to Bowman .
• State-store. The state-store provides a mechanism for a-flows to store and retrieve state that is indexed by a unique key. The Bowman state-store interface provides functions for creating, storing and retrieving data from named state-stores. Further, using the underlying state store mechanism, Bowman also provides an interface for creating indexed registries for arbitrary data types.

Though elegant, the channel, a-flow, and state-store abstractions arenot quite enough for a complete implementation of an active node.Interfaces to lower level mechanisms such as memory management,processing threads, synchronization primitives, and device input/ outputare required. Thus, Bowman is layered on top of a host operatingsystem that provides these lower level services. On the other hand, theBowman channel, a-flow, and state-store abstractions are too elementaryto be useful for most users. Thus, Bowman provides an extensionmechanism that is analogous to loadable modules in traditional operatingsystems. Using extensions, the Bowman interface can be extended toprovide support for additional abstractions such as queues, routingtables, user protocols and services.Channels

Introduction :
• Channel Overview : Overview of Channel Abstraction for communicationStructure :
• Channel Structure : Specification of the components of a channelAPI :
• Channel Information : Information about a channel
• Channel Creation : Creating a channel
• Channel Modification : Modifying the components of a channel
• Channel Selection : Choosing a channel based on requirements
• Channel Subscription : Subscribing to packets on a channel

Overview of ChannelChannels are an abstraction of the communication resources provided bythe node operating system in an active networking environment.The channels in Bowman are local to an active node -- they represent communication end-points. Communicationbetween nodes is accomplished via abstract links. An abstractlink is an association between a set of channels.Bowman channels are logical entities; i.e., there is a many-to-manymapping between the set of channels and physical interfaces at anode. Obviously, each data operation on a channel resolves to atleast one physical interface (2),however, the binding between channels and physical interfaces need not be pre-determined or static. Thus, channels serve to abstract theparticulars of available physical interfaces from all higher layers.

• Protocols Associated with each Bowman channel is a set of protocol functions that encapsulate the processing done as part of data transfer over the channel. It may be helpful to consider channel protocols as a traditional protocol stack, though the underlying implementation need not adhere to this structure. For example, a channel could be configured with theIP protocols much like the Internet protocol stack. Note that there may be an implicit order in the channel protocols, e.g., UDP data must always be encapsulated in IP datagrams. We do not, a-priori, enforce any particular ordering. Instead, we tacitly assume that the channel creation will fail if the set of protocols are ill-specified. Bowman channel protocols need not all be communication related -- it is possible to create channels that securely transfer compressed data by specifying, for example, theEthernet set of protocols (3). In general, the protocols specified on the peers of a channel should match; however, Bowman channels neither specify nor enforce this condition. Along with the protocols, all relevant protocol-specific parameters, including peer endpoint addresses, must also be specified when a channel is created. Bowman channels, in general, have both local and remote endpoint addresses specified; this, however, is not always necessary (e.g., see broadcast channels below).
• Type The channel type determines degree of connectivity, resolution to physical interfaces, and data direction for channels. The degree of connectivity is one of point-to-point, point-to-multipoint, broadcast. The choice of point-to-point channels are obvious; point-to-multipoint channels provide a mapping to MAC layer multicast (e.g. on Ethernet interfaces). Broadcast channels provide physical layer broadcast and are useful for auto-configuration of network nodes and for initializing certain network protocols. As mentioned above, channels are logical entities and are not mandated to be bound to particular physical interfaces. However, certain channels (e.g. broadcast and point-to-multipoint channels) must resolve to physical interfaces at channel creation time -- we term these absolute channels. Relative channels do not have an associated physical channel at channel creation time -- the upper layer routing and protocol stack selects a physical interface when data is transmitted on a relative channel. The selected interface for a logical channel may change during the lifetime of the channel: a point-to-point relative UDP channel may choose different interfaces at different times for the same address depending upon the state of IP routing tables. The channel direction is one of incoming, outgoing, or bi-directional.
• Attributes Associated with each channel is a named set of attributes. No specific attribute is necessary, and the set of attributes can change over the lifetime of the channel. For the most part, attributes are used by higher layers to select channels for data input. As an example, the UDP channel could have an attribute "Secure" to indicate that it may be selected for secure data transmission.
• Filters Packet filters provide a mechanism for classifying incoming packets. Bowman channels use user-specified filters to segregate and demultiplex each incoming packet. The filters are dynamic (i.e. the set of filters and filter expressions may be changed during the operation of the channel); Section section Packet Classifier describes further the operation of the packet filters.
• Status Bowman channels may exist without participating in communication. The channel's status determines whether it may be used to transfer data. Users can supply filters to channels that have been created but whose status is set to down; matching packets will be available when the channel's status is set to up.
• Queues Bowman channels support per-user, per-channel output queues. Per-channel queues are useful because channels eventually map to physical interfaces and per-channel queues make bandwidth allocation on physical links easier. Though not implemented, we envision a hierarchical scheduling policy in which each channel using a link is given a certain share of the link bandwidth; bandwidth allocated to the channel is then distributed to its users using the channel scheduling policy. An open research question concerns relative (unbound) channels: it is not clear how to efficiently guarantee bandwidth on the outgoing physical link to channels that do not resolve to the same outgoing interface for each packet.Bowman specifies per-user queues for the efficient support ofapplication-specific congestion-control and other active applications inwhich data for a particular user may have to be specially processed orevicted from a congested output queue.The channel schedule policy for queues is not specified, however thearchitecture document ArchDraft does suggest work-conservingqueuing policies in order to conserve node resources and maintainnetwork stability.
• QoS The quality of service parameter for Bowman channels is intended to provide per-channel per-user guarantees using queue scheduling policies. Currently, however, it is neither specified nor implemented.
• Access The access parameter for the channel provides a mechanism for implementing security policy on a per-channel basis. The current Bowman implementation does not identify security principals in the system and does not implement access restrictions.

Channel APIChannel InformationThe structure o_channel_info captures all the fields described in the previous section. This structure is used to define a channel duringcreation.typedef struct o_channel_info_t o_channel_type type; /* Type (Connectivity, etc.) */ o_channel_dir dir; /* Direction of flow of packets */ o_channel_status status; /* Alive (usable) or not */ o_channel_access access; /* Privileges */ o_channel_addr_list addr_list; /* Set of remote addresses */ o_channel_attr_list attr_list; /* Set of attributes */ o_channel_pattern pattern; /* Identify packets on this channel */ o_channel_proto_stack proto; /* Protocol stack */ o_proto_param param; /* Parameters for Protocol processing */ o_channel_info;Each of the fields in o_channel_info are described bycorresponding structures as follows:

@bullet o_channel_type: The generic "type" byte of a channel includes:
@bulletconnectivity@bulletplumbing@bulletOS support
typedef u_char o_channel_type;Allocation of the bits in the "type" byte and specific macros aredescribed in the header files "o_channel.h"@bullet o_channel_dir: Direction of the flow of packets through thechannel
@bulletBi-direction: either way@bulletUni-incoming-direction: this channel receives packets.@bulletUni-outgoing-direction: sends packets out on this channel.
typedef enum o_uni_incoming_dir, o_uni_outgoing_dir, o_bi_dir o_channel_dir;@bullet o_channel_status: Status to indicate whether the channel isalive or not. Even though a channel is created, it cannot be used unlessthe status flag is set. typedef enum o_up, o_down o_channel_status;@bullet o_channel_access: Access privileges to ensure security inmodifying the characterisics of a channel.typedef enum o_privileged, o_regular o_channel_access;@bullet o_channel_addr_list: A channel can be associated withmultiple remote end points and all their addresses are captured by thisaddress list. But in this release, this field has no significance as westore the addresses of remote end points in protocol parameters fields.typedef struct o_channel_addr_list_t generic_addr ga_list[_O_CH_MAX_ADDRS]; int num_addrs; o_channel_addr_list;@bullet o_channel_attr_list: Aflows access a channel by specifying anattribute. This list of attributes is used for channel selection.typedef struct o_channel_attr_list_t char name_attr[_O_CH_MAX_ATTRS][_O_CH_MAX_NAME]; int num_attrs; o_channel_attr_list;@bullet o_channel_pattern: A description of the link headers thatwill be used to divert packets to this channel. This pattern will be putin the demux right before the channel protocol processing.typedef struct o_channel_pattern_t char desc_filter[_O_CH_MAX_STRING_LEN]; o_channel_pattern;@bullet o_channel_proto_stack: The set of protocols that form acombination (stack) to do the processing of packets on this channel.typedef struct o_channel_proto_stack_t char proto_name[_O_CH_MAX_NAME]; o_channel_proto_stack;@bullet o_proto_param: This structure contains the protocol specificparameters used during the protocol processing especially during theencapsulation/decapsulation of the protocol headers. This structure isin the header file "".

Every channel in an Odyssey node has a corresponding entry in thechannel table that has the following type:typedef struct o_channel_t u_int id; /* Descriptor of the channel */ o_channel_info info; /* Characteristics of channel */ o_pf_handle pfh; /* Demultiplexing Handle */ o_prot