ecen5273

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