Finding the best path in a binary Block Interference network

Abstract

A binary block interference channel (BIC) is model of binary channels with memory that allows for a mathematically tractable computation of channel capacity. One can easily imagine interconnecting such channels into a network that allows point-to-point communication between any two nodes in the network. Given a pair of network nodes, finding the path with the highest capacity is quite trivial if we can assume that all participating nodes in any path connecting the two nodes can perform coding at arbitrary complexity such that at each link capacity is achieved. However, even if the complexity assumption is not taken into account, in most real-life networks (such as the current Internet), only a minimum amount of coding is performed at the link layer. In most networks, coding is performed five or six layers up in the OSI network model, i.e., on either the presentation or the application layer. Under such realistic circumstances, finding the path with the highest capacity is no longer trivial. In this paper, we propose a solution based on a modified version of the Dijkstrapsilas Algorithm.