#119 Extreme performance issues with PCAPs with many packets

Lezárt
megnyitva ekkor: 6 éve carlos.garcia által · 1 hozzászólás
Carlos Garcia hozzászólt 6 éve

ID2T is extremely slow calculating statistics when there are many packets in a PCAP. This is due to the following code in statistics.cpp

    // Increment Degrees for sender and receiver, if Sender sends its first packet to this receiver
    std::vector<std::string>::iterator found_receiver = std::find(contacted_ips[ipAddressSender].begin(), contacted_ips[ipAddressSender].end(), ipAddressReceiver);
    if(found_receiver == contacted_ips[ipAddressSender].end()){
        // Receiver is NOT contained in the List of IPs, that the Sender has contacted, therefore this is the first packet in this direction
        ip_statistics[ipAddressSender].out_degree++;
        ip_statistics[ipAddressReceiver].in_degree++;

        // Increment overall_degree only if this is the first packet for the connection (both directions)
        // Therefore check, whether Receiver has contacted Sender before
        std::vector<std::string>::iterator sender_contacted = std::find(contacted_ips[ipAddressReceiver].begin(), contacted_ips[ipAddressReceiver].end(), ipAddressSender);
        if(sender_contacted == contacted_ips[ipAddressReceiver].end()){
            ip_statistics[ipAddressSender].overall_degree++;
            ip_statistics[ipAddressReceiver].overall_degree++;
        }  

        contacted_ips[ipAddressSender].push_back(ipAddressReceiver);
    }

The complexity of that piece of code is O(n^2). The call to std::find is extremely slow.

ID2T is extremely slow calculating statistics when there are many packets in a PCAP. This is due to the following code in `statistics.cpp` ```c++ // Increment Degrees for sender and receiver, if Sender sends its first packet to this receiver std::vector<std::string>::iterator found_receiver = std::find(contacted_ips[ipAddressSender].begin(), contacted_ips[ipAddressSender].end(), ipAddressReceiver); if(found_receiver == contacted_ips[ipAddressSender].end()){ // Receiver is NOT contained in the List of IPs, that the Sender has contacted, therefore this is the first packet in this direction ip_statistics[ipAddressSender].out_degree++; ip_statistics[ipAddressReceiver].in_degree++; // Increment overall_degree only if this is the first packet for the connection (both directions) // Therefore check, whether Receiver has contacted Sender before std::vector<std::string>::iterator sender_contacted = std::find(contacted_ips[ipAddressReceiver].begin(), contacted_ips[ipAddressReceiver].end(), ipAddressSender); if(sender_contacted == contacted_ips[ipAddressReceiver].end()){ ip_statistics[ipAddressSender].overall_degree++; ip_statistics[ipAddressReceiver].overall_degree++; } contacted_ips[ipAddressSender].push_back(ipAddressReceiver); } ``` The complexity of that piece of code is O(n^2). The call to `std::find` is extremely slow.
Jens Keim hozzászólt 6 éve
Közreműködő

Was fixed in pull request #120.

Was fixed in pull request #120.
jens.klein lezárta ekkor: 6 éve
Jelentkezzen be hogy csatlakozhasson a beszélgetéshez.
Nincs mérföldkő
Nincs megbízott
2 Résztvevő
Töltés...
Mégse
Mentés
Még nincs tartalom.