The Temporally-Ordered Routing Algorithm (TORA)

3/13/98


Click here to start


Table of Contents

The Temporally-Ordered Routing Algorithm (TORA)

Properties

Properties (cont.)

Three Basic Functions

“Link-reversal” Algorithms

Conceptual Description

Conceptual Description (cont.)

Conceptual Description (cont.)

Conceptual Description (cont.)

Conceptual Description (cont.)

Conceptual Description (cont.)

“Height” Metric

Link Direction Assignment

Example of the creating routes process

Node C requires a route and sends QRY

Nodes A and G send QRY

Nodes B and D send QRY, node H responds to QRY

Nodes B and G receive UPD

Node E responds to QRY, nodes B and G propagate reference level

Nodes A, C, and D receive UPD

Nodes A, C, and D propagate reference level

Creating routes process complete

Maintaining Routes: Decision Tree

Example of link failure that does not require a reaction

Each node still has at least one downstream link

Example of link failure that requires a reaction

Node B has no downstream links

Node B defines new reference level

Node D has no downstream links

Node D propagates reference level

Node A has no downstream links

Node A propagates reference level

Failure reaction complete

Example of link failure that partitions the network

Node C has no downstream links

Node C defines new reference level

Node A has no downstream links

Node A propagates reference level

Node D has no downstream links

Node D propagates reference level

Node B has no downstream links

Node B reflects reference level

Node D has no downstream links

Node D propagates reference level

Node A has no downstream links

Node A propagates reference level

Node C has no downstream links

Node C detects partition and sends CLR

Node A sends CLR

Nodes B and D send CLR

Failure reaction complete, all invalid routes erased

Performance Comparison

Simulation Design: Parameters

Simulation Design: Performance Measures

Bandwidth Utilization (19 nodes with 90% connectivity)

Message Packet Delay (19 nodes with 90% connectivity)

Bandwidth Utilization (43 nodes with 90% connectivity)

Message Packet Delay (43 nodes with 90% connectivity)

Bandwidth Utilization (99 nodes with 90% connectivity)

Message Packet Delay (99 nodes with 90% connectivity)

Bandwidth Utilization (43 nodes with 32 min MTTF)

Message Packet Delay (43 nodes with 32 min MTTF)

Summary of Results

Region of Applicability