Reliable data transfer over an UnReliable Channel

Question

I have a data channel which can transfer some data over it, the channel is a wireless system implemented by myself with a low reliability 90% and very low bandwidth due to physical limitation.

In order to overcome this, I'm planning to wrap the whole data channel with a system which should use some data correct method, and send request for resend when when the data is corrupted (corruption will be checked with a checksum).

Whenever one of the wrapper receives a bad data it will send a resend request, and hold place in memory for the unknown data, in a stack.The stack will grow quickly when the reliability drops down, since each side will start send resend request to each other since it had not received the last resend request. Even when the reliability returns to normal, it will try to resend all the resend requests until the stack goes empty.

This will affect the bandwidth since most of the request won't be data, but resend requests.Moreover this system will run on a microcontroller with a very limited RAM, just a few bytes, which may cause a stack overflow in rare cases.

Any suggestions?

Here is a Java model which describes the data channel:

public interface DataChannel {

    abstract void send(String s);
    abstract void setOnDataListener(OnDataListener l);

    interface OnDataListener {
        abstract void onData(String s);
    }

}

Here is an abstract class for a DataChannel which simplifies the implementation later on

public abstract class AbstractReliableChannel implements DataChannel,OnDataListener {

    protected DataChannel mUnReliable;
    private OnDataListener mUnDataListener;

    public AbstractReliableChannel(DataChannel unReliableChannel){
        mUnReliable = unReliableChannel;
    }

    @Override
    public abstract void send(String s);

    @Override
    final public void setOnDataListener(OnDataListener l) {
        mUnDataListener = l;
    }

    /*
     * Should be called by the implimanting class
     */
    final protected void notifiyListenerThatDataReceived(String s){
        mUnDataListener.onData(s);
    }

    /**
     * should be called by the implanting class
     */
    final protected void sendOverUnreliableChannel(String s){
        mUnReliable.send(s);
    }

}

Here is an implementation of an UnReliable Channel

public class UnReliableChannel extends AbstractReliableChannel {

    public ReliableChannel(DataChannel unReliableChannel) {
        super(unReliableChannel);
    }

    @Override
    public void send(String s) {
        if( new Random().nextInt(10) % 5 == 0 )
            s = ModifyStringRandomly(s);

        sendOverUnreliableChannel(s);
    }

    @Override
    public void onData(String s) {
        if( new Random().nextInt(10) % 5 == 0 )
            s = ModifyStringRandomly(s);

        notifiyListenerThatDataReceived(s);
    }

}

Here is a reliable channel implementation which i described erlier

public class ReliableChannel extends AbstractReliableChannel implements Runnable {

    public static String DATA = "D";
    public static String RESEND = "R";
    public static String OK = "O";
    private Thread mThread;

    public ReliableChannel(DataChannel unReliableChannel) {
        super(unReliableChannel);
        mThread = new Thread(this);
        mThread.start();
    }

    private Stack<String> mSend;

    @Override
    public void send(String s) {
        mSend.add(s);
    }

    @Override
    public void onData(String s) {
        if(isDataValid(s)){
            if(s.equals(RESEND)){
                String toResend = mSend.pop();
                mSend.push(toResend);
                mThread.notify();
            } else if (s.equals(OK) ) {
                mSend.pop();
                mThread.notify();
            } else if(s.startsWith(DATA)){
                notifiyListenerThatDataReceived(s.substring(1));
                mSend.push(OK);
            }
        } else {
            mSend.add(RESEND);
            mThread.notify();
        }
    }

    private void sendOverUnreliableChannelWithCheckSum(String s){
        // ADD checkSUM
        sendOverUnreliableChannel(RESEND);
    }

    @Override
    public void run() {
        while(true){
            while(mSend.isEmpty())
                ;
            sendOverUnreliableChannelWithCheckSum(mSend.pop());
            mThread.wait();
        }
    }


    private boolean isDataValid(String s){
        // SHOULD BE SOME CHECKSUM IMPLEMINTATION
        return true;
    }


}

Answer 1

The problem comes from your inefficient protocol design, rather than programming. To get a reliable link in lossy channel, simply use tcp connection or define a protocol similar to tcp. Basically, number each of your data packet at Tx. At Rx, when you receive a bad packet, just throw it away to save memory. You check the integrity of your packets by checking whether all packets have continuous numbers. By maintaining a proper sliding window, you will reach both good effective bandwidth and affordable memory usage.