Brief Announcement: Complexity and Solution of the Send-Receive Correlation Problem

Date Added: Jul 2010
Format: PDF

During the analysis of packet log files from network experiments, the question arises which received packet belongs to which of the potentially many binary identical send events. The authors discuss this send-receive correlation problem for networks with local broadcast media. They can prove that assigning send and receive events is an NP-complete problem. However, there is a solution algorithm that is exponential only in the number of nodes; if the number of network nodes is fixed, its complexity is polynomial.