ADVANCED COMPUTER NETWORKS
EXAM QUESTIONS WITH CORRECT
ANSWERS
Explain the bloom filter: - Answer-We maintain M bit cells. Then we apply a hash
function on incoming data and set the corresponding value to 1.
Only supports "Insert" and "Check".
Often multiple hash functions. Elements is then only considered if ALL the hash values
map to 1.
What are the probabilities in bloom filters?
M = Cells
N = Elements
1. Element to be mapped to cell
2. Element not mapped to a cell
3. Probability of a cell being 0
4. False positive rate - Answer-1. Element to be mapped to cell = 1/M
2. Element not mapped to a cell = 1 - (1/M)
3. Probability of a cell being 0 = (1 - (1/M)) ^ N
4. False positive rate = 1 - ((1 - (1/M)) ^ N)
What are the probabilities in bloom filters with multiple hash functions (K)?
M = Cells
N = Elements
1. Element to be mapped to cell
2. Element not mapped to a cell
3. Probability of a cell being 0
4. False positive rate - Answer-1. Element to be mapped to cell = 1/M
2. Element not mapped to a cell = 1 - (1/M)
3. Probability of a cell being 0 = (1 - (1/M)) ^ NK
4. False positive rate = 1 - ((1 - (1/M)) ^ KN) ^ K
What is the tradeoff space for bloom filters? - Answer-Memory
Number of Operations
False Positive Rate
Name two bloom filter extensions - Answer-1. Counting Bloom Filters
2. Invertible Bloom lookup tables
What is Count Min? - Answer-Multiple Bloom filters.
Value + 1 on hit.
, When requesting count, we get all and take the min (most probable true value)
What is DNS? - Answer-The Domain Name System (DNS) converts domain names or
host names into IP addresses.
What is the RNS? - Answer-Root Name Server
Lists the top-level domains and who controls them
What is the flow of recursive DNS? - Answer-1. Query the local DNS server
2. On no entry found go to root
3. Reply: Please contact "com"
4. Query for "www.google.com"
5. Reply: Please contact "ns1.google.com"
6. Query for "www.google.com"
7. Reply "www.google.com" = "172.217.20.110"
8. Local DNS replies with IP
Name the four DNS types: - Answer-1. DNS resolution (Type A or AAAA)
2. Alias (CNAME)
3. Query DNS server (NS)
4. Look for the mail server (MX)
What are sockets? - Answer-Sockets represents the communication endpoints. It's an
abstraction for user applications to access network functionalities.
name three ways of detecting errors in Packets - Answer-1. Parity Checks (1D and 2D)
2. Checksumming (add and take opposite)
3. Cyclic Redundancy Check (CRC)
How could colliding signals be corrected? - Answer-e.g.
Forward Error Correction (ECC)
Retransmission
What are important principles to follow in Multiple Access Protocol (4)? - Answer-Work-
conserving: Maximum Utilization
Fairness
Decentralized
Simple
Why don't switches have Ethernet Addresses? - Answer-Switches are unknown to end
host (they are invisible helpers)
What are the pros/cons of "Store and Forward" routers and "Cut-through" routers? -
Answer-"Store and Forward"
Pro: Error Checks
Con: Time to buffer
EXAM QUESTIONS WITH CORRECT
ANSWERS
Explain the bloom filter: - Answer-We maintain M bit cells. Then we apply a hash
function on incoming data and set the corresponding value to 1.
Only supports "Insert" and "Check".
Often multiple hash functions. Elements is then only considered if ALL the hash values
map to 1.
What are the probabilities in bloom filters?
M = Cells
N = Elements
1. Element to be mapped to cell
2. Element not mapped to a cell
3. Probability of a cell being 0
4. False positive rate - Answer-1. Element to be mapped to cell = 1/M
2. Element not mapped to a cell = 1 - (1/M)
3. Probability of a cell being 0 = (1 - (1/M)) ^ N
4. False positive rate = 1 - ((1 - (1/M)) ^ N)
What are the probabilities in bloom filters with multiple hash functions (K)?
M = Cells
N = Elements
1. Element to be mapped to cell
2. Element not mapped to a cell
3. Probability of a cell being 0
4. False positive rate - Answer-1. Element to be mapped to cell = 1/M
2. Element not mapped to a cell = 1 - (1/M)
3. Probability of a cell being 0 = (1 - (1/M)) ^ NK
4. False positive rate = 1 - ((1 - (1/M)) ^ KN) ^ K
What is the tradeoff space for bloom filters? - Answer-Memory
Number of Operations
False Positive Rate
Name two bloom filter extensions - Answer-1. Counting Bloom Filters
2. Invertible Bloom lookup tables
What is Count Min? - Answer-Multiple Bloom filters.
Value + 1 on hit.
, When requesting count, we get all and take the min (most probable true value)
What is DNS? - Answer-The Domain Name System (DNS) converts domain names or
host names into IP addresses.
What is the RNS? - Answer-Root Name Server
Lists the top-level domains and who controls them
What is the flow of recursive DNS? - Answer-1. Query the local DNS server
2. On no entry found go to root
3. Reply: Please contact "com"
4. Query for "www.google.com"
5. Reply: Please contact "ns1.google.com"
6. Query for "www.google.com"
7. Reply "www.google.com" = "172.217.20.110"
8. Local DNS replies with IP
Name the four DNS types: - Answer-1. DNS resolution (Type A or AAAA)
2. Alias (CNAME)
3. Query DNS server (NS)
4. Look for the mail server (MX)
What are sockets? - Answer-Sockets represents the communication endpoints. It's an
abstraction for user applications to access network functionalities.
name three ways of detecting errors in Packets - Answer-1. Parity Checks (1D and 2D)
2. Checksumming (add and take opposite)
3. Cyclic Redundancy Check (CRC)
How could colliding signals be corrected? - Answer-e.g.
Forward Error Correction (ECC)
Retransmission
What are important principles to follow in Multiple Access Protocol (4)? - Answer-Work-
conserving: Maximum Utilization
Fairness
Decentralized
Simple
Why don't switches have Ethernet Addresses? - Answer-Switches are unknown to end
host (they are invisible helpers)
What are the pros/cons of "Store and Forward" routers and "Cut-through" routers? -
Answer-"Store and Forward"
Pro: Error Checks
Con: Time to buffer
