Whereas the standard maximum network flow problem (single commodity) has well known polynomial-time solutions [27], multicommodity problems are much harder, and fall into the general category of linear programming. There is a fair amount of research on the multicommodity problem [59,3,68,89] but the algorithms, based on Linear Programming, are exponential on the worst case.