We present a methodology to improve network throughput by reordering communication in HPC codes. In contrast to all previous work, our approach does not require any information about network and application communication topology. We implement on-the-fly algorithms that reorder message streams based on statistics inferred during execution. Our intuition is that long operations that occur in ranks that exhibit large execution variability need to be prioritized. We consider two approaches: 1) reorder using statistics of a group of significant ranks; and 2) reorder around an outlier rank. For robustness on noisy systems, our final algorithm combines group and outlier reordering and it allows continuous adaptation of the schedule. We validate on two different networks: Cray Aries and InfiniBand. Micro-benchmarks show that performance between two different schedules of communication can be as high as 74%. Given an initial ordering, our algorithm can recuperate as much as 90% from the potential perfor-mance improvements. When employed in applications, we see improvements as large as 70% in communication times. If interference is present, the algorithm additionally reduces outliers and variance in the communication times.