High Performance Router Architectures for Networkbased Computing

High Performance Router Architectures for Networkbased Computing By Dr. Timothy Mark Pinkston University of South California Computer Engineering Division Dept. of Electrical EngineeringSystems

Outline Introduction Topology Routing Deadlock Network Reconfiguration

Introduction High-Performance Router Architectures for Network-based Computing Multiprocessor system Cluster computing environment Core components within the switch/router Network Latency as a function of time for transmission of packet propagation delay switching delay Time required for contention handling

Introduction Four major areas of concern of network design Topology Routing Path selection, deadlock handling, congestion & load balancing Switching Defines the network architecture Path set-up, degree of pipelining, channel sharing Flow control Resource allocation, contention resolution, channel sharing,scheduling

Topology Bisection width Number of links that needed to be removed when dividing the network into 2 nearly equal half Larger width Latency is lower May not be scalable

Routing-Oblivious vs. Adaptive Oblivious routing Path selection in regardless of load Pro: Simple routing function result in lower switching delay Con: Unable to adapt to network condition result in higher contention delay

Routing Oblivious vs. Adaptive Adaptive routing Path selection based on network status Pro: Distribute load more evenly result in lower contention delay Con: Decision based on local information can cause congestion More complex decision logic can increase the switching delay

Routing – Minimal vs. Nonminimal Minimal routing Packets consume less bandwidth Minimal path may consists congested/faulty node Non-minimal routing Packets can route around congestion Provide better worst case performance

Routing - Deadlock Cause Theorem Congestion lead to cyclic waits for resources If no cycles appear in directed graph or connected sub-graph, then it is deadlockfree Solutions Avoidance based Recovery based

Deadlock – Avoidance based Path-based Observation Idea Deadlocks occur when packet change their direction in the network Prohibit certain turns so as to eliminate cycles Examples Direction Order Routing Turn Model Up/Down Model

Path-based Example Dimension Order Routing Turn Model

Deadlock – Avoidance based Path-based Pro: Does not depend on virtual circuits for deadlock-freedom Con: Routing flexibility is sacrificed in general case

Deadlock – Avoidance based Channel based Observation Idea Deadlocks occur when packet cannot escape from cyclic resource dependency Explicitly impose an ordering on the use of virtual circuit resources Examples Entire channel set Escape channel set

Deadlock – Avoidance based Channel based Pro: No need for replication of physical channels Con: Additional control needed for channel selection

Network Reconfiguration Why? Goal To restore or make more efficient the network connectivity when nodes fail/are added Keep network up and running during reconfiguration Discard as few packets as possible How? Static Reconfiguration Dynamic Reconfiguration

Static Reconfiguration Three steps Stop all network traffic and discard all existing packets Update the routing function Reactivate the network Problem Poor reliability, availability, performance and predictability

Dynamic Reconfiguration Problem Reconfiguration-dependent deadlocks due to ghost dependencies: interactio n of old and new routing functions Duato’s Theory Only need to ensure that the escape path (particular VC) remains cycle-fre e during reconfiguration

Dynamic Reconfiguration Application of Duato’s theory Escape channel resources doubled du ring reconfiguration One of the normal channels is drained an d configures as the new escape resource Reconfiguration done with 2 escape chan nels Old escape resource is used as a new ada ptive resource