5 Naming, Addressing, and Forwarding

Question 1

Name the mechanism and techniques for MPLS, Ethernet, and ATM Protocols

Answer 1

Mechanism: Exact Match
Techniques: Direct Lookup, Associative lookup, hashing, binary tree

+ Simple
+ O(1)
- Insufficient use of memory

Question 2

Name the mechanism and techniques for IPv4 and IPv6 protocols

Answer 2

Mechanism: Longer Prefix Match
Techniques: Radix Trie, Compressed Trie, Binary Search on prefix int.

LPM harder than exact match. Dest. IP does not indicate length

Question 3

Trie

Answer 3

prefixes “spelled out” by following path from root

Question 4

Single Bit Trie

Answer 4

very efficient, efficient use of memory.

Main problem is the number of memory access required to perform a lookup.

At worst 32 accesses.

Question 5

Direct Trie

Answer 5

Instead of 1 bit per lookup, there is one memory access responsible for looking at a large number of bits

inefficient use of memory

Question 6

Multi-bit Trie (“Multi-Ary Trie”)

Answer 6

memory efficiency of a single bit trie + fast lookup properties of a direct trie

Question 7

Content-Addressable Memory (CAM)

Answer 7

Alternative to LPM w/Tries

input: tag (address)
output: value (port)

exact match O(1)

Question 8

Ternary CAM

Answer 8

Instead of exact match (0,1,*), permits implementation of LPM

Question 9

Solutions to IPv4 running out of addresses

Answer 9

• Network Address Translation (NAT)

- IPv6 (128-bit addresses)

Question 10

Network Address Translation (NAT)

Answer 10

Multiple networks can reuse the same private IP address space

Question 11

IPv6

Answer 11

simpler header and addresses that are much larger (more bits)

multihoming is easier

security

Question 12

Name incremental deployments for IPv6 (Issue is that IPv6 results in significant incompatibility)

Answer 12

“Dual Stack” deployment - host speaks both IPv4 and IPv6

Relies on a translator

v6 to 4 tunneling - encapsulation/decapsulation of packets