commit 24728b61f7cb0b965b1839741225fa0c808e79c6
parent a681f63007d2b9d9eeabe617f2af2da610418347
Author: Alex Balgavy <alex@balgavy.eu>
Date: Fri, 9 Apr 2021 10:50:48 +0200
Distributed algs notes
Diffstat:
2 files changed, 159 insertions(+), 0 deletions(-)
diff --git a/content/distributed-algorithms-notes/_index.md b/content/distributed-algorithms-notes/_index.md
@@ -6,3 +6,4 @@ title = 'Distributed Algorithms'
1. [Introduction](introduction)
2. [Waves, trees & deadlock detection](waves-deadlock-detection)
3. [Termination detection & garbage collection](termination-detection-garbage-collection)
+4. [Routing](routing)
diff --git a/content/distributed-algorithms-notes/routing.md b/content/distributed-algorithms-notes/routing.md
@@ -0,0 +1,158 @@
++++
+title = 'Routing'
++++
+
+# Routing
+Guiding a packet in network to its destination.
+
+Routing table at node u stores for each v a neighbor w of u.
+Packets with destination v that arrive at u re passed to w.
+
+## Chandy-Misra shortest path algorithm
+Undirected weighted network with positive weights.
+Centralised algorithm to compute shortest paths to initiator u₀.
+
+Initially:
+- dist(u₀, u₀) = 0
+- dist(v, u₀) = ∞ for othe nodes
+- parent(v, u₀) = ⊥ for all v
+
+u₀ sends message ⟦0⟧ to its neighbors
+
+node v receives ⟦d⟧ from neighbor w. if d + wt(v, w) < dist(v, u₀), then
+- dist(v, u₀) = d + wt(v, w) and parent(v, u₀) = w
+- v sends ⟦dist(v, u₀)⟧ to its neighbors (except w)
+
+Termination detection by e.g. Dijkstra-Scholten
+
+Complexity:
+- worst-case message; exponential
+- worst-case messag efor minimum-hop: O(N²·E)
+
+...
+
+## Merlin-Segall shortest path algorithm
+Centralised algorithm to compute shortest paths to initiator u₀.
+
+Initially, dist(u₀, u₀) = 0, dist(v, u₀) = ∞ for other nodes, and parent(v, u₀) values form sink tree with root u₀.
+
+Each round, u₀ sends ⟦0⟧ to its neighbors.
+1. let node v receive ⟦d⟧ from neighbor w.
+ - if d + wt(v, w) < dist(v, u₀), then dist(v, u₀) = d + wt(v, w)
+ - v stores w as future value for parent(v, u₀)
+ - if w = parent(v, u₀), then v sends ⟦dist(v, u₀⟧ to its neighbors except parent(v, u₀).
+2. When a v ≠ u₀ has received message from all neighbors, it sends ⟦dist(v, u₀)⟧ to parent(v, u₀) and updates parent(v, u₀).
+
+u₀ starts a new round after receiving a message from all neighbors.
+
+Complexity:
+- message: Θ(N²·E)
+
+Topology changes:
+- number attached to distance messages
+- when edge fails or becomes operational, adjacent nodes send message to u₀ via sink tree
+- when u₀ receives such a message, it
+ - rebuilds sink tree
+ - starts new set of N-1 rounds, with higher number
+
+## Floyd-Warshall all-pairs shortest path algorithm
+Initially, S = ∅ (S is explained in the next section).
+
+While S doesn't contain all nodes, a pivot w ∉ S selected:
+- d[S ∪ {w}] computed from d[S]
+- w is added to S
+
+When S contains all nodes, d[S] is standard distance function.
+
+Complexity:
+- time: Θ(N³)
+
+## Toueg's algorithm
+Computes for each pair (u,v) a shortest path from u to v
+
+dS(u, v), with S set of nodes, denotes length of shortest path fro u to v with all intermediate nodes in S
+- d[S](u, u) = 0
+- d[∅](u, v) = wt(u, v) for two different nodes connected by an edge
+- d[∅](u, v) = ∞ for two different nodes not connected by an edge
+- d[S ∪ {w}](u, v) = min{ d[S](u, v), d[S](u, w) + d[S](w, v)} if w not in S
+
+When S contains all nodes, d[S] is the standard distance function
+
+Assume each node knows the IDs of all nodes
+
+Initially at each node u:
+- S(u) = ∅
+- dist(u, u) = 0 and parent(u, u) = ⊥
+- for each other node,
+ - either dist(u, v) = wt(u, v) and parent(u, v) = v if there is an edge uv,
+ - or dist(u, v) = ∞ and parent(u, v) = ⊥
+
+
+At w-pivot round, w broadcasts its values dist(w, v) for all nodes v.
+
+If parent(u, w) = ⊥, for a node u ≠ w at the w-pivot round, then dist(u, w) = ∞, so dist(u, w) + dist(w, v) ≥ dist(u, v) for all nodes v.
+
+Hence the sink tree toward w can be used to broadcast dist(w)
+
+If u is in sink tree toward w, it sends ⟦request, w⟧ to parent(u, w), to let it pass on dist(w).
+
+If u isn't in sink tree towards w, it proceeds to next pivot round, with S(u) = S(u) ∪ {w}
+
+Consider any node u ni sink tree toward w:
+- if u ≠ w, it waits for values dist(w, v) from parent(u, w)
+- u forwards values dist(w, v) to neighbors that send ⟦request, w⟧ to u
+- if u ≠ w, it checks for each node v whether dist(u, w) + dist(w, v) < dist(u, v)
+ - if yes, dist(u, v) = dist(u, w) + dist(w, v) and parent(u, v) = parent(u, w)
+- finally, u proceeds to next pivot round, with S(u) = S(u) ∪ {w}
+
+Complexity:
+- message: O(N²)
+
+## Distance-vector routing
+Network in which nodes/links may fail or be added.
+Such a change is eventually detected by its neighbors.
+
+If topology change is detected, a node sends its entire routing table to its neighbors.
+Each node locally computes shortest paths.
+
+## Link-state routing
+Nodes periodically send link-state packet, with
+- node's edges and their weights (based on latency, bandwidth)
+- sequence number (increases with each broadcast)
+
+- Link-state packets are flooded through the network
+- Nodes store link-state packets to obtain view of the entire network
+- sequence numbers avoid old info overwriting new info
+- each node locally computes shortest paths, e.g. with Dijkstra's
+
+When node recovers from crash, its sequence number starts at 0
+- so packets carry time-to-live (TTL) field
+- after this time, info from packet may be discarded by packet with lower sequence number
+- to reduce flooding, each time a link-state packet is forwarded, its TTL field decreases
+ - when it becomes 0, the packet is discarded
+
+## Autonomous systems
+RIP protocol uses distance-vector routing
+
+OSPF protocol uses link-state routing
+
+These routing algorithms don't scale to the internet because of sending whole routing tables, or flooding.
+So, internet divided into autonomous sytems, where each system uses RIP or OSPF.
+
+Border Gateway Protocol routes between autonomous systems.
+- border routers broadcast updates of their routing tables (like Chandy-Misra)
+- border router updates its routing table
+ - because it detects topology change
+ - or because of update in routing table of neighbor
+
+You can still get deadlock, if you fill up memory at the nodes.
+
+## Slow-start with TCP
+TCP protocol provides reliable packet delivery.
+
+To avoid congestion, nodes maintainn congestion window for each of their edges.
+This is the max number of unacknowledged packets on this edge.
+
+Congestion window grows linearly with each received ack, up to some threshold.
+
+With each lost data packet, the congestion window is reset to initial size (TCP Tahoe) or halved (TCP Reno)
