ndt

README

ndn-dpdk/container/ndt

This package implements the Name Dispatch Table (NDT).

The NDN-DPDK forwarder uses a sharded PIT structure, where each forwarding thread owns a shard of the PIT. The NDT decides which PIT shard an Interest belongs to. One or more input threads query the NDT using the names of the incoming Interests, and then dispatch each Interest to the forwarding thread that handles the chosen PIT shard.

In this implementation, the NDT is a linear array of 2^B entries, where each entry indicates a PIT shard number. Each NUMA socket has a replica of this array, so that it can be accessed efficiently.

This implementation chooses the correct PIT shard with the following algorithm:

1. Compute the hash of the name's first prefixLen components. If the name has fewer than prefixLen components, use all components.
2. Truncate the hash to the last B bits.
3. Lookup the table using the truncated hash. The table entry indicates the chosen PIT shard.

The NDT maintains counters of how many times each table entry has been selected. With these counters, a maintenance thread (not yet implemented in this codebase) can periodically reconfigure the NDT to balance the load among the available forwarding threads.

Documentation

Overview

Package ndt implements the Name Dispatch Table.

Index

• Constants
• Variables
• type Config
• type Entry
• type Ndt
  • func New(cfg Config, sockets []eal.NumaSocket) (ndt *Ndt)
  • func (ndt *Ndt) Close() error
  • func (ndt *Ndt) ComputeHash(name ndn.Name) uint64
  • func (ndt *Ndt) Config() Config
  • func (ndt *Ndt) Get(index uint64) (entry Entry)
  • func (ndt *Ndt) IndexOfHash(hash uint64) uint64
  • func (ndt *Ndt) IndexOfName(name ndn.Name) uint64
  • func (ndt *Ndt) List() (list []Entry)
  • func (ndt *Ndt) Lookup(name ndn.Name) (index uint64, value uint8)
  • func (ndt *Ndt) Randomize(max int)
  • func (ndt *Ndt) Threads() (list []*Thread)
  • func (ndt *Ndt) Update(index uint64, value uint8)
• type Thread
  • func (ndtt *Thread) Close() error
  • func (ndtt *Thread) Lookup(name ndn.Name) uint8
  • func (ndtt *Thread) Ptr() unsafe.Pointer

Constants

const (
	MinPrefixLen     = 1
	MaxPrefixLen     = ndni.PNameCachedComponents
	DefaultPrefixLen = 2

	MinCapacity     = 1 << 4
	MaxCapacity     = 1 << 60
	DefaultCapacity = 1 << 16

	MinSampleInterval     = 1 << 0
	MaxSampleInterval     = 1 << 30
	DefaultSampleInterval = 1 << 10
)

Limits and defaults.

Variables

var (
	GqlConfigType *graphql.Object
	GqlEntryType  *graphql.Object
)

GraphQL types.

Types

type Config

type Config struct {
	// PrefixLen is the number of name components considered in NDT lookup.
	//
	// If this value is zero, it defaults to DefaultPrefixLen.
	// Otherwise, it is clamped between MinPrefixLen and MaxPrefixLen.
	PrefixLen int `json:"prefixLen,omitempty"`

	// Capacity is the number of NDT entries.
	//
	// If this value is zero, it defaults to DefaultCapacity.
	// Otherwise, it is clamped between MinCapacity and MaxCapacity, and adjusted up to the next power of 2.
	Capacity int `json:"capacity,omitempty"`

	// SampleInterval indicates how often per-entry counters are incremented within a lookup thread.
	//
	// If this value is zero, it defaults to DefaultSampleInterval.
	// Otherwise, it is clamped between MinSampleInterval and MaxSampleInterval, and adjusted up to the next power of 2.
	SampleInterval int `json:"sampleInterval,omitempty"`
}

Config contains NDT configuration.

type Entry

type Entry struct {
	Index int    `json:"index"`
	Value int    `json:"value"`
	Hits  uint32 `json:"hits"`
}

Entry contains information from an NDT entry.

type Ndt

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

Ndt represents a Name Dispatch Table (NDT).

var (
	// GqlNdt is the NDT instance accessible via GraphQL.
	GqlNdt *Ndt
)

func New

func New(cfg Config, sockets []eal.NumaSocket) (ndt *Ndt)

New creates an Ndt. sockets indicates NUMA sockets of lookup threads.

func (*Ndt) Close

func (ndt *Ndt) Close() error

Close releases memory of all replicas and threads.

func (*Ndt) ComputeHash

func (ndt *Ndt) ComputeHash(name ndn.Name) uint64

ComputeHash computes the hash used for a name.

func (*Ndt) Config

func (ndt *Ndt) Config() Config

Config returns effective configuration.

func (*Ndt) Get

func (ndt *Ndt) Get(index uint64) (entry Entry)

Get returns one entry.

func (*Ndt) IndexOfHash

func (ndt *Ndt) IndexOfHash(hash uint64) uint64

IndexOfHash returns table index used for a hash.

func (*Ndt) IndexOfName

func (ndt *Ndt) IndexOfName(name ndn.Name) uint64

IndexOfName returns table index used for a name.

func (*Ndt) List

func (ndt *Ndt) List() (list []Entry)

List returns all entries.

func (*Ndt) Lookup

func (ndt *Ndt) Lookup(name ndn.Name) (index uint64, value uint8)

Lookup queries a name without incrementing hit counters.

func (*Ndt) Randomize

func (ndt *Ndt) Randomize(max int)

Randomize updates all elements to random values < max. This should only be used during initialization.

func (*Ndt) Threads

func (ndt *Ndt) Threads() (list []*Thread)

Threads returns lookup threads.

func (*Ndt) Update

func (ndt *Ndt) Update(index uint64, value uint8)

Update updates an element.

type Thread

type Thread C.NdtThread

Thread represents an NDT lookup thread.

func (*Thread) Close

func (ndtt *Thread) Close() error

Close releases memory.

func (*Thread) Lookup

func (ndtt *Thread) Lookup(name ndn.Name) uint8

Lookup queries a name and increments hit counters.

func (*Thread) Ptr

func (ndtt *Thread) Ptr() unsafe.Pointer

Ptr returns *C.NdtThread pointer.