Deflection routing is a novel, distributed, adaptive routing technique proposed for very high speed packet switched networks. In deflection routing contention for access to communication links is resolved by intentionally misrouting or deflecting packets. In this dissertation we study the performance of deflection routing on regular, time-slotted networks.
We begin by deriving performance measures valid for any regular network with deflection routing. We introduce a categorization of networks based on topological properties which determine suitability for deflection routing. First we derive a simple expression for mean packet transit delay under uniform traffic loading. We then examine worst case transit delay under arbitrary offered loads. Here we consider both the evacuation of packets admitted in a batch in a single time slot, and also the maximum delay of packets admitted continuously over multiple time slots.
Our next topic is deflection routing on a specific topology, the Manhattan Street Network (MSN). We derive approximate transit delay distributions for the network operating with a uniform offered load and several priority-based contention resolution rules. We also examine two types of performance enhancements, first supplementing nodes with store-and-forward buffers, and secondly using a conjectured routing "optimization." Network simulation results are reported and compared with analytical results. We then analyze an MSN with a nonuniform offered load. Again we derive approximate delay distributions and throughput measures, and investigate the ability of deflection routing to diffuse localized congestion.
Finally, we consider a novel way of combining trunk grouping
and deflection routing.
We study a trunk group
switch known as the Statistical Data Fork,
and show how trunk grouping can be used to
dramatically reduce deflections.
We derive delay statistics
for networks of these switches under arbitrary offered traffic loads.
In summary, we argue that the combination of
trunk grouping and deflection routing
offers many of the advantages of both techniques,
and solves certain problems inherent in each.