diff options
author | Jack Sangdahl <[email protected]> | 2024-10-17 12:48:01 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-17 12:48:01 -0600 |
commit | be5c2aa696d3d3c499ab8817ee23bf5fe851363c (patch) | |
tree | b984317d54477276f6139ce2b7770357b511e684 | |
parent | bba288a79171b2f3cf7efb72e56c0c6fb5cf6116 (diff) | |
download | ecen5273-be5c2aa696d3d3c499ab8817ee23bf5fe851363c.tar.gz ecen5273-be5c2aa696d3d3c499ab8817ee23bf5fe851363c.zip |
Problem Set 2
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | problem_sets/ps2.pdf | bin | 0 -> 708252 bytes | |||
-rw-r--r-- | problem_sets/ps2.typ | 536 |
2 files changed, 536 insertions, 0 deletions
diff --git a/problem_sets/ps2.pdf b/problem_sets/ps2.pdf Binary files differnew file mode 100644 index 0000000..5ff8fbc --- /dev/null +++ b/problem_sets/ps2.pdf diff --git a/problem_sets/ps2.typ b/problem_sets/ps2.typ new file mode 100644 index 0000000..d0f2137 --- /dev/null +++ b/problem_sets/ps2.typ @@ -0,0 +1,536 @@ +#show link: underline +== Problem Set 2 #h(1fr) Jack Sangdahl + +=== Problem 1 ++ Is `10.72.0.255/255.255.254.0` a valid IP address for a host? + +No, this is not a valid host IP address for the following reasons. The subnet +mask `255.255.254.0` or `/23` specifies that the first 23 bits represent the +network portion. In a `/23` network, the last IP address (broadcast address) for +a network starting at `10.72.0.0` would be `10.72.1.255`. So, `10.72.0.255` is +within the range of assignable IPs, but is generally reserved as a broadcast +address for the `10.72.0.0/23` subnet. Hosts cannot be assigned the broadcast +address. + ++ Divide the `10.72.0.0/6` subnets into five large networks of 8192 IPs each, 8 + medium-sized networks of 2048 IPs each, and 10 small-sized networks of 128 IPs + each. + +Begin by breaking down the total address space for the given IP. A `/6` subnet +has a block size of $2^(32 - 6) = 2^26 = 67,108,864$ IP addresses. This range +goes from `10.0.0.0` to `10.63.255.255`. Now divide the subnets into specifed +ranges. + +*Five networks of 8192 IPs* + +$8192 = 2^13$, so we we need `/19` subnets. These five subnets can be allocated +starting from `/10.72.0.0`: +- `10.72.0.0/19` +- `10.72.32.0/19` +- `10.72.64.0/19` +- `10.72.128.0/19` + +*Eight networks of 2048 IPs* + +$2048 = 2^11$, so we need `/21` subnets. These eight subnets can be allocated +starting after above networks: +- `10.72.160.0/21` +- `10.72.168.0/21` +- `10.72.176.0/21` +- `10.72.184.0/21` +- `10.72.192.0/21` +- `10.72.200.0/21` +- `10.72.208.0/21` +- `10.72.216.0/21` + +*Ten networks of 128 IPs* + +$128 = 2^7$, so we need `/25` subnets. These ten subnets can be allocated +starting after the above networks: +- `10.72.224.0/25` +- `10.72.224.128/25` +- `10.72.225.0/25` +- `10.72.225.128/25` +- `10.72.226.0/25` +- `10.72.226.128/25` +- `10.72.227.0/25` +- `10.72.227.128/25` +- `10.72.228.0/25` +- `10.72.228.128/25` + ++ Is `151.101.2/23` and `151.101.3/23` representing the same subnet? Please + justify your answer. + +Yes, these IP addresses represent the same subnet. A `/23` subnet has a block +size of $2^(32 - 23) = 512$ addresses. In binary, the subnet `151.101.2.0/23` covers +the range from `151.101.2.0` to `151.101.3.255`. Since both `151.101.2` and `151.101.3` fall +within this range, they belong to the same subnet. Secondly, the `/23` notation +indicates that the first 23 bits of the address are the same, meaning the +network includes both of these addresses. + +=== Problem 2 +An organisation has been assigned the prefix `151.101.1.0/23` and wants to form +subnets for 4 departments which have the following hosts: +#align( + center, +)[ + #table( + columns: 2, table.header[*Department*][*Hosts*], [A], [130], [B], [120], [C], [60], [D], [31], + ) +] ++ Give a possible arrangement of subnet masks to make this possible. + +To arrange the subnets, Variable Length Subnet Masking should be used to +allocate different subnet sizes based on number of hosts needed. Begin by +calculating required subnet sizes. The number of usable IP address in a subnet +is given by $2^n - 2$, where $n$ is the number of host bits. The number of +required hosts should be rounded to the nearest power of 2. + +*Department A (130 hosts)* + +- Nearest power of 2: $2^8 = 256$ addresses #sym.arrow.r `/24` mask +- Subnet: `151.101.1.0/24` (covers `151.101.1.0` to `151.101.1.255`) + +*Department B (120 hosts)* + +- Nearest power of 2: $2^8 = 256$ addresses #sym.arrow.r `/24` mask +- Subnet: `151.101.2.0/24` (covers `151.101.2.0` to `151.101.2.255`) + +*Department C (60 hosts)* + +- Nearest power of 2: $2^7 = 128$ addresses #sym.arrow.r `/25` mask +- Subnet: `151.101.1.128/25` (covers `151.101.128` to `151.101.1.255`) + +*Department D (31 hosts)* + +- Nearest power of 2: $2^6 = 64$ addresses #sym.arrow.r `/26` mask +- Subnet: `151.101.1.64/26` (covers `151.101.1.64` to `151.101.1.127`) + ++ Suggest what the organisation might do if department C grows to 65 hosts. + +As calculated above, Department C would be assigned a `/25` subnet which +provides 128 IP addresses, meaning it is suitable for up to 126 hosts. So if +Department C grows to 65 hosts, no changes are necessary. + +=== Problem 3 +For the network given below in Figure 3, give global distance-vector tables for +each node when: +#align(center)[ + #image("fig3.png", width: 70%) +] ++ Each node knows only the distance of its immediate neighbours. + +At this point, each node only has information about its directly connected +neighbours and the cost to reach them. The distance to itself is 0 and it can be +assumed the distance to nodes that are not directly connected is +unknown/infinity. + +*Node A* +- To A: 0 (self) +- To B: 5 +- To C: 2 +- To D, E, & F: #sym.infinity + +*Node B* +- To A: 5 +- To B: 0 (self) +- To D: 2 +- To C, E, & F: #sym.infinity + +*Node C* +- To A: 2 +- To C: 0 (self) +- To D: 8 +- To E: 2 +- To B & F: #sym.infinity + +*Node D* +- To B: 2 +- To C: 8 +- To D: 0 (self) +- To F: 4 +- To A & E: #sym.infinity + +*Node E* +- To C: 2 +- To E: 0 (self) +- To F: 4 +- To A, B, & D: #sym.infinity + +*Node F* +- To D: 4 +- To E: 4 +- To F: 0 (self) +- To A, B, & C: #sym.infinity + ++ Each node has reported the information it had in the first step (a) to its + immediate neighbours. + +Now, each node shares its known distances with its immediate neighbours. This +means the neighbours can update their tables if they find a shorter path to a +certain node. + +*Node A* +- To A: 0 +- To B: 5 +- To C: 2 +- To D: $min(5 + 2, infinity) = 7$ (through B) +- To E: $min(2 + 2, infinity) = 4$ (through C) +- To F: $min(7 + 4, 4 + 4, infinity) = 8$ (through E) + +*Node B* +- To A: 5 +- To B: 0 +- To C: $min(5 + 2, infinity) = 7$ (through A) +- To D: 2 +- To E: $min(7 + 2, infinity) = 9$ (through C) +- To F: $min(2 + 4, 9 + 4, infinity) = 6$ (through D) + +*Node C* +- To A: 2 +- To B: $min(2 + 5, infinity) = 7$ (through A) +- To C: 0 +- To D: 8 +- To E: 2 +- To F: $min(2 + 4, infinity) = 6$ (through E) + +*Node D* +- To A: $min(2 + 5, infinity) = 7$ (through B) +- To B: 2 +- To C: $min(2 + 8, 8) = 8$ +- To D: 0 +- To E: $min(8 + 2, infinity) = 10$ (through C) +- To F: 4 + +*Node E* +- To A: $min(2 + 2, infinity) = 4$ (through C) +- To B: $min(2 + 7, infinity) = 9$ (through C) +- To C: 2 +- To D: $min(4 + 4, infinity) = 8$ (through F) +- To E: 0 +- To F: 4 + +*Node F* +- To A: $min(4 + 4, infinity) = 8$ (through E) +- To B: $min(4 + 6, infinity) = 10$ (through D) +- To C: $min(4 + 2, infinity) = 6$ (through E) +- To D: 4 +- To E: 4 +- To F: 0 + ++ Repeat step (b) one more time. + +Once again, the nodes share their updated distances with neighbours. It's +unlikely that many shorter paths have been found, thus the values reported in +this step will be the smallest found. + +*Node A* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [0], [5], [2], [7], [4], [8], +) + +*Node B* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [5], [0], [7], [2], [9], [6], +) + +*Node C* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [2], [7], [0], [8], [2], [6], +) + +*Node D* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [7], [2], [8], [0], [8], [4], +) + +*Node E* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [4], [9], [2], [8], [0], [4], +) + +*Node F* +#table( + columns: 7, table.header[To][A][B][C][D][E][F], [Cost], [8], [10], [6], [4], [4], [0], +) + +=== Problem 4 +Again for the network graph in Figure 3, show how the link-state algorithm +builds the routing table for node D. ++ Show the detailed steps with the link-state algorithm. + +Begin by marking Node D as the starting point, and create an initial distance +table: +- To D: 0 (self) +- To B: 2 +- To C: 8 +- To F: 4 +- To A & E: #sym.infinity + +We can use a set `s` to keep track of the shortest paths. `s` initially contains +only D, since it is zero: `s = {D}`. Next from D, the smallest tentative +distance is to B (2): `s = {D, B}`. Now see if there is a shorter path to other +nodes from B: +- To *A* through *B*: Distance to B + distance from B to A is $2 + 5 = 7$. +- To *C* through *B*: Distance to B + distance from B to C is $2 + infinity = infinity$. +- To *F* through *B*: Distance to B + distance from B to F is $2 + infinity = infinity$. + +Updated distances from D: +- To D: 0 +- To B: 2 +- To C: 8 +- To F: 4 +- To A: 7 (updated value) +- To E: #sym.infinity + +The next node with the smallest tentative distance not in `s` is F: `s = {D, B, F}`. +Repeat above step to check if there is a shorter path to other nodes through F: +- To *A* through *F*: Distance to F + distance from F to A is $4 + infinity = infinity$. +- To *C* through *F*: Distance to F + distance from F to C is $4 + 4 = 8$. +- To *E* through *F*: Distance to F + distance from F to E is $4 + 4 = 8$. + +Updated distances from D: +- To D: 0 +- To B: 2 +- To C: 8 +- To F: 4 +- To A: 7 +- To E: 8 (updated value) + +The next node with the smallest tentative distance not in `s` is A: `s = {D, B, F, A}`. +Repeat above step: +- To *C* through *A*: Distance to A + distance from A to C is $7 + 2 = 9$. +- To *E* through *A*: Distance to A + distance from A to E is $7 + infinity = infinity$. + +No shorter values were found, so the table remains the same. + +The next node with the smallest tentative distance not in `s` is C: `s = {D, B, F, A, C}`. +Repeat above step: +- To *E* through *C*: Distance to C + distance to C from E is $8 + 2 = 10$. + +No shorter values were found, so the table remains the same. + +The next node with the smallest tentative distance not in `s` is E: `s = {D, B, F, A, C, E}`. +At this point, the shortest paths to all nodes from D are known. + ++ Show the final routing table of node D. + +#table( + columns: 3, table.header[Destination][Cost][Next Hop], [D], [0], [N/A], [B], [2], [B], [C], [8], [C], [F], [4], [F], [A], [7], [B], [E], [8], [F], +) + +=== Problem 5 +The network graph is shown in figure 4. +#align(center)[ + #image("fig5.png", width: 70%) +] ++ Host H1 sends a packet to the destination `128.96.34.126`. Explain how this + packet traverses in the network described below. You need to describe who + received the packet and what are their reactions. + +Here, the destination IP and subnet are the same, meaning host H1 will use ARP +to transfer the packet. During ARP transmission, the packet will be sent to +destination MAC address. If the MAC address is unknown, the packet will be +broadcasted to all hosts, but only the destination host will respond with an +ACK. In the scope of this scenario, the host IP does not belong to the +networking, meaning we will not receive any response during the ARP process. + ++ Host H3 sends a packet to the destination `128.96.34.250`. Explain how this + packet traverses in the network. + +The address `128.96.34.250` belongs to network H2. Host H3 will initiate packet +transfer via router R2 and broadcast an ARP request to the destination IP +through the default gateway (R2). From R2, the packet will be forwarded to a +port in red circled region of the figure. If successful, the packet's source +host and router R2 will exchange MAC addresses and the packet will be forwarded +to reach the destination in subnet within the red circled area. + ++ The subnet of H1 has now two different teams and would like to split it into two + subnets. Please add one more subnet and add R3 and change the network + configurations as you need. Note that you are allowed to modify the network as + least disruptive as possible. + +The subnet of H1 will change to `128.93.34.0/255.255.255.192`. An additional +router R3 will connect IPs `128.93.34.0` with `128.93.34.64` via Ethernet. On +the left side of R3, `128.93.34.65` will be connected with `128.93.34.128`, and +with subnet `128.93.34.64/255.255.255.192`. +#align(center)[ + #image("5c.png", width: 70%) +] + +=== Problem 6 +#align(center)[ + #image("fig6.png", width: 70%) +] +Above in Figure 5 is the network graph with 4 routers (R1, R2, R3, R4) and 4 +hosts (A, B, C, D). Each router interfaces and hosts are labeled with both IP +and MAC address, Routing is enabled so that any two hosts can communicate with +each other and the default gateway of each host is set to its gateway router. ++ Suppose that B sends an IP packet to C through R3, R2, R4. Write down the IP + packet's content (`src MAC`, `dst MAC`, `src IP`, `dst IP`) along the path in + the table +#align( + center, +)[ +#table( + columns: 5, table.header[][`src MAC`][`dst MAC`][`src IP`][`dst IP`], [B #sym.arrow.r R3], [`0D:23:42:AC:EE:FC`], [`AF:0C:EF:11:22:11`], [`22.1.23.45`], [`33.2.2.18`], [R3 #sym.arrow.r R2], [`AA:BB:CC:AF:2F:11`], [`AF:CC:1F:11:EE:10`], [`22.1.23.45`], [`33.2.2.18`], [R2 #sym.arrow.r R4], [`0C:32:56:90:09:EF`], [`89:98:AF:FF:FF:0C`], [`22.1.23.45`], [`33.2.2.18`], [R4 #sym.arrow.r C], [`00:1C:AA:FE:F1:1A`], [`00:0C:EA:17:98:32`], [`22.1.23.45`], [`33.2.2.18`], +) +] ++ When A sends out an ARP query for its default gateway, what is the reply to that + query? + +The reply to A's ARP query is a MAC address: +- Source IP: `123.123.123.1` +- Source MAC: `0C:AF:10:00:1E:1C` +- Destination IP: `123.123.123.111` +- Destination MAC: `79:AA:EF:AC:11:21` + ++ Suppose the routers use link-state routing protocol, what will be R3's routing + table entries? + +#table( + columns: 3, table.header[Route][Direction][Destination Subnet], [R3 #sym.arrow.r B], [Towards B], [`22.1.0.0/16`], [R3 #sym.arrow.r R2], [Towards A], [`123.123.123.0/24`], [R3 #sym.arrow.r R2], [Towards C & D], [`33.2.-.2/24`], +) + +=== Problem 7 +Suppose a computer just boot up, connected to wireless network, and successfully +obtained IP, gateway, and DNS address. Now it wants to access #link("www.yahoo.com") from +its browser. Describe the sequence of packets exchanged to and from this +computer until the webpage starts to load. (Include what kind of protocol and +what is the content of the packets). + ++ ARP #sym.dash.em Local Gateway Discovery +The computer knows the IP address of the default gateway (typically provided by +DHCP), but does not yet know its MAC address. To obtain this, it sends an ARP +request to the network. An ARP request packet consists of the computer querying +the gateway IP address and requesting a response. In this response (the ARP +reply packet), the router responds with its IP and MAC address. + ++ DNS Request +The domain name #link("www.yahoo.com") makes sense to us, but the computer does +not understand. The next step is to resolve this domain name into an IP address +so the computer can send HTTP requests. To achieve this, a DNS query is sent to +the DNS server (also typically provided by DHCP) using UDP port 53. The query +packet consists of requesting what the IP address of the requested domain name +is. In the response, the corresponding IP address is sent to the computer. + ++ TCP Connection Setup +This step establishes a reliable connection between the computer and Yahoo's web +server(s). To initiate a TCP connection (port 80 (HTTP) or port 443 (HTTPS)), +the computer first sends a SYN packet to Yahoo's server. If/When the SYN packet +is received by Yahoo's server, it responds with a SYN-ACK packet acknowledging +the computer's request. To finalise the connection, the computer responds with +an ACK packet to the server. + ++ HTTP(S) Request +This step requests the webpage served by #link("www.yahoo.com"). If the +connection is using HTTPS, an additional step involving a TLS handshake occurs +to secure the connection. After this, the computer sends an HTTP request to the +server. This request looks something like: +```http +GET / HTTP/1.1 +Host: www.yahoo.com +``` + ++ HTTP(S) Response +Upon receiving the `GET` request, the server processes this and sends back an +HTTP response containing the webpage data: +```http +HTTP/1.1 200 OK +Content-Type: text/html +Content-Length: <size> +<HTML content...> +``` + ++ TCP Connection Termination +Once the webpage has been received, the TCP connection between the computer and +server can be closed. To begin, the computer sends a FIN packet to the server, +the server responds with an ACK packet as well as a FIN packet, and finally the +computer responds with an ACK packet to terminate the connection. + +Note, if the webpage depends on additional content (HTML, CSS, JavaScript, etc.) +not included in the HTML content sent in the above steps, the same process is +repeated. + +=== Problem 8 +Consider the simple network in Figure 5 below. X, Y, and Z are routers and their +link costs are specified. Assume the network uses a Distance Vector algorithm. Y +and Z's routing tables look like Table 2. +#align(center)[ + #image("fig8.png", width: 70%) +] ++ Now lets assume the cost of link X-Y suddenly changed to 100. Write down Y and + Z's routing table regarding distance to X, after Y updates this information to Z + and then Z updates its information back. + +*Y Routing Table* +#table( + columns: 3, table.header[Node Y/Distance][Via X][Via Z], [X], [100], [6], +) + +*Z Routing Table* +#table( + columns: 3, table.header[Node Z/Distance][Via X][Via Y], [X], [50], [7], +) + +#align(center)[ + #image("6a.png", width: 70%) +] + ++ Write down Y and Z's routing table regarding X after Y updates this information + to Z again and then Z updates back again. + +*Y Routing Table* +#table( + columns: 3, table.header[Node Y/Distance][Via X][Via Z], [X], [100], [8], +) + +*Z Routing Table* +#table( + columns: 3, table.header[Node Z/Distance][Via X][Via Y], [X], [50], [9], +) + +#align(center)[ + #image("6b.png", width: 70%) +] + ++ How many updates did Y get until its distance to X have converged with Distance + Vector algorithm? + +In total, Y's distance will update 23 times until its distance to X has +converged with the Distance Vector algorithm. + +=== Problem 9 +Consider a network with MPLS enabled routers as show in Figure 1 below. We would +like to perform traffic engineering using MPLS so that traffic from R1 to R6 +will be routed as R1 #sym.arrow.r R3 #sym.arrow.r R5 #sym.arrow.r R6 #sym.arrow.r A +and traffic from R2 to R6 will be routed as R2 #sym.arrow.r R3 #sym.arrow.r R4 #sym.arrow.r C. +#align(center)[ + #image("fig9.png", width: 70%) +] +Fill in the followingtables of MPLS entries for each router. + +*R1*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [-], [1], [A], [0], +) +*R2*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [-], [2], [C], [0], +) +*R3*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [1], [4], [A], [1], [2], [2], [C], [0], +) +*R4*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [3], [-], [C], [0], [3], [6], [A], [1], +) +*R5*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [4], [5], [A], [0], +) +*R6*: +#table( + columns: 4, [In Label], [Out Label], [Destination], [Out Interface], [5], [-], [A], [0], +) |