Implementing A Very Simple Protocol

From ARL Wiki
Revision as of 22:58, 9 July 2009 by Ken Wong (talk | contribs)
Jump to navigationJump to search

This page explains what would be involved in implementing a new protocol using an SPP by describing the SPP implementation of the very simple virtual circuit protocol (VSVCP). VSVCP is not a practical protocol and is incomplete. But a study of its implementation will be sufficient to understand the process of supporting a new protocol using an SPP; i.e., support a new metanet. We will also relate parts of the discussion to the IPv4 metanet implementation to give a broader perspective on implementation issues.

Example

File:A-VSVCP-Network.png
A VSVCP Network

Two processes (endpoints) in a VSVCP network communicate over a virtual circuit. Each virtual circuit is identified by a Virtual Circuit Identifier (VCI) which is globally unique. Each VSVCP packet contains an eight-byte header that contains a VCI which is used by VSVCP routers to forward packets. (We ignore how endpoints acquire VCIs, and we assume that each VSVCP router is magically loaded with an appropriate forwarding table.)

A VSVCP forwarding table maps a VCI to a meta-interface. Note that a VSVCP header is immutable; i.e., it does not change during transit from the sender to the receiver (unlike an ATM cell header). As shown in the figure (right), a packet going from H1 to H6 has a VCI of 6 throughout its journey to H6. At R1, the forwarding table maps VCI 6 to meta-interface (MI) 4. At R2, the forwarding table maps VCI 6 to meta-interface (MI) XXX. Thus, there is a continuous forwarding path from H1 to H6.


File:VSVCP-Header.png
VSVCP Header

A VSVCP header (right) contains eight bytes that make up four fields:

  • 2-byte Virtual Circuit Identifier (VCI)
  • 2-byte data length (DL)
  • 2-byte header checksum (HC)
  • 2-byte reserved field

The VCI field is used by routers for forwarding. The DL field indicates the number of bytes in the data portion of the packet; i.e., it excludes the eight bytes in the header. The HC is an Internet checksum (ones complement sum of 16-bit integers) over the header. The last 2-byte field is reserved for future use.

For this example, we assume that communication patterns between hosts are such that each receiver has atmost one sender (i.e., the communication graph is injective). Furthermore, for simplicity, we assume that VCI x is used to communicate with host Hx. In the example, H1 sends to H4 using VCI 4, and H4 responds to H1 using VCI 1; H2 sends to H5 using VCI 5, and H5 responds to H2 using VCI 2; and H3 sends to H6 using VCI 6, and H6 responds to H3 using VCI 3. But a process can also send to a GPE process running at router Rx using VCI 32768+x; e.g., VCI 32769 is used for communication with R1.


Background

Program Description
create_fp Configure the fastpath and handle
local delivery and exception traffic
client Configure a meta-interface and queues
fltr Install/Update a filter

Let's review the important highlights from The GEC 4 Demo and Overview Of The SPP Architecture that are relevant in implementing support for a new metanet. First, let's assume that we want to configure the SPP in a manner that is similar to what was done for the The GEC 4 Demo that showcased the IPv4 metanet. The table (right) lists the three programs used to configure The GEC 4 Demo . Note that:

  • Every metanet must have a fastpath before meta-interfaces (MIs) can be defined.
  • Every metanet will have one or more MIs, and each MI will have one or more queues.
  • The filter table is the forwarding table.

Thus, the only logical difference between configuring an IPv4 metanet and a VSVCP metanet is in their forwarding tables. We should be able to reuse the two programs create_fp and client (as is) from The GEC 4 Demo to configure the fastpath and the meta-interfaces and queues for the VSVCP metanet.

From a developer's perspective, an IPv4 metanet router forwards an incoming packet to a queue based on five fields from the metanet header (source IP address, source port, destination IP address, destination port and protocol) and meta-level information (input MI). But a VSVCP metanet router forwards based on only the VCI field from the metanet header. It does this by extracting the VCI field from the VSVCP metanet header, searching a forwarding table containing key-result (VCI-QID) pairs, and forwarding the packet to the queue indicated by the matching forwarding table entry. The implication is that the developer will have to create a version of the fltr program that can be used to insert VCI-QID entries into the forwarding table. Although there are a few other minor details, the developer will need to modify the write_fltr() routine in the fltr.cc code so that it will insert a filter entry consisting of a VCI and a QID.


There are only three more changes to the SPP required to support the processing of VSVCP packets: 1) it must recognize VSVCP packets; 2) it must extract the VCI field from VSVCP packet headers and form a lookup key in a format understood by the the Lookup block; and 3) it must verify that the packet header has not been damaged. If the packet header has been damaged, it must send an exception packet to the GPE process that handles exceptions. This exception packet is the original packet encapsulated in an internal header that contains a tag indicating the exception. Again, there are a few other minor details, but in essence, that's all that is needed.

In SPP terminology, the SPP needs a new code option. This code option involves modifying the code in the Parse block and the Header Format block:

  • The Parse block must:
    • Check for a damaged header.
    • Extract the VCI field from VSVCP packets.
    • Form the lookup key for the SPP's Lookup block.
  • The Lookup block must:
    • Form an exception packet if there was an exception.

All of these modifications requires that code in the SPP's IXP 2800 microengines be modified. At this time, these modifications must be done by the SPP developers, not the metanet developer. Thus, the metanet developer must tell the SPP developer the structure of the metanet header, the fields that need to be extracted, and the format of the code-option lookup key.

Even if the metanet developer, supplies the SPP developer with the above information and the SPP developer modifies the SPP accordingly, how is it possible for the SPP to handle the new protocol? The answer is that the SPP's lookup engine treats most of the key portion of the TCAM as a generic, unstructured 112-bit vector. The main job of the SPP's Parse block is to format the packet key so that a search of the TCAM's filter database makes sense. We need to digress to a short explanation of lookup keys and SPP filters to clarify this answer before returning to a discussion of the fltr.cc code.


Lookup Keys And SPP Filters

Generic TCAM Key-Result

Recall that the TCAM filter database is a set of filters. A filter consists of a key K, a mask M and a result R. The SPP's Parse block creates a key K' based on a packet's header. A TCAM filter matches a packet if (K' & M) = (K & M). The TCAM returns the result R of the matching filter. The result R determines how the packet should be processed. For example, R includes the QID of the queue where the packet should be stored until it is time for its transmission.

The TCAM key has two parts: 1) the substrate key (pink), and 2) the code-option key (blue). The substrate key is 32 bits (4 bytes), and the code-option key is 112 bits (14 bytes). The substrate key always has four fields:

  • Type ('T')
    • 0: Normal filter
    • 1: Substrate-only filter
  • Input Interface ('if')
    • The meta-interface that received the packet
  • FP ID ('fpid')
    • The fastpath ID of the packet (= the VLAN tag)
  • RX Port# (rxport)
    • The UDP port number of the meta-interface that received the packet

The code-option key has no special meaning to the TCAM (or the SPP). The format of the code-option key is determined by the program fltr that inserts a filter into the TCAM.

The result XXXXX


IPv4 TCAM Key-Result

For example, the figure (above) shows the format of an IPv4 TCAM filter.



VSVCP TCAM Key-Result



Modifying The fltr.cc Code

Notes to the Writer

Very Simple Virtual Circuit Protocol

THE REST OF THIS IS PROBABLY USELESS AND IS DEFINITELY OUT OF DATE.

Goals

  • Describe basic user procedure
  • Begin to describe underlying architecture and components
  • Talk about substrate concept

Sections

  • xxx

Figures

  • Application header format
  • xxx

Links

Versions

  • 0
    • Protocol header chosen to work with iperf
    • Words (4 bytes) in header
      • Pkt ID (iperf UDP compatible)
      • Timestamp tv_sec
      • Timestamp tv_usec
      • VCI
      • Flow label (used in v1)
    • VCI is globally unique
    • 0.0
      • Minimalistic example
      • 1 router (R1), 2 hosts (H1, H2)
    • 0.1
      • Add monitoring daemon
    • 0.2
      • Like GEC 4, Part 1 but routes based on VCI
      • 2 routers (R1, R2), 6 hosts (H1-H6)
  • 1
    • VCI can change during transit as part of pkt processing
    • Add Flow Label field

Configuring R1.0.0

  • Use 2 physical interfaces from GEC4
  • Use 2 hosts H1 and H2
  • Replace R2 in GEC4 with H2
  • FP
    • copt = 2
    • bw = 205 Mb/s
    • fltrs = xxx
    • qs = xxx
    • buffs = xxx
    • stats = fltrs
    • sram = xxx
  • MIs
    • m1 (to H1)
      • bw = 100 Mb/s
      • ipaddr = 10.1.1.1
      • port = 20000
      • i.e., socket s1 = (10.1.1.1, 20000)
    • m2 (to H2)
      • bw = 100 Mb/s
      • ipaddr = 10.1.16.1
      • port = 20000
      • i.e., socket s2 = (10.1.16.1, 20000)
  • Queues
    • q48 (LD): threshold = 100 pkts, bw = 1 Mb/s, mi = 0
    • q49 (EX): threshold = 100 pkts, bw = 1 Mb/s, mi = 0
    • q1: threshold = 1000 pkts, bw = m0.bw = 100 Mb/s, mi = 1
    • q2: threshold = 1000 pkts, bw = m1.bw = 100 mb/s, mi = 2
    • q0: not used
  • VCIs
    • (R1, H1, H2) = (0, 1, 2) ==> Path (x,y) uses VCI 3*x+y
      • (H1, H2) uses VCI 5 = 3*1 + 2
      • Use 6 of 9 VCIs
    • Communication matrix
      • ( R1 (-, 1, 2), H1 (3, -, 5), H2 (6, 7, -) )
      • Unused VCIs: 0, 4, 8
  • Filters (key = rxmi, vci)
    • f1 (R1 to H1): (rxmi, vci) = (0, 1), s = (10.1.1.1, 20000), qid = 1, sindx = 1 # substrate only
    • f2 (R1 to H2): (rxmi, vci) = (0, 2), s = (10.1.16.2, 20000), qid = 2, sindx = 2 # substrate only
    • f3 (H1 to R1): (rxmi, vci) = (1, 3), s = (10.1.16.1, 5555), qid = 0, sindx = 3
    • f4 (H1 to H2): (rxmi, vci) = (1, 5), s = (10.1.16.2, 20000), qid = 2, sindx = 4
    • f5 (H2 to R1): (rxmi, vci) = (2, 6), s = (10.1.16.1, 5555), qid = 0, sindx = 5
    • f6 (H2 to H1): (rxmi, vci) = (2, 7), s = (10.1.1.1, 20000), qid = 1, sindx = 6


User-space pkt

  • Tunnel socket appears in UDP header
  • VCI is first word of UDP payload
  • Payload also has timestamp (for RTT and space-time diagram)

Substrate Implementation Concepts

  • Physical interfaces
  • Physical MIs
  • Queues
  • Filters
  • Code option demultiplexor
  • Parse, Lookup, Header Format

Slowpath Implementation

  • Filters for local delivery
  • User-space process to handle LD and EX traffic
    • Has VCI-MI Socket map; i.e., M : VCI --> MI Socket
    • Forwards pkt to socket M(pkt.VCI)
  • Artifacts
    • Tunnel-aware sender and receiver
    • User-space process to handle monitoring data
    • spp-config-sp-vsvc-XXX.sh (slowpath) configuration scripts

Fastpath Implementation

  • Requires mods to Parse and Header Format
  • Uses generic Lookup
  • Additional artifacts
    • spp-config-fp-vsvc-XXX.sh (fastpath) configuration scripts
    • Monitoring

Interesting Demo

  • xxx
Retrieved from "http://wiki.arl.wustl.edu/index.php?title=Implementing_A_Very_Simple_Protocol&oldid=774"