A PERFORMANCE-MODEL OF DEFLECTION ROUTING IN MULTIBUFFER NETWORKS WITH NONUNIFORM TRAFFIC

Deflection routing can be used in networks whose stations have the sam e number of input and output links, Fixed-length packets arrive synchr onously on the station's input links at the beginning of time slots, a nd each packet is routed via the output link that offers the shortest path to its destination, Since the number of packet buffers at each ou tput link is finite, the simultaneous contention of two packets for th e last buffer of a common output link must be resolved by ''deflecting '' one of the packets to another output link, Thus, the deflection of a packet could result in the packet following a route that is not a sh ortest path, The potentially unbounded number of routes that a given p acket can take makes analyzing the performance of such networks diffic ult, In particular, there currently are no analytical models that can analyze multibuffer deflection-routing networks with nonuniform traffi c, Using independence assumptions, we develop a performance model of d eflection routing that allows us to estimate accurately and efficientl y the mean transport time and throughput in a network that has any giv en two-connected topology, multiple buffers at each output port, and a n arbitrary traffic matrix.