Techniques are described for avoiding data packet fragmentation in a routing device such as a router or network switch. Path Maximum Transport Unit (PMTU) values are monitored for a plurality of egress links of a networking device. A statistical analysis of fragmentation rates is performed. The statistical analysis can be performed on a per-link basis, per-flow basis or both per-link and per-flow basis. If the packet fragmentation rate of data flows through a particular egress link exceeds a determined threshold value, one or more data flows can be re-routed to a different egress link having a higher PMTU, thereby preventing data packet fragmentation.