Fast detection and identification of lost packets
View Patent ↗The invention provides a packet loss detection system that in near-real time detects packet loss and reports the identities of the lost packets. The identities of the lost packets are based on a set of packet-specific information that includes five-tuple flow information of the packet and other unique packet identifiers. A set of meters are placed at various vantage points in the network, each meter generates digests summarizing all the traffic passing through itself. The digests are exported to a collector/analyzer, which decodes the digests and performs an analysis to detect packet losses and to determine the lost packets' identities. The collector compares between the traffic digests generated by all the meters surrounding the segment. Mismatches among the digests indicate packet losses. The collector restores the identifiers of the lost packets by further decoding the mismatches between the digests.
1. A method for a computing device monitoring packets flowing through a segment of a network, the network segment comprising a plurality of forwarding elements, the method comprising:
receiving a first digest of a first plurality of packets entering the segment of the network, wherein the first plurality of packets enters the segment through a plurality of input ports of a first set of forwarding elements, the input ports monitored by a corresponding plurality of upstream meters, wherein each upstream meter tags its monitored packets with an identifier uniquely associated with the upstream meter's corresponding input port;
receiving a second, different digest of a second plurality of packets leaving the segment of the network, wherein the second plurality of packets exit the segment through a plurality of output ports of a second set of forwarding elements, the output ports monitored by a corresponding plurality of downstream meters;
identifying as lost a packet that is in the first plurality of packets but not in the second plurality of packets by decoding a difference between the first digest and the second digest; and
reporting the identity of the identified lost packet.
2. The method of claim 1 further comprising tagging each packet in the first plurality of packets with a first batch identifier, wherein a set of packets entering the monitored segment after the first plurality of packets are tagged with a second, different batch identifier.
3. The method of claim 2 , wherein generating the second digest comprises excluding packets that are not tagged with the first batch identifier.
4. The method of claim 1 , wherein the first plurality of packets is monitored by the plurality of upstream meters, wherein generating the first digest comprises merging a plurality of digests generated at the plurality of meters.
5. The method of claim 1 , wherein the second digest is time-synchronized with the first digest such that the second plurality of packets corresponds to the first plurality of packets.
6. The method of claim 1 , wherein generating the second digest comprises accumulating information from packets tagged with a particular identifier that is associated with a particular input port.
7. For a segment of a network comprising a plurality of forwarding elements, a system comprising:
a first meter that generates a first digest of a first plurality of packets entering the segment of the network, wherein the first plurality of packets enters the segment through a plurality of input ports of a first set of forwarding elements, the input ports monitored by a corresponding plurality of upstream meters, wherein each upstream meter tags its monitored packets with an identifier uniquely associated with the upstream meter's corresponding input port;
a second meter that generates a second, different digest of a second plurality of packets leaving the segment of the network, wherein the second plurality of packets exit the segment through a plurality of output ports of a second set of forwarding elements, the output ports monitored by a corresponding plurality of downstream meters; and
an analyzer, executed by a set of hardware processors of a computer, that (i) receives the first and second digests from the first and second meters through the network, (ii) identifies as lost a packet that is in the first plurality of packets but not in the second plurality of packets by decoding a difference between the first digest and the second digest, and (iii) reports the identity of the identified lost packet.
8. The system of claim 7 , wherein the first meter tags each packet in the first plurality of packets with a first batch identifier, wherein the first meter tags packets entering the monitored segment after the first plurality of packets with a second, different batch identifier.
9. The system of claim 8 , wherein the second meter generates the second digest by excluding packets that are not tagged with the first batch identifier.
10. The system of claim 7 , wherein the first plurality of packets is monitored by the plurality of upstream meters, wherein generating the first digest comprises merging a plurality of digests generated at the plurality of upstream meters.
11. The system of claim 7 , wherein the second digest is time-synchronized with the first digest such that the second plurality of packets corresponds to the first plurality of packets.
12. The system of claim 7 , wherein generating the second digest comprises accumulating information from packets tagged with a particular identifier that is associated with a particular input port.
13. A computing device for monitoring packets flowing through a segment of the network, the network segment comprising a plurality of forwarding elements, the device comprising:
a set of processing units; and
a machine readable medium storing a program for execution by at least one of the processing units, the program comprising sets of instructions for:
receiving a first digest of a first plurality of packets entering the segment of the network, wherein the first plurality of packets enters the segment through a plurality of input ports of a first set of forwarding elements, the input ports monitored by a corresponding plurality of upstream meters, wherein each upstream meter tags its monitored packets with an identifier uniquely associated with the upstream meter's corresponding input port;
receiving a second, different digest of a second plurality of packets leaving the segment of the network, wherein the second plurality of packets exit the segment through a plurality of output ports of a second set of forwarding elements, the output ports monitored by a corresponding plurality of downstream meters;
identifying as lost a packet that is in the first plurality of packets but not in the second plurality of packets by decoding a difference between the first digest and the second digest; and
reporting the identity of the identified lost packet.
14. The computing device of claim 13 , wherein each packet in the first plurality of packets is tagged with a first batch identifier, wherein each packet entering the monitored segment after the first plurality of packets is tagged with a second, different batch identifier.
15. The computing device of claim 14 , wherein the second digest excludes packets that are not tagged with the first batch identifier.
16. The computing device of claim 13 , wherein the first plurality of packets is monitored by the plurality of upstream meters, wherein the first digest is merged from a plurality of digests generated at the plurality of meters.