We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded. The latter result has implications for the running time of themax-weight protocol when it is used to solve multicommodity flowproblems. In particular, for a fixed problem instance we show thatif the value of the optimum solution is known, the max-weight protocolfinds a flow that is within a (1-)-factor of optimal in time O(1/) (improving the previous bound of O(1/ 2)). If thevalue of the optimum solution is not known, we show how to apply themax-weight algorithm in a binary search procedure that runs in O(1/) time.