TY - PAT T1 - Fast and scalable approximation methods for finding minimum cost flows with ... Y1 - 2007 A1 - Fleischer,Lisa Karen A1 - Saniee,Iraj A1 - Shepherd,Frederick Bruce A1 - Srinivasan, Aravind ED - Lucent Technologies Inc. AB - Broadly, techniques for solving network routing within a predetermined error are disclosed. These techniques may be applied to networks supporting dedicated reserve capacity, where reserved capacity on links in the network is dedicated for a particular commodity (generally, a source and sink pair of computers), and shared recovery, where reserved capacity on links is shared amongst two or more commodities. These techniques use an iterative process to determine flows on each of the links in a network. Costs are set for each commodity, and primary and secondary (i.e., backup) flows are initialized. A commodity is selected and demand for the commodity is routed through the shortest path. Costs are updated for each potential failure mode. For each commodity, the flows and costs are updated. Once all flows and costs are updated, then it is determined if a function is less than a predetermined value. If the function is less than a predetermined value, then the commodity selection, and... VL - 10/053,079 UR - http://www.google.com/patents?id=rkWpAAAAEBAJ CP - 7280526 ER -