Sampling for passive internet measurement: a review. (English) Zbl 1100.62107

Summary: Sampling has become an integral part of passive network measurement. This role is driven by the need to control the consumption of resources in the measurement infrastructure under increasing traffic rates and the demand for detailed measurements from applications and service providers. Classical sampling methods play an important role in the current practice of Internet measurement. The aims of this review are (i) to explain the classical sampling methodology in the context of the Internet to readers who are not necessarily acquainted with either, (ii) to give an account of newer applications and sampling methods for passive measurement and (iii) to identify emerging areas that are ripe for the application of statistical expertise.


62P30 Applications of statistics in engineering and industry; control charts
90B18 Communication networks in operations research


Full Text: DOI


[1] Adams, A., Bu, T., Friedman, T., Horowitz, J., Towsley, D., Cáceres, R., Duffield, N. G., Lo Presti, F., Moon, S. B. and Paxson, V. (2000). The use of end-to-end multicast measurements for characterizing internal network behavior. IEEE Communications Magazine 38 (5) 152–159. Available at www.research.att.com/ duffield/pubs/minc.ps.gz.
[2] Amer, P. D. and Cassel, L. N. (1989). Management of sampled real-time network measurements. In Proc. 14th IEEE Conference on Local Computer Networks 62–68. IEEE Press, New York.
[3] Apisdorf, J., Claffy, K., Thompson, K. and Wilder, R. (1996). OC3MON: Flexible, affordable, high performance statistics collection. Available at www. nlanr.net/NA/Oc3mon.
[4] Armitage, G. J. (2000). MPLS—The magic behind the myths. IEEE Communications Magazine 38 (1) 124–131. Available at www.comsoc.org/ci/private/2000/jan/pdf/ Armitage.pdf.
[5] Barbara, D., DuMouchel, W., Faloutsos, C., Haas, P. J., Hellerstein, J. M., Ioannidis, Y., Jagadish, H. V., Johnson, T., Ng, R., Poosala, V., Ross, K. A. and Sevcik, K. C. (1997). The New Jersey data reduction report. IEEE Data Engineering Bulletin 20 (4) 3–42. Available at ftp://ftp.research.microsoft.com/pub/ debull/97DEC-CD.pdf.
[6] Berners-Lee, T., Fielding, R. and Frystyk, H. (1996). Hypertext transfer protocol—HTTP/1.0. RFC 1945. Available at www.ietf.org/rfc/rfc1945.txt.
[7] Broder, A. and Mitzenmacher, M. (2002). Network applications of Bloom filters: A\(\!\) survey. In Proc. Allerton Conference . Available at www.eecs.harvard.edu/ \(\!\)michaelm/ NEWWORK/postscripts/BloomFilterSurvey.pdf. · Zbl 1090.68515
[8] Cáceres, R., Duffield, N. G., Feldmann, A., Friedmann, J., Greenberg, A., Greer, R., Johnson, T., Kalmanek, C., Krishnamurthy, B., Lavelle, D., Mishra, P. P., Ramakrishnan, K. K., Rexford, J., True, F. and van der Merwe, J. E. (2000). Measurement and analysis of IP network usage and behavior. IEEE Communications Magazine 38 (5) 144–151. Available at www.research.att.com/ duffield/pubs/ measure.ps.gz.
[9] Case, J., Fedor, M., Schoffstall, M. and Davin, J. (1990). A simple network management protocol (SNMP). RFC 1157. Available at www.ietf.org/rfc/rfc1157.txt.
[10] Chaudhuri, S., Motwani, R. and Narasayya, V. R. (1999). On random sampling over joins. In Proc. ACM SIGMOD 1999 263–274. ACM Press, New York. Available at doi.acm.org/10.1145/304182.304206.
[11] Choi, B.-Y., Park, J. and Zhang, Z.-L. (2002). Adaptive random sampling for load change detection (extended abstract). In Proc. ACM SIGMETRICS 2002 272–273. ACM Press, New York. Available at parapet.ee.princeton. edu/ sigm2002/papers/p272-choi.pdf.
[12] Cisco NetFlow. Available at www.cisco.com/warp/ public/732/netflow/index.html.
[13] Cisco NetFlow services and applications customer profiles. Available at www.cisco.com/warp/public/cc/pd/iosw/ ioft/neflct/profiles/.
[14] Claffy, K. C., Braun, H.-W. and Polyzos, G. C. (1995). A parameterizable methodology for Internet traffic flow profiling. IEEE J. Selected Areas in Communications 13 1481–1494. Available at www.nlanr.net/ Flowsresearch/Flowspaper/flows.html.
[15] Claffy, K. C., Polyzos, G. C. and Braun, H.-W. (1993). Application of sampling methodologies to network traffic characterization. Computer Communication Review 23 194–203. Also appeared in Proc. ACM SIGCOMM 1993 . Available at www.caida.org/outreach/ papers/1993/asmw/sigcomm.sampling.pdf.
[16] Coates, A., Hero, A., Nowak, R. and Yu, B. (2002). Internet tomography. IEEE Signal Processing Magazine 19 (3) 47–65. Available at www.ece.mcgill.ca/ coates/ publications/tomoreview.ps.gz.
[17] Cochran, W. (1977). Sampling Techniques , 3rd ed. Wiley, New York. · Zbl 0353.62011
[18] Corbató, S. (1996). Backbone performance analysis techniques. In Proc. INET 96 . Available at www.isoc.org/inet96/proceedings/d3/d3_1.htm.
[19] Cormode, G. and Muthukrishnan, S. (2004). What’s new: Finding significant differences in network data streams. In Proc. IEEE INFOCOM 2004 3 1534–1545. IEEE Press, New York.
[20] Cozzani, I. and Giordano, S. (1998). Traffic sampling methods for end-to-end QoS evaluation in large heterogeneous networks. Computer Networks and ISDN Systems 30 1697–1706. Available at netserv.iet.unipi.it/students/ cozzani/cozzani/Papers/TNC98.ps.gz.
[21] Cranor, C., Gao, Y., Johnson, T., Shkapenyuk, V. and Spatscheck, O. (2002). Gigascope: High performance network monitoring with an SQL interface. Demonstration. In Proc. ACM SIGMOD 2002 623. Available at athos.rutgers.edu/ muthu/demo_02.pdf.
[22] Dean, D., Franklin, M. and Stubblefield, A. (2001). An algebraic approach to IP traceback. In Proc. Network and Distributed System Security Symposium . Available at www.isoc.org/isoc/conferences/ndss/01/2001/ papers/dean01.pdf.
[23] Demaine, E., López-Ortiz, A. and Munro, J. I. (2002). Frequency estimation of internet packet streams with limited space. Proc. 10th European Symposium on Algorithms. Lecture Notes in Comput. Sci. 2461 348–360. Available at theory.lcs.mit.edu/ edemaine/ papers/NetworkStats_ESA2002/paper.pdf. · Zbl 1019.68502
[24] Drobisz, J. and Christensen, K. (1998). Adaptive sampling methods to determine traffic statistics including the Hurst parameter. In Proc. 23rd IEEE Conference on Local Computer Networks 238–247. IEEE Press, New York. Available at citeseer.ist.psu.edu/335773.html.
[25] Duffield, N. G., Gerber, A. and Grossglauser, M. (2002). Trajectory engine: A backend for trajectory sampling. In IEEE Network Operations and Management Symposium 437–450. IEEE Press, New York. Available at www.research.att.com/ duffield/pubs/DGG01-engine.pdf.
[26] Duffield, N. G. and Grossglauser, M. (2001). Trajectory sampling for direct traffic observation. IEEE/ACM Transactions on Networking 9 280–292. An abridged version appeared in Proc. ACM SIGCOMM 2000 271–282. Available at www.research.att.com/ duffield/pubs/ DG-TS-ToN.pdf.
[27] Duffield, N. G. and Lund, C. (2003). Predicting resource usage and estimation accuracy in an IP flow measurement collection infrastructure. In Proc. ACM SIGCOMM Internet Measurement Conference 179–191. ACM Press, New York. Available at www.research.att.com/  duffield/pubs/p313-duffield-lund.pdf.
[28] Duffield, N. G., Lund, C. and Thorup, M. (2001). Charging from sampled network usage. In Proc. ACM SIGCOMM Internet Measurement Workshop 245–256. ACM Press, New York. Available at www.research.att.com/ duffield/pubs/DLT01-usage.pdf.
[29] Duffield, N. G., Lund, C. and Thorup, M. (2001). Learn more, sample less: Control of volume and variance in network measurement. Unpublished manuscript. Available at www.research.att.com/ duffield/pubs/ DLT05-optimal.pdf. · Zbl 1296.94015
[30] Duffield, N. G., Lund, C. and Thorup, M. (2002). Properties and prediction of flow statistics from sampled packet streams. In Proc. ACM SIGCOMM Internet Measurement Workshop 159–171. ACM Press, New York. Available at www.research.att.com/ duffield/pubs/DLT02-flows.pdf.
[31] Duffield, N. G., Lund, C. and Thorup, M. (2003). Estimating flow distributions from sampled flow statistics. In Proc. ACM SIGCOMM 2003 325–336. ACM Press, New York. Available at www.research.att.com/ duffield/pubs/DLT03-lengths.pdf.
[32] Duffield, N. G., Lund, C. and Thorup, M. (2004). Flow sampling under hard resource constraints. In Proc. ACM SIGMETRICS 2004 85–96. ACM Press, New York. Available at www.research.att.com/ duffield/pubs/DLT03-constrained.pdf.
[33] DuMouchel, W. (2002). Data squashing: Constructing summary data sets. In Handbook of Massive Data Sets (J. Abello, P. M. Pardalos and M. G. C. Resende, eds.) 579–591. Kluwer, Dordrecht. · Zbl 1050.68027
[34] DuMouchel, W., Volinksy, C., Johnson, T., Cortes, C. and Pregibon, D. (1999). Squashing flat files flatter. In Proc. Fifth ACM Conference on Knowledge Discovery and Data Mining 6–15. ACM Press, San Diego. Available at www.research.att.com/ corinna/ papers/kddsquash.ps.gz.
[35] Durand, M. and Flajolet, P. (2003). Loglog counting of large cardinalities. Proc. 11th Annual European Symposium on Algorithms . Lecture Notes in Comput. Sci. 2832 605–617. Springer, Berlin. · Zbl 1266.68236
[36] Estan, C. and Varghese, G. (2003). New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems 21 270–313. Available at www.acm.org/sigcomm/sigcomm2002papers/traffmeas.pdf.
[37] Estan, C., Varghese, G. and Fisk, M. (2003). Bitmap algorithms for counting active flows on high speed links. In Proc. ACM SIGCOMM Internet Measurement Conference 153–166. ACM Press, New York. Available at www.icir.org/vern/imc-2003/papers/p327-estan.ps.
[38] Feldmann, A., Cáceres, R., Douglis, F., Glass, G. and Rabinovich, M. (1999). Performance of Web proxy caching in heterogeneous bandwidth environments. In Proc. IEEE INFOCOM 1999 1 107–116. Available at www.research.att.com/ misha/network/proxim_full.ps.gz.
[39] Feldmann, A., Greenberg, A., Lund, C., Reingold, N. and Rexford, J. (2000). NetScope: Traffic engineering for IP networks. IEEE Network 14 (2) 11–19. Available at www.cs.princeton.edu/ jrex/papers/ ieeenet00.pdf.
[40] Feldmann, A., Greenberg, A., Lund, C., Reingold, N., Rexford, J. and True, F. (2001). Deriving traffic demands for operational IP networks: Methodology and experience. IEEE/ACM Transactions on Networking 9 265–279. Available at www.cs.princeton.edu/ jrex/papers/ton01.pdf.
[41] Feldmann, A., Rexford, J. and Cáceres, R. (1998). Efficient policies for carrying web traffic over flow-switched networks. IEEE/ACM Transactions on Networking 6 673–685. Available at www.cs.princeton.edu/ jrex/papers/ton98.ps.
[42] Feldmeier, D. C. (1986). Statistical monitors for local area networks. In Proc. 11th IEEE Conference on Local Computer Networks 142–146. IEEE Press, New York.
[43] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P. and Berners-Lee, T. (1999). Hypertext transfer protocol—HTTP/1.1. RFC 2616. Available at www.ietf.org/rfc/rfc2616.txt.
[44] Foundry Networks (2004). Foundry enterprise configuration and management guide. Appendix A. Remote network monitoring. Available at www.foundrynet.com/ services/documentation/ecmg/Net_Monitoring.html.
[45] Gibbons, P. B. and Matias, Y. (1998). New sampling-based summary statistics for improving approximate query answers. In Proc. ACM SIGMOD International Conference on Management of Data 331–342. ACM Press, New York. Available at citeseer.ist.psu.edu/gibbons98new.html.
[46] Gibbons, P. B. and Matias, Y. (1999). Synopsis data structures for massive data sets. In External Memory Algorithms (J. M. Abello and J. S. Vitter, eds.) 39–70. Amer. Math. Soc., Providence, RI. Available at www.math.tau.ac.il/ matias/papers/synopsis.ps. · Zbl 0952.68040
[47] Gilbert, A. C., Kotidis, Y., Muthukrishnan, S. and Strauss, M. J. (2001). QuickSAND: Quick summary and analysis of network data. Technical Report 2001-43, DIMACS. Available at www.math.lsa.umich.edu/ annacg/ ps.files/quickdimacstr.ps.
[48] Golab, L., DeHaan, D., Demaine, E., Lopez-Ortiz, A. and Munro, J. (2003). Identifying frequent items in sliding windows over on-line packet streams. In Proc. ACM SIGCOMM Internet Measurement Conference 173–178. ACM Press, New York. Available at www.imconf.net/imc-2003/papers/p318-golab.pdf.
[49] Grossglauser, M. and Rexford, J. (2005). Passive traffic measurement for IP operations. In The Internet as a Large-Scale Complex System (K. Park and W. Willinger, eds.). Oxford Univ. Press. Available at www.cs.princeton.edu/ jrex/papers/sfi.pdf.
[50] Hernandez, E. A., Chidester, M. C. and George, A. D. (2001). Adaptive sampling for network management. J. Network and Systems Management 9 409–434. Available at citeseer.nj.nec.com/544063.html.
[51] Hohn, N. and Veitch, D. (2003). Inverting sampled traffic. In Proc. ACM SIGCOMM Internet Measurement Conference 222–233. ACM Press, New York. Available at www.icir.org/vern/imc-2003/papers/thinning1.pdf.
[52] Horvitz, D. G. and Thompson, D. J. (1952). A generalization of sampling without replacement from a finite universe. J. Amer. Statist. Assoc. 47 663–685. · Zbl 0047.38301
[53] IETF. Packet sampling working group charter. Available at www.ietf.org/html.charters/psamp-charter.html.
[54] IETF Working Group. Internet protocol flow information export (IPFIX). Available at net.doit.wisc.edu/ipfix/.
[55] InMon Corporation (2004). sFlow accuracy and billing. Available at www.inmon.com/pdf/sFlowBilling.pdf.
[56] International Organization for Standardization (1984). ISO information processing systems—data communication high-level data link control procedure—frame structure. Report IS 3309, 3rd ed., ISO.
[57] Jacobson, V., Leres, C. and McCanne, S. (1989). tcpdump. Available at ftp://ftp.ee.lbl.gov/tcpdump.tar.Z.
[58] Jedwab, J., Phaal, P. and Pinna, B. (1992). Traffic estimation for the largest sources on a network, using packet sampling with limited storage. Technical Report 92-35, Hewlett–Packard Laboratories, Bristol. Available at www.hpl.hp.com/techreports/92/HPL-92-35.html.
[59] Juniper Networks. Configure traffic sampling. Available at www.juniper.net/techpubs/software/junos/junos63/ swconfig63-policy/html/sampling-config4.html.
[60] Knuth, D. E. (1998). The Art of Computer Programming 3 , 3rd ed. Addison–Wesley, Reading, MA. · Zbl 0895.68054
[61] Kodialam, M. and Lakshman, T. V. (2003). Detecting network intrusions via sampling: A game theoretic approach. In Proc. IEEE INFOCOM 2003 3 1880–1889. IEEE Press, New York. Available at www.ieee-infocom.org/2003/papers/46_02.PDF.
[62] Kodialam, M., Lakshman, T. V. and Mohanty, S. (2004). Runs based traffic estimator (RATE): A simple, memory efficient scheme for per-flow rate estimation. In Proc. IEEE INFOCOM 2004 3 1808–1818. IEEE Press, New York.
[63] Krishnaiah, P. R. and Rao, C. R., eds. (1988). Sampling. Handbook of Statistics 6 . North-Holland, Amsterdam. · Zbl 0662.62006
[64] Kumar, A., Xu, J., Wang, J., Spatschek, O. and Li, L. (2004). Space-code Bloom filter for efficient per-flow traffic measurement. In Proc. IEEE INFOCOM 2004 3 1762–1773. IEEE Press, New York.
[65] L’Ecuyer, P. (1988). Efficient and portable combined random number generators. Communications of the ACM 31 742–751. Available at doi.acm.org/10.1145/62959.62969.
[66] Lee, W. Readings in intrusion detection (online bibliography). Available at www.cc.gatech.edu/ wenke/ids-readings.html.
[67] Leland, W. E., Taqqu, M. S., Willinger, W. and Wilson, D. V. (1994). On the self-similar nature of Ethernet traffic. IEEE/ACM Transactions on Networking 2 1–15. Available at dx.doi.org/10.1109/90.282603.
[68] Level 3 Communications, Inc. (2000). Level 3 promises huge savings. Discount Long Distance Digest . August 2000. Available at www.thedigest.com/more/ 119/119-73.html.
[69] Madigan, D., Raghavan, N., DuMouchel, W., Nason, M., Posse, C. and Ridgeway, G. (2000). Likelihood-based data squashing: A modeling approach to instance construction. Technical report, AT&T Labs. Available at www.stat.rutgers.edu/ madigan/PAPERS/lds.pdf. · Zbl 0996.68564
[70] Manku, G. S. and Motwani, R. (2002). Approximate frequency counts over data streams. In Proc. 28th International Conference on Very Large Data Bases . Available at www-db.stanford.edu/ manku/papers/ 02vldb-freq.pdf.
[71] Mathis, M. and Mahdavi, J. (1996). Diagnosing Internet congestion with a transport layer performance tool. In Proc. INET 96 . Available at www.isoc.org/inet96/proceedings/d3/d3_2.htm.
[72] Micheel, J., Braun, H.-W. and Graham, I. (2001). Storage and bandwidth requirements for passive Internet header traces. In Proc. Workshop on Network-Related Data Management . Available at wand.cs.waikato.ac.nz/ pubs/6/pdf/nrdm2001.pdf.
[73] Moon, S. B. and Roscoe, T. (2001). Metadata management of terabyte datasets from an IP backbone network: Experience and challenges. In Proc. Workshop on Network-Related Data Management . Available at berkeley. intel-research.net/troscoe/pubs/NRDM2001.pdf.
[74] Moore, D., Paxson, V., Savage, S., Shannon, C., Staniford, S. and Weaver, N. (2003). The spread of the sapphire/slammer worm. Technical report, CAIDA. Available at www.caida.org/outreach/papers/ 2003/sapphire/sapphire.html.
[75] Owen, A. (2000). Data squashing by empirical likelihood. Technical report, Dept. Statistics, Stanford Univ. Available at www-stat.stanford.edu/ owen/reports/squash.ps.
[76] Paxson, V. (1994). Empirically-derived analytic models of wide-area TCP connections. IEEE/ACM Transactions on Networking 2 316–336. Available at ftp://ftp.ee.lbl.gov/papers/WAN-TCP-models.ps.gz.
[77] Paxson, V. (1997). End-to-end routing behavior in the Internet. IEEE/ACM Transactions on Networking 5 601–615. Available at ftp://ftp.ee.lbl.gov/papers/ vp-routing-TON.ps.gz.
[78] Paxson, V., Almes, G., Mahdavi, J. and Mathis, M. (1998). Framework for IP performance metrics. RFC 2330. Available at www.ietf.org/rfc/rfc2330.txt.
[79] Pederson, S. and Johnson, M. (1990). Estimating model discrepancy. Technometrics 32 305–314.
[80] Phaal, P., Panchen, S. and McKee, N. (2001). InMon corporation’s sFlow: A method for monitoring traffic in switched and routed networks. RFC 3176. Available at www.ietf.org/rfc/rfc3176.txt.
[81] Postel, J. (1980). User datagram protocol. RFC 768. Available at www.ietf.org/rfc/rfc768.txt.
[82] Postel, J. (1981). Internet protocol. RFC 791. Available at www.ietf.org/rfc/rfc791.txt.
[83] Postel, J. (1981). Transmission control protocol. RFC 793. Available at www.ietf.org/rfc/rfc793.txt.
[84] QoSient. Argus. Available at www.qosient.com/ argus/index.htm.
[85] Random sampled NetFlow. Available at www.cisco.com/ en/US/products/sw/iosswrel/ps5207/products_feature_ guide09186a00801a7618.html#16984.
[86] Reeves, J. and Panchen, S. (2002). Traffic monitoring with packet-based sampling for defense against security threats. In Proc. Passive and Active Measurement Workshop . Available at www.sflow.org/ SamplingforSecurity.pdf.
[87] Reynolds, J., ed. (2002). Assigned numbers: RFC 1700 is replaced by an on-line database. RFC 3232. Available at www.ietf.org/rfc/rfc3232.txt.
[88] Riverstone Networks, Inc. Available at www.riverstonenet.com/.
[89] Rivest, R. (1992). The MD5 message–digest algorithm. RFC 1321. Available at www.ietf.org/rfc/rfc1321.txt.
[90] Savage, S., Wetherall, D., Karlin, A. and Anderson, T. (2000). Practical network support for IP traceback. In Proc. ACM SIGCOMM 2000 295–306. Available at www.acm.org/sigcomm/sigcomm2000/conf/paper/ sigcomm2000-8-4.ps.gz.
[91] Schervish, M. J. (1995). Theory of Statistics . Springer, New York. · Zbl 0834.62002
[92] Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakountio, F., Kent, S. T. and Strayer, W. T. (2001). Hash-based IP traceback. In Proc. ACM SIGCOMM 2001 3–14. Available at www.acm.org/sigcomm/sigcomm2001/p1-snoeren.pdf.
[93] Song, D. and Perrig, A. (2001). Advanced and authenticated marking schemes for IP traceback. In Proc. IEEE INFOCOM 2001 2 878–886. IEEE Press, New York. Available at www.ieee-infocom.org/2001/paper/476.ps.
[94] Taylor, C. and Alves-Foss, J. (2001). NATE: Network analysis of anomalous traffic events, a low-cost approach. In Proc. 2001 Workshop on New Security Paradigms 89–96. ACM Press, New York. Available at doi.acm.org/10.1145/508171.508186.
[95] Thompson, S. K. and Seber, G. A. F. (1996). Adaptive Sampling . Wiley, New York. · Zbl 0860.62008
[96] Vardi, Y. (1996). Network tomography: Estimating source–destination traffic intensities from link data. J. Amer. Statist. Assoc. 91 365–377. · Zbl 0871.62103
[97] Vitter, J. S. (1985). Random sampling with a reservoir. ACM Trans. Math. Software 11 37–57. Available at doi.acm.org/10.1145/3147.3165. · Zbl 0562.68028
[98] Waldbusser, S. (2000). Remote network monitoring management information base. RFC 2819. Available at www.ietf.org/rfc/rfc2819.txt.
[99] WinDump—tcpdump for Windows. Available at windump.polito.it/.
[100] Wolff, R. (1982). Poisson arrivals see time averages. Oper. Res. 30 223–231. · Zbl 0489.60096
[101] XACCT Technologies, Inc. Available at www. amdocs.com.
[102] Zhang, Y., Duffield, N. G., Paxson, V. and Shenker, S. (2001). On the constancy of Internet path properties. In Proc. ACM SIGCOMM Workshop on Internet Measurement 197–211. ACM Press, New York. Available at www.cs.utexas.edu/users/yzhang/papers/constancy-imw01.pdf.
[103] Zseby, T. (2002). Deployment of sampling methods for SLA validation with non-intrusive measurements. In Proc. Passive and Active Measurement Workshop . Available at www.labs.agilent.com/hosted/conferences/pam2002/ proceedings/Deployment_of_Sampling_Methods_for_SLA_ Validation.pdf.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.