--- 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()`: current shorted distance from `u` to ``. - `P()`: predecessor node in the shortest path to `` > 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. ![Graph](./assignments/2/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. ```ruby require 'ipaddr' class RoutingTable def initialize(default, routes) @default = default @routes = routes end def route_to(ip) destination = @routes.fetch(@routes.keys.find { |route| route.include?(ip) }, @default) "#{ip} => #{destination}" end end table = RoutingTable.new("Router 3", { IPAddr.new('135.46.56.0/22') => "Interface 0", IPAddr.new('135.46.60.0/22') => "Interface 1", IPAddr.new('192.53.40.0/23') => "Router 2", }) a = IPAddr.new("135.46.61.10") b = IPAddr.new("135.46.53.16") c = IPAddr.new("192.53.40.6") d = IPAddr.new("192.53.56.7") puts table.route_to(a) puts table.route_to(b) puts table.route_to(c) puts table.route_to(d) ``` Result: ```bash 135.46.61.10 => Interface 1 135.46.53.16 => Router 3 192.53.40.6 => Router 2 192.53.56.7 => 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.