Revisiting High-Speed Forwarding: Cases forState-full forwarding and Learned Index
based Forwarding
1st International Workshop on Theory andPractice of Programmable Forwarding
June 28, 2021
Toru Hasegawa
Osaka Univierity

INTRODUCTION

2

Introduction
High speed packet forwarding is an important researchissue for the new network architecture: Named Data
Networking (NDN) NDN is different from IPv4 in terms of






Toward 100 Gbps and 10 Tbps NDN packet forwarding
3

Hierarchical human readable names like URL
A huge number of name prefixes is not recorded at SRAMdevices
Request-response style communications require routers to record
states called Pending Interest Table (PIT) entries
In-network caching is supported by routers
Survey of the studies
Achievements at Hasegawa Lab., Osaka University

NAMED DATA NETWORKING

4Named Data Networking (NDN) [1]Name-based Routing/Forwarding Content name rather than the host address Network Name ≒ Application Name Each chunk (packet) has a name Hierarchical human-readable names like URL/jp/ac/osaka-u/ist/www-hasegawa
E-mail WWW VoIPBrower Chat

SMTP HTTP

File Stream

TCP UDP

SecurityIPContentEthernet PPPStrategy

CSMA SONET DSL

IP UDP P2P

Copper Fiber Radio
5IP

Copper Fiber RadioNDN/CCNInterest/Data Packet Forwarding
Interest packet

name

NDN Router/NDN/sports/video1/NDN/sports/video1

A huge number ofentries

FIB

Data packet In-network caching is
supported/CCN/sports/video1

PITCS

Record flow states to support
request-response stylecommunications/CCN/sports/video1

NDN Router
Interest /aConsumer
6

face
#1

PIT
name:/aface: #1

face
#2

Data /aProducer

NDN vs IP Packet ForwardingHuge number of name prefixes/names

Name prefixes : 2.1*108 >> IP prefixes: 7*105

Variable size names/name prefixes
NDN: Average component length and number, 28 bytes [2]

7Average component length: 7 bytes
Average component number: 4

IP: 32 bits/128 bits, fixed length

Stateful forwarding:

LPM

Flow request-response
state integrity
Flow states should be maintained to support)[3]style communication (Interest and Data packets
Load balancing
Huge number of flows’ states: More than 106 PIT entries at thecore router [4]Packet-level in-network cachingReality Check [5]

8A large FIB is not stored at fast memory devices like SRAM devices
10 Tbps and 100 Gbps are feasible targets of forwarding speeds forhardware and software NDN routers, respectively
15M packet/s * 1K bytes = 120 Gbps
1G packet/s * 1K bytes = 8 T bps
ObjectiveFIB

PITCS

Edge

20M prefixes
15M packet/s(Interest)
0.417Mpacket/s(Data Caching)

On-Chip SAM (200Mbits)
Bloom Filter Off-Chip(140M bytes)
Hash table

RLDRAM (70M DRAM(6G byte)
bits)
Index table
Hash table
SSD (1T bytes)
Packet store

Core250M prefixes
1G packet/s(Interest)
120Mpacket/s(Data Caching)

On-Chip SRAM (4Gbits)
Bloom Filter Off-Chip(1.5G bytes)
Hash table

SRAM(266Mbits)
Hash tableat each line
card

RLDRAM(266Mbits):
Index table
DRAM (10Gbytes)
Cited from [5]TOWARD 100 GBPSFORWARDING: SOFTWARENDN ROUTERS
9

Software Router :Toward 100 Gbps forwarding
Goal: 100 Gbps packet forwarding at commodity PC
servers with network interface cards (NICs)[2,6-11]
 System model:

PC Server: multi-core CPU device and NIC with DPDKDesign rational
Exploits parallelism of multiple CPU cores
40x PCIe 3.0 lanes
DPDK eliminates
1)Receive Packet
Packetcontext switches
NICPCIe Controller
Packet3)Send Packet
NIC’s Receive Side
L1
L
D
Scaling (RSS) so that
Core
2
L1I
Sharedpackets are equally
L3
L1
L
D
dispatched to cores
Core
2DRAM

L1I

Full Duplex On-dieRing Interconnect

L
2

L1
D
L1I

CoreL
2

L1
D
L1I

Core

Instruction
Data
10PITFI
B

Memory ControllerCS2) Run NDN Protocol
4x DRAM Channels

Approaches to LPM and Load Balancingl [6]Hash table-based FIB is selected to compensate for late
DRAM access latencyThe whole FIB cannot be recorded at high speed memory
devices like SRAM

Sharding according to font end cache[12] to mitigate load
imbalance due to heavy hitters

Sharding should be used: Interest/Data packets of the same
name should be handled by the same CPU core in order to avoid
using mutual exclusion of the same PIT entry
Even if sharding is used, packets are unequally assigned CPU
cores due to heavy hitters
NICCPUCore #1

Packet11Core #2

MemoryPIT

CS#1
CS#2

LPM (Longest Prefix Matching) :Hash Tablebased FIB [2,6]Hash tables


Hash table lookup

namehashh

4.fetch entry if found (Ef)h…

hhash bucket

1) Fetching a hash5.check entry (Ec)hashname …
bucket by usinghash entry
a hash value of a key2) Searching a pointer to a hash entry by traversing the bucket3) Fetching the hash entry if the bucket has a pointer to theentry

LPM: Hash table lookup is repeatedly by the match

12

Chained hash table3.checkbucket (Bc)

2.fetchbucket (Bf)name /a/b/c/dhash(/a/b/c/d)hash(/a/b/c)…

LPM: Bloom Filter, Trie-baseBloom filter-based FIB[7,8]

1st: Decide the matched prefix length using the bloom filter
2nd :Exact of matching of name with the decided length using thehash table = similar to exact matching of the hash table

Trie FIB

Binary Patricia tree is the most compact amongbit, character and component-based trie [9]Tree search/a /a/b/a/c /b/b/a/b/c

Component-based Patricia
13

Dependent DRAM accesses for LPM [6]Assumption: Some part of FIB is recorded at DRAM, andthus hiding DRAM accesses by prereftch is important Dependent DRAM accesses number (defined by [6])Dependent data pieces should be fetched in sequence fromDRM
Two data pieces are dependent







Dependent accesses should be as small as possible to hide
DRAM access latency

LPM at hash-table FIB requires the smallest dependent
DRAM access number:
14

Access latency of fetching the dependentpiece cannot be hidden by prefetch

Hash table-based FIB[2,6] : 2Bloom filter-based FIB[7] : 2

Trie FIB[8]We choose hash table-based FIB: 7 (average)Naïve Packet Processing : Waiting time due tohash bucket and entry fetchesWaiting time to fetch hash buckets and hash entries
must be hidden
Exact matching of name prefix

Interest Packet1

Bf1

Hash1

Bc1

CS1

Bf1

Bc1

checking afetching a
Bf hash bucket Bc hash bucket
HashPIT1

Bf1

Bc1

Ef1

Ec1

checking afetching a
Ef hash entry Ec hash entry

hashCSPITFIBcomputation CS processing PIT processing FIB processingC:811,M:89
C:295,M:440
B5: Look up
Miss B4: Insert
PIT Entry
FIB
B3: Look up
C:176,M:131
CS
B6: Create
Hit Data Packet

C:199,M:110

C:461,M:179
Interest B2 Compute Hashesof Prefixes
C:110,M:81
B1: Receive andDecode Packet
C:73,M:292
C:146,M:41
B8: Delete
B7: Compute
Data Hash of NamePIT Entry
15

C:63,M:10
B10: Send
Packet

C:275,M:392
B9: Insert Data
into CS

C : CPU Cycles [cycles], M : DRAM Access [bytes]

FIB1

Hiding DRAM Access Latency with Prefetch
Issue: Unhidden data fetches in the naïve processingThere is no time between computations of addresses to data to
be fetched and its uses

Design guidelines of packet processing


Early computations of addresses to data to be fetched
Put some computations irrelevant to the fetched data between
the address computation and uses of the fetched data
No timeIrrelevant
computation

Early computationof address
Address
computationprefetch
16

Address
computationprefetchunhidden Computation

with the data

Data fetch

Place computations
Computation
Irrelevantwith the data
computation

hiddenData fetch

1) Pre-Hash Computation

Reordering hash computations of consecutive 2 packetsCompute hashes for the packet 1 and 2 in advance
Addresses to Cb1 and Cb2 are early computed

Put computations irrelevant to hash buckets of CS justafter hash computations


Cb1: hidden by hash computation of packet 2
Cb2: hidden by computations of packet 1Cp1 CS1 Pp1 PIT1 Fp1

Hash1
Cb1
Pb1
Fb1

FIB1
Fe1

17Pb1
Fb1

Cb2 hidden
Pb2
Fb2

Cp2 CS2 Pp2 PIT2 Fp2
Cb2
Pb2
Fb2

Hash1 Hash2 Cp1 CS1 Pp1 PIT1 Fp1

hidden Cb1

Hash2

FIB1
Fe1

FIB2
Fe2Cp2 CS2 Pp2 PIT2 Fp2

FIB2Fe22) Speculative Hash Table Lookup (SHTL)
Reordering tasks composing multiple hash table lookupsof one packet
Speculatively search pointers to entries of all the tablesAddress to Fe1 is early computed

Put computations of CS, PIT just after finding the pointerFe1: hidden by computations of CS and PIT
Hash1 Hash2 Cp1 CS1 Pp1 PIT1 Fp1
Cb1
Pb1
Fb1

Cb2
Pb2
Fb2

FIB1
Fe1

Hash1 Hash2 Cp1 Pp1 Fp1 CS1 PIT1 FIB1

18Cb1
Pb1
Fb1

Cb2
Pb2
Fb2

Fe1hidden

Forwarding Speed
Pre-Hash and SHTL hide DRAM access latency of datafetches 43.48 MPPS (about 36 Gbps) packet forwarding on asingle computerXeon E5-2699 v4 (2.20GHz*22 CPU cores), 8*16 G bytes DRAM,
2*40 G Etherー12%

19

ー10%

CPU cycles for processing one packet (Single-Threaded)

19

How NIC Dispatches Incoming Packets to CPU Cores
Random dispatching: NIC randomly
chooses CPU cores
CPUCore #1Packet

Core #2-40%Sharding[13]: Heavy hitters (Highly popular objects)
cause load imbalance
20

Mutual exclusion
degradesforwarding speed

NIC

Interest packets are
not equally dispatched,
whereas Data packets
are equally assigned

MemoryPIT

CS#1
CS#2

Design Rational of Equal Load Balancing [3]Equal Dispatching

Radom dispatching of Interest packets of highly popular objects:
CPU cores are randomly selected
Shading of the other Interest packets and Data packets
 Interest and Data packets…….
of unpopular objects aredispatched to the same
CPU cores: No need ofmutual exclusion of PITentries



Avoiding mutual exclusion for highly popular objects


21

Most Interest packets of highly popular objects hit thecorresponding Data packets in the CS, thus PIT is not accessed
The remaining issue is mutual exclusion of CS entries for highly
popular objects

Algorithms of NIC and PIT
Packet dispatching: NIC/a PacketData?

Yes

Sharding-based
dispatching

No
Highlypopularname?
No



22

Yes

Highlypopularname?

No/a

Yes
Randomdispatching

Setting L
bit to 1

Sharding-based
dispatching/a/aFine-grained pessimistic locking: PIT CAS instruction (for mutual exclusion) is rarely issued
because most Interest packets
A binary lockvariable
Interestof highly popular/bName
LockFaces
do not access theThread #1
1#1/aPIT/c0/bThread #2/c0L

Algorithm of CS: FIFO Queue with Optimistic
Locking [13]
Setup

CS: Look up table and FIFO queues
Version variables are prepared for entries of the look up table

Optimistic locking provides mutual exclusion for Data
packet replacement
 When a Data packet is received,

23If the version variable is an odd value, the CPU core writes theCS entry to insert or to evict a Data packet
If the version variable is an even value, the CPU core does notaccess the CS entry, then retries reading the version variableEvaluation by Simulation
Conditions: 22 CPU cores, CS hit rate 0.35
 Proposed dispatching method achieves equal loadbalancing of CPU cores




24

Packet loss rates of CPU cores are similar even if
the router is lightly overloadedSummary of Software NDN routers


Most research issues are solved for 100 Gbps packet
forwarding, in the case of large Data packets (1-8Kbytes)

Full-fledged Implementation [11]
 Leveraging state-of-art techniques
Open source




25

DPDK: multi-threading, ring-buffer, bypass kernel
2-stage LPM [2]
FIB replication on NUMA sockets

Cefore : NICT https://cefore.net/
NFD (NDN Forwarding Demon) : UCLA https://nameddata.net/doc/NFD/current/
CICN: .io https://wiki.fd.io/view/Cicn
CCN-lite: https://github.com/cn-uofbasel/ccn-lite

TOWARD 10 TBPSFORWARDING: HARDWARENDN ROUTERS
26

Toward 10 Tbps NDN Packet Forwarding
Research for toward 10 Tbps NDN packet forwarding is
still in the early stage
 Approaches for hardware NDN routersNaïve backplane switch and interface cardsCaesar [15]: One of the first hardware routers

P4 programmable switch
 Programmable ASIC and interfaces
 NDN.p4 [16]: A prototype NDN implementation on P4
programmable switches
P4 programmable switch and a few serversOn going at Osaka University

27

Learned index-base FIB as a candidate for high speed LPM

High speed per-packet caching is not addressed, sofar

Caesar [15] : One of the first hardware routers
FIB is separated to line cards (LCs) so that FIB is stored
at SRAM devices of them Simple Sharding: LCi records prefixes of which hashvalue of the first name component is i (hash routingaccording to the first component) But, LC of the FIB entry is not always the outgoing face Packets traverse the backplane switch twice28

Cited from [14]

NDN Router on P4 Programmable Switch Is in
The Early State

NDN.p4 [16]:Prototype on BMv2


Do not support large numbers of FIB and PIT enries

Cited from [15]29How to Store a Large number of FIB Entries
Compact FIB Data Structures which can be stored at
TCAM and SRAM Devices of P4 ASIC

Multi-bit Trie:

Learned Index [17]The look up depth is larger than the number of stages of a single pipeline
Float point calculations are required

Offloading FIB to another device


DRAM device at the controller
DRAM device at a server

Switch ASIC
Pipeline

Pipeline
30

PITServersCPUDRAM
FIBLPM Using Learned Index [17]Learned index:Learning key-position relationships usingmachine learning (e.g., neural network)
 FIB based on learned index (learned FIB) for IP LPM

Sort IP prefixes in ascending order and store them in an array
Learn the relation between each IP prefix and its position with aneural network
Predict the position of the destination IP address of an ingress
packet with the neural network
Search for the longest matching prefix around the predictedposition
FIB

Destination
IP Address
133.1.6.1

LearnedIndex

Predict the position

IP prefix

2021
22
23

133.1.0.0 /16
133.1.2.0 /23
133.1.5.0 /24
133.1.16.0 /20...

31

Search for the longest
matching prefix

Position

Next Hop...

Ingress packet

ABCD

Computation Time and Memory Size

Computation time: The number of CPU cycles required
to find the next hop for one IP addressLC-Trie FIB: 112 CPU cycles
Learned FIB: 115 CPU cycles

Memory sizeLC-Trie FIB: 2.504 Mbytes

vertices: 534,093 (32 bits/vertices)bits for the skip bit validation: 6,772 bytes

next-hop information: 360,879 bytes

Learned FIB: 1.173 Mbytes32LC-Trie FIB must maintain a bit sequence for validating skipped bits

Keys in FIB entries: 229,454 (4 byte/entry)
weights in model: 6,400 (4 byte/weight)
next-hop information: 360,879 bytes

Summary

100 Gbps NDN packet forwarding is almost solved

Remaining issues for toward 10 Tbps NDN packetforwarding

33

High speed LPM for name prefixes
Sharding based on front end cache

Approaches of hardware routers
Research direction for accommodating large FIB

REFERENCES

34

References[1] V. Jacobson, D. Smetters, J. Thornton, M. Plass, N. Briggs, and R. Braynard,“Networking Named Content,” Proceeding of ACM CoNEXT 2009, pp.1-12, December
2009.
[2] W, So, a. Narayanan, D. Orran, “Named data networking on a router: fast and DoSresilient forwarding with hash tables,” in Proceedings of ACM/IEEE ACNS, pp.21-226,
2013.
[3] J. Takemasa, Y. Koizumi and T. Haseagawa, “Load Balancing for Stateful Forwarding
by Mitigating Heavy Hitters: A Case for Multi-Threaded NDN Software Routers,” IEEEAccesss, vol. 8, pp. 155071-155085, 2020.
[4] G. Carofiglio, M. Gallo, L. Muscariello and D. Perino, “Pending Interest Table Sizing inNamed Data Networking,” in Proceedings of ACM ICN 2015, pp. 49–58, Sept. 2015.
[5] D. Perino and M. Varvello, “A Reality Check for Content Centric Networking,” inProceedings of ACM ICN 2011, pp.44-49, Aug. 2011.
[6] J. Takemasa, Y. Koizumi and T. Hasegawa, “Data Prefetch for Fast NDN Software
Routers based on Hash Table-based Forwarding Tables,” Computer Networks, Volume173, 22 May 2020.
[7] H. Dai, J. Lu, Y. Wang and B. Liu, “BFAST: Unified and scalable index for NDN
forwarding architecture,” in Proceedings of IEEE Infocom, pp.2290-2298, May, 2015.
35

References[8] Y. wang, T. Pan, Z. Mi, H. Dai and X. Guo, T. Zhang, B. Liu and Q. Dong, “NameFilter:Achieving fast name look up with low memory cost via applying two-stage bloom filters,”
in Proceedings of IEEE Infocom Mini Conference, pp. 95-99, May. 2013.
[9] T. Song, H. Yuan, P. Crowley and B. Zhang, “Scalable name-based packet forwarding:from millions to billions,” in Proceedings of ACM ICN, pp.19-28, Sept. 2015.
[10] D. Kirchner, R. Ferdous, R. Lo Cigno, L. Maccari, M. Gallo, D. Perino, and L. Saino,“Augustus: a CCN router for programmable networks,” in Proceedings of ICN, pp. 31–39,2016.
[11] J. Shi, D. Pesaventoa and L. Benmohamed, “NDN-DPDK: NDN Forwarding at 100
Gbps on Commodity Hardware,” in Proceedings of ACM ICN, pp.30-40, Sept. 2020.
[12] B. Fan, H. Lim, D. G. Anderson and M. Kaminsky, “Small cache, big effort: Provableload balancing for randomly portioned cluster services,” in Proceedings of 2nd ACM Symp.
Cloud Comput., pp.1-12, 2013.
[13] L. Saino, I. Psaras, and G. Pavlou, ``Understanding sharded caching systems,'' in Proc. 35th Annu. IEEE Int. Conf. Comput. Commun., Apr. 2016, pp. 1-9.
[14] Hyeontaek Lim et al., “MICA: A holistic approach to fast in-memory key-valuestorage”, in Proceedings od USENIX NSDI 14, pp.429-444, April 2014.
[15] D. Perino, M. Varvello, L. Linguaglossa, R. Laufer, R. Boislaigue, “Caesar: A content
router for highspeed forwarding on content names,” In Proceedings of ACM ANCS 2014,oo.137-148, Feb. 2014.
36

References[16] S. Signorello, R. State, J. François and O. Festor, "NDN.p4: Programming
information-centric data-planes," 2016 IEEE NetSoft Conference and Workshops(NetSoft), 2016, pp. 384-389, doi: 10.1109/NETSOFT.2016.7502472.
[17] Shunsuke Higuchi, Junji Takemasa, Yuki Koizumi, Atsushi Tagami and Toru
Hasegawa, “Feasibility of Longest Prefix Matching using Learned Index Structures,” ACM
SIGMETRICS Performance Evaluation Review, Volume 48, Issue 4, pp 45–48, March2021.

37