aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-17 12:48:01 -0600
committerJack Sangdahl <[email protected]>2024-10-17 12:48:01 -0600
commitbe5c2aa696d3d3c499ab8817ee23bf5fe851363c (patch)
treeb984317d54477276f6139ce2b7770357b511e684
parentbba288a79171b2f3cf7efb72e56c0c6fb5cf6116 (diff)
downloadecen5273-be5c2aa696d3d3c499ab8817ee23bf5fe851363c.tar.gz
ecen5273-be5c2aa696d3d3c499ab8817ee23bf5fe851363c.zip
Problem Set 2
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--problem_sets/ps2.pdfbin0 -> 708252 bytes
-rw-r--r--problem_sets/ps2.typ536
2 files changed, 536 insertions, 0 deletions
diff --git a/problem_sets/ps2.pdf b/problem_sets/ps2.pdf
new file mode 100644
index 0000000..5ff8fbc
--- /dev/null
+++ b/problem_sets/ps2.pdf
Binary files differ
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],
+)