Networks-on-Chip (NoCs) for contemporary multiprocessors systems must integrate complex multimedia applications which require not only high performance but also timing guarantees. However, in existing NoCs, designed for real-time systems, timing constraints are frequently implemented at the cost of decreased hardware utilization, i.e strict spatial or temporal isolation between transmissions. In this work, we propose an alternative - multi-path scheduling (MPS) - mechanism exploiting the multidimensional structure of NoCs, to combine the path selection and the temporal flow control based on the global state of the system. Consequently, MPS allows a safe sharing of NoC resources while preserving a high utilization achieved through a predictable load distribution of data traffic among different paths, reachable from source to destination. We demonstrate using benchmarks, that MPS not only provides higher average performance compared to existing solutions, but also allows to provide worst-case guarantees. We prove this important feature using formal timing analysis. Moreover, MPS induces a low implementation overhead as it can be applied to many existing wormhole-switched and performance optimized NoCs without requiring complex hardware modifications.