This paper considers compression in packet networks. Since data packets may be dropped or arrive reordered, streaming compression algorithms result in a considerable decoding latency. On the other hand, standard stateless packet compression algorithms that compress each packet independently, give a relatively poor compression ratio. We introduce a novel compression algorithm for packet networks: delayed-dictionary compression. By allowing delay in the dictionary construction, the algorithm handles effectively the problems of packet drops and packet reordering, while resulting with a compression quality which is often substantially better than standard stateless packet compression and has a smaller decoding latency than that of streaming compression. We conducted extensive experiments to establish the potential improvement for packet compression techniques, using many data files including the Calgary corpus and the Canterbury corpus. Experimental results of the new delayed-dictionary compression show that its main advantage is in low to medium speed links.