Ishtiyaq - Research

In today's modern world, it is very important to transport information from one place to another place. Information networks are used to transport information and hence finding the capacity of information networks becomes extremely important.

To transport information over the networks, routing or network coding can be used. One of the important unsolved problems in information theory is the conjecture that network coding has no rate benefit over routing in undirected unicast networks. If the conjecture is true, then the undirected unicast network information capacity is the same as the routing capacity.

Introduction

Routing vs network coding in directed acyclic unicast networks

As mentioned earlier, one can use routing or network coding to transport information from a source node s(i) to its respective sink (destination) node t(i).

Routing

In the network shown in the figure, only one path is available to transport information from s(1) to t(1) and is shown by thick red arrows. Similarly, the only path to transport information from s(2) to t(2) is shown by black arrows. Due to the bottleneck edge (the common orange coloured edge in both of these paths), a total of one bit can be delivered at a time.

Network coding

On the other hand, upon using the simple network coding (by doing XOR operations as shown in the figure), a sum-rate of two bits can be delivered in the same network.

This shows a clear advantage of network coding over routing in these types of networks.

A directed acyclic network demonstrates the advantage of network coding over routing. The capacity of every edge in the network is 1.

Is network coding required in undirected unicast networks?

For the network shown in the figure, routing is sufficient to achieve the information capacity of the network. An optimal routing solution is shown in the figure by red and black arrows. This solution achieves the sum-rate of 2 bits which is the information capacity of the network as even a network coding cannot achieve more than this rate in the network.

It is conjectured that network coding has no rate benefit over routing in undirected unicast networks.

An undirected network demonstrates that a routing solution is sufficient to achieve the information capacity of the network. The capacity of every edge in the network is 1.

A challenging conjecture

It is a conjecture that network coding has no rate benefit over routing in undirected unicast networks if fractional routing is allowed in the network.

Some Results

An upper bound for undirected unicast networks

Information capacity of a class of networks called Type-I n-partite networks

In the unicast network shown in the figure, the symmetric information capacity is achievable by a routing solution, the sketch of which is shown by the animated arrows.

In this network, s(i) are source nodes and t(i) are sink (destination) nodes. To achieve the capacity, we send a certain amount of information flow from each source to its respective sink present in a partition set using routing over all of its two-hops paths via the nodes in the other partition set. As we achieve the information capacity using this routing solution, hence network coding is not needed in the network.

This network is an instance of a network class called Type-I n-partite networks. In our work, we gave a routing solution that achieves the symmetric information capacity of the class and hence as a result, we proved a very important and challenging conjecture called multiple-unicast conjecture for symmetric rates for the class.

A bipartite network with 2 partition sets (a partition set is a node-set surrounded by dashed rectangles) and a sketch of a routing solution that achieves the information capacity of the network.

Information capacity of a class of networks called Type-I 3-layered networks

In the unicast network shown in the figure, the symmetric information capacity is achievable by a routing solution, the sketch of which is shown by the animated arrows.

we send a certain amount of flow from each source present in layer-1 to its respective sink using routing over all of its two-hops paths via the nodes in layer-2.
we send a certain amount of flow from each source present in layer-3 to its respective sink using routing over all of its two-hops paths via the nodes in layer-2.
we send a certain amount of flow from each source present in layer-2 to its respective sink using routing over all of its two-hops paths via the nodes in layer-1 and layer-3.

Sending information using routing in this way achieves the information capacity of the network, and hence network coding is not needed in the network.

This network is an instance of a network class called Type-I 3-layer networks. In our work, we gave a routing solution that achieves the symmetric information capacity of the class and hence as a result, we proved the multiple-unicast conjecture for symmetric rates for the class.

A 3-layer network (a layer is a node-set surrounded by dashed rectangles) and a sketch of a routing solution that achieves the information capacity of the network.

Information capacity of a new network, the capacity of which was not known earlier

In a recently published paper, authors proved the conjecture for a class of networks and showed that every network instance and network class for which the conjecture was proved before was an element of this class.

The class of networks was characterized by two conditions (orthogonality and compatibility) based on cut-sets and shortest paths between source-sink pairs in a network. A network belongs to the class if any of these conditions violate for the network.

The network shown in the figure satisfies both the conditions, however, the conjecture holds for the network.

A set of edges F is orthogonal to session i if every shortest path from s(i) to t(i) crosses F at most once, and a set of edges H is called compatible with session i if every shortest path from s(i) to t(i) intersects H the minimum number of times among all the paths from s(i) to t(i).

A network does not belong to the class given by the authors if all possible F are non-orthogonal to some sessions and all possible H are non-compatible with some sessions.

To check condition - 1

For an instance, the F (set of red edges) is non-orthogonal to session 3 as the shortest path shown by thick green arrows crosses the cut-set twice.

Similarly, this can be checked that all possible F are non-orthogonal to some session and hence condition - 1 satisfies for the network.

To check condition - 2

For an instance, the set H of orange edges is non-compatible with session 3 as the shortest path shown by thick blue arrows intersects H twice but the shortest path shown by thick yellow arrows does not intersect H.

Similarly, this can be checked that all possible sets H are non-compatible to some session and hence condition - 2 satisfies for the network.

But as the network is Type-I n-partite network the conjecture holds for the network.

A Type-I 3-partite network. This is a new network for which we proved the multiple-unicast conjecture, and hence obtained symmetric information capacity for the network.

Papers Published/Accepted

Journal Papers

M. I. Qureshi and S. Thakor, “A Bound on Undirected Multiple-Unicast Network Information Flow,” IEEE Transactions on Information Theory, vol. 68, no. 7, pp. 4453-4469, July 2022.
M. I. Qureshi and S. Thakor, “On the Information Capacity of Layered Undirected Unicast Networks,” IEEE Communications Letters, vol. 24, no. 12, pp. 2715-2718, Dec. 2020.

International Conferences

S. Thakor and M. I. Qureshi, “On Computing the Partition Bound for Undirected Multi-Source Unicast Network Information Flow” in National Conference on Communications, 2024. (Accepted)
M. I. Qureshi and S. Thakor, “On the Partition Bound for Undirected Unicast Network Information Capacity,” in IEEE International Symposium on Information Theory, pp. 1623-1628, 2020. arXiv
S. Thakor and M. I. Qureshi, “Undirected Unicast Network Capacity: A Partition Bound,” in IEEE International Symposium on Information Theory, pp. 196-200, 2019. arXiv