Internet Routers
[Link]
Sample Routers
Router Functionality
O U T P U T P O R T S
I N P U T P O R T S
Rule Table
Used to decide where to send a packet next (next hop).
Destination address. Can get as large as ~1M rules
Router Rule Table
USA Output port 1 Illinois Port 2 Chicago Port 3 Europe Port 4 Asia Port 5 Etc.
Router Rules
Range
[35, 2096]
Address/mask pair
101100/011101 Matches 101100, 101110, 001100, 001110.
Prefix filter.
Mask has 1s at left and 0s at right. 101100/110000 = 10* = [32, 47]. Special case of a range filter.
Example Router Table
P1 = 10* P2 = 111* P3 = 11001* P4 = 1* P5 = 0* P6 = 1000* P7 = 100000* P8 = 1000000*
P1 matches all addresses that begin with 10.
Tie Breakers
First matching rule. Highest-priority rule. Most-specific rule.
[2,4] is more specific than [1,6]. [4,14] and [6,16] are not comparable.
Longest-prefix rule.
Longest matching-prefix.
Longest-Prefix Matching
P1 = 10* P2 = 111* P3 = 11001* P4 = 1* P5 = 0* P6 = 1000* P7 = 100000* P8 = 1000000*
Destination = 100000000 P1, P4, P6, P7, P8 match this destination P8 is longest matching prefix
Table Size
1M+ rules Prefix up to 32 bits in IPv4 Prefix up to 128 bits in IPv6 OC192, 10Gbps 32 mpps (40-byte packets) Log2 n schemes make too many memory accesses. 50,000 updates/sec
Handling Updates
Batch
Control Plane Updates
No lookup delay Rebuild time Time to switch Double resource Data Plane Lookups
Handling Updates
Incremental
Control Plane Updates
Minimize lookup lockout
Data Plane Lookups
Ternary CAMs
011*
000*
H7 H6 H5 H4 H3 H2 H1 SRAM
d = 011001
Priority Encoder
11*
Longest prefix matching
Highest priority matching Insert/Delete
01*
00*
0*
*
TCAM
Ternary CAMs
Capacity Cost Power Board space Scalability to IPv6? Ranges? Multidimensional filters?
1-Bit Trie
P1 = 10* P2 = 111* P3 = 11001* P4 = 1* P5 = 0* P6 = 1000* P7 = 100000* P8 = 1000000*
P8 P5 P4 P1
P2
P6
P3
P7
Complexity
P5 P4 P1
O(W)/operation
P6
P2
P3
P7 P8
Batch Updates
Reduce number of memory accesses for a lookup.
Multibit trie.
Multibit Tries
Branching at a node is done using >= 1 bit (rather than exactly 1 bit)
Fixed stride
Nodes on same level use same number of bits
Variable stride
Fixed-Stride Tries
Number of levels = number of distinct prefix lengths. Use prefix expansion to reduce number of distinct lengths.
Prefix Expansion
P1 = 10* P2 = 111* P3 = 11001* P4 = 1* P5 = 0* P6 = 1000* P7 = 100000* P8 = 1000000* P1 = 10* P2a = 11100* P2b = 11101* P2c = 11110* P2d = 11111* P3 = 11001* P4a = 11* P5a = 00* P5b= 01* P6a = 10000* P6b = 10001* P7a = 1000001* P8 = 1000000*
#lengths = 7
#lengths = 3
Fixed-Stride Trie
2 3
P6 P6
P5 P5 P1 P4
3
P3 P2 P2 P2 P2
2
P8 P7
Optimization Problem
Find least memory fixed-stride trie whose height is at most k.
P5 P5 P1 P4
P6 P6 P3 P8 P7 P2 P2 P2 P2
Variable-Stride Tries
P6
P5
P4
P1
P2
P3
P7
P8
P5 P5 P1 P4
3
5
P8 P7 P6 P6 P6 P6 P6 P6
P3 P2 P2 P2 P2
...
Binary Tries
011* 000* 11* 01*
H7 H6 H5 H4 H3 H2 H1 H6 H3
H1
H2
H4 H7 H5
00*
0* *
Succinct Representation of Tries
4 bytes/ptr 8 bytes+ per node
24+ bytes
Succinct Representation of Tries
a b a b
c
d d
Internal Bit Map (IBM) = 101001001000000
Next Hop List = abcd 15 bits for IBM vs 24 bytes for child pointers
Popcount
Succinct Representation of Tries
a
b
c d
Shape Bit Map (SBM) = 111101001
Internal Bit Map (IBM) = 101011 Next Hop List = abcd
15 bits for SBM & IBM vs 24 bytes for child pointers
Binary Trie
P1 = * P2 = 0* P3 = 000* P4 = 10* P5 = 11* (a) prefixes
Tree Bitmap
Shape Shifting Trie
Hybrid Shape Shifting Trie
Ternary CAMs and Tries
011* 000* 11* 01*
H7 H6 H5 H4 H3 H2 H1 SRAM 00* 000*
0*
01* 011* 11*
00*
0* * TCAM
Ternary CAMs and Tries
00*
* 0* 00* 000* 01* 011* 11*
0,2
2,3 5,2 ISRAM
000*
00* 011* 01*
H6 H3 H7 H4
0*
* ITCAM
0* 11*
* DTCAM
H2 H5
H1 DSRAM
Two-Dimensional Filters
Destination-Source pairs. (0*, 1100*)
Dest address begins with 0 and source with 1100
Least-cost tie breaker
(0*, 11*, 4) and (00*, 1*, 2) Packet (00, 11) Use second rule.
2D 1-Bit Tries
F1 = (0*, 1100*, 1) F2 = (0*, 1110*, 2) F3 = (0*, 1111*, 3) F4 = (000*, 10*, 4) F5 = (000*, 11*, 5) F6 = (0001*, 000), 6) F7 = (0*, 1*, 7)
2D Multibit Tries
F1 = (0*, 1100*, 1) F2 = (0*, 1110*, 2) F3 = (0*, 1111*, 3) F4 = (000*, 10*, 4) F5 = (000*, 11*, 5) F6 = (0001*, 000), 6) F7 = (0*, 1*, 7)
Space-Optimal 2D Multibit Tries
Given k. Find 2DMT that can be searched with <= k memory accesses and has minimum memory requirement.
2D Binary Tries
Succinct representations 2D hybrid shape shifting tries with minimal memory and specified bound on number of memory accesses to do a lookup