TY - JOUR

T1 - Optimal multihop routing - an iterative approach to TWDM embedding

AU - Bhattacharya, Sourav

AU - Guha, Aloke

AU - Pavan, Allalaghatta

AU - Du, David H.C.

PY - 1995/12/1

Y1 - 1995/12/1

N2 - This paper introduces the concept of time slot synchronization in time-wave division multiplexed (TWDM) multihop lightwave networks. It is shown that the time slot assignments of the intermediate nodes in a multihop path have significant effect on the end-to-end message delay. This is different from traditional notions in routing, where the hop count and congestion control are the primary concerns. Assuming a TWDM embedding of a given logical topology already exists, we formulate the optimal routing problem for arbitrary propagation delays. We propose a graph unfolding technique which converts this problem into the shortest path routing problem for weighted graphs with well known solutions. We show a method to estimate the buffering cost at the intermediate nodes (in multihop routing) to accommodate high-bandwidth traffic (e.g., video). Next, we address the question: given a logical topology what should the TWDM embedding be so that the routing delays are optimized? This leads us to an iterative approach for TWDM embedding. Given an initial embedding an optimal route is estimated for each pair of nodes. A weighted average of these optimal route distances is used as a metric to evaluate the TWDM embedding. Using a heuristic the TWDM embedding is modified and the process iterated to improve along this metric. Preliminary performance results illustrating the improvement in routing delay are provided. For example, for a 4-cube network an average delay minimization of 10% to 20% is observed.

AB - This paper introduces the concept of time slot synchronization in time-wave division multiplexed (TWDM) multihop lightwave networks. It is shown that the time slot assignments of the intermediate nodes in a multihop path have significant effect on the end-to-end message delay. This is different from traditional notions in routing, where the hop count and congestion control are the primary concerns. Assuming a TWDM embedding of a given logical topology already exists, we formulate the optimal routing problem for arbitrary propagation delays. We propose a graph unfolding technique which converts this problem into the shortest path routing problem for weighted graphs with well known solutions. We show a method to estimate the buffering cost at the intermediate nodes (in multihop routing) to accommodate high-bandwidth traffic (e.g., video). Next, we address the question: given a logical topology what should the TWDM embedding be so that the routing delays are optimized? This leads us to an iterative approach for TWDM embedding. Given an initial embedding an optimal route is estimated for each pair of nodes. A weighted average of these optimal route distances is used as a metric to evaluate the TWDM embedding. Using a heuristic the TWDM embedding is modified and the process iterated to improve along this metric. Preliminary performance results illustrating the improvement in routing delay are provided. For example, for a 4-cube network an average delay minimization of 10% to 20% is observed.

UR - http://www.scopus.com/inward/record.url?scp=0029510259&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029510259&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0029510259

SN - 0742-1303

SP - 92

EP - 101

JO - Conference on Local Computer Networks

JF - Conference on Local Computer Networks

T2 - Proceedings of the 20th Conference on Local Computer Networks

Y2 - 16 October 1995 through 19 October 1995

ER -