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 establishes a connection between a client and a server using a 3-way
handshake. It provides reliable data transfer through several mechanisms like
built-in error detection to identify corrupted data, sequencing to ensure
that data is reassembled in the correct order, retransmission of lost
or corrupted packets, and traffic/congestion control to manage network
load efficiently.

## 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?

Go-Back-N (GBN) achieves reliable data transfer using several mechanisms
like pipelining with a sending window, cumulative acknowledgments,
timeouts for the oldest unacknowledged packet, and a sliding window that
advances as new acknowledgments are received.

## 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-bit addresses, allowing for roughly 4 billion unique
addresses. As this limit is being reached, IPv6 was introduced, using
128-bit addresses which is enough to assign an IP to every grain of sand
on Earth. This eliminates the need for techniques like NAT to map public
addresses to private subnets.

The transition to IPv6 is gradual. Many hosts, switches, and
routers support dual-stack operation, allowing both IPv4 and IPv6
simultaneously. IPv6 can also be tunneled over IPv4 for legacy
support, and mechanisms like NAT64 enable IPv6 clients to reach IPv4
services. Because most everyday users are unaware of the trade-offs,
much of the transition is being managed incrementally by ISPs, CDNs,
and large organizations.

## 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 (Simple Network Management Protocol) is designed to manage devices
within a network efficiently. In busy networks, a low-overhead protocol is
crucial, as devices may not have the resources to establish or maintain
a TCP connection. Unlike TCP, which requires a 3-way handshake, UDP
is lightweight and works well as a "fire and forget" protocol for
sending management instructions.

- `GetRequest`: Sent by the network manager to read the current state of a device's configuration. Configurations are stored in MIB (Management Information Base) objects, which act as key/value pairs.
- `SetRequest`: Sent by the manager to modify a device's configuration, allowing centralized control of network devices.

## 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?

Software-Defined Networking (SDN) enables programmatic control of
network packet flow through software rather than embedded firmware,
making updates significantly faster to deploy. SDN supports modern
protocols like OpenFlow and NETCONF while providing extensibility for
future protocol development. The centralized architecture delivers
enhanced throughput and reduced latency through quality of service
(QoS) policies and sophisticated traffic engineering that dynamically
optimizes network paths. Operators gain comprehensive telemetry and
real-time visibility into traffic patterns and network behavior,
while centralization streamlines access control and simplifies
administration. Security integration becomes straightforward, enabling
rapid deployment of intrusion detection and prevention systems across
the entire infrastructure. Networks can expand seamlessly to accommodate
IoT devices like cameras, HVAC systems, NAS without manual per-device
configuration, as the SDN controller automates provisioning and management
at scale.

## 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?

Network loops occur when a routing path revisits the same node (Autonomous
System) multiple times while attempting to reach a destination. These
loops prevent packets from reaching their destination, waste bandwidth,
increase latency, and can create black holes where traffic is effectively
dropped. By exhausting network resources, loops can destabilize critical
infrastructure and have been exploited by state actors to disrupt
economies and communications.

BGP prevents loops through its path-vector design. Each BGP route
carries an `AS_PATH` attribute which is an ordered list of every AS the
route advertisement has traversed. When a router receives a route,
it examines the `AS_PATH` for its own AS number. If found, the router
immediately rejects the route, preventing the loop from forming. This
mechanism ensures that routing information propagates acyclically across
the Internet.

# 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.
- Subsequent columns shows the best known distance from `u` to each node.
  - `D(<node>)`: current shorted distance from `u` to `<node>`.
  - `P(<node>)`: predecessor node in the shortest path to `<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.

![./assignments/2/graph](./graph.png)

```ruby
adjacency_list = {
  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]]
}

def dijkstra(graph, source, destination)
  heap = Heap.new
  heap.push(0, source)
  total_cost = 0
  until (heap.empty?) do
    top = heap.min
    distance = graph.distance_between(source, top) || 0
    total_cost += distance
    p "#{source.name} -> #{top.name} (#{distance})"
    return total_cost if top == destination

    neighbors = graph.neighbors(top)
    neighbors.each do |x|
      heap.push(graph.distance_between(source, x) || 100, x)
    end
    source = top
  end
end
```

| 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 forward packets using longest prefix matching among all
matching routing table entries, the route with the longest network mask
is selected. If no entries match, the default route is used.

Routing Table:

| 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).

Context:

- Single TCP flow over 1 Gbps link with no buffering
- Segment size = 1,500 bytes (12,000 bits)
- Round-trip time (RTT) = 15 ms
- Always in congestion avoidance phase

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

Maximum window equals the bandwidth-delay product (BDP):

- BDP = 1 Gbps * 15 ms = 1,000,000,000 * 0.015 = 15,000,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?

In congestion avoidance, the window oscillates between `W_max` and `W_max`/2 due to AIMD (additive increase, multiplicative decrease):

- Average window = 0.75 * 1,250 = 937.5 segments
- Average throughput = (937.5 * 12,000) / 0.015 = 750 Mbps (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 loss, window drops to `W_max`/2 = 625 segments, then increases by 1 segment per RTT:

- Segments to recover = 1,250 - 625 = 625
- Recovery time = 625 * 0.015 = 9.375 seconds

> 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.

The buffer should hold BDP/2 worth of segments to compensate for the congestion window drop during loss recovery:

- Buffer size ~ 625 segments (BDP/2)

This ensures the link remains saturated while the congestion window ramps back up from `W_max`/2 to `W_max`.

# References

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