Appia: automatic storage area network fabric design
Julie Ann Ward, Michael J. O’Sullivan, Troy Shahoumian, John Wilkes · 2002
Designing a storage area network (SAN) fabric requires devising a set of hubs, switches and links to connect hosts to their storage devices. The network must be capable of simultaneously meeting specified data flow requirements between multiple host-device pairs, and it must do so cost-effectively, since large-scale SAN fabrics can cost millions of dollars. Given that the number of data flows can easily number in the hundreds, simple overprovisioned manual designs are often not attractive: they can cost significantly more than they need to, may not meet the performance needs, may expend valuable resources in the wrong places, and are subject to the usual sources of human error. Producing SAN fabric designs automatically can address these difficulties, but it is a non-trivial problem: it extends the NP-hard minimum-cost fixed-charge multicommodity network flow problem to include degree constraints, node capacities, node costs, unsplittable flows, and other requirements. Nonetheless, we present here two efficient algorithms for automatic SAN design. We show that these produce cost-effective SAN designs in very reasonable running times, and explore how the two algorithms behave over a range of design problems.