Abstract
This paper considers the link capacity requirement for a N × N mesh-torus network under a uniformall-to-all traffic model. Both primary capacity and spare capacity for recovering from link failures are examined. In both cases, we use a novel method of "cuts on a graph" to obtain lower bounds on capacity requirements and subsequently find algorithms for routing and failure recovery that meet these bounds. Finally, we quantify the benefits of path based restoration over that of link based restoration; specifically, we find that the spare capacity requirement for a link based restoration scheme is nearly N times that for a path based scheme.