Randomization is one of the main strategies in providing security in moving-target-defense (MTD) systems. However, randomization has an associated cost and estimating this cost and its impact on the overall system is crucial to ensure adoption of the MTD strategy. In this paper we discuss our experience in attempting to estimate the cost of path randomization in a message transmission system that used randomization of paths in the network. Our conclusions are (i) the cost crucially depends on the underlying network control technology, (ii) one can reduce this cost by better implementation, and (iii) reducing one type of cost may result in increased costs of a different type, for example a higher device cost. These suggest that estimating the cost of randomization is a multivariable optimization problem that requires a full understanding of the system components.