path: root/assignments/2/README.md

---
title: "COMP-347: Computer Networks"
author: "Munir Khan (ID: 3431709)"
date: "September 2025"
subtitle: "Assignment 2"
institute: "Athabasca University"
geometry: margin=1in
fontsize: 11pt
linestretch: 1.0
---

# Part 1: Short Answer Questions (30%)

## 1.1 TCP Reliable Data Transfer (5%)

> (5%) TCP provides a reliable data transfer service on top of IP's
unreliable best‑effort service. Study related sections of the textbook
and articles from other sources. In your own words, explain how TCP
provides a reliable data transfer service.

TCP uses a 3-way handshake to establish a connection from client to
server. It has built in error detection and correction for corrupted
data, sequencing to ensure data is reassembled in order, the ability to
retransmit data due to network errors, just-in-time traffic/congestion
management.

## 1.2 Go-Back-N Protocol (5%)

> (5%) While the RDT protocols are essentially stop‑and‑wait
protocols, the GBN protocol allows the sender to send multiple packets
without waiting for acknowledgement from the receiving parties. How does
GBN achieve that?

GBN is able to achieve that through several mechanisms such as pipelining with a
sending window, sending cumulative acknowledgement packets, timeout for the
oldest packet that has not been acknowledged, and a sliding window that moves as
new acknowledgement packets arrive.

## 1.3 IPv6 Transition (5%)

> (5%) Invention and adoption of IPv6 is a big advance in computer
networking. What problems was IPv6 intended to solve? With the large
number of networking devices and applications using IPv4 still in use,
how is the transition from IPv4 to IPv6 being resolved?

IPv4 uses 32 bits for addresses which means that it can address 2^32 (4 billion)
devices. This upperbound is being exhausted and IPv6 was designed to alleviate
this issue by using 128 bits for addressing. This is enough to assign an IP
address to every grain of sand on the planet. This removes the need for things
like NAT to translate packets destined to the public interface of a router to
the private subnet of the router.

The transition is being resolved by using hosts, switches, routers that support
both IPv4 and IPv6 to give devices time to upgrade. IPv6 can also be carried
over IPv4 to offer a form of tunneling to support legacy devices. There are also
layers that allow IPv6 clients reach IPv4 services such as NAT64. Many average
day consumers do not understand the trade-offs so much of this transition is
being carried out piecemeal by bigger players like IPS, CDN's and larger
corporations.

## 1.4 SNMP Protocol (5%)

> (5%) SNMP is a protocol for network management. It has seven message
types. What are the purposes of the SNMP GetRequest and SetRequest
messages? Why were UDP datagrams chosen to transport SNMP messages?

SNMP is the Simple Network Management Protocol which is meant to be used to
manage devices within a network. Sometimes the network can be busy so using a
protocol with low overhead to manage busy devices is important. TCP has more
overhead that UDP because TCP requires a 3-way handshake to establish a
connection. When a device on the network is busy and needs instructions from a
network manager it may not have the resources to establish/maintain a TCP connection.
UDP is a better choice for this because it is a fire and forget protocol.

The `GetRequest` type is sent by network manager to read the current state of
configuration from a device. The configuration is stored in something called MIB
objects which serves as a sort of key/value store. The `SetRequest` type is used
to change configuration from a manager to an agent/device. This allows the
manager to change the state of configuration on different devices on the
network.

## 1.5 SDN-Enabled Devices (5%)

> (5%) In today’s market and its applications, there are many
SDN-enabled networking devices. What are the preferrable features that
an SDN-enabled networking device usually has?

A software defined network (SDN) allows software to control the flow of packets
within a network. This type of software is typically easier to update than the
firmware embedded in most traditional routers/switches. This allows for
protocols like OpenFlow and NETCONF to be used as well as creates extensions
points for new protocol to form. SDN offers things like higher throughput, lower
latency with quaility of service (QoS) and other forms of traffic engineering.
On top of this the centralization helps to offer improved telemetry data to see
everything that is happening withing a network. It also allows for improved
security by making it easier to integrate intrusion detection and prevention
mechanisms. Centralization through a SDN also makes it easier for human
operators to access and control who can manage and operate the network.
Extending a network through an SDN gives the network capability to grow over
time which can lead to enhancements such as the ability to connect cameras, hvac
controls, and network attached storage without needing to manually managing each
of these devices through cumbersome protocols.

## 1.6 BGP Loop Detection (5%)

> (5%) BGP is a routing protocol used for routing among ISPs. One problem
that BGP faces is detecting loops in paths. What are the loops? Why
should loops be avoided? How does BGP detect the loops in paths?

A network loop occurs when a path revisits the same node (AS) more than once
while attempting to reach a destination. This loops creates a problem because
packets may never reach their destination and could exhaust network resources.

Loops waste bandwidth, increase latency and may effectively send certain traffic
the equivalent of `/dev/null` (a black hole). This can destabilize a network by
exhausting available resources and can be used by state actors to destablize
economies, communication and more.

BGP is path-vector (i.e. an array of visited nodes) where each route carries the list of AS that it has visited in something called an `AS_PATH`.
If a router sees its own AS in the received `AS_PATH`, it rejects the route and
prevents looping.

# Part 2: Long Answer Questions (70%)

## 2.1 1's Complement Checksum (10%)

> (10%) UDP and TCP use 1’s complement for their checksums to detect
errors. Suppose you have the following 8‑bit bytes: 11011001, 01010010,
11001010, 10100100 and 01011001.

> a) What is the 1’s complement of the sum of these 8‑bit bytes? Show all the details of your work.

The 1's complement is 00001011.

```
1.
     11011001
  +  01010010
  ===========
   1 00101011 (carry out = 1)

2. wrap around the carry.

     00101011
  +         1
  ===========
     00101100

3.

     00101100
  +  11001010
  ===========
     11110110

3.

     11110110
  +  10100100
  ===========
   1 10011010

4.
     10011010
   +        1
   ==========
     10011011

5. Total Sum

     10011011
  +  01011001
  ===========
     11110100

6. Find 1's complement by flipping each bit

   11110100
   ========
   00001011 <- 1's complement
```

The 1's complement is 00001011 which would be used to check for errors.

```
1. sum the 5 bytes
    11011001
    01010010
    11001010
    10100100
  + 01011001
  ==========
 10 11110010 -> carry 10 around

2. carry the 10 around

    11110010
  +       10
  ==========
    11110100

3. add the 1's complement

  11110100
+ 00001011
==========
  11111111

All bits are on! Valid!
```

> b) Why do UDP and TCP take the 1's complement of the sum as their checksum, instead of the just sum of these bytes?

It makes the verification at the receiver simpler and less costly to
compute because when the receiver gets the 5 bytes + the 1 byte checksum
value it can add all bytes together and that is a single computation
and ensure that all bits are set to 1. If we sent the sum instead of the
1's complement then the receiver would have to sum all 5 bytes and then
compare it to the 6th byte value. This would require more than a single
addition operation and would add quite a bit of overhead.

> c) With the 1's complement scheme, how does the receiver detect errors?

The receiver computes the 1's complement sum over the received data
and checksum. If the result is 11111111 (all 1s) then it is valid.

> d) With this checksum scheme, is it possible that any 1‑bit error will go undetected? How about a 2‑bit error? Explain your answer.

Any 1-bit error will change the sum and is always detected. Some 2-bit
errors that are complementary in the same bit position across two words
can cancel and go undetected.

## 2.2 Dijkstra's Shortest Path Algorithm (20%)

> (20%) The following table is used to compute the shortest path from u
to all other nodes in a network, according to the link‑state algorithm,
which is better known as Dijkstra's shortest path algorithm.

| Step | N'     | D(v),P(v) | D(w),P(w) | D(x),P(x) | D(y),P(y) | D(z),P(z) |
|------|--------|-----------|-----------|-----------|-----------|-----------|
| 0    | u      | 2,u       | 5,u       | 1,u       | -         | -         |
| 1    | ux     | 2,u       | 4,x       |           | 2,x       | -         |
| 2    | uxy    | 2,u       | 3,y       |           |           | 4,y       |
| 3    | uxyv   |           | 3,y       |           |           | 4,y       |
| 4    | uxyvw  |           |           |           |           | 4,y       |
| 5    | uxyvwz |           |           |           |           |           |

> a) Interpret the table above in your words: what it is showing and what are each row and each column showing?

- Each row shows the state after each iteration of the algorithm.
- N' is the set of nodes with the shortest path distance from the source.
- Each subsequent column shows the best known distance from `u` to the node
  descried in the column as well as the node before it.
  - `D(<node>)`: the best known distance from `u` to `<node>`.
  - `P(<node-1>)`: the node that was last visited before `<node>`.

> b) Consider the network shown in the following diagram. With the indicated link costs, use Dijkstra's shortest path algorithm to compute the shortest path from x to all other network nodes. Show how the algorithm works by computing a table like the one above.

```dot
strict graph {
  s -- t [label=1]
  s -- v [label=5]
  t -- s [label=1]
  t -- u [label=9]
  t -- v [label=6]
  t -- y [label=5]
  t -- z [label=3]
  u -- t [label=9]
  u -- v [label=1]
  u -- w [label=1]
  u -- x [label=2]
  u -- y [label=1]
  v -- s [label=5]
  v -- t [label=6]
  v -- u [label=1]
  v -- w [label=3]
  w -- u [label=1]
  w -- v [label=3]
  w -- x [label=3]
  x -- u [label=2]
  x -- w [label=3]
  x -- y [label=5]
  y -- t [label=5]
  y -- u [label=1]
  y -- x [label=5]
  y -- z [label=11]
  z -- t [label=3]
  z -- y [label=11]
}
```

![graph](./graph.png)

```ruby
{
  s: [[:t,1], [:v,5]]
  t: [[:s,1], [:u,9], [:v,6], [:y,5], [:z,3]]
  u: [[:t,9], [:v,1], [:w,1], [:x,2], [:y,1]]
  v: [[:s,5], [:t,6], [:u,1], [:w,3]]
  w: [[:u,1], [:v,3], [:x,3]]
  x: [[:u,2], [:w,3], [:y,5]]
  y: [[:u,1], [:x,5], [:t,5], [:z,11]]
  z: [[:t,3], [:y,11]]
}
```

| Step | N'       | D(s),P(s) | D(t),P(t) | D(u),P(u) | D(v),P(v) | D(w),P(w) | D(y),P(y) | D(z),P(z) |
| ---- | --       | --------- | --------- | --------- | --------- | --------- | --------- | --------- |
| 0    | x        | -         | -         | 2,x       | -         | 3,x       | 5,x       | -         |
| 1    | xu       | -         | 11,u      |           | 3,u       | 3,x       | 3,u       | -         |
| 2    | xuw      | -         | 11,u      |           | 3,u       |           | 3,u       | -         |
| 3    | xuwv     | 8,v       | 9,v       |           |           |           | 3,u       | -         |
| 4    | xuwvy    | 8,v       | 8,y       |           |           |           |           | 14,y      |
| 5    | xuwvys   |           | 8,y       |           |           |           |           | 14,y      |
| 6    | xuwvyst  |           |           |           |           |           |           | 11,t      |
| 7    | xuwvystz |           |           |           |           |           |           |           |

## 2.3 CIDR Routing (20%)

> (20%) A router running classless interdomain routing (CIDR) has the following entries in its routing table:
> Address/mask  Next hop
> 135.46.56.0/22 Interface 0
> 135.46.60.0/22 Interface 1
> 192.53.40.0/23 Router 2
> Default Router 3
>
> How does a CIDR router route the packets it receives? For each of the following IP addresses, explain what the router will do if a packet with that address arrives.
> a) 135.46.61.10
> b) 135.46.53.16
> c) 192.53.40.6
> d) 192.53.56.7

CIDR routers use the longest prefix match. Among all entries that match
the destination it will choose the one with the longest mask. If none
match, then is uses the default route.

| CIDR           | start       | end           | Route       |
| ----           | -----       | ---           | ---------   |
| 135.46.56.0/22 | 135.46.56.0 | 135.46.59.255 | Interface 0 |
| 135.46.60.0/22 | 135.46.60.0 | 135.46.63.255 | Interface 1 |
| 192.53.40.0/23 | 192.53.40.0 | 192.53.41.255 | Router 2    |
| Default        |             |               | Router 3    |

a. 135.46.61.10 -> matches 135.46.60.0/22 -> forward to Interface 1.
b. 135.46.53.16 -> no /22 match -> forward using Default -> Router 3.
c. 192.53.40.6 -> matches 192.53.40.0/23 -> forward to Router 2.
d. 192.53.56.7 -> no /23 match -> forward using Default -> Router 3.

## 2.4 TCP Congestion Control (20%)

> (20%) Consider that only a single TCP connection uses a 1 Gbps link,
which does not buffer any data. Suppose that this link is the only
congested link between the sending and receiving hosts. Assume that the
TCP sender has a huge file to send to the receiver and the receiver's
receive buffer is much larger than the congestion window. Further assume
that each TCP segment size is 1,500 bytes; the two-way propagation delay
of this connection is 15 msec; and this TCP connection is always in the
congestion avoidance phase (ignore slow start).

Given: 

* Single TCP flow over a 1 Gbps link, no buffering at the link
* segment size = 1500 B (12,000 bits)
* two-way propagation delay (RTT) = 15 ms
* always in congestion avoidance

> a) What is the maximum window size (in segments) that this TCP connection can achieve?

Maximum window is equal to the bandwidth delay product in segments.

- BDP: 1,000,000,000 bps * 0.015 s = 15,000,000 bits.
- segment size: = 1,500 B * 8 = 12,000 bits.
- Maximum window = 15,000,000 / 12,000 = 1,250 segments.

> b) What is the average window size (in segments) and average throughput (in bps) of this TCP connection?

The window will go and up down between the window maximum and half the window maximum.

- Average window: 0.75 * maximum window = 937.5 segments.
- Average throughput: = 
  - (average window * segment size) / RTT
  - (937.5 * 12,000) / 0.015 = 750,000,000 bps (0.75 Gbps).

> c) How long would it take for this TCP connection to reach its maximum window again after recovering from a packet loss?

After a loss, congestion window equal window max / 2 = 625 segments and then grows by 1 segment per RTT.

- 1,250 / 2 = 625 segments
- 625 * 0.15 s = 9.375 s

Time to return to the maximum window is 9.375 s.

> d) Assume we want the 1 Gbps link to buffer a finite number of segments and always keep the link busy sending data. How would you choose a buffer size? Justify your answer.

To keep the link busy right after a drop, the queue should supply the missing in-flight data between BDP and the congestion window.
Provision about BDP/2 worth of buffering. Then congestion window + queue so that the link can be fully utilized while the congestion window ramps up.

# References

- Kurose, J. F., & Ross, K. W. (8th ed.). Computer Networking: A Top‑Down Approach.