Online matching of appliction's requests with responses in Linux Kernel
<p>Using Netfilter's hooks I have implemented a Linux kernel module that inspects all the incoming and outgoing packets of a host. Using this module I can monitor the flows of a given application running on that host, i.e., by knowing the src/dst ports/IPs I can filter out (classify) the relevant packets as they being received/sent. </p>

<p>What I want to do next, is to match at run-time, the incoming application's requests with corresponding outgoing responses. Each request/response is identified by the src/dst IP and a unique ID.</p>

<p><strong>The naive implementation</strong> is the flowing: </p>

<ul>
<li>Store each incoming request in a list (array/linked list etc.)</li>
<li>For each outgoing reply:

<ul>
<li>Search through the list to find matching request. If request is found, remove it from the list. </li>
</ul></li>
<li>Periodically prune the list of requests to remove requests that are older than X seconds. </li>
</ul>

<p><strong>The problem</strong> is that for every response, this naive algorithm requires a linear search through the list of requests to identify a match. This is costly at high rates. </p>

<p>Could you suggest an algorithm that can reduce the complexity. It is acceptable to sacrifice precision (loose some of the matches) to maintain performance. </p>

<p>Thanks!</p>