ForCES Model Extension
draft-haleplidis-forces-packet-parallelization-00

Abstract

Forwarding and Control Element Separation (ForCES) defines an architectural framework and associated protocols to standardize information exchange between the control plane and the forwarding plane in a ForCES Network Element (ForCES NE). RFC5812 has defined the ForCES Model provides a formal way to represent the capabilities, state, and configuration of forwarding elements within the context of the ForCES protocol, so that control elements (CEs) can control the FEs accordingly. More specifically, the model describes the logical functions that are present in an FE, what capabilities these functions support, and how these functions are or can be interconnected.

Many network devices support parallel packet processing. This document describes how ForCES can model a network device's parallelization datapath.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http:/⁠/⁠datatracker.ietf.org/⁠drafts/⁠current/⁠.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on April 10, 2013.

Copyright Notice

Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http:/⁠/⁠trustee.ietf.org/⁠license-⁠info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Terminology and Conventions
• 1.1. Requirements Language
• 1.2. Definitions
• 2. Introduction
• 3. Packet Parallelization
• 4. Parallel Base Types
• 4.1. Frame Types
• 4.2. Data Types
• 4.3. MetaData Types
• 5. Parallel LFBs
• 5.1. Splitter
• 5.1.1. Data Handling
• 5.1.2. Components
• 5.1.3. Capabilities
• 5.1.4. Events
• 5.2. Merger
• 5.2.1. Data Handling
• 5.2.2. Components
• 5.2.3. Capabilities
• 5.2.4. Events
• 6. XML for Parallel LFB library
• 7. Acknowledgements
• 8. IANA Considerations
• 9. Security Considerations
• 10. References
• 10.1. Normative References
• 10.2. Informative References
• Authors' Addresses

1. Terminology and Conventions

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

1.2. Definitions

This document follows the terminology defined by the ForCES Model in [RFC5812]. The required definitions are repeated below for clarity.

FE Model - The FE model is designed to model the logical processing functions of an FE. The FE model proposed in this document includes three components; the LFB modeling of individual Logical Functional Block (LFB model), the logical interconnection between LFBs (LFB topology), and the FE-level attributes, including FE capabilities. The FE model provides the basis to define the information elements exchanged between the CE and the FE in the ForCES protocol [RFC5810].

LFB (Logical Functional Block) Class (or type) - A template that represents a fine-grained, logically separable aspect of FE processing. Most LFBs relate to packet processing in the data path. LFB classes are the basic building blocks of the FE model.

LFB Instance - As a packet flows through an FE along a data path, it flows through one or multiple LFB instances, where each LFB is an instance of a specific LFB class. Multiple instances of the same LFB class can be present in an FE's data path. Note that we often refer to LFBs without distinguishing between an LFB class and LFB instance when we believe the implied reference is obvious for the given context.

LFB Model - The LFB model describes the content and structures in an LFB, plus the associated data definition. XML is used to provide a formal definition of the necessary structures for the modeling. Four types of information are defined in the LFB model. The core part of the LFB model is the LFB class definitions; the other three types of information define constructs associated with and used by the class definition. These are reusable data types, supported frame (packet) formats, and metadata.

Element - Element is generally used in this document in accordance with the XML usage of the term. It refers to an XML tagged part of an XML document. For a precise definition, please see the full set of XML specifications from the W3C. This term is included in this list for completeness because the ForCES formal model uses XML.

Attribute - Attribute is used in the ForCES formal modeling in accordance with standard XML usage of the term, i.e., to provide attribute information included in an XML tag.

LFB Metadata - Metadata is used to communicate per-packet state from one LFB to another, but is not sent across the network. The FE model defines how such metadata is identified, produced, and consumed by the LFBs, but not how the per-packet state is implemented within actual hardware. Metadata is sent between the FE and the CE on redirect packets.

ForCES Component - A ForCES Component is a well-defined, uniquely identifiable and addressable ForCES model building block. A component has a 32-bit ID, name, type, and an optional synopsis description. These are often referred to simply as components. LFB Component - An LFB component is a ForCES component that defines the Operational parameters of the LFBs that must be visible to the CEs.

LFB Class Library - The LFB class library is a set of LFB classes that has been identified as the most common functions found in most FEs and hence should be defined first by the ForCES Working Group.

2. Introduction

A lot of network devices can process packets in a parallel manner. The ForCES Model [RFC5812] presents a formal way to describe the Forwarding Plane's datapath with Logical Function Blocks (LFBs) using XML. This document describes how packet parallelization can be described with the ForCES model.

The modelling concept has been influenced by Cilc. Cilc is a programming language that has been developed since 1994 at the MIT Laboratory to allow programmers to identify elements that can be executed in parallel. The two Cilc concepts used in this document is spawn and sync. Spawn being the place where parallel work can start and sync being the place where the parallel work finishes and must collect all parallel output.

3. Packet Parallelization

This document addresses the following two types of packet parallelization:

1. Flood - where a copy of a packet is sent to multiple LFBs to be processed in parallel.
2. Split - where the packet will be split in equal size chunks specified by the CE and sent to multiple LFB instances probably of the same LFB class to be processed in parallel.

This document introduces two LFBs that are used in before and after the parallelization occurs:

1. Splitter - similar to Cilc's spawn. An LFB that will split the path of a packet and be sent to multiple LFBs to be processed in parallel.
2. Merger - similar to Cilc's sync. An LFB that will receive packets or chunks of the same initial packet and merge them into one.

Both parallel packet distribution types can currently be achieved with the ForCES model. The splitter LFB has one group output that produces either chunks or packets to be sent to LFBs for processing and the merger LFB has one group input that expects either packets or chunks to aggregate all the parallel packets or chunks and produce a single packet. Figure 1 shows an simple example of a split parallel datapath along with the splitter and merger LFB. Figure 2 shows an example of a flood parallel datapath along with the splitter and merger LFB. This modelling framework however allows for more complex parallel datapath topologies as can be seen in Figure 3 which shows one of the parallel paths to be further splitted into a new parallel section.

                           +-------+
                   +------>|  LFB  |-------+
    +----------+   |       +-------+       |       +----------+
    |          |---+                       +------>|          |
    |          |           +-------+               |          |
--->| Splitter |---------->|  LFB  |-------------->|  Merger  |--->
    |   LFB    |           +-------+               |   LFB    |
    |          |---+                       +------>|          |
    +----------+   |       +-------+       |       +----------+
                   +------>|  LFB  |-------+
                           +-------+
		

Figure 1: Simple split parallel processing

                          +------------+
                          | Classifier |
                    +---->|    LFB     |-----+
    +----------+    |     +------------+     |     +----------+
    |          |----+                        +---->|          |
    |          |          +------------+           |          |
--->| Splitter |          |   Meter    |           |  Merger  |--->
    |   LFB    |--------->|    LFB     |---------->|   LFB    |
    |          |          +------------+           |          |
    |          |---+                         +---->|          |
    +----------+   |      +------------+     |     +----------+
                   +----->|  IPv4 TTL  |-----+
                          |  Decrement |
                          |    LFB     |
                          +------------+
		

Figure 2: Simple flood parallel processing

                              +-------+
                          +-->|  LFB  |--+
            +----------+  |   +-------+  |   +----------+
            |          |--+              +-->|          |
            |          |      +-------+      |          |
       +--->| Splitter |----->|  LFB  |----->|  Merger  |---+
       |    |   LFB    |      +-------+      |   LFB    |   |
       |    |          |--+              +-->|          |   |
       |    +----------+  |   +-------+  |   +----------+   |
       |                  +-->|  LFB  |--+                  |
       |                      +-------+                     |
       |                                                    |
       +------------------------------+                     |
                                      |                     |
                           +-------+  |        +------------+
                   +------>|  LFB  |--+        |
    +----------+   |       +-------+           |   +----------+
    |          |---+                           +-->|          |
    |          |           +-------+               |          |
--->| Splitter |---------->|  LFB  |-------------->|  Merger  |--->
    |   LFB    |           +-------+               |   LFB    |
    |          |---+                       +------>|          |
    +----------+   |       +-------+       |       +----------+
                   +------>|  LFB  |-------+
                           +-------+
		

Figure 3: Complex parallel processing

One important element to a developer is the ability to define which LFBs can be used in a parallel mode, with which other LFBs can they be parallelized with and the order of the LFBs can be assembled. This information must be accesible in the core LFBs and therefore this document needs to append one more capability in the FEObject LFB. The topology of the parallel datapath can be deferred and manipulated from the FEObject LFB's LFBTopology.

The FEObjectLFB must be able to specify for the LFB to be used in a parallel mode:

• The Name of the LFB.
• The Class ID of the LFB.
• The Version of the LFB.
• The number of instances that class can support in parallel.
• A list of LFB classes that can follow this LFB class in a pipeline for a parallel path.
• A list of LFB classes that can exist before this LFB class in a pipeline for a parallel path.
• A list of LFB classes that can process packets or chunks in parallel with this LFB class.

    <!-- Datatype -->
    <dataTypeDef>
       <name>ParallelLFBType</name>
       <synopsis>Table entry for parallel LFBs</synopsis>
       <struct>
          <component componentID="1">
             <name>LFBName</name>
             <synopsis>The name of an LFB Class</synopsis>
             <typeRef>string</typeRef>
          </component>
          <component componentID="2">
             <name>LFBClassID</name>
             <synopsis>The id of the LFB Class</synopsis>
             <typeRef>uint32</typeRef>
          </component>
          <component componentID="3">
             <name>LFBVersion</name>
             <synopsis>The version of the LFB Class used by this FE
             </synopsis>
             <typeRef>string</typeRef>
          </component>
          <component componentID="4">
             <name>LFBParallelOccurenceLimit</name>
             <synopsis>The upper limit of instances of the same
                parallel LFBs of this class</synopsis>
             <optional />
             <typeRef>uint32</typeRef>
          </component>
          <component componentID="5">
             <name>AllowedParallelAfters</name>
             <synopsis>List of LFB Classes that this parallel LFB
                class can follow in a parallel pipeline</synopsis>
             <optional />
             <array>
                <typeRef>uint32</typeRef>
             </array>
          </component>
          <component componentID="6">
             <name>AllowedParallelBefores</name>
             <synopsis>List of LFB Classes that this LFB class can
                follow in a parallel pipeline</synopsis>
             <optional />
             <array>
                <typeRef>uint32</typeRef>
             </array>
          </component>
          <component componentID="7">
             <name>AllowedParallel</name>
             <synopsis>List of LFB Classes that this LFB class be run
                in parallel with</synopsis>
             <array>
                <typeRef>uint32</typeRef>
             </array>
          </component>
       </struct>
    </dataTypeDef>
    
    <!-- Capability -->
          <capability componentID="32">
             <name>ParallelLFBs</name>
             <synopsis>List of all supported parallel LFBs</synopsis>
             <array type="Variable-size">
                <typeRef>ParallelLFBType</typeRef>
             </array>
          </capability>
		

Figure 4: XML Definition for FEObjectLFB extension

While the ForCES model cannot describe how the splitting or the merging is actually done as that is an implementation issue of the actual LFB, however this document defines operational parameters to control the splitting and merging, namely the size of the chunks, what happens if a packet or chunk has been marked as invalid and whether the merge LFB should wait for all packets or chunks to arrive. Additionally this document defines metadata, which contain necessary information to assist the merging procedure. The following metadata are defined:

1. ParallelType - Flood or split
2. ParallelID - Identifies packets or chunks on the same parallel work
3. ParallelNum - Number of packet or chunk for specific parallelID.
4. ParralelPartsCount - Total number of packets or chunks for specific parallelID.
5. Valid - Whether a packet or chunk is valid.

This metadata is produced from the Splitter LFB and is passed without being consumed by the LFBs in the parallel datapath. In case that in a parallel path there is an additional Splitter LFB therefore parallelizing even more that path, a new set of metadata MUST be produced for that specific path and the first set of metadata MUST be tunneled through without being consumed or changed until reaching the corresponding Merger LFB where it will be sent out again in the previous parallel path.

An LFB inside a parallel path decides that a packet or a chunk has to be dropped it MAY drop it but the metadata MUST be sent on the path to be received by the Merger LFB for merging purposes. Additional metadata produced by LFBs inside a datapath MAY be aggregated within the Merger LFB and sent on after the merging process.

4. Parallel Base Types

4.1. Frame Types

One frame type has been defined in this library.

4.2. Data Types

No data types have been defined in this library.

4.3. MetaData Types

The following metadata are defined in the OpenFlow type library:

5. Parallel LFBs

5.1. Splitter

A splitter LFB takes part in parallelizing the processing datapath by sending either the same packet or chunks of the same packet to multiple LFBs.

5.1.1. Data Handling

The splitter LFB receives any kind of packet via the singleton input, Input, along with the ParallelType metadata to identify how the packet will be treated. If the parallel type is of type flood, the same packet will be sent through all of the group output ParallelOut's instances. If the parallel type is of type split, the packet will be split into same size chunks, the size being defined by the ChunkSize component, and each chunk will be sent through one of the group output ParallelOut's instances. Each packet or chunk will be accompanied by the following metadata:

• ParallelType - The paralleltype split or flood.
• Parallel ID - generated by the splitter LFB to identify that chunks or packets belong to the same parallel work.
• Parallel Num - each chunk or packet of a parallel id will be assigned a number in order for the merger LFB to know when it has gathered them all along with the ParallelPartsCount metadata.
• ParallelPartsCount - the number of chunks or packets for the specific parallel id.
• Valid - with a default value of true. The merger LFB must know if a packet or a chunk must be set invalid by an LFB in one part of the parallel pipeline.

5.1.2. Components

This LFB has only one component specified the ChunkSize, an uint32 that specifies the size of a chunk when a packet is split into multiple same size chunks.

5.1.3. Capabilities

This LFB has only one capability specified, the MinMaxChunkSize a struct of a uint32 to specify the minimum chunk size and a uint32 to specify the maximum chunk size.

5.1.4. Events

This LFB has no events specified.

5.2. Merger

A merger LFB receives multiple packets or multiple chunks of the same packet and merge them into one merged packet.

5.2.1. Data Handling

The Merger LFB receives either a packet, a chunk via the group input ParallelIn, along with the ParallelType metadata to identify whether what was received was a packet or a chunk, the ParallelID, the ParallelNum the ParallelPartsCount and the Valid metadata. In case that an LFB has dropped a packet or a chunk within a parallale path only the metadata is received. If the MergeWaitType is set to false the Merger LFB will initiate the merge process. If false it will wait for all packet in the ParallelID to arrive. Before the merging process begins, the Merger LFB will check for the valid flags in each of the packets or chunks. If the InvalidAction Component has been set to 0 then if one packet or chunk is not valid all will dropped, else the process will initiate. Once the merging process has been finished the resulting packet will be sent via the singleton output port PacketOutput

5.2.2. Components

This LFB has three components specified:

1. InvalidAction - a uchar defining what the Merge LFB will do if an invalid chunk or packet is received. If set to 0 (DropAll) the merge will be considered invalid and all chunks or packets will be dropped. If set to 1 (Continue) the merge will continue.
2. MergeWaitType - a boolean. If true the Merger LFB will wait for all packets or chunks to be received prior to sending out a response. If false, when one packet or a chunk with a response is received by the merge LFB it will start with the merge process.
3. InvalidCounter - a uint32 that counts the number of invalid merges

5.2.3. Capabilities

This LFB has no capabilities specified.

5.2.4. Events

This LFB specifies only one event. It detects whether the invalidcounter has exceeded a specific value. The error report will send the invalid counter value.

6. XML for Parallel LFB library

<?xml version="1.0" encoding="UTF-8"?>
<LFBLibrary xmlns="urn:ietf:params:xml:ns:forces:lfbmodel:1.0"
   xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
   xsi:schemaLocation="http://ietf.org/forces/1.0/lfbmodel"
   provides="Parallel">
   <load library="BaseTypeLibrary" location="BaseTypeLibrary.LFB" />
   <frameDefs>
      <frameDef>
         <name>Chunk</name>
         <synopsis>A chunk is a frame that is part of an original
            larger frame</synopsis>
      </frameDef>
   </frameDefs>
   <metadataDefs>
      <metadataDef>
         <name>ParallelType</name>
         <synopsis>The type of parallelization this packet will go
            through</synopsis>
         <metadataID>32</metadataID>
         <atomic>
            <baseType>uchar</baseType>
            <specialValues>
               <specialValue value="0">
                  <name>Flood</name>
                  <synopsis>The packet should be sent as a whole to
                     multiple recipients</synopsis>
               </specialValue>
               <specialValue value="1">
                  <name>Split</name>
                  <synopsis>The packet should be split into multiple
                     chunks and sent to recipients</synopsis>
               </specialValue>
            </specialValues>
         </atomic>
      </metadataDef>
      <metadataDef>
         <name>ParallelID</name>
         <synopsis>An identification number to specify that packets
           or chunks belong to the same parallel work.</synopsis>
         <metadataID>33</metadataID>
         <typeRef>uint32</typeRef>
      </metadataDef>
      <metadataDef>
         <name>ParallelNum</name>
         <synopsis>Defines the number of the specific packet or chunk
            of the specific parallel ID.</synopsis>
         <metadataID>34</metadataID>
         <typeRef>uint32</typeRef>
      </metadataDef>
      <metadataDef>
         <name>ParallelPartsCount</name>
         <synopsis>Defines the total number of packets or chunks for
            the specific parallel ID.</synopsis>
         <metadataID>35</metadataID>
         <typeRef>uint32</typeRef>
      </metadataDef>
      <metadataDef>
         <name>Valid</name>
         <synopsis>Marks whether the chunk or a parallel processed
            packet as valid or not.</synopsis>
         <metadataID>36</metadataID>
         <typeRef>boolean</typeRef>
      </metadataDef>
   </metadataDefs>
   <LFBClassDefs>
      <LFBClassDef LFBClassID="30">
         <name>Splitter</name>
         <synopsis>A splitter LFB takes part in parallelizing the
            processing datapath. It will either send the same packet
            or chunks of one packet to multiple LFBs</synopsis>
         <version>1.0</version>
         <inputPorts>
            <inputPort>
               <name>Input</name>
               <synopsis>An input port expecting any kind of frame
               </synopsis>
               <expectation>
                  <frameExpected>
                     <ref>Arbitrary</ref>
                  </frameExpected>
                  <metadataExpected>
                     <ref>ParallelType</ref>
                  </metadataExpected>
               </expectation>
            </inputPort>
         </inputPorts>
         <outputPorts>
            <outputPort group="true">
               <name>ParallelOut</name>
               <synopsis>An parallel output port that sends the same
                  packet to all output instances or chunks of the 
                  same packet different chunk on each instance.
                  </synopsis>
               <product>
                  <frameProduced>
                     <ref>Arbitrary</ref>
                     <ref>Chunk</ref>
                  </frameProduced>
                  <metadataProduced>
                     <ref>ParallelType</ref>
                     <ref>ParallelID</ref>
                     <ref>ParallelNum</ref>
                     <ref>ParallelPartsCount</ref>
                     <ref>Valid</ref>
                  </metadataProduced>
               </product>
            </outputPort>
         </outputPorts>
         <components>
            <component componentID="1" access="read-write">
               <name>ChunkSize</name>
               <synopsis>The size of a chunk when a packet is split
                  into multiple same size chunks</synopsis>
               <typeRef>uint32</typeRef>
            </component>
         </components>
         <capabilities>
            <capability componentID="2">
               <name>MinMaxChunkSize</name>
               <synopsis>The minimum and maximum size of a chunk
                  capable of splitted by this LFB</synopsis>
               <struct>
                  <component componentID="1">
                     <name>MinChunkSize</name>
                     <synopsis>Minimum chunk size</synopsis>
                     <optional />
                     <typeRef>uint32</typeRef>
                  </component>
                  <component componentID="2">
                     <name>MaxChunkSize</name>
                     <synopsis>Maximum chunk size</synopsis>
                     <typeRef>uint32</typeRef>
                  </component>
               </struct>
            </capability>
         </capabilities>
      </LFBClassDef>
      <LFBClassDef LFBClassID="31">
         <name>Merger</name>
         <synopsis>A merger LFB receives multiple packets or multiple
            chunks of the same packet and merge them into one merged
            packet</synopsis>
         <version>1.0</version>
         <inputPorts>
            <inputPort group="true">
               <name>ParallelIn</name>
               <synopsis>An parallel input port that accepts packets
                 or chunks from all output instances</synopsis>
               <expectation>
                  <frameExpected>
                     <ref>Arbitrary</ref>
                     <ref>Chunk</ref>
                     <ref>Null</ref>
                  </frameExpected>
                  <metadataExpected>
                     <ref>ParallelType</ref>
                     <ref>ParallelID</ref>
                     <ref>ParallelNum</ref>
                     <ref>ParallelPartsCount</ref>
                     <ref>Valid</ref>
                  </metadataExpected>
               </expectation>
            </inputPort>
         </inputPorts>
         <outputPorts>
            <outputPort>
               <name>PacketOutput</name>
               <synopsis>An output port expecting any kind of frame
               </synopsis>
               <product>
                  <frameProduced>
                     <ref>Arbitrary</ref>
                  </frameProduced>
               </product>
            </outputPort>
         </outputPorts>
         <components>
            <component componentID="1" access="read-write">
               <name>InvalidAction</name>
               <synopsis>What the Merge LFB will do if an invalid 
                  chunk or packet is received</synopsis>
               <atomic>
                  <baseType>uchar</baseType>
                  <specialValues>
                     <specialValue value="0">
                        <name>DropAll</name>
                        <synopsis>Drop all packets or chunks
                        </synopsis>
                     </specialValue>
                     <specialValue value="1">
                        <name>Continue</name>
                        <synopsis>Continue with the merge</synopsis>
                     </specialValue>
                  </specialValues>
               </atomic>
            </component>
            <component componentID="2">
               <name>MergeWaitType</name>
               <synopsis>Whether the Merge LFB will wait for all
                  packets or chunks to be received prior to sending
                  out a response</synopsis>
               <typeRef>boolean</typeRef>
            </component>
            <component componentID="3">
               <name>InvalidCounter</name>
               <synopsis>Counts the number of invalid merges
               </synopsis>
               <typeRef>uint32</typeRef>
            </component>
         </components>
         <events baseID="30">
            <event eventID="1">
               <name>ManyInvalids</name>
               <synopsis>An event that specifies if there are too 
               many invalids</synopsis>
               <eventTarget>
                  <eventField>InvalidCounter</eventField>
               </eventTarget>
               <eventGreaterThan>50</eventGreaterThan>
               <eventReports>
                  <eventReport>
                     <eventField>InvalidCounter</eventField>
                  </eventReport>
               </eventReports>
            </event>
         </events>
       </components>
      </LFBClassDef>
   </LFBClassDefs>
</LFBLibrary>
		

Figure 5: Parallel LFB library

7. Acknowledgements

The authors would like to thank Jamal Hadi Salim for discussions that made this document better.

8. IANA Considerations

This memo includes no request to IANA.

9. Security Considerations

10. References

10.1. Normative References

10.2. Informative References

Authors' Addresses