Watermark carriers of existing network flow watermarking schemes are limited to packet payload, traffic rate, and packet timing. However, packet payload is based on flow watermarking schemes, which depend on specific application protocols, such as telnet and rlogin, but encryted traffic and are invisible to traffic interceptors. At the same time, traffic rate and packet timing based ones are vulnerable to timing perturbation introduced by network transmission and attackers. Even worse, most of them have a low watermark capacity and are visible to multi-flow attack, mean-square autocorrelation attack and timing analysis attacks. This paper utilizes packet order as a watermark carrier and proposes a novel packet reordering based flow watermarking (PROFW) scheme. To achieve robustness against packet out-of-order pertubation, a theory of error correcting code is introduced into watermark encoding. Meanwhile, this paper utilizes a stochastic modulation approach to increase the stealthiness of PROFW scheme by controlling packet reordering degree not exceeding normal levels. Empirical results prove its robustness against timing and packet out-of-order pertubations, introduced by network transmission and deliberately by attackers. Compared with typical flow watermarking schemes, PROFW scheme, which has a higher watermark capacity, is more robust against timing and packet out-of-order pertubations.