#119 Extreme performance issues with PCAPs with many packets

已關閉
carlos.garcia6 年之前創建 · 1 條評論

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 評論 6 年之前'
協同者

Was fixed in pull request #120.

Was fixed in pull request #120.
登入 才能加入這對話。
未選擇標籤
Bug
未選擇里程碑
未指派成員
2 參與者
正在加載...
取消
保存
尚未有任何內容