Delay Minimisation in Network Coding.

Network coding is a promising generalization of routing which provides a mechanism to improve the performance of multicast networks. The core notion of network coding is to allow and encourage mixing of data at intermediate network nodes and enable the final receiver to deduce the original message from the mixed message data packets that it receives. Thanks to the above features; network coding seems an appealing solution in wireless networks that are characterized by limited energy, computational and communication resources. In the case of multicast network coding it is essential to have multipath routing from a source to destinations. The transmitted coded packets will be sent over different paths to the multiple receivers and then will be decoded at the receivers for data extraction once all the coded packets are received. A key component of an efficient network coding based on multipath routing in multicast networks is the delay minimisation that deals with how to minimise the delay of the encoded packets distributed amongst the multiple paths from a source to destinations. This is an important issue as coding is performed over a block of packets and the actual delay is the time needed for the receiver to wait for receiving all the necessary packets within the block for decoding. To address this issue, two broad set of approaches have been proposed in the literature. In the first category, delay reduction is achieved through better coding techniques whereas in the second approach, delay reduction is achieved through better routing and rate control schemes. In this thesis we have investigated delay minimisation in network coding based on multipath routing using an appropriate routing and rate control approach over the network. We have shown that delay minimisation in network coding from one source to several destinations is subset of delay minimisation on the multi path network from one source to one destination. To achieve such delay minimisation two strategies of average delay minimisation and maximum delay minimisation, through an appropriate route selection and traffic allocation were analytically investigated. Using analysis and simulation we have proved that delay synchronisation is the key policy for delay minimisation in network coding. Based on this finding we proposed an adaptive algorithm to achieve delay synchronisation. By applying this algorithm to the network coding scenario in butterfly network we have shown that the proposed end to end delay minimisation solution allows the network to obtain the maximum achievable throughput with finite delay