5-Naming, Addressing & Forwarding Flashcards
IP Addressing or “dotted quad”
32-bit number or 2^32 = 4294967296
32/4 = 8 bits each
Pre-1994: Classful” Addressing
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) |
IP Address Allocation
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
IANA recently allocated all /8 address blocks
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)
Query an IP Address
whois -> tells you the owner and gives contact email of that particular prefix
Adopted in 1994: 32 bits: IP address + “mask”
CIDR - Classless Interdomain Routing
Longest Prefix Match
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)
The benefits of CIDR and Longest Matching Prefix
Efficiency, Hierarchy /aggregation
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.
Multihoming
Frustrates Aggregation
Multihoming
Can be used to control inbound traffic
Longest Prefix
Link aggregation
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
How many IP addresses in a /22 prefix?
2^10 or 1024
The /22 represents the length of the network ID.
The remaining 10 bits are for hosts on that /22 prefix.
IPv4 and IPv6 lookup algoritms
Mechanism: Longest Prefix Match
Techniques: Radix Trie
Compressed trie
Binary search on prefix intervals
Alternative to LPM or longest prefix match: exact match
Address lookup using tries
LPM is horribly innefficient and wasteful of memory
Prefixes are “spelled out” by following path from root
In a Trie (Bit 1 takes us to the right and bit 0 takes us to the left)
During a lookup, if the entry isn’t there, use entry of last node of tree we traversed.
“Single -bit trie”
Can be bad… 32 accesses in the worst case.
Inefficient use of memory
Direct trie
remember the diagram with 2 memory accesses and the quiz with 3 memory accesses
How many entries for a /20 prefix?
16
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 ……
Multi-bit Trie (aka Multi-ary-trie)
Saves space by pushing entries to the left and right side of the node
“Leaf-pushed” trie
Lulea is a 3-level trie
Patricia is another algorithm
A hardware based route lookup where the input is a tag and the output is a value
CAM = Content addressable Memory
Ternary CAM supports a wildcard -> permits implementation of LPM (Longest prefix match)
possible solutions to the IPv4 problem?
NAT - Network Address Transalation
IPv6 (128 bit addresses)
allows multiple networks to reuse the same private IP address space by translating them to a globally visible IP address.
NAT
Popular on Broadband access networks, SOHO (small or home offices), VPNs… this violates the end to end model
NAT
10/8
- 16/12
- 168/16
(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)
IPv6
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)
IPv6 benefits
More addresses
Simpler header
Multihoming is easier
Security (IPv6 crypto extentions)
IPv6 hardships
Hard to deploy incrementally!
The narrow waist -> so many things are built on this topology
Host can speak both IPv4 and IPv6
Dual stack host
A v6 packet is encapsulated in a v4 packet
v6 to 4 tunneling (requires gateway boundaries to perform encapsulation and decapsulation when ntering and leaving)
