fib

README

ndn-dpdk/container/fib

This package implements the Forwarding Information Base (FIB).

The FIB is replicated across all NUMA sockets. The Fib type in Go represents the entire FIB, while the Fib C struct represents a single replica.

The FIB implements a 2-stage LPM algorithm for efficient Longest Prefix Match (LPM) lookups.

Go Code

The Fib type provides methods to execute read or update commands. Supported commands include:

• Exact match lookup.
• Reading counters.
• Inserting or replacing an entry.
• Erasing an entry.

The FIB uses the fibtree package to organize FIB entries in a name hierarchy. Read commands are fulfilled in this tree.

Update commands are executed, sequentially, in these steps:

1. Validate command parameters.
2. Apply the update to the tree, which determines what should be inserted and deleted in every replica.
3. Locate old entries in each replica.
4. Allocate new entries in each replica. If allocation fails, revert the update in the tree.
5. Insert or replace new entries in each replica.
6. Release the memory of old entries via RCU.

The FIB uses the fibreplica package to access replicas that are implemented in C.

C Code

The FibEntry struct represents either a real entry or a virtual entry. A real entry has height set to zero, and must have at least one nexthop and a reference to a strategy. Conversely, a virtual entry has height set to a non-zero value and does not have any nexthops.

The Fib struct is a thread-safe hash table. It combines a DPDK mempool for entry allocation with a URCU lock-free resizable RCU hash table (lfht) for indexing.

In the hash table, the key type is the name's TLV-VALUE, the hash value is the SipHash of the name, and the element type is FibEntry. In case both a real entry and a virtual entry exist at the same name, the virtual entry appears in the hash table, while the real entry is accessible via the realEntry pointer.

The Fib_Find function performs exact match lookups. The Fib_Lpm function implements the 2-stage LPM procedure. These are the only functions intended to be called from other packages, and always return a real entry. The caller is responsible for acquiring and releasing the RCU read lock.

FibEntry carries a sequence number that is incremented upon every insertion. This allows a PIT entry to save a reference to a FIB entry (PitEntry_RefreshFibEntry function) and detect whether the reference is still valid during future retrievals (PitEntry_FindFibEntry function).

The FibEntryDyn struct contains counters and strategy scratch area. Each FibEntry contains a vector of FibEntryDyn. Each forwarding thread is assigned one position in this vector, and may update the FibEntryDyn without RCU.

Documentation

Overview

Package fib implements the Forwarding Information Base.

Index

• Variables
• type Entry
  • func (entry *Entry) Counters() (cnt fibdef.EntryCounters)
• type Fib
  • func New(cfg fibdef.Config, threads []LookupThread) (*Fib, error)
  • func (fib *Fib) Close() (e error)
  • func (fib *Fib) Erase(name ndn.Name) (e error)
  • func (fib *Fib) Find(name ndn.Name) *Entry
  • func (fib *Fib) Insert(entry fibdef.Entry) (e error)
  • func (fib *Fib) Len() int
  • func (fib *Fib) List() (list []Entry)
  • func (fib *Fib) Replica(socket eal.NumaSocket) *fibreplica.Table
• type LookupThread

Variables

var (
	GqlEntryCountersType graphql.Type
	GqlEntryNodeType     *gqlserver.NodeType
	GqlEntryType         *graphql.Object
)

GraphQL types.

Types

type Entry

type Entry struct {
	fibdef.Entry
	// contains filtered or unexported fields
}

Entry represents a FIB entry.

func (*Entry) Counters

func (entry *Entry) Counters() (cnt fibdef.EntryCounters)

Counters retrieves counters, aggregated across all replicas and lookup threads.

type Fib

type Fib struct {
	// contains filtered or unexported fields
}

Fib represents a Forwarding Information Base (FIB).

var (
	// GqlFib is the FIB instance accessible via GraphQL.
	GqlFib *Fib

	// GqlDefaultStrategy is the default strategy when inserted a FIB entry via GraphQL.
	GqlDefaultStrategy *strategycode.Strategy
)

func New

func New(cfg fibdef.Config, threads []LookupThread) (*Fib, error)

New creates a Fib.

func (*Fib) Close

func (fib *Fib) Close() (e error)

Close frees the FIB.

func (*Fib) Erase

func (fib *Fib) Erase(name ndn.Name) (e error)

Erase deletes a FIB entry.

func (*Fib) Find

func (fib *Fib) Find(name ndn.Name) *Entry

Find retrieves an entry by exact match.

func (*Fib) Insert

func (fib *Fib) Insert(entry fibdef.Entry) (e error)

Insert inserts or replaces a FIB entry.

func (*Fib) Len

func (fib *Fib) Len() int

Len returns number of entries.

func (*Fib) List

func (fib *Fib) List() (list []Entry)

List lists entries.

func (*Fib) Replica

func (fib *Fib) Replica(socket eal.NumaSocket) *fibreplica.Table

Replica returns replica on specified NUMA socket.

type LookupThread

type LookupThread interface {
	eal.WithNumaSocket

	SetFib(replica unsafe.Pointer, i int)
}

LookupThread represents an entity that can perform FIB lookups, such as a forwarding thread.