In a modern stored-program-controlled telephone network, a considerable amount of information regarding the state of the network can be made available for operational decisions such as traffic routing. This paper is an attempt to obtain a computable solution to the problem of optimum traffic routing with state information, in the framework of the theory of Markov decision processes.