Examination of the tail behavior of a distribution F that generates teletraffic measurements is an important first step toward building a network model that explains the link between heavy tails and long-range dependence exhibited in such data. When knowledge of the tail behavior of F is vague, the family of the generalized Pareto distributions (GPDs) can be used to approximate the tail probability of F, and the value of its shape parameter characterizes the tail behavior. To detect tail behavior of F between two host computers on a network, the estimation procedure must be carried out over all possible combinations of host computers, and thus, the performance of the estimator under repeated use becomes the primary concern. In this article, we evaluate the long-run performance of several existing estimation procedures and propose a Bayes estimator to overcome some of the shortcomings. The conditions in which the procedures perform well in the long run are reported, and a simple rule of thumb for choosing an appropriate estimator for the task of repeated estimation is recommended.