L5 - Naming, addressing, forwarding

Question 1

How was IP addressing done before 1994?

Answer 1

“Classful Addressing” - the 32 bit addresses were divided into a network id portion and a host ID portion.

Question 2

What were class A addresses?

Answer 2

An IP address starting with a 0 to indicate a class A address, followed by 7 bits for the network and 24 bits for the host.

Question 3

What were class B addresses?

Answer 3

An IP address starting with a 10 to indicate a class B address, followed by 14 bits for the network and then 16 bits for the host

Question 4

What were class C addresses?

Answer 4

An IP address starting with a 110 to indicate a class C address, followed by 21 bits for the network and then 8 bits for the host (meaning each class C network could only have 255 hosts!)

Question 5

By 1994 growth rates were exceeding hardware and software capabilities, and we were running out of class C networks. What was the solution?

Answer 5

CIDR - classless interdomain routing

Question 6

Who assigns IP address space?

Answer 6

IANA (internet assigned numbers authority) allocates regional routing registries to AFRINIC, APNIC, ARIN (North America), LACNIC, and RIPE (Europe). IANA just finished allocating all remaining /8 blocks, hence “we are out of IPv4 addresses”

Question 7

What is CIDR?

Answer 7

Classless Interdomain Routing. Instead of having a fixed network ID and host ID portions, we have an IP address and a network ‘mask’ indicated by a slash. This allows assigners to allocate a range appropriate to the size of the assignee.

Question 8

How does CIDR deal with overlapping network prefixes in IP addresses?

Answer 8

Routers must use “longest prefix match” for when an IP address has a prefix that matches two or more entries in a routing table .

Question 9

What are the benefits of longest prefix match (LPM) in CIDR?

Answer 9

1 - Efficiency - prefix blocks can be allocated on a much finer granularity than with classical routing
2 - Aggregation - this can happen if two downstream networks with more specific prefixes are treated in the same way by an upstream network, which can just combine two prefixes into one entry in a routing table.

Question 10

What is ‘multi-homing’?

Answer 10

Multi-homing is the ability for an AS to be reachable through two or more ISPs. It was a significant contributor to the fast growth of routing tables around 2000.

Question 11

What is a problem of multi-homing combined with LPM matching?

Answer 11

If an AS is reachable from two ISPs, each ISP cannot aggregate the prefix. This is the AS will always receive traffic from the ISP which did not aggregate (because it advertises a longer prefix). This resulted in a lot of /24 addresses.

Question 12

How can you load balance your traffic with LPM?

Answer 12

In addition to advertising a shorter prefix on multiple links, you would also split your prefix into multiple parts and advertise one on each link. The ‘split’ prefix is more specific.

Question 13

How are IP addresses looked up in routing tables?

Answer 13

It depends on the protocol - Ethernet uses exact match lookup (using binary tree, hash lookup, whatever). IPv4 and IPv6 use LPM most often as a trie

Question 14

What are the advantages and disadvantages of exact match lookup in Ethernet?

Answer 14

Advantages of exact match is that it is simple and has O(1) time. However, it is an inefficient use of memory.

Question 15

What are the main forms of trie used for LPM?

Answer 15

• Single bit tries (efficient use of memory, easy insertion, but could require 32 lookups in worst case)
• Direct tries (more bits used at each lookup, fewer lookups, but inefficient use of memory)
• Multi-ary trie (this combines the memory efficiency of single bit and fast lookup of direct)

Question 16

What is a multi-ary trie?

Answer 16

It is a trie that resolves k bits at each level, so the degree (number of branches at each level) is 2^k, depth is W/k (where W is the depth of the 32 bit binary trie)

Question 17

What are two solutions to the internet routing problem (not enough addresses)

Answer 17

IPv6 and NAT

Question 18

How can we do incremental IPv6 deployment?

Answer 18

We can do dual-stack deployment (the host speaks IPv4 and IPv6, depending on who it is communciating with). We can achieve this through a translator, embedding IPv4 inside an IPv6 address, or “6 to 4 tunneling” where a v6 packet is encapsulated inside a v6 packet.