aboutsummaryrefslogtreecommitdiff
path: root/problem_sets
diff options
context:
space:
mode:
Diffstat (limited to 'problem_sets')
-rw-r--r--problem_sets/.gitignore1
-rw-r--r--problem_sets/ps4.pdfbin0 -> 208426 bytes
-rw-r--r--problem_sets/ps4.typ317
3 files changed, 318 insertions, 0 deletions
diff --git a/problem_sets/.gitignore b/problem_sets/.gitignore
index 363661a..bf7e12b 100644
--- a/problem_sets/.gitignore
+++ b/problem_sets/.gitignore
@@ -4,3 +4,4 @@
*.fls
*.synctex.gz
*_questions.pdf
+img
diff --git a/problem_sets/ps4.pdf b/problem_sets/ps4.pdf
new file mode 100644
index 0000000..d18348c
--- /dev/null
+++ b/problem_sets/ps4.pdf
Binary files differ
diff --git a/problem_sets/ps4.typ b/problem_sets/ps4.typ
new file mode 100644
index 0000000..5f1971b
--- /dev/null
+++ b/problem_sets/ps4.typ
@@ -0,0 +1,317 @@
+#show link: underline
+== Problem Set 4 #h(1fr) Jack Sangdahl
+
+=== Problem 1 Hashing
+The hash table has 13 slots, and integer keys are hashed into the table with the
+following hash function H:
+```c
+int H(int key) {
+ int x = (key + 5) * (key - 3);
+ x = (int)(x / 7) + key;
+ x %= 13;
+ return x;
+}
+```
++ Fill in the final hash table with the following keys: 17, 22, 73, 56,
+310, 100, 230, 12, 42, 18, 19, 24, 49.
+
+#table(
+ columns: 14, table.header[*Slot*][*0*][*1*][*2*][*3*][*4*][*5*][*6*][*7*][*8*][*9*][*10*][*11*][*12*], [*Contents*], [310, 49], [], [18], [], [22, 230, 42], [], [], [100, 12, 24], [73, 19], [17], [56], [], [],
+)
+
++ List one or two methods that can handle collision hashing.
+
+- *Separate chaining*: Each slot in the hash table points to a linked
+list (or similar data structure). All keys that hash to the same slot are stored
+in the list, so collisions are handled by adding the new key to the list.
+
+- *Open addressing*: Resolves collisions by finding another open slot
+in the table using strategies like simply linearly searching for an open slot,
+quadratic probing, or double hashing to calculate the step size for probing when
+a collision occurs.
+
+=== Problem 2 (Distributed Hash Tables)
+There is a chord DHT in Figure 1 with 5 nodes. The finger tables are listed
+beside the nodes. Each node may be storing some items according to the Chord
+rules (Chord assigns keys to nodes in the same way as consistent hashing).
+
+#align(center)[
+ #image("img/fig1.png", width: 70%)
+ Figure 1
+]
+
++ Fill in the table for node ID's 1 and 7.
+
+#align(
+ center,
+)[
+ #table(
+ columns: 3, table.header[*ID 1*][*$"ID" + 2'$*][*Successor*], [0], [2], [2], [1], [3], [3], [2], [5], [5],
+ )
+
+ #table(
+ columns: 3, table.header[*ID 2*][*$"ID" + 2'$*][*Successor*], [0], [0], [0], [1], [1], [1], [2], [3], [3],
+ )
+]
+
++ List the node(s) that will receive a query from node 1 for item 5
+(item named by key 5).
+
+If node ID 1 is querying for item 5, Node 1 will check its finger table and find
+the closest entry that does not exceed 5. This entry is 5, meaning the success
+of 5 is Node 5 itself. Therefore, Node 1 will directly query Node 5 for item 5.
+
+=== Problem 3 Bloom Filters
+Derive the probability of false positive rate after 10 keys (or elements) are
+inserted into a table of size 100. Assume that 5 hash functions are used to
+setup bit positions in the table for the keys. 5 hashing functions mean for each
+key there will be 5 bits to set to 1 in the table (it can also be less than 5 if
+the hash functions generate the same output).
+
+Assume $m$ is the number of bits, $n$ is the number of elements, and
+$k$ is the number of hash functions used. After inserting one key, the
+probability of a particular bit being 0 is $(1 - 1/m)^k$. This is because $k$ hash
+functions are independent, and each hash function will have $(1 - 1/m)$ probability
+for a particular bit remaining 0. Then after inserting $n$ keys, the probability
+for a particular bit remaining 0 is $(1 - 1/m)^(k n)$. Now apply this this to
+case of false positive.
+
+Given the following:
+- $m = 100$: number of bits in the table
+- $n = 10$: number of keys/elements inserted
+- $k = 5$: number of hash functions
+
+Probability of bit being after inserting 1 key:
+$ P(x) = (1 - 1/m)^k $
+
+Probability of bit being 0 after inserting $n$ keys:
+$ P(x) = (1 - 1/m)^(k n) $
+
+Probability of a false positive:
+$ P(x) = (1 - (1 - 1/m)^(k n))^k $
+
+Substitute values:
+$ P(x) = (1 - 1/100)^(5 times 10) = (99/100)^50 $
+$ P(x) = (1 - (99/100)^50)^5 $
+$ (99/100)^50 approx 0.605 $
+$ P(x) = 1 - 0.605 = 0.395 $
+$ P(x) = 0.395^5 approx 0.0096 $
+
+The probability of a false positive after inserting 10 keys into a table of size
+100 with 5 hash functions is approximately *0.96%*.
+
+=== Problem 4 P2P System
+Three nodes A, B, and C are connected with each other via 5 MBps duplex link as
+shown in Figure 2. Node A wants to share a 2500 MB file to Node B and C. During
+the actual transmission, a 2.5 MB chunk of the file can be sent on the links
+each time. Ignore RTT in this problem.
+
+#align(center)[
+ #image("img/fig2.png", width: 70%)
+ Figure 2
+]
+
++ What is the time of the sharing process using a centralised approach?
+(The process ends when B and C all received the file, and the centralised
+approach means B and C are communicating with A independently and there is no
+communication between B and C.)
+
+Given the following:
+- File size: 2500 MB
+- Chunk size: 2.5 MB per transmission
+- Link capacity: 5 MBps between each pair of nodes
+- Ignoring RTT
+
+With a duplex link, Node A can send data simultaneously to Node B and Node C.
+The time to transfer one chunk of 2.5 MB over a 5 MBps link is given by:
+
+$ T_"chunk" = 2.5/5 = 0.5 "seconds" $
+
+However, Node A can send a chunk to both B and C at the same time because the
+links are independent. So the time to send the entire 2500 MB file, split into
+2.5 MB chunks is:
+
+$ T_"cent" = 2500/5 = 500 "seconds" $
+
+This lengthy time is because Node A can transmit to both nodes at the same time,
+and the bottleneck is the time required to send the full file to one node.
+
++ What is the ideal minimum time of sharing process P2P approach?
+(P2P approach means after B and C received a chunk from A, they immediately
+share their piece to the other node.)
+
+In the ideal P2P case, Node B and C work together perfectly to distribute the
+file. After the first chunk is transmitted, the additional upload bandwidth
+between Node B and C effectively halves the remaining time to distribute the
+remaining chunks. Meaning the minimum time for the P2P approach will be roughly
+half the centralised time because B and C are working together after
+transmitting the first chunk:
+
+$ T_"P2P" = T_"cent"/2 = 500/2 = 250 "seconds" $
+
+=== Problem 5 File Distribution
+Considering distributing a file of $F = 20$ gigabits to $N$ peers. The server
+has an upload rate of $u_s = 30$ Mbps, and each peer has a download rate of $d_i = 2$ Mbps
+and an upload rate of $u$. For
+$N = 10, 100$ and $u = 300$ and $u = 2$ Mbps, prepare a chart giving the minimum
+distribution time for each of the combination of $N$ and
+$u$ for both client-server distribution and P2P distribution.
+
+==== Client-Server
+In this distribution, the server must upload the entire file to each peer. The
+time to distribute depends solely on the server's upload rate and the number of
+peers $N$. The distribution time for client-server is given by:
+
+$ T_("cs") = F/u_s$, where $F = 20 $
+
+Given the following:
+- $F = 20$: the file size in gigabits
+- $u_s = 30$: the server's upload rate in Mbps
+
+This time is the same for any number of peers because the server needs to upload
+the entire file, regardless of how many peers download it.
+
+$ T_("cs") = 20/30 = (20 times 10^3)/30 = 666.67 "seconds" $
+
+#align(
+ center,
+)[
+ #table(
+ columns: 3, table.header[*U*][*$N = 10$*][*$N = 100$*], [*300 Kbps*], [666.67 sec], [666.67 sec], [*2 Mbps*], [666.67 sec], [666.67 sec],
+ )
+]
+
+==== Peer to Peer
+In this distribution, peers both download and upload parts of the file. The time
+to distribute depends on both the server and peers' rates. The minimum
+distribution time in a P2P network is determined by two factors:
+
++ The server constraint, meaning the server must upload one copy of
+the file, which we know from the above work is 666.67 seconds.
+
++ The peer constraint, meaning all peers must download the file, and
+some must upload parts of it. This depends on the peer upload rate
+$u$, the peer download rate $d_i$, and the total number of peers $N$. For a P2P
+network, the total amount of data that needs to be transferred is $F times N$.
+The total capacity in the network is the sum of the upload rates of the server
+and the peers. Therefore, the distribution is given by:
+
+$ T_"P2P" = max(F/u_s, F/(u_s + sum_(i = 1)^N u_i)) $
+
+Given the following:
+- $u_i$ is the upload rate of each peer
+- $u_s$ is the server's upload rate
+
+For $u = 300$ Kbps:
+- Each peer uploads at 0.3 Mbps
+- For $N = 10$, the total upload rate is $0.3 times 10 + 30 = 33$ Mbps
+- For $N = 100$, the total upload rate is $0.3 times 100 + 30 = 60$
+Mbps
+
+For $u = 2$ Mbps:
+- Each peer uploads at 2 Mbps
+- For $N = 10$, the total upload rate is $2 times 10 + 30 = 50$ Mbps
+- For $N = 100$, the total upload rate is $2 times 100 + 30 = 230$
+Mbps
+
+Calculate the distribution times for each combination:
+
+For $u = 300$ Kbps:
+- $N = 10$:
+$ T_"P2P" = max(666.67, (20 times 10^3)/33) = 666.67 $
+- $N = 100$:
+$ T_"P2P" = max(666.67, (20 times 10^3)/60) = 666.67 $
+
+For $u = 2$ Mbps:
+- $N = 10$:
+$ T_"P2P" = max(666.67, (20 times 10^3)/50) = 666.67 $
+- $N = 100$:
+$ T_"P2P" = max(666.67, (20 times 10^3)/230) = 666.67 $
+
+#align(
+ center,
+)[
+ #table(
+ columns: 3, table.header[*U*][*$N = 10$*][*$N = 100$*], [*300 Kbps*], [666.67 sec], [666.67 sec], [*2 Mbps*], [666.67 sec], [666.67 sec],
+ )
+]
+
+=== Problem 6 BGP
++ Give the types of business relationships in BGP peering and mention
+who pays whom. What conditions make the internet stable?
+
+- *Customer-provider*: where a customer pays a provider for transit
+services to reach the rest of the internet. For example, in Figure 3, Node 1 is
+a customer of Node 3.
+
+- *P2P*: where two networks of roughly equal size exchange traffic
+with each other without any payment. Peers do not provide full transit to each
+other; they exchange traffic only for their customers. For example, in Figure 3,
+Node 4 and Node D are peers.
+
+Conditions for internet stability:
+- *Route leak avoidance*: Peers should not send traffic that violates
+the business relationship (eg. a customer announcing a provider's route to
+another provider).
+
+- *Routing policies*: Relationships should enforce policies where
+providers can announce all destinations known to them, and peers should only
+announce customer routes to other peers
+
+- *Global reachability*: Providers should provide access to all
+reachable destinations on the internet, while peers should limit route
+announcements.
+
++ Identify which of the following paths are valid and which of them
+are invalid based on the network topology of Figure 3.
+
+Paths are valid or invalid based on the business relationships (customer to
+provider and peer to peer) and the typical routing behaviour where customers can
+send traffic to providers, providers cannot use customer links to transit to
+other providers, and P2P paths only allow traffic between their customers.
+
+#align(
+ center,
+)[
+ #table(
+ columns: 2, table.header[*Path*][*Validity*], [1 3 d], [Valid], [1 4 d], [Valid], [8 d], [Invalid], [6 d], [Invalid], [4 d], [Valid], [7 5 d], [Valid], [7 5 3 d], [Valid], [2 1 3 d], [Valid], [1 4 6], [Invalid],
+ )
+
+ #image("img/fig3.png", width: 70%)
+ Figure 3
+]
+
+=== Problem 7 Security
+Diffie-Hellman Symmetric key exchange solves the distribution issue of symmetric
+keys. Assume that Alice and Bob know p-ordered group $G$ and a generator $g$,
+and Alice's and Bob's random seeds are $a$ and $b$
+and their public keys are $A$ and $B$ respectively, and computes a shared key $s$.
+Use $p = 23$, $g = 11$, $a = 13$, and $b = 8$. Note that Eve is an eavesdropper
+and can see any communication between Alice and Bob.
+
+Given the following:
+- $p = 23$: the group order's prime number (modulo 23)
+- $g = 11$: the value that generates the group
+- $a = 13$: Alice's private key
+- $b = 8$: Bob's private key
+
+Begin by calculating public keys for Alice and Bob, respectively.
+$ A = g^a mod p = 11^13 mod 23 $
+$ 11^13 mod 23 = 17 $
+$ B = g^b mod p = 11^8 mod 23 $
+$ 11^8 mod 23 = 8 $
+So Alice's public key is $A = 17$, and Bob's public key is $B = 8$.
+
+Next calculate the shared key $s$ for Alice and Bob, respectively.
+$ s = B^a mod p = 3^13 mod 23 $
+$ 3^13 mod 23 = 9 $
+$ s = A^b mod p = 15^8 mod 23 $
+$ 15^8 mod 23 = 4 $
+So Alice's shared key is $s = 9$, and Bob's shared key is $s = 4$.
+
+Eve can see their public key values $A = 17$ and $B = 8$, the generator value $g = 11$,
+and the prime number $p = 23$. However, without knowing the private values $a$ and $b$,
+she cannot compute the shared key $s$ without brute-forcing it (discrete
+logarithm problem, which is computationally infeasible for large enough
+numbers). Thus, Alice and Bob securely share the key $s = 21$, even though Eve
+can observe the public communication.