Routing Algorithms
The brain of the Network Layer: How routers decide the best path for your data.
A router has two primary jobs that work at different scales and speeds.
Forwarding
- Action: Move packet from input link to output link.
- Scale: Purely local computation.
- Speed: Must be very fast (nanoseconds).
Routing
- Action: Determine the end-to-end path.
- Scale: Global decisions (Network-wide).
- Speed: Slower (important when topology changes).
To solve routing, we model the network as a Graph (G = V, E).
- Nodes (V): Represent Routers.
- Edges (E): Represent Physical Links.
- Cost (c): Delay, $, or congestion level.
Link State algorithms require every router to know the entire network topology via "Link State Broadcast".
Key Notation:
c(i,j): Cost from node i to j.D(v): Current cost of path to destination v.p(v): Predecessor (the node before v).N: Set of nodes whose least cost is known.
Algorithm Steps (Simplified)
- Initial: Start with the source. Neighbors get their actual cost, others get ∞ (infinity).
- Find Minimum: Look for the node w not in
Nwith the smallestD(w). - Update: For all neighbors of w, update their costs if going through w is cheaper.
- Repeat: Until all nodes are in
N.
Unlike Dijkstra, this is Distributed and Iterative. Routers only talk to their neighbors.
Bellman-Ford Equation (The Logic):
Cost from X to Y via neighbor Z = (Cost to Z) + (Best cost from Z to Y).
Key Characteristics:
- Iterative: Self-terminating (stops when no more info).
- Asynchronous: Neighbors don't need to be in lock-step.
- Distributed: Each node calculates its own table.
شرح الـ Distance Vector:
الراوتر هنا "عمي" شوية، مش شايف الخريطة كلها. هو بس بيسأل جيرانه: "إنتو بتوصلوا لـ (أ) في قد إيه؟". وبناءً على ردهم بيحسب أحسن طريق لنفسه. ميزته إنه بسيط وبيستجيب للتغييرات بسرعة بين الجيران.