GBN and Selective Repeat ARQs simulations.

arqs.py

import random
from collections import deque

class GBNSender:
    def __init__(self):
        self.to_send_idx = 0
        self.transmitted = 0

    def get_msg(self):
        msg = {'idx': self.to_send_idx}
        self.to_send_idx += 1
        return msg

    def put_msg(self, msg):
        if msg['is_broken']:
            # TODO: start resending packets.
            self.to_send_idx = msg['idx']
        else:
            self.transmitted = msg['idx']

class GBNReceiver:
    def __init__(self): pass
    def put_msg(self, msg): pass

class Channel:
    def __init__(self, perror, delay, sender, receiver):
        self.perror = perror
        self.sender = sender
        self.receiver = receiver
        self.delay = delay

        self.loopback_queue = deque([])
        self.time = 0

    def tick(self, t):
        lbq = self.loopback_queue

        if len(lbq) != 0:
            rsp = lbq.popleft() # destructive pop
            if rsp['recv'] <= self.time: # time to ACK
                self.sender.put_msg(rsp)
            else: lbq.appendleft(rsp) # put message back

        msg = self.sender.get_msg()
        msg['sent'] = self.time
        msg['recv'] = self.time + self.delay
        msg['is_broken'] = random.random() < self.perror

        self.receiver.put_msg(msg)
        lbq.append(msg)
        # print t, msg, rsp

        self.time += 1

class SRSender:
    def __init__(self):
        self.to_send_idx = 0
        self.transmitted = 0
        self.render_new_msg = True # False if shifted.
        self.buf = deque([])

    def get_msg(self):
        if self.render_new_msg:
            msg = {'idx': self.to_send_idx}
            self.buf.appendleft(msg)
            self.to_send_idx += 1
        else:
            msg = self.buf[0]
        return msg

    # XXX: This sender is suboptimal!
    # ... but it works for all receiver buffer sizes
    def put_msg(self, msg): # response
        bmsg = self.buf.pop()
        assert msg == bmsg

        if msg['is_broken'] or msg['overflowed']:
            self.buf.appendleft(msg) # schedule retransmission
            self.render_new_msg = False
        else:
            self.transmitted += 1
            self.render_new_msg = True

class SRSenderOptimal1BS:
    def __init__(self):
        self.transmitted = 0
        self.buf = deque([])

        self.state = 'EMPTY'
        self.oldest_to_receive = 0
        self.newest_to_generate = 0
        self.render_new_msg = True # False if shifted.

        self.need_retransmit = False

    def get_msg(self):
        if self.render_new_msg:
            msg = {'idx': self.newest_to_generate}
            self.buf.appendleft(msg)
            self.newest_to_generate += 1
        else:
            msg = self.buf[0]
        return msg

    def put_msg(self, msg): # response
        bmsg = self.buf.pop()
        assert msg == bmsg
        #fr = self.state

        if self.state == 'EMPTY':
            if self.oldest_to_receive != msg['idx']:
                self.schedule_retransmission(msg)
            else:
                if msg['is_broken']:
                    self.schedule_retransmission(msg)
                    self.state = 'TOBUFFER'
                else:
                    assert self.oldest_to_receive == msg['idx']
                    self.transmitted += 1
                    self.oldest_to_receive += 1
                    self.render_new_msg = True

        elif self.state == 'TOBUFFER':
            if msg['is_broken']: # NO BUFFERING FOR U ;)
                self.schedule_retransmission(msg)
                self.state = 'EMPTY' # will loop there
            else:
                self.newest_to_generate = msg['idx'] + 1
                self.render_new_msg = True
                self.state = 'BUFFERED'

        elif self.state == 'BUFFERED':
            if msg['idx'] != self.oldest_to_receive:
                if self.need_retransmit:
                    self.schedule_retransmission(msg)
                else:
                    self.render_new_msg = True
            else:
                if msg['is_broken']:
                    self.need_retransmit = True
                    self.schedule_retransmission(msg)
                else:
                    self.transmitted += 2
                    self.oldest_to_receive += 2
                    self.need_retransmit = False
                    self.render_new_msg = True
                    self.state = 'EMPTY'
        # print fr, '->', self.state, msg, [x['idx'] for x in self.buf], self.render_new_msg, self.newest_to_generate

    def schedule_retransmission(self, msg):
        self.buf.appendleft(msg)
        self.render_new_msg = False

class SRReceiver:
    def __init__(self, bufsize):
        self.oldest_to_receive = 0 # has min index
        self.bufsize = bufsize
        self.buf = bufsize * [None]

    def put_msg(self, msg):
        idx = msg['idx']
        otr = self.oldest_to_receive
        bs = self.bufsize

        msg['overflowed'] = False
        msg['buffered'] = False

        if idx == otr:
            if not msg['is_broken']:
                self.oldest_to_receive += 1
                self.clear_buffer()

        elif idx > otr + bs: # Buffer overflow
            msg['overflowed'] = True

        elif idx < otr:
            print idx, otr, self.buf
            raise Exception('IMPOSSIBLE')

        else: # fill in the hole
            if not msg['is_broken']:
                msg['buffered'] = True
                k = idx - otr - 1
                self.buf[k] = msg
        # print msg, otr, self.buf

    def clear_buffer(self):
        while(True):
            if self.buf[0] != None:
                self.oldest_to_receive += 1
                self.buf.pop(0)
                self.buf.append(None)
            else:
                self.buf.pop(0)
                self.buf.append(None)
                break

def main(senderf, receiverf, delay):
    total_slots = 100000
    step = 0.01
    perror = 0.0
    while perror < 1.0:
        sender = senderf() # need to get new instance for every 'perror'
        receiver = receiverf()
        channel = Channel(perror, delay, sender, receiver)
        for t in xrange(0, total_slots):
            channel.tick(t) # t is passed for debugging purposes

        print perror, sender.transmitted * 1.0 / total_slots
        perror += step

def main_gbn():     main(lambda: GBNSender(), lambda: GBNReceiver(), 5)
def main_sr_opt():  main(lambda: SRSenderOptimal1BS(), lambda: SRReceiver(1), 5)
def main_sr_cool(): main(lambda: SRSender(), lambda: SRReceiver(20), 5)

if __name__ == '__main__': main_sr_cool()