tidy up final answer of a2 and add ruby example of shorted path algorithm

1 files changed, 39 insertions, 22 deletions

diff --git a/assignments/2/README.md b/assignments/2/README.md
index 1ccb815..b51499e 100644
--- a/assignments/2/README.md
+++ b/assignments/2/README.md
@@ -257,7 +257,7 @@ which is better known as Dijkstra's shortest path algorithm.
 ![./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]]
@@ -267,6 +267,25 @@ which is better known as Dijkstra's shortest path algorithm.
   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) |
@@ -324,43 +343,41 @@ 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:
+Context:
 
-* 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
+- 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 is equal to the bandwidth delay product in segments.
+Maximum window equals the bandwidth-delay product (BDP):
 
-- 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.
+- 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?
 
-The window will go and up down between the window maximum and half the window maximum.
+In congestion avoidance, the window oscillates between `W_max` and `W_max`/2 due to AIMD (additive increase, multiplicative decrease):
 
-- 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).
+- 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 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
+After loss, window drops to `W_max`/2 = 625 segments, then increases by 1 segment per RTT:
 
-Time to return to the maximum window is 9.375 s.
+- 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.
 
-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.
+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