Skip to content

OpenFlow Extended Match

Jump to bottom Edit New page
Eder Leão Fernandes edited this page Sep 13, 2018 · 3 revisions

When compared to OpenFlow 1.1, in the number of supported match fields, the version 1.3 of the OpenFlow protocol supports nearly twice as much fields as the former version. This growth was only possible due to changes in the match structure specification. A match structure from OpenFlow 1.1 was a fixed number of fields, carrying 88 bits of information in every message carrying a new flow. Match fields not set in the message were sent, adding unnecessary space overhead.

In order to keep the protocol evolution and to support more fields, the OpenFlow Extended Match (OXM) was introduced by the OpenFlow 1.2 specification. The OXM format is Type-Lenght-Value (TLV) based and replaces the old fixed match structure. A less restricted definition of the match struct adds more flexibility for the insertion of new match fields. The Figure below shows an example of how a field is defined by an OXM field and the TLV respective sizes in bits.

The Type of a match field is formed by the OXM Class and OXM Field. An OXM class represents a vendor number, where 0x8000 is the basic class for the specification of the match fields. OXM Field defines the match field. In the example, the field number 15 represents the UDP protocol in OpenFlow. The last bit of the Type is left for the Has Mask field, which indicates if the match is masked or not. Finally, the Length field is the value size.

Some challenges arise with the OXM introduction. Whereas extension of match support for messages is solved, there is nothing concerning the packet parsing in the Datapath. The next subsections discuss how our implementation deals with protocol fields extensibility in the software switch.

Packet Parser

Each new protocol added for the OpenFlow specification demands the addition of an specific code to extract the new fields. Distinct protocols may have singular and complex parsing methods. For instance, variable fields such as IP options can require cumbersome deep packet inspection. For this reason, the Packet Parser implementation needs to be flexible and easy to extend. Also, the idea of simple insertion of new match fields meets the ease of extension requisite.

As a means to achieve a Packet Parser implementation featuring the mentioned characteristics, we have come up with a design which uses a packet description language to assist the parsing. The Figure below shows the Packet Parser model implemented on the switch Datapath.

Each module is described as follows:

  • NetPDL. The Network Protocol Description Language (NetPDL) is the packet description language. It is a XML-based language and has a large number of protocols and specified encapsulations. In addition, the simple language definition allows easy and fast addition of non available protocol description. In the previous Figure the NetPDL module feeds the parsing library with the description of the OpenFlow 1.3 supported match fields.

  • NetBee library Parser. Netbee is as library for packet processing. It is composed by several modules for different types of network application, such as packet filtering and sniffing. For our Packet Parser implementation, we use the Netbee library decoding objects. These objects come from a C++ set of classes and methods that ease packet decoding. To accomplish this, firstly Netbee loads the NetPDL protocols specification into the machine Random Access memory (RAM) and on a packet. Then, received packets are decoded according to the NetPDL description and the extracted information is stored in a protocol tree. Finally, packet field values can be retrieved from the tree using specific methods of the library.

  • nbee_link. This module is where packets are converted in the flow match structure. Arriving packets are sent for the Netbee library for decoding. From the protocols tree generated by Netbee, the nbee_link module
    extracts the field values and builds the packet match structure that will be sent to the Flow Table look up. The code to extract a protocol is shown the code below.

if (protocol_Name.compare("ethernet") == 0 && pkt_proto->eth == NULL)
    {
        pkt_proto->eth = (struct eth_header *) ( (uint8_t*) pktin->data + proto->Position);
        PDMLReader->GetPDMLField(proto->Name, (char*) "dst", proto->FirstField, &field);
        nblink_extract_proto_fields(pktin, field, pktout, OXM_OF_ETH_DST);
        PDMLReader->GetPDMLField(proto->Name, (char*) "src", proto->FirstField, &field);
        nblink_extract_proto_fields(pktin, field, pktout, OXM_OF_ETH_SRC);
        PDMLReader->GetPDMLField(proto->Name, (char*) "type", proto->FirstField, &field);
        nblink_extract_proto_fields(pktin, field, pktout, OXM_OF_ETH_TYPE);
    }

Using the Netbee method GetPDMLField, we get the three ethernet protocol supported fields in OpenFlow 1.3. The second argument of GetPDMLField reflects the field name defined in the NetPDL specification. The function nblink_extract_proto_fields receives the extracted field value and type and inserts this into the match structure. Another important piece of code is present in the third line. For possible further processing, for instance, the application of a

An example of how helpful is a flexible design for the Packer Parser is on the support for IPv6 Extension Headers (EH). EHs parsing execution is not a trivial task, as there are different types and formats. What is more, IPv6 packets may present complex combinations of headers. In OpenFlow 1.3 support for IPv6 EHs is not based on values, but on a special bitmap that matches in the presence of EHs. Besides, a bit field matches an IPv6 packet only if their EHs are in the recommended order. All of these details would result in a large ammount of code to parse EHs correctly. However, this is done in few lines due to our extensible implementation and the NetPDL language.

Flow Match Prerequisites

Another change brought by OXMs is the introduction of flow match fields prerequisites. In order to obtain flow match consistency, some match fields require the presence of other fields. For example, matching any ARP protocol field requires the ethertype field having the correct value for an ARP packet. Thereby, inconsistent flows are denied by the Flow Table.

To map OXM fields prerequisites, a file* with several C Preprocessor macros, was created. The macros map each field with their respective network layer 2, layer 3 or upper level requisite. In addition there is a field that tells if a field is maskable or not. The code below shows prerequisites and fields macros definition. Also, it gives an example of a field created by the DEFINE_FIELD macro.

*This file was inpired by the old way that OVS handled the Nicira Extended Match (NXM) format. NXM is the format that gave origin to OXM.

#define OXM_DL_NONE   (0, 0)
#define OXM_DL_ARP    (ETH_TYPE_ARP, 0)
#define OXM_DL_PBB    (ETH_TYPE_PBB,0)
#define OXM_DL_IP     (ETH_TYPE_IP, 0)
#define OXM_DL_MPLS   (ETH_TYPE_MPLS, ETH_TYPE_MPLS_MCAST)
#define OXM_DL_IPV6   (ETH_TYPE_IPV6, 0)
#define OXM_DL_IP_ANY (ETH_TYPE_IP, ETH_TYPE_IPV6)

#define DEFINE_FIELD_M(HEADER,  DL_TYPES, NW_PROTO, MASKABLE)  \
    DEFINE_FIELD(HEADER,  DL_TYPES, NW_PROTO, MASKABLE)        \
    DEFINE_FIELD(HEADER##_W, DL_TYPES, NW_PROTO, true)

DEFINE_FIELD    (OF_TCP_SRC,        OXM_DL_IP_ANY,   IPPROTO_TCP,    false)

OXMs matches definitions are loaded by the Oflib, and used in the function oxm_pull_match, which is called during the match unpack. Among the tests performed to detect invalid OXM fields are: bad prerequisite, duplicate fields, wrongly masked and nonexistent field.

Flow Matching

In the pursuit for the best way to perform flow matching inside the Flow Table, developers might want to try different algorithms and data structures. For this reason, the switch implements a flexible and easy interface to change the way packets are matched.

Match fields are part of the software switch flow_entry struct. Instead of defining a fixed match as one of the flow_entry member, a pointer to Oflib struct ofl_match_header is left as a reference for the entry match fields. Therefore, if a developer wants to experiment his own match structure, there is only the need to make it start with an ofl_match_header.

The implementation presents a default flow matching using the Oflib match structure called ofl_match. Besides the match header, the struct includes a Hash Map structure to store OXM TLVs. Each OXM entry in the Hash Map has an exclusive key, created by the combination of the field Type and Length information. Storing only flow specified fields saves memory space, at a small cost of the pointers created to mantain the data structure. Another advantage in the Hash Map use in the match structure is the constant access time for the OXMs. Fast element access is very important for two of the most common operations:

  • Check packet matching. Packet fields are extracted and matched against the flows. Matching is performed by look ups of the packet fields in the Hash Map.

  • Check flow collision. Flows collide when a new flow is installed and the Flow Table contains a flow with the same match fields and priority. In this case the old one is replaced by the new one. The Hash Map allows a direct comparison of fields.

Another detail about flow matching in the software switch is about the linear behavior of Flow Table look up. The Flow Table stores flows in a list ordered by priority. When a packet is sent to the flow match it loops through the flow list until it finds a matching rule or it reaches its end. This is the most simple approach for the flow match and was chosen for its simplicity. Developers who might want to modify the behaviour of Flow Table look up just need to add their own code for the function flow_table_lookup.

Extensible context expression in ’packet-in’

Former *packet-in message contained little information about the packet parsed in the Datapath. The only match field present was the switch input port. In order to get the other packet fields, a controller needs to parse the packet header, included in the end of packet-in. This causes an unnecessary parsing repetition in the control plane. With the OXM introduction, OpenFlow 1.3 solves this problem sending the extracted packet fields in the form of OXMs, making it easier for the control plane to retrieve the packet fields.

While an standard switch implementation requires only context information, which are input port, metadata and tunnel_id, our implementation follows the option to add all parsed fields in a packet-in message.

Add a custom footer
Add a custom sidebar
Clone this wiki locally