#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 名参与者
正在加载...
取消
保存
这个人很懒,什么都没留下。