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
