Fast detection and identification of lost packets

Abstract

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 - 28 . (canceled) 
     
     
         29 . A non-transitory machine readable medium storing a program executable by at least one processing unit, the program for monitoring packets passing through a network segment, the program comprising sets of instructions for:
 receiving a first plurality of digests associated with a first plurality of packets entering the network segment;   receiving a second plurality of digests associated with a second plurality of packets leaving the network segment;   merging the first plurality of digests into an upstream digest union and the second plurality of digests into a downstream digest union; and   identifying a packet that is (i) in the first plurality of packets entering the network segment and (ii) not in the second plurality of sets of packets leaving the network segment, by identifying a difference between the upstream digest union and the downstream digest union.   
     
     
         30 . The non-transitory machine readable medium of  claim 29 , wherein
 the network segment comprises a first set of forwarding elements comprising a plurality of input ports and a second set of forwarding elements comprising a plurality of output ports,   each input port is associated with a different upstream meter that monitors packets entering the network segment through that input port, and   each output port is associated with a different downstream meter that monitors packets leaving the network segment through that output port.   
     
     
         31 . The non-transitory machine readable medium of  claim 30 , wherein
 each digest in the first plurality of digests is a digest for a different subset of the first plurality of packets entering the network segment through a different input port, and   each digest in the second plurality of digests is a digest for a different subset of the second plurality of packets leaving the network segment through a different output port.   
     
     
         32 . The non-transitory machine readable medium of  claim 31 , wherein at least two packets in a same particular subset of the first plurality of packets are each in different subsets of the second plurality of packets. 
     
     
         33 . The non-transitory machine readable medium of  claim 31 , wherein
 each digest in the first plurality of digests is generated by the upstream meter associated with the input port corresponding to the digest, and   each digest in the second plurality of digests is generated by the downstream meter associated with the output port corresponding to the digest.   
     
     
         34 . The non-transitory machine readable medium of  claim 29 , wherein the set of instructions for merging a plurality of digests into a digest union comprises a set of instructions for:
 for each digest in the plurality of digests,
 accumulating extracted information of each packet in the digest to a plurality of cells, wherein the plurality of cells are selected from among an array of cells by a plurality of hash functions based on the extracted information; and 
 providing values accumulated in the array of cells in the digest. 
   
     
     
         35 . The non-transitory machine readable medium of  claim 34 , wherein the accumulated extracted information of each packet is accumulated to selected cells in the same array of cells for all digests. 
     
     
         36 . The non-transitory machine readable medium of  claim 34 , wherein the extracted information is accumulated at the selected cells by adding the extracted information to an accumulated value in each of the selected cells by bit-wise exclusive or (XOR), wherein each cell maintains an accumulated value for accumulating packet-identifying information and a counter value for counting the number of packets that are hashed into the cell. 
     
     
         37 . The non-transitory machine readable medium of  claim 29 , wherein
 at least one upstream meter executes on a same host machine also executing the forwarding element to which the associated input port belongs, and   at least one downstream meter executes on a same host machine also executing the forwarding element to which the associated output port belongs.   
     
     
         38 . The non-transitory machine readable medium of  claim 29 , wherein the network segment is a packet-processing pipeline. 
     
     
         39 . A method for monitoring packets passing through a network segment, the method comprising:
 receiving a first plurality of digests associated with a first plurality of packets entering the network segment;   receiving a second plurality of digests associated with a second plurality of packets leaving the network segment;   merging the first plurality of digests into an upstream digest union and the second plurality of digests into a downstream digest union; and   identifying a packet that is (i) in the first plurality of packets entering the network segment and (ii) not in the second plurality of sets of packets leaving the network segment, by identifying a difference between the upstream digest union and the downstream digest union.   
     
     
         40 . The method of  claim 39 , wherein
 the network segment comprises a first set of forwarding elements comprising a plurality of input ports and a second set of forwarding elements comprising a plurality of output ports,   each input port is associated with a different upstream meter that monitors packets entering the network segment through that input port, and   each output port is associated with a different downstream meter that monitors packets leaving the network segment through that output port.   
     
     
         41 . The method of  claim 40 , wherein
 each digest in the first plurality of digests is a digest for a different subset of the first plurality of packets entering the network segment through a different input port, and   each digest in the second plurality of digests is a digest for a different subset of the second plurality of packets leaving the network segment through a different output port.   
     
     
         42 . The method of  claim 41 , wherein at least two packets in a same particular subset of the first plurality of packets are each in different subsets of the second plurality of packets. 
     
     
         43 . The method of  claim 41 , wherein
 each digest in the first plurality of digests is generated by the upstream meter associated with the input port corresponding to the digest, and   each digest in the second plurality of digests is generated by the downstream meter associated with the output port corresponding to the digest.   
     
     
         44 . The method of  claim 39 , wherein merging a plurality of digests into a digest union comprises:
 for each digest in the plurality of digests,
 accumulating extracted information of each packet in the digest to a plurality of cells, wherein the plurality of cells are selected from among an array of cells by a plurality of hash functions based on the extracted information; and 
 providing values accumulated in the array of cells in the digest. 
   
     
     
         45 . The method of  claim 44 , wherein the accumulated extracted information of each packet is accumulated to selected cells in the same array of cells for all digests. 
     
     
         46 . The method of  claim 44 , wherein the extracted information is accumulated at the selected cells by adding the extracted information to an accumulated value in each of the selected cells by bit-wise exclusive or (XOR), wherein each cell maintains an accumulated value for accumulating packet-identifying information and a counter value for counting the number of packets that are hashed into the cell. 
     
     
         47 . The method of  claim 39 , wherein
 at least one upstream meter executes on a same host machine also executing the forwarding element to which the associated input port belongs, and   at least one downstream meter executes on a same host machine also executing the forwarding element to which the associated output port belongs.   
     
     
         48 . The method of  claim 39 , wherein the network segment is a packet-processing pipeline.