Add graph and image

1 files changed, 226 insertions, 55 deletions

diff --git a/assignments/2/README.md b/assignments/2/README.md
index c72f500..cf014cc 100644
--- a/assignments/2/README.md
+++ b/assignments/2/README.md
@@ -18,14 +18,11 @@ 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.
 
-Answer:
-- Error detection: a 16-bit ones' complement checksum over header and payload detects bit errors.
-- Sequencing and in-order delivery: byte sequence numbers and reassembly buffers deliver a contiguous, ordered byte stream.
-- Positive acknowledgments: cumulative ACKs (and optional SACK) inform the sender of data received and gaps.
-- Retransmissions on loss: timeout-based retransmission using RTT/RTO estimation; fast retransmit after 3 duplicate ACKs repairs loss quickly.
-- Sliding window pipelining: allows multiple unacknowledged segments in flight for efficiency.
-- Flow control: receiver-advertised window (rwnd) prevents buffer overrun.
-- Connection management: three-way handshake syncs initial sequence numbers and options; graceful close ensures all data is delivered.
+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%)
 
@@ -34,11 +31,10 @@ protocols, the GBN protocol allows the sender to send multiple packets
 without waiting for acknowledgement from the receiving parties. How does
 GBN achieve that?
 
-Answer:
-- Pipelining with a sending window: up to N unacknowledged packets may be outstanding (window size N).
-- Cumulative ACKs: the receiver ACKs the highest in-order packet; out-of-order packets are discarded (in basic GBN).
-- One timer for the oldest unacked packet: on timeout, the sender retransmits that packet and all later packets in the window (go back N).
-- As ACKs arrive, the window slides forward and new packets are sent immediately.
+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%)
 
@@ -47,17 +43,20 @@ 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?
 
-Answer:
-- Problems IPv6 addresses:
-  - Address exhaustion: 128-bit addressing provides vastly more addresses than IPv4.
-  - Simpler, extensible header (with extension headers) and efficient forwarding.
-  - Improved autoconfiguration (SLAAC), multicast, and neighbor discovery; easier renumbering.
-  - Reduced reliance on NAT; IPsec support designed in.
-- Transition mechanisms (since IPv4 persists):
-  - Dual stack hosts/routers choose IPv4 or IPv6 per destination.
-  - Tunneling (e.g., 6rd, GRE) to carry IPv6 over IPv4 (or vice versa).
-  - Translation (NAT64/DNS64, 464XLAT) to let IPv6-only clients reach IPv4 services.
-  - Incremental, piecemeal deployment driven by ISPs, enterprises, content and CDNs.
+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%)
 
@@ -65,10 +64,20 @@ Answer:
 types. What are the purposes of the SNMP GetRequest and SetRequest
 messages? Why were UDP datagrams chosen to transport SNMP messages?
 
-Answer:
-- GetRequest: manager reads current values of MIB objects (OIDs) from an agent; agent replies with GetResponse.
-- SetRequest: manager writes values to writable MIB objects to configure the device.
-- UDP was chosen because it is simple and lightweight (no connection state), matches request/response with app-layer timeouts and retries, avoids TCP setup and head-of-line blocking for sporadic polls, and supports asynchronous notifications (Traps/Inform) easily.
+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%)
 
@@ -76,16 +85,21 @@ Answer:
 SDN-enabled networking devices. What are the preferrable features that
 an SDN-enabled networking device usually has?
 
-Reference: Kurose & Ross, 8th ed., Ch. 5 (SDN control plane, generalized forwarding).
-
-Answer:
-- Open southbound programming interfaces: OpenFlow, P4Runtime, or NETCONF/YANG.
-- Flexible match-action pipeline (TCAM/ACL capacity), possibly P4-programmable parsing and tables.
-- High-throughput, low-latency forwarding with QoS (queues, shaping, scheduling) and traffic engineering (ECMP, segment routing).
-- Rich telemetry: streaming telemetry (gNMI), sFlow/NetFlow/IPFIX, accurate counters and timestamps; in-band network telemetry support.
-- Secure, robust control-plane: TLS, RBAC, high availability, fast failover.
-- Virtualization and overlay support: VRFs, VXLAN/EVPN, NAT/ACL features for multi-tenancy.
-- APIs/SDKs and upgradable software for automation and programmability.
+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%)
 
@@ -93,10 +107,18 @@ Answer:
 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?
 
-Answer:
-- Loops: a path that revisits the same autonomous system (AS) more than once (e.g., AS1->AS2->AS3->AS1), creating a forwarding loop.
-- Why avoid: loops waste bandwidth, increase latency, may blackhole traffic, and can destabilize routing.
-- Detection: BGP is path-vector; each route carries AS_PATH. If a router sees its own AS in the received AS_PATH, it rejects the route. Within an AS, iBGP loop-prevention uses rules with route reflectors (ORIGINATOR_ID, CLUSTER_LIST).
+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%)
 
@@ -108,31 +130,179 @@ errors. Suppose you have the following 8‑bit bytes: 11011001, 01010010,
 
 > a) What is the 1’s complement of the sum of these 8‑bit bytes? Show all the details of your work.
 
-> 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?
+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.
 
-Answer:
-- a) Sum the 8-bit words using ones' complement addition (end-around carry). In decimal: 217 + 82 + 202 + 164 + 89 = 754. Reduce with ones' complement modulus 255: 754 - 2*255 = 244 (binary 11110100). The checksum is the ones' complement (bitwise invert) of 244, which is 00001011 (decimal 11). Check: 244 + 11 = 255 (all 1s).
-- b) Using ones' complement of the sum makes the overall ones' complement sum of all words (data + checksum) equal to all 1s, enabling simple verification, incremental update, and better detection of many common error patterns than straight modulo-2^n addition.
-- c) The receiver computes the ones' complement sum over the received data and checksum. If the result is 11111111 (all 1s), accept; otherwise, declare a checksum error.
-- d) Any single-bit error changes the sum and is always detected. Some two-bit errors that are complementary in the same bit position across two words can cancel and go undetected; thus not all two-bit (or multi-bit) errors are detected.
+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 A
+> (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.
+which is better known as Dijkstra's shortest path algorithm.
 
-> a) Interpret the table above in your words: what it is showing and what are each row and each column showing?
+| 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 |           |           |           |           |           |
 
-> 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.
+> a) Interpret the table above in your words: what it is showing and what are each row and each column showing?
 
-Answer:
-- a) Each row (Step k) shows the state after the k-th iteration of Dijkstra's algorithm. N' is the set of nodes whose shortest-path distance from the source is known (settled). For each other node n, D(n) is the current best-known distance from the source to n, and P(n) is the predecessor on that tentative path. At each iteration, the node outside N' with minimum D(n) is added to N', and distances to its neighbors are relaxed.
-- b) From source x (using the link costs in the figure), the algorithm proceeds as follows:
+- 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.
+
+```plaintext
+        z
+        |\
+     3  |  11
+        |   \
+        t----y
+       /|\   |
+    5 / | \5 | 1
+     /  |9  \ |
+    x   u---- v
+     \  |1  / |6
+    2 \ |  /  |
+       \| /   |
+        w-----s
+          3    5
+
+   (z)-(t)
+    |   |
+   (y)--+
+
+    |------------------------------------
+    |                             |     |
+    |                             |     |
+   (t)   (u)   (v)   (w)   (x)   (y)   (z)
+
+```
+
+```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(u), P(u) | D(w), P(w) | D(y), P(y) |
+| ---- | -- | ---        | ---        | ---        |
+| 0    | x  | 2,x        | 3,x        | 5,x        |
+| 1    | xu |            | 1,x        | 1,x
+
+
+From source x (using the link costs in the figure), the algorithm proceeds as follows:
   - Step 0: N' = {x}; D(u)=1 via x; D(y)=1 via x; D(w)=3 via x; D(v)=inf; D(z)=inf
   - Step 1: add y; N' = {x,y}; relax y->w and y->z: D(w)=2 via y; D(z)=3 via y; D(u)=1 via x; D(v)=inf
   - Step 2: add u; N' = {x,y,u}; relax u->v (cost 2): D(v)=3 via u; others unchanged
@@ -141,6 +311,7 @@ Answer:
   - Step 5: add z; done
   Shortest-path costs from x: to u = 1 (x->u); to y = 1 (x->y); to w = 2 (x->y->w); to v = 3 (x->u->v); to z = 3 (x->y->z).
 
+
 ## 2.3 CIDR Routing (20%)
 
 > (20%) A router running classless interdomain routing (CIDR) has the following entries in its routing table: