#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: ``` + 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], )