Routing Algorithms

 

Routing algorithm determines the path used to get a packet from a source node to a destination node.

Shall study deterministic minimal routing algorithms.

Deterministic

• Path chosen depends solely on source and destination.
• Route does not depend on traffic.

Minimal

• Path chosen is shortest path.

• Deadlock
• Dimension Order Routing
• Determining Deadlock Freedom
• Breaking Cycles
• ...