diff options
author | Jack Sangdahl <[email protected]> | 2024-12-11 11:26:30 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-11 11:26:30 -0700 |
commit | 24f111e3dff96dfafcef6676b9c21ef4d257b53e (patch) | |
tree | a14c41a087a3e6f2973f3fbcfe32b303d978bbb6 /problem_sets | |
parent | 7d3c6e7fbd03645c90613f0140b6597c6dcc2e43 (diff) | |
download | ecen5273-24f111e3dff96dfafcef6676b9c21ef4d257b53e.tar.gz ecen5273-24f111e3dff96dfafcef6676b9c21ef4d257b53e.zip |
Problem Set 4
Signed-off-by: Jack Sangdahl <[email protected]>
Diffstat (limited to 'problem_sets')
-rw-r--r-- | problem_sets/.gitignore | 1 | ||||
-rw-r--r-- | problem_sets/ps4.pdf | bin | 0 -> 208426 bytes | |||
-rw-r--r-- | problem_sets/ps4.typ | 317 |
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 Binary files differnew file mode 100644 index 0000000..d18348c --- /dev/null +++ b/problem_sets/ps4.pdf 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. |