Quality-of-Services routing algorithms that utilize probes are criticized for not being able to achieve optimal path selection for real-time flows. This is because probe-based algorithms do not have a global view of the network. This paper introduces a new probe-based routing algorithm for packet-switched networks that supports both best-effort and real-time flows. Unlike other probe-based algorithms, probes are routed via routing tables to achieve optimal performance. Simulations were carried out on QColony and other QoS probe-based routing systems under various network traffic loads and irregular network topologies. Simulation results, concerning resource utilization and connection request success rates, show that QColony provides good performance under heavy loads with failure conditions especially for large networks. The paper also introduces a novel approach for traffic protection in case of network failure conditions.