lec9

Interconnection Networks: 

Interconnection Networks Lecture 9 : Valentines Day Special Routing Algorithms and Mechanism Prof. Chung-Kuan Cheng University of California San Diego Transcribed by: Jason Thurkettle

Topics: 

Topics Routing Algorithms Deterministic Oblivious Adaptive Mechanisms

Traffic Patterns: 

Traffic Patterns Neighbor -> dx = sx + 1 mod k Transpose: di = si + b/2 mod b Complement Tornado

Deterministic Routing Algorithm: 

Deterministic Routing Algorithm Deterministic Routing Algorithm Ex: Butterfly Route according to address of the destination K-ary N-cube network Route in a shortest path The order of the dimension is set

Deterministic Routing: 

Deterministic Routing Only uses half of the available resources

Oblivious Routing Algorithm: 

Oblivious Routing Algorithm Oblivious Routing Algorithm Variant’s Algorithm K-ary N-cube Send each packet on average distance of K/4 in each of N dimensions Route the packet to the destination Minimal Oblivious Routing: on Tourous Find minimal quadrant between sender (S) and destination (D) (S&D) Select an intermediate node X in the quadrant Route S to X and X to D (where X is chosen randomly)

Oblivious Routing Algorithm: 

Oblivious Routing Algorithm Oblivious Routing Algorithm Load Balanced Routing: Find quadrant: in each dimension I Select the short direction Di = Di with p=(K-Δi)/K Select the long direction Di = Di with p=Δi/K Repeat second step of Minimal Oblivious Routing Repeat third step of Minimal Oblivious Routing

Oblivious Routing Algorithm: 

Oblivious Routing Algorithm Traffic Models vs Bandwidth Usage

Adaptive Routing Algorithm: 

Adaptive Routing Algorithm Adaptive Routing Algorithm Productive hop The packet goes closer to its destination Local Congestion Length of Queue Minimal Adaptive Routing The router chooses only productive hops If these are choices, the hop with minimal congestion is chosen.

Adaptive Routing Algorithm: 

Adaptive Routing Algorithm Adaptive Routing Algorithm Fully Adaptive Routing The router chooses a productive hop if the congestion is less than a threshold. Otherwise the hop with minimal congestion is taken (with a probability) Live lock is possible Load Balanced Adaptive Routing We use load balanced oblivious routing to choose the quadrant The minimum adaptive routing is performed in the quadrant

Routing Mechanisms: 

Routing Mechanisms Table Based Routing R : NxN -> P(p) N: Node Deterministic – determined at source R : NxN -> P(c) C: Channel R : NxN -> P(c) P: Path Algorithm Based Routing: Source Routing [R : SxD -> P(s) ]

Routing Mechanisms: 

Routing Mechanisms Algorithm Based Routing: Source Routing Table of Source (00) from last slide

Routing Mechanisms: 

Routing Mechanisms Algorithm Based Routing: Source Routing The path is chosen at the source node. Each source node contains a table of the route per destination. The advantage: simplified the packet movement between source and destination. Node – Table Routing Each node has a table with index=destination, entry=next hop The method can be used for adaptive routing