Computation framework for an extensible network router ECSL

A Computation Framework for an Extensible Network Router:Design,Implementation and EvaluationPrashant Pradhan Tzi-Cker ChiuehComputer Science DepartmentState University of New York at Stony BrookStony Brook,NY11794-4400prashant,chiueh@AbstractDynamic addition of computation in the interior of the network holds significant promise for improving overall end-to-end application performance,either by exposing and exploiting global network context,or by placing functionality strategically within the network.This observation has motivated the study of extensible router architectures,especially for routers at the network edge.In this paper we present and study a simple,but powerful framework for composing and performing compu-tation in an extensible network router.The key design goal of the framework is to provide a router extension mechanism that does not compromise safety and performance of the system in the face of dynamic extensibility,while allowing performance isolation betweenflows that have computation interposed in their datapath.The framework achieves these goals through a combination of intra-address space protection,explicitflow context and CPU scheduling.Wefirst identify and isolate a minimal set of functions that form the router’s core.A set of abstractions is then presented,in terms of which computation is composed and resources allocated.A set of services exposed by the core is then presented,that forms the mechanism for composing and carrying out this computation.Asynchronous controlflow and explicitflow context allow the core to run a dataflow-driven CPU scheduler that controls the progress of computation in the system in accordance with the perfor-mance requirements offlows,and avoids redundant scheduling decisions.We present an implementation and performance evaluation of the proposed framework to put the design decisions in context.1IntroductionTraditionally,the design of data networks has been based upon the end-to-end argument[1],which argues for simplicity in the network core and complexity at the end hosts.The success of this design principle is brought out by the rich suite of network applications enabled by this simple architecture,and the success of end-to-end algorithms,like TCP congestion control,in maintaining network stability.However,it is being realized that significant performance optimizations and/or richer functionality are enabled by placing computation strategically within the network.For instance,congestion state sharing[2]at the portal router of an intranet allows TCP connections to share network congestion state previously probed by other connections sharing the same bottleneck link,thus significantly improving short TCP connection throughput.Similarly, stream’thinning’using media transcoding[3]and efficient use of network resources by deploying multicast,are examples where placing computation strategically within the network can enable new and useful applications.However,the transition from a simple network core to a functionally richer,dynamically extensible core must be made carefully so that the desirable features of the existing design are preserved.A desirable requirement for such a transition is to isolate the core router functions from the computational framework supported by the router.Such isolation allows the performance of network traffic that does not require high-level computation,to stay unperturbed by the presence of computation in the router,thus keeping the simple forwarding abstraction intact for such traffic.A secondary issue is that of providing good throughput and performance isolation even toflows that require computation.While performance isolation can be provided through abstractions such as explicitflow context,the level of forwarding performance achievable dependsupon the extension and invocation mechanism used.In the context of general-purpose operating systems,certain extension mechanisms provide a tradeoff between the level of safety provided and the performance achieved.Isolated address spaces and in-kernel modules form the two extremes of this spectrum.An ideal mechanism,that of language-based protection [4],affords good performance as well as safety if the compiler can be trusted,and the router implementation as well as the extensions are written in a type-safe,modular language.Since safety of the router’s core functionality is a key concern,the only applicable extension mechanisms are those that provide strong protection guarantees.Thus,the need for isolation of the router’s integrity as well as performance dictates that the extension mechanism should be able to provide performance protection through appropriate resource scheduling,as well as memory protection through a safe extension mechanism.Beyond simple isolation betweenflows,a desirable goal is that of scheduling computation in the router intelligently so as to match the computation requirements offlows to their network-level delay and bandwidth requirements.Without such a provision,true end-to-end guarantees can not be provided toflows that require computation in their datapaths.This calls for extending the sophistication of the scheduling mechanism further,to provide performance guarantees toflows or aggregates offlows.In this paper,we present the design,implementation and evaluation of an extensible router operating system that attempts to address these requirements.Wefirst identify a small set of primitives that provide the router’s simple forwarding func-tionality,and isolate them in a protected router core.The primary intent of the extension framework then,is to allowflexible composition of computation in the router while providing memory as well as performance protection to this core.For this purpose,we proceed to define a set of abstractions,vizflows and safe extension functions,in terms of which computation can be composed and resources can be allocated.Flows are computation contexts,that would typically translate to sets of packets bound to a particular computation.Safe extension functions provide the required memory protection to the core with low invocation overhead.The mechanism for composing computation and achieving desired controlflow is then presnted in the form of a service interface that the core exposes for extension functions to use.Given a computation framework,performance protection is still not guaranteed to the core from runaway extensions. Moreover,as mentioned above,it is desirable to extend end-to-end performance guarantees even toflows that require com-putation in their datapath.These requirements are addressed using a CPU scheduler that performs two key tasks.Firstly,it provides performance isolation to the core by prioritizing core router functions over extension functions.Secondly,it allo-cates the CPU betweenflows in such a way as to match theflows’computation requirements to their link-level performance bounds.A key feature of the controlflow is that all controlflow is asynchronous.Explicitflow context and asynchronous controlflow allows us to use a dataflow-driven CPU scheduler that avoids redundant scheduling decisions while maintaining tight control over CPU allocation.We discuss the implementation of this framework on our chosen hardware platform,viz the Intel IA32,highlighting some important details pertaining to preemption and scheduling of extensions.Finally,we perform performance evaluation of a prototype system that implements this framework,quantifying the impacts of the various design decisions we have made.2The Minimal RouterThe router core,by itself,is a complete minimal router.It implements the basic datapath functionality required from a router.We identify three functions that the minimal router needs,viz classification,data forwarding,and link scheduling1.Classification imposes structure on the raw data stream seen by the router.A classification operation on a data packet tells the router how to process the packet,by mapping it to aflow.Aflow may be one of several real-timeflows,a per-output interface best-effortflow,or one of several computation contexts in the router.Real-time and best effortflows are directly processed by the link scheduler running on their respective output interfaces.Thus,the result of the classification operation for packets belonging to theseflows is some link scheduler queue.Packets bound to computation contexts must be handed over to the some function that is part of the computation framework implemented on top of the core.All extension function invocations in our framework are asynchronous.Hence,such packets are placed in per-flow2.queues and function invocations are made by the CPU scheduler in accordance with its scheduling policy.Thus,the result of every classification operation is a queue.In case a target queue overflows,the classifier drops the packet.Flows are responsible for dimensioning their bufferpools and computation reservations appropriately to avoid drops.All queues in the system are based upon a lock-free data structure explained in[5].The classification operation uses a set of classification rules,which match afixed number of packetfields against constants or ranges of constants3.If a rule involves matchingfields apart from thisfixed set offields,further computation,in an extension function,must be performed to fully classify the packet.As an example,a rule might match the source address field of a packet with a constant and the source portfield with a constant range.There are two parts to the classification operation,viz extracting the values of thefields from a packet,and given these values,looking up a search data sructure to make the classification decision.For thefirst part,the classifier must understand sufficient protocol specifics like fragmentation and variable-sized headers,that would allow it to extract the values for its chosenfields.For the purpose of lookup,if the classifier acts uponfields,thefield values extracted from a packet define a point in-dimensional space, and the rules define-dimensional hypercubes[6].A geometric point location algorithm is then performed in dimensions to perform the lookup.For our core implementation,the classifier understands IP fragmentation and variable length IP and TCP headers(with options).Thefixed set offields that are used in the rules are the protocol,the source and destination addresses,and the transport protocol ports,yielding.In some network interface architectures,classification may be performed on the receiving interface[5],thus making the classification operation independent of the load on the CPU.In the absence of such a provision,the CPU must serve classification requests with higher priority compared to otherflow-related computation.While this can easily be achieved by performing all classification in the context of interrupt handlers,interrupt overhead may severely degrade packet throughput. In our design,we do not interrupt the CPU upon arrival of every packet,but instead rely on the scheduler to prioritize classification requests over all other computation,whenever it gets control.Once a classification decision has been made for a packet,it must be posted to the queue that is the result of the classifica-tion.While in a simple router like our prototype,the forwarding operation is a simple enqueueing operation,the forwarding operation becomes more interesting in a distributed router architecture[5,8,9],where some queues may be remote,i.e.not accessible to the classifier for direct read/write.Again,it might be possible to avoid CPU intervention for remote writes by using peer-to-peer data transfer operations[5]between network interfaces.However,we assume that such a provision is absent and that the forwarding operation is performed by the classification function itself.Priority and weighted fairness are two key scheduling primitives which are supported by the core link scheduler.Weighted fairness is supported in accordance with the weighted fair queueing formulation of[10].Prioritized traffic,when contending for the link,takes precedence over traffic using weighted fairness.All prioritized traffic is servedfirst-infirst-out.It can be contended that link scheduling is itself a candidate for extensibility.However,note that the scheduling performed by the core can be completely overriden by a single extension function which allflows use to send packets to the link. The function can then implement its own scheduling algorithm,and expose only a singleflow to the core’s link scheduler, effectively replacing the link scheduling algorithm entirely.The important point here is that the core’s scheduling algorithm is provided as an optimized common case that provides a fairly general scheduling abstraction(that of priority and weighted fairness).The scheduling algorithm is a cycle-based scheduling algorithm,operationally much like a weighted round-robin sched-uler,but with tighter performance bounds[11].The cycle-based operation implies that the scheduler is invoked at well-defined time instants,at which it makes a scheduling decision and sets up data transfers for the next cycle.The data transfer can then proceed in parallel with any other computation in the system till the next cycle.The desirability of this scheduling mechanism is that it can execute in the context of a relatively coarse-grained timer interrupt.This is in contrast to running in the context of a transmit interrupt for every packet sent on the link.3Abstractions for Computation in the Minimal RouterIn this section,we present the key abstractions in terms of which all computation is composed and carried out.Flows are contexts for carrying out all computation in the router.Flows are also used as units of resource reservation.ExtensionCFigure 1.Interpretation of the bandwidth reservation parameters.functions are stateful functions that can be invoked in various flow contexts to carry out computation.Since extension functions are stateful,they can maintain per-flow state and thus carry out flow-specific computation in different flow contexts.Extension functions may be co-located with the core,in which case the core is provided with memory protection from extension functions.Before introducing flows and extension functions,we present processes ,akin to processes in a general-purpose OS,that are required to define the notion of ownership for flows.Processes are identical to processes in a general-purpose operating system,except for the following important difference :a process is not the basic schedulable unit for the purpose of CPU scheduling.Instead,a flow is the basic schedulable unit.Thus,a process that allocates multiple flow creates multiple schedulable entities.Processes are used in our framework for two reasons.First,the simplicity and prevalance of the isolated address space model allows us to carry over legacy applications that do not need the highest level of performance,for example,routing protocol code and other kinds of control path processing.Secondly,a notion of flow ownership is required for allocating flows,reserving resources on their behalf,and for setting up resource sharing between flows.Resource sharing allows certain flows to statistically multiplex a subset of their resources,while still maintaining the abstraction of independent threads of computation for each flow.We use processes as owners of flows,both for flow administration,and for setting up resource sharing,in which case processes can exchange sharing rights for the resources of flows they own.A flow represents a single context for computation and a single unit of resource allocation.All computation in the router proceeds in the context of a flow,just like the context of a process is used to carry out all computation in a general purpose operating system.Since this context is understood by the core,it can not be forged for the purposes of scheduling and resource allocation.Every flow is associated with three kinds of resources :CPU bandwidth,link bandwidth and a buffer pool.The buffer pool is a chain of free buffers,for which the classifier is the consumer (by using up free buffers for posting packets to the flow),and extension functions are the producers (by freeing up buffers after computation or forwarding).CPU and link bandwidth use a common reservation model that allows decoupling of delay and bandwidth requirements.Resources can be shared between flows,to statistically multiplex CPU and link resources,or to simply share data when the functions on the flow’s control flow path are in different protection domains.These are explained in the following sections.3.2.1Reservation ModelLink and processor bandwidth reservation requires three parameters :delay (),average bandwidth (),and an averaging interval ().This reservation corresponds to a channel as depicted in figure 1,where is the total link or CPU bandwidth.The CPU or link scheduler attempt to serve computation or data transfer requests with an instantaneous bandwidth of .Moreover,at mostunits of work will be done by the scheduler for this flow over a time period .”Work”is in terms of bits for the link and cycles for the CPU.Both the CPU and the link scheduler are work-conserving schedulers.This means that any bandwidth not used by a flow is available to other flows that coule use extra bandwidth.Though a CPU reservation and a link reservation can be specified independently for a flow,it would be natural to havea relationship between them.Thus,for a flow requiring a link bandwidth of,that requires cycles worth of processing per packet,meaningful link and CPU reservations would be anddesirable that the choice of,or slack management be done by the system.Algorithms for doing so are a topic of our further study.3.2.2Sharing ResourcesIn many situations,flows may need to selectively share their resources.Such a need arises when independent computation contexts are still needed,but it is natural to specify an aggregate resource requirement.For example,suppose that we define two classes of traffic through a router,viz HTTP traffic and FTP traffic,and it is desired to share an output link in such a way that each class should receive half of the link bandwidth.If the demand from any class does not saturate this share,it goes to the other class.However,each class may want to statistically multiplex its share among itsflows,even though each HTTP or FTPflow needs independent computation context.Sharing link resources in this case allows the link scheduler to maintain only two queues,instead of several per-flow queues.As another example,consider a layered multicastflow[12]going through a yeredflows are mediaflows that consist of a set of layers,where the base layer represents the least resolution and lowest bandwidth,and additional layers can be used to improve the resolution at the cost of extra bandwidth.Theflow fans out,in the form of subflows,to a subset of router interfaces,depending upon the receiver distribution downstream.Since layer addition and dropping[13](in response to changing available bandwidth)must be done for every subflow independently,independent computation contexts are needed for every subflow.However,all the subflows as well as the sourceflow can share the same buffer pool,which would consist of data corresponding to various resolutions that can be picked as needed by each subflow.Further,assume that there are several senders to this multicast group,of which only one can be actively sending at a time,but each sender needs independent contexts within each subflow.In this case,subflows can be further split into per-sender subflows,but they can share an aggregate bandwidth requirement equal to the maximum of the sender rates4.It is important to note that resource sharing is possible on a per-resource basis,rather than on an”all-or-none”basis. Moreover,note that sharing of link and CPU bandwidth decouples the need for independent computation contexts from the need for independent scheduling state.While the former is dictated by the most natural way of writing aflow application,the latter is dictated by the application’s semantics.The mechanisms for setting up resource sharing will be presented in section 4.4.Extension functions are simple non re-entrant functions that can retain state across invocations.Each function has a well-defined interface that yields a signature for the function,which is a hash of the function name and the types of its arguments. The signature provides a global naming mechanism for the functions.We assume for simplicity that signatures are unique. Functions are registered with the core using their signature,which allows the core to provide a naming service for these functions.Extension functions can be placed in a process address space,or in the core’s address space.In the latter case,care must be taken to provide memory protection to the core from potentially misbehaving functions.For the processor architecture (x86)that we use,it is possible to associate privilege levels with segments of the virtual address space.When code lying in a segment is invoked,it executes at the privilege level associated with the segment.Such code is prevented,through checks performed entirely in hardware,from accessing code and data lying in segments at higher privilege levels.Thus,extension functions co-located with the core are placed in a lesser privileged subset of the core’s virtual address space.Co-locating extension functions with the core has several advantages.Firstly,the core’s virtual address space is global,in the sense that it is shared among(though protected from)all process address spaces.Thus,co-location allows the extension functions,and the state they maintain,to be shared by multipleflows without switching address spaces.Secondly,co-located extensions can invoke other co-located extensions more efficiently by avoiding address space switching.All function invocations are performed in the context of someflow,but extension functions are not bound to any specific flow.Since functions can maintain state across invocations,it is possible for a single function to compute on behalf of severalflows,by maintainingflow-specific state.This provides the basic mechanism through which differentflows share state.Another pont to be noted is that since the computation on behalf of aflow may be done by several extension functions, and different functions may lie in different protection domains,there is no single protection domain in which theflow stack can be placed.Thus,even though it is natural to maintain one stack per computation context,and hence perflow,we must maintain stacks per extension function.4Composing ComputationWe now describe the mechanisms provided by the core to compose computation in the context offlows.Before describing the service interface that the core exposes for this purpose,we describe the controlflow and function naming mechanisms.To perform computation in aflow context,an invocation must be made on thatflow.Every invocation on aflow is asynchronous and multiple invocations on aflow are ordered sequentially.Everyflow must specify thefirst function that should get control when an invocation is made on theflow.Control is passed between functions using an explicit asynchronous invocation,using a post()service exposed by the core.Such an invocation takes a function,a targetflow context and a set of arguments as parameters.If the targetflow context is different from theflow context in which the invocation is made,the invoked function runs in the targetflow context. The invocation is asynchronous in the sense that the actual invocation happens when the scheduler picks the targetflow for execution.The core may also set up an implicit control transfer to aflow using a binding through the classifier.Recall that a classification rule binds a set of packets satisfying some criterion to aflow.Thus,when the classifier classifies a packet as belonging to aflow,and posts it to a per-flow queue,an implicit invocation has been made to thefirst function of theflow’s control path.Thus,it would be typical for thefirst function invocation for aflow to be made implicitly through a binding, whereas subsequent invocations,made by the functions in the controlflow path,will be explicit control transfers.Given a mechanism to carry out controlflow,functions need to name other functions to pass control to.For a static set of functions,this naming is in the form of function addresses generated by a compiler.However,in a framework with a dynamic function pool,naming has to be done at composition time,or at run time,if the controlflow path can dynamically change.As mentioned before,functions register unique signatures with the core.This allows a function to dynamically query for other functions using their signature.If the queried function has been registered,the core provides a handle to the queried function,which can be subsequently used to make an invocation to it.If function names(and hence their signatures)have semantic connotations,the naming service can provide highlyflexible and dynamic controlflow.Thisflexibility comes from the ability to construct function names using the functionality they implement,and to use these names to query and invoke them.For example,if encryption functions have a naming structure of the form ENCRYPT name,a function can choose between various encryption algorithms like DES or RSA at run-time and invoke the more desirable one,if both are present.Dynamic resolution of function names allows a lot of flexibility sinceflow data could provide input for constructing names.Of course,the naming convention and the exact semantic meanings of names must be agreed upon before putting this functionality to practical use.What our framework provides is a generic mechanism for doing name resolution at function run-time.Recall that resource sharing is supported betweenflows on a per-resource basis.To setup resource sharing,flows should be able to name otherflows’resources.Flow identifiers,like process identifiers,have global scope,and hence they provide a simple naming mechanism.To allow aflow’s owner to exclusively control the sharing of its resources,we use a simple capability-based mechanism.For everyflow and every resource of theflow,the core maintains a list offlows that can share these resources.The owner sets up this list using one of the core’s services,viz allow().To request sharing of a particular resource,aflow may specify the id of theflow and the resource type that it intends to share,instead of a complete reservation spec.If the access list for thisflow id contains the requestingflow,resource sharing is set up by the core.The exact mechanism to setup the sharing is resource dependent.If the sharing is for link or CPU bandwidth,theflows simply share the same scheduler queue.If it is for the memory pool,the buffer pools of bothflows point to a single set of buffers. This further requires setting up a shared set of pages which can be accessed by the functions of bothflows.Some applications will encode permission and sharing behaviour in their logic.For instance,suppose a multicast appli-cation wants to share resources between one sourceflow and subflows.It can do so by creatingflows,and then adding each of the subflows to the access list of the sourceflow.In other cases,theflow owner and the desiring sharer can6use application-level protocols to negotiate sharing.Again,our intent is to provide a mechanism for setting up sharing,rather than dictating how theflows determine what criterion to use to allow sharing.In this section,we list the set of services that the core exposes for composing and carrying out computation in the router. Since the description is in terms of function prototypes,it would be useful to describe theflow and function structure briefly.A list offlows is maintained,in which eachflow is characterized by its identifier,its owner,a list of pending invocations, a”first”function for implicit invocation,CPU scheduler state and two reservation specifications using triples as explained in section3.2.1.As discussed in section4.3,for resource sharing a reservation specification could be replaced by the the id of anotherflow.A list of extension functions is also maintained,which are further placed either in a process address space,or within one of a set of core-resident,lesser privileged,segments(called psegs).Functions are characterized by their signature,their entry point address,a kernel stack and an extension stack.The need for two separate stacks is explained in section6.Given the structure of the key units of the computation framework,we now proceed to describe the service interface.1.flow flow(flow f)This function creates aflow using the parameters specified inflow structure f and returns a handle to theflow that can be used for subsequent calls pertaining to thisflow,or for setting up resource sharing.2.void allow/disallow(int sharer,int which)This function adds or deletes theflow with id sharer to the access list of resource which,in the callingflow.3.pseg pseg(pseg p)The function is used to create a lower privileged segment in the core’s address space.The argument to this function is a pseg structure,which specifies the size of the desired segment,and some object code(an ELF binary in practice).The object code contains various extension functions that are going to reside in this pseg.This function returns a handle to the inserted pseg.4.function function(psegpseg service,and provides information to the core(via structure f)about the location and signature of some function in the pseg’s object code.The core then registers this function and its signature,and sets up the extension and kernel stacks for this function.In case the function resides in a process address space,it must specify its own stack in the function structure.The core still sets up the kernel stack for the function.5.void post(flow handle g,void*arg)The post function provides an explicit,asynchronous invocation mechanism to invoke function g inflow context f.arg contains the arguments for the called function.”Syntactic sugar”can be added on top of the post()service to have it formulate arg on its own by pulling data from the caller’s stack.However,we do not use such a form in our description.6.void bind(flowhandle resolve(signature s)This function is used to query and extract a function handle using the unique signature s of the function.8.void timer(interval t)A timer facility is also one of the core’s services,to support functions that use real time5.Thefiring of the timer causesthe core to post a timeout argument to theflow in whose context this call was ing this function,aflow can。