For mobile agents to be widely accepted in a distributed environment like the Internet, performance and security issues on their use have to be addressed. In this paper, we first present a parallel dispatch model with secure dispatch route structures. This model facilitates efficient dispatching of agents in a hierarchical manner, and ensures route security by exposing minimal route information to hosts. To further enhance route robustness, we also propose a mechanism with substitute routes that can bypass temporarily unreachable hosts, dispatch agents to substitute hosts before attempting the failed hosts again. Finally, a model for distributing the load of decrypting substitute routes is presented. We also present results of both analytical and empirical studies to evaluate different models.