A method for an ingress node to send packets to an egress node, the method comprising: sending a plurality of service packets over a first network path; and sending a supplemental packet comprising a plurality of hash values over a second network path, wherein the plurality of packet hash values are computed respectively from the plurality of service packets. A method for an egress node to receive packets from an ingress node, the method comprising: extracting a plurality of packet hashes from a supplemental packet received from a second network path; computing a plurality of packet hash values, each hash value computed from a corresponding service packet comprised in a plurality of service packets received over a first network path; and recovering a lost service packet that is identified by comparing the plurality of computed packet hash values with the plurality of extracted packet hash values.