5-Naming, Addressing & Forwarding

Question 1

IP Addressing or “dotted quad”

Answer 1

32-bit number or 2^32 = 4294967296

32/4 = 8 bits each

Question 2

Pre-1994: Classful” Addressing

Answer 2

Addresses were divided into 2 portions

1) Network ID portion
2) Host ID portion

Class A |0Net ID (8 bits) |Host ID (2^24 bits) | Class B |10|Net ID (2^14 bits) |Host ID (2^16 bits) |
Class C |110|Net ID (24 bits) |Host ID (8 bits) |

Question 3

IP Address Allocation

Answer 3

IANA (Internet Assign Numbers Authority) -> has authority to allocate address space
Regional Routing Registries: AFRINIC (Africa), APNIC (Aisia and Austraila), ARIN (North America), LACNIC (Latin america) , RIPE (Europe)
ARIN-> allocates address space to individual networks like GAtech

Question 4

IANA recently allocated all /8 address blocks

Answer 4

Out of IPv4 addresses! Doesn’t mean that you can no longer attach a new device to the internet (there are other ways of coping)

Question 5

Query an IP Address

Answer 5

whois -> tells you the owner and gives contact email of that particular prefix

Question 6

Adopted in 1994: 32 bits: IP address + “mask”

Answer 6

CIDR - Classless Interdomain Routing

Question 7

Longest Prefix Match

Answer 7

If a routing table has 2 overlapping entries, it should forward according to the entry that has the longest prefix/mask length (the prefix with longer mask length is more specific than the prefix with shorter mask or the larger prefix)

Question 8

The benefits of CIDR and Longest Matching Prefix

Answer 8

Efficiency, Hierarchy /aggregation

Question 9

The practice of connecting a host or a computer network to more than one network. This can be done in order to increase reliability or performance.

Answer 9

Multihoming

Question 10

Frustrates Aggregation

Answer 10

Multihoming

Question 11

Can be used to control inbound traffic

Answer 11

Longest Prefix

Question 12

Link aggregation

Answer 12

Link aggregation (LAG) is used to describe various methods for using multiple parallel network connections to increase throughput beyond the limit that one link (one connection) can achieve

Question 13

How many IP addresses in a /22 prefix?

Answer 13

2^10 or 1024

The /22 represents the length of the network ID.
The remaining 10 bits are for hosts on that /22 prefix.

Question 14

IPv4 and IPv6 lookup algoritms

Answer 14

Mechanism: Longest Prefix Match
Techniques: Radix Trie
Compressed trie
Binary search on prefix intervals

Question 15

Alternative to LPM or longest prefix match: exact match

Answer 15

Address lookup using tries

LPM is horribly innefficient and wasteful of memory

Question 16

Prefixes are “spelled out” by following path from root

Answer 16

In a Trie (Bit 1 takes us to the right and bit 0 takes us to the left)

Question 17

During a lookup, if the entry isn’t there, use entry of last node of tree we traversed.

Answer 17

“Single -bit trie”

Can be bad… 32 accesses in the worst case.

Question 18

Inefficient use of memory

Answer 18

Direct trie

remember the diagram with 2 memory accesses and the quiz with 3 memory accesses

Question 19

How many entries for a /20 prefix?

Answer 19

16

Question 20

To achieve the memory efficiency of a single-bit trie with the fast lookup properties of a direct trie… a compromise is to use a ……

Answer 20

Multi-bit Trie (aka Multi-ary-trie)

Question 21

Saves space by pushing entries to the left and right side of the node

Answer 21

“Leaf-pushed” trie

Lulea is a 3-level trie
Patricia is another algorithm

Question 22

A hardware based route lookup where the input is a tag and the output is a value

Answer 22

CAM = Content addressable Memory

Ternary CAM supports a wildcard -> permits implementation of LPM (Longest prefix match)

Question 23

possible solutions to the IPv4 problem?

Answer 23

NAT - Network Address Transalation

IPv6 (128 bit addresses)

Question 24

allows multiple networks to reuse the same private IP address space by translating them to a globally visible IP address.

Answer 24

NAT

Question 25

Popular on Broadband access networks, SOHO (small or home offices), VPNs… this violates the end to end model

Answer 25

NAT

Question 26

10/8

172. 16/12
173. 168/16

Answer 26

(10. 0.0.0 through 10.255.255.255)
(172. 16.0.0 through 172.31.255.255)
(192. 168.0.0 through 192.168.255.255)

Question 27

IPv6

Answer 27

128 bits:
Top 48 bits: Public Routing Topology (3 bits for aggregation, 13: tier 1 ISP, 8 reserved, 24 additional)
16-bit site identifier
64 bit: interface ID (48 bit ethernet + 16 more bits)

Question 28

IPv6 benefits

Answer 28

More addresses
Simpler header
Multihoming is easier
Security (IPv6 crypto extentions)

Question 29

IPv6 hardships

Answer 29

Hard to deploy incrementally!

The narrow waist -> so many things are built on this topology

Question 30

Host can speak both IPv4 and IPv6

Answer 30

Dual stack host

Question 31

A v6 packet is encapsulated in a v4 packet

Answer 31

v6 to 4 tunneling (requires gateway boundaries to perform encapsulation and decapsulation when ntering and leaving)