routing.md (6028B)
1 +++ 2 title = 'Routing' 3 +++ 4 5 # Routing 6 Guiding a packet in network to its destination. 7 8 Routing table at node u stores for each v a neighbor w of u. 9 Packets with destination v that arrive at u re passed to w. 10 11 ## Chandy-Misra shortest path algorithm 12 Undirected weighted network with positive weights. 13 Centralised algorithm to compute shortest paths to initiator u₀. 14 15 Initially: 16 - dist(u₀, u₀) = 0 17 - dist(v, u₀) = ∞ for othe nodes 18 - parent(v, u₀) = ⊥ for all v 19 20 u₀ sends message ⟦0⟧ to its neighbors 21 22 node v receives ⟦d⟧ from neighbor w. if d + wt(v, w) < dist(v, u₀), then 23 - dist(v, u₀) = d + wt(v, w) and parent(v, u₀) = w 24 - v sends ⟦dist(v, u₀)⟧ to its neighbors (except w) 25 26 Termination detection by e.g. Dijkstra-Scholten 27 28 Complexity: 29 - worst-case message; exponential 30 - worst-case messag efor minimum-hop: O(N²·E) 31 32 ... 33 34 ## Merlin-Segall shortest path algorithm 35 Centralised algorithm to compute shortest paths to initiator u₀. 36 37 Initially, dist(u₀, u₀) = 0, dist(v, u₀) = ∞ for other nodes, and parent(v, u₀) values form sink tree with root u₀. 38 39 Each round, u₀ sends ⟦0⟧ to its neighbors. 40 1. let node v receive ⟦d⟧ from neighbor w. 41 - if d + wt(v, w) < dist(v, u₀), then dist(v, u₀) = d + wt(v, w) 42 - v stores w as future value for parent(v, u₀) 43 - if w = parent(v, u₀), then v sends ⟦dist(v, u₀⟧ to its neighbors except parent(v, u₀). 44 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₀). 45 46 u₀ starts a new round after receiving a message from all neighbors. 47 48 Complexity: 49 - message: Θ(N²·E) 50 51 Topology changes: 52 - number attached to distance messages 53 - when edge fails or becomes operational, adjacent nodes send message to u₀ via sink tree 54 - when u₀ receives such a message, it 55 - rebuilds sink tree 56 - starts new set of N-1 rounds, with higher number 57 58 ## Floyd-Warshall all-pairs shortest path algorithm 59 Initially, S = ∅ (S is explained in the next section). 60 61 While S doesn't contain all nodes, a pivot w ∉ S selected: 62 - d[S ∪ {w}] computed from d[S] 63 - w is added to S 64 65 When S contains all nodes, d[S] is standard distance function. 66 67 Complexity: 68 - time: Θ(N³) 69 70 ## Toueg's algorithm 71 Computes for each pair (u,v) a shortest path from u to v 72 73 dS(u, v), with S set of nodes, denotes length of shortest path fro u to v with all intermediate nodes in S 74 - d[S](u, u) = 0 75 - d[∅](u, v) = wt(u, v) for two different nodes connected by an edge 76 - d[∅](u, v) = ∞ for two different nodes not connected by an edge 77 - d[S ∪ {w}](u, v) = min{ d[S](u, v), d[S](u, w) + d[S](w, v)} if w not in S 78 79 When S contains all nodes, d[S] is the standard distance function 80 81 Assume each node knows the IDs of all nodes 82 83 Initially at each node u: 84 - S(u) = ∅ 85 - dist(u, u) = 0 and parent(u, u) = ⊥ 86 - for each other node, 87 - either dist(u, v) = wt(u, v) and parent(u, v) = v if there is an edge uv, 88 - or dist(u, v) = ∞ and parent(u, v) = ⊥ 89 90 91 At w-pivot round, w broadcasts its values dist(w, v) for all nodes v. 92 93 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. 94 95 Hence the sink tree toward w can be used to broadcast dist(w) 96 97 If u is in sink tree toward w, it sends ⟦request, w⟧ to parent(u, w), to let it pass on dist(w). 98 99 If u isn't in sink tree towards w, it proceeds to next pivot round, with S(u) = S(u) ∪ {w} 100 101 Consider any node u ni sink tree toward w: 102 - if u ≠ w, it waits for values dist(w, v) from parent(u, w) 103 - u forwards values dist(w, v) to neighbors that send ⟦request, w⟧ to u 104 - if u ≠ w, it checks for each node v whether dist(u, w) + dist(w, v) < dist(u, v) 105 - if yes, dist(u, v) = dist(u, w) + dist(w, v) and parent(u, v) = parent(u, w) 106 - finally, u proceeds to next pivot round, with S(u) = S(u) ∪ {w} 107 108 Complexity: 109 - message: O(N²) 110 111 ## Distance-vector routing 112 Network in which nodes/links may fail or be added. 113 Such a change is eventually detected by its neighbors. 114 115 If topology change is detected, a node sends its entire routing table to its neighbors. 116 Each node locally computes shortest paths. 117 118 ## Link-state routing 119 Nodes periodically send link-state packet, with 120 - node's edges and their weights (based on latency, bandwidth) 121 - sequence number (increases with each broadcast) 122 123 - Link-state packets are flooded through the network 124 - Nodes store link-state packets to obtain view of the entire network 125 - sequence numbers avoid old info overwriting new info 126 - each node locally computes shortest paths, e.g. with Dijkstra's 127 128 When node recovers from crash, its sequence number starts at 0 129 - so packets carry time-to-live (TTL) field 130 - after this time, info from packet may be discarded by packet with lower sequence number 131 - to reduce flooding, each time a link-state packet is forwarded, its TTL field decreases 132 - when it becomes 0, the packet is discarded 133 134 ## Autonomous systems 135 RIP protocol uses distance-vector routing 136 137 OSPF protocol uses link-state routing 138 139 These routing algorithms don't scale to the internet because of sending whole routing tables, or flooding. 140 So, internet divided into autonomous sytems, where each system uses RIP or OSPF. 141 142 Border Gateway Protocol routes between autonomous systems. 143 - border routers broadcast updates of their routing tables (like Chandy-Misra) 144 - border router updates its routing table 145 - because it detects topology change 146 - or because of update in routing table of neighbor 147 148 You can still get deadlock, if you fill up memory at the nodes. 149 150 ## Slow-start with TCP 151 TCP protocol provides reliable packet delivery. 152 153 To avoid congestion, nodes maintainn congestion window for each of their edges. 154 This is the max number of unacknowledged packets on this edge. 155 156 Congestion window grows linearly with each received ack, up to some threshold. 157 158 With each lost data packet, the congestion window is reset to initial size (TCP Tahoe) or halved (TCP Reno)