Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS6250 - Networking > Lesson 5 - Naming, Addressing, Forwarding > Flashcards

Lesson 5 - Naming, Addressing, Forwarding Flashcards

1
Q

Nuts and bolts that make routing possible

A

Naming, addressing, forwarding

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

IP stands for

A

Internet Protocol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Which version of IP is widely deployed on the internet today?

A

Version 4 (IPv4)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How many bits in an IPv4 address?

A

32

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How is an IP address formatted?

A

Dotted notation

  • Breaking it up with dots is just a convenient way of writing an 32-bit number. It’s made up of 4 8-bit numbers.
  • It allows for 4^32 addresses (or about 4 billion)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Problems with pure IPv4

A
  • We’re running out of addresses
  • 4 billion is a lot to deal with. Can’t just have it in one table. Lookups would be slow. Need a way to group. Was much more inefficient pre-1994.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Classful addressing

A

-Addresses were divided into a network ID portion and a host ID portion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Class A address

A
  • Starting with a 0 as the first bit is a class A address
  • This picks half of all IP addresses
  • Next 7 bits (combined with the first) represent the network ID for the network that owns this portion of address space
  • Remaining portion (24 bits) is dedicated for hosts ON THAT NETWORK. This means that a class A address can support 2^24 IP addresses.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Class B address

A
  • Starts with a 10
  • First 16 bits signify network ID, remaining 16 bits signify host ID
  • Each class B address SPACE represents about 1/65,000th of all internet address space
  • Discounting the first 2 bits which indicate it’s a class B network we have about 2^14th class B’s
  • Each of the class B networks can have 2^16 (65,000) hosts on each network
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Class C address

A
  • Use the first 24 bits for the NET ID and the remaining 8 for the host ID
  • Each class C network essentially can only have 255 hosts on it
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

BGP routing table from ’89-’94

A
  • Grew slowly. By 1994, had around 1500 IP addresses.
  • Growth rates were exceeding hw/sw capabilities, and in particular we began to run out of the class C address allocation, because only a certain range of the IP address space could be used for class C addresses
  • Began to accelerate around 1994
  • There began to be a need for more flexible allocation. The solution to this problem was something called Classless Interdomain Routing or “CIDR” (pronounced like cider)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

IANA

A

“eye-ana”

  • The top of the hierarchy, allocates IP address space to ISP’s
  • has authority to allocate address space to what are called regional routing registries
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

IANA regional routing registries

A
  • AfriNIC (Africa)
  • APNIC (Asia and Australia)
  • ARIN (North America)
  • LACNIC (Latin America)
  • RIPE (Europe)
  • A regional routing registry, ARIN for example, allocates address space to individual networks like GaTech
  • Address space across regions is far from even
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

/8 address space means

A

IPv4 address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does it mean to say we’re running out of IPv4 addresses?

A

It doesn’t mean you can’t get a new device on the internet. There are various ways of coping with it. It just means that IANA no longer has anymore /8 blocks to give to these regional registries

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

whois

A
  • Querying an IP address using whois and a routing registry such as ra.net will tell you the owner of that particular prefix
  • Also gives the autonomous system number
  • Routing registry entry also gives us more information such as who to contact if we need to contact the owner of this address space.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

CIDR

A
  • Classless Interdomain Routing
  • Instead of having fixed network ID and host ID portions of the 32 bits, we’d simply have an IP address, plus what’s known as a mask, which is variable length and indicates the length of the network ID.
  • For example, suppose we have an IP address like 64.14.248.0/22. The “/22” indicates the mask length, which says that the first 22 bits should represent the network ID.
  • The key is that the mask length is variable, and no longer depends on the range of IP addresses that are being used.
  • This allows those allocating IP address ranges to both allocate a range that’s more fitting to the size of the network, and also not have to be constrained about how big the network ID should be depending on where in the IP address space the prefix is being allocated from.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Complications of CIDR

A
  • it’s possible to have overlapping address prefixes.
  • For example: 64.14.248.0/24 is a subset of 64.14.248.0/22
  • What do you do when they both show up in a routing table?
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Longest prefix match

A
  • Suppose overlapping address prefixes show up in a routing table
  • The solution is to forward on what’s called the “longest prefix match”. Meaning that if a routing table has 2 overlapping entries, it should forward according to the entry that has the longest prefix or the longest mask length.
  • Intuitively that makes sense because the prefix with the longer mask length is more specific than the prefix with the shorter mask (aka the larger prefix).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Benefits of CIDR and Longest prefix match

A
  • Efficiency: prefix blocks can be allocated on a much finer granularity than with classful interdomain routing
  • Hierarchy/organization: opportunity for aggregation if 2 downstream networks with more specific/longer prefixes should be treated in the same way by an upstream network, who might simply aggregate 2 contiguous shorter prefixes into 1 forwarding table entry with a shorter prefix
  • If the rest of the internet only reached A and B via C, then the rest of the internet need only know about C’s address space which might be 12/8. This would allow the upstream network to simply aggregate or not announce these more specific prefixes since they’re already covered by the less specific upstream prefix
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

CIDR’s effect on growth of internet routing table

A
  • Significant slowing from 1994 to 1998
  • We see roughly linear growth during that time
  • Fast growth resumed around 2000 because of multihoming, which can make it difficult for upstream providers to aggregate IP prefixes together, often requiring an upstream provider to store multiple IP prefixes for a single autonomous system. Sometimes those IP prefixes are contiguous and sometimes they aren’t.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Multihoming

A
  • AS (30308 for example) wants to be reachable via 2 upstream internet service providers
  • To do so, it needs to advertise its prefix which it received from AT&T via both AT&T and Verizon.
  • The problem occurs when AT&T and Verizon want to advertise that prefix to the rest of the internet.
  • AT&T would like to aggregate this prefix, but it can’t. If it did, Verizon would still be advertising the longer /24 via its upstream link, and because of longest prefix match, all of the traffic would then arrive via the Verizon link, regardless of what AS 30308 wanted to have happen to that incoming traffic.
  • As a result, both AT&T and Verizon must advertise the same /24 to the rest of the internet. This results in an explosion of /24’s in the global internet routing table.
  • If a lot of “Stub” AS’s wanted to be multihomed, then suddenly we’ve got a lot more /24’s in the global routing table than might not otherwise exist without multihoming
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

AS path pre-pending

A
  • Can be used to control inbound traffic

- Longest prefix match can too! Re-watch video on this.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

CIDR Report

A
  • Released weekly
  • Shows AS’s who are advertising IP prefixes that, at least according to observation, are contiguous and could be aggregated
  • Top offender for the week shown below was advertising more than 3,000 unique IP prefixes. The CIDER Report’s analysis suggests that with appropriate aggregation, this AS could instead advertise only 56 unique IP prefixes.
  • This might be overly optimistic (sometimes deaggregating necessary), but altogether the CIDR Report shows that there are a lot more IP prefixes in the global internet routing table than there could be if AS’s took full advantage of aggregation.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

How many IP addresses in a /22 prefix?

A

2^10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

LPM can be implemented in different ways

A
  • Radix trie
  • Compressed trie
  • Binary search on prefix intervals
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What lookup algorithm does a router use

A

Depends on the protocol that it’s using to forward packets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

IPv4 and IPv6 use which protocol to forward packets?

A

Longest prefix match

-Some protocols use exact match

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Ethernet-based forwarding is based on…

A

An exact match of a layer 2 address

  • Usually 48 bits long
  • It’s global (not just local to the link) and the range or size of the address is not negotiable
  • 2^48 is MUCH bigger than 2^12. Therefore, not possible to hold all the addresses in the table and use direct lookup
30
Q

Advantages of exact matches in ethernet switches

A
  • Exact match is simple

- Expected lookup time is small , or O(1)

31
Q

Disadvantages of exact match in ethernet switches

A
  • Inefficient use of memory

- Potentially resulting in non-deterministic lookup time if a lookup might require multiple memory accesses

32
Q

LPM is _____ to perform than exact match

A

Harder.
-Destination IP address does not indicate the length of the longest matching prefix, so some algorithm needs to determine the length of the longest matching prefix
-We somehow need a way to search the space of all prefix lengths, as well as prefixes of a given length
-

33
Q

LPM in IPv4 using exact match

A
  • Horribly inefficient
  • We’d have to have tables for each of these lengths, and every time a packet arrived we’d have to send it to each of these 32 tables. This is extremely wasteful memory
34
Q

A trie is a type of _____

A

Data structure

-Rewatch these lectures

35
Q

Single bit trie

A

Go right or left for each bit

  • Very efficient, very efficient use of memory
  • Updates very simple
  • Main problem is # of memory accesses required to perform a lookup
  • For a 32-bit address, a lookup in a single-bit trie might require 32 lookups in the worst case (one for each bit). Each bit in the address requires one traversal in the trie, aka one memory lookup.
  • For perspective, an OC48 requires at most 4 accesses. 32 accesses is far too many, especially for high-speed links.
36
Q

Direct trie

A
  • Other extreme from single bit
  • Instead of 1 bit per lookup, we might have 1 memory access responsible for looking up a much larger number of bits.
  • For example, a 2-level trie: first memory access is dictated by the first 24 bits of the address, and the second memory access is dictated by the last 8 bits of the address. In the second access, we can look up an entry in the forwarding table with just 2 memory accesses. The problem is that this whole structure results in a very inefficient use of memory, unlike the single-bit try.
  • Suppose that we want to represent a /16 prefix. Unfortunately we have no way of encoding a lookup that’s just 16 bits. We have to, rather, encode 2^8 identical entries corresponding to the 2^8 /24 prefixes that are contained in that /16, so this is an extremely inefficient use of memory.
  • REWATCH VIDEOS
37
Q

Suppose we have a direct trie where the first level is 16 bits, the next level is 8 bits, and the 3rd level is the final 8 bits. In the worst case, how many memory accesses would be required per lookup?

A

3

-Because the trie has a depth of 3, in the worst case, a lookup might require 3 memory accesses

38
Q

Suppose we have a direct trie where the first level is 16 bits, the next level is 8 bits, and the 3rd level is the final 8 bits. How many entries would I need to represent a /20 prefix?

A

16.
-A /20 prefix is 2^4 or 16 /24’s. I need to basically represent 16 entries at the 24-bit level of the trie or the second level, and therefore I’d need 16 entries to represent a /24 prefix.

39
Q

How do we achieve the memory efficiency of a single-bit try with the fast-lookup properties of a direct trie?

A
  • Double check if this question is even correct

- Use a Multi-bit Trie (AKA “Multi-Ary” Trie). It has multiple (k) bits per level

40
Q

What is the simplest case of the multi-ary trie?

A

Binary trie (k = 1)

41
Q

What is k in a 4-ary trie?

A

2

42
Q

Leaf-pushed trie

A

Helps save space further (beyond using a k-ary trie

-Instead of having pointers we can push entries into the left and right side of the node

43
Q

Lulea

A

Optimization algorithm, uses a 3-level trie, often a bitmap to compress out repeated entries

44
Q

PATRICIA

A

Optimization algorithm

45
Q

Alternatives to LPM with Tries

A
  • Content-addressable memory (CAM)

- Ternary CAM

46
Q

CAM

A
  • Only supports exact match
  • Content-addressable memory
  • HW-based route lookup where the input is a tag and the output is a value (example: address and output port)
  • Really only supports exact match but is an O(1) lookup
47
Q

Ternary CAM

A
  • Instead of exact matching in the tag, you can have 0, 1, or don’t care (*)
  • Ternary CAM’s support for wildcard permits implementation of LPM
  • One can thus have multiple matching entries but then prioritize the match to the longest prefixing the ternary CAM
48
Q

2 solutions to IPv4 internet routing table growth/running out of address space

A
  • Network Address Translation (NAT)
  • IPv6 (whose main feature is 128-bit addresses). Basically, add more bits!

-Note about running out: In addition to being limited to 2^32 total unique addresses, IPv4 addresses are typically allocated in blocks. That fragmentation can mean that IPv4 addresses can be quickly exhausted. The last /8 has already been given out to a registry, so in some sense you can say we’ve already run out.

49
Q

NAT

A
  • Network Address Translation
  • Allows multiple networks to use the same private IP address space
  • Takes private IP address spaces that are behind the NAT and translates them to a single globally visible IP address
  • Now, to the rest of the internet, network 1 appears to be reachable by a single IP address, and network 2 by a different single distinct IP address
50
Q

Where NAT is needed

A

-Suppose se have 2 networks. They might be homes, or larger networks in regions of the internet where IPv4 address space is scarce (e.g. in developing regions)

51
Q

The key behind NAT

A
  • The the packet has a source port, and the NAT is going to take that source IP address and port, and translate it into a publicly reachable source IP address and port. The destination remains the same.
  • Now when a packet comes back from the global internet destination, the NAT has a table that knows the mapping between the public IP address/port and the private IP address/port. It can rewrite the destination IP address of the packet to the corresponding private address.
52
Q

Where are NATs popular?

A
  • On broadband access networks, small or home office (SOHO), and VPN’s
  • There’s a clear savings in IPv4 address space since there can be many devices in one of these private networks, and yet all of the devices behind the NAT only use up 1 public IP address
53
Q

Drawbacks of NAT

A
  • End-to-end model is broken
  • If the NAT device failed in this instance, for example, the mapping between the private source IP address and port and the public IP address/port would be lost, thereby breaking all active connections for which the NAT is on the path
  • It’s also asymmetric. In certain circumstances, it’s difficult for a host on the global internet to reach a host in a private address space because by default those devices do not have public globally reachable IP addresses
54
Q

What 2 things does NAT break?

A

End-to-end communications AND bidirectional communication (it’s asymmetric!)

55
Q

IPv6 provides

A
  • more addresses
  • simpler header
  • multihoming supposedly easier
  • various aspects of security are built in (IPv6 crypto extensions)
56
Q

IPv6 address format

A
  • Top 48 bits = public routing topology (3 bits for aggregation, 13 “tier-1” for top level provider like an ISP, 8 reserved bits, and 24 additional bits
  • Then a 16-bit site identifier
  • Then a 64-bit interface ID (48-bit Ethernet + 16 more bits)
57
Q

“Today”, how many IPv4 and IPv6 addresses?

A
  • 500,000 IPv4

- 16,000 IPv6

58
Q

Why is IPv6 hard to deploy incrementally?

A
  • Narrow waist: everything runs on IPv4, which was designed to run over a variety of physical layers.
  • This common protocol has allowed tremendous growth, but because everything depends on the narrow waist of IPv4, and because IPv4 is build on top of so many other types of infrastructure, changing it becomes extremely tricky.
  • Incremental deployment (part of the internet running IPv4 and other parts upgraded to IPv6) results in significant incompatibility. There are various incremental deployment options for IPv6.
59
Q

Dual stack deployment

A
  • One option for incremental deployment for IPv6
  • Communicates with an IPv4 host using IPv4, and with an IPv6 host using IPv6
  • This means it has to have an IPv4-compatible address
  • Either the host has to have an IPv4 and IPv6 address, thus allowing it to speak to an IPv4 host, OR it must rely on a translator, which knows how to take a v4-compatible IPv6 address and translate it to the IPv4 address.
  • It either has both or has an IPv4-compatible IPv6 address
60
Q

One way to ensure IPv4-compatibility of an IPv6 address

A

Embed the 32 bits of the IPv4 address in the 128 allocated for the IPv6 address

61
Q

Problem that dual stack deployment doesn’t solve

A

IPv6 deployments might exist as islands

62
Q

IPv6 islands

A
  • What if multiple independent portions of the internet might deploy IPv6, but the middle of the network only speaks and routes IPv4?
  • Solution: v6 to v4 tunneling
63
Q

v6 to v4 tunneling

A
  • v6 is encapsulated in a v4 packet
  • v4 packet is routed to a particular v4-v6 gateway corresponding to the v6 address that lies behind that gateway
  • at this point, outer layer can be stripped, and the v6 packet can be sent to its destination. Requires the gateways at the boundaries between v4 and v6 networks to perform encapsulation of the packet as it enters the v4-only part of the network, and decapsulation as the packet enters the v6 island where the destination host resides
64
Q

stride

A

how many bits you’re comparing at a time

65
Q

Which forwarding protocols implement exact match?

A

Ethernet-based, ATM, MPLS

66
Q

What are the techniques for exact match?

A

Direct lookup, associative lookup, binary tree, hashing

67
Q

What are the techniques for longest prefix match?

A

Radix, compressed trie, binary search on prefix intervals

68
Q

iBGP vs eBGP

A

We can think of iBGP as a means to disseminate information about external routes inside the AS.
eBGP is used to disseminate the routes among ASes.

69
Q

How to calculate degree of trie

A

w^k

70
Q

Stride

A

k

CS6250 - Networking (19 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions