On the Fly Network Coding: A Protocol Simulation

decoder.py

#!/usr/bin/python3

from typing import List, Tuple
from prime_ring import PrimeRing
from galois import GF


class Decoder:
    def __init__(self, target_rank: int) -> None:
        self._target_rank = target_rank
        self._pieces = []
        self._pr = PrimeRing(256)
        self._gf = GF(2**8)

    def _decodable_coding_vector(self, pos: int) -> List[int]:
        vec = [1]*self._target_rank
        self._pr.set(pos)
        vec[pos] = self._pr.cur()
        return vec

    def _rich_coding_vector(self, pos: int) -> List[int]:
        vec = [1]*self._target_rank
        self._pr.set(pos)
        for i in range(pos, pos+self._target_rank):
            idx = i % self._target_rank
            if idx == pos:
                vec[idx] = self._pr.cur()
            else:
                vec[idx] = self._pr.next()
        return vec

    def add(self, piece: Tuple[int, int, int]):
        if piece[0] == None:
            self._pieces.append([*[1]*self._target_rank, piece[1]])
            return

        self._pieces.append(
            [*self._decodable_coding_vector(piece[0]), piece[1]])

        if piece[2] != None:
            self._pieces.append(
                [*self._rich_coding_vector(piece[0]), piece[2]])

        _pieces = self._gf(self._pieces)
        _pieces = _pieces.row_reduce()
        self._pieces = _pieces.tolist()

    def decoded(self) -> List[int]:
        def decoded_row(row_idx: int, row: List[int]) -> bool:
            if row_idx >= self._target_rank:
                return False

            return all([row[i] == 1 if i == row_idx else row[i] ==
                        0 for i in range(self._target_rank)])

        if len(self._pieces) == 0:
            return None

        _pieces = [None]*self._target_rank
        for i, j in enumerate(self._pieces):
            if decoded_row(i, j):
                _pieces[i] = j[-1]

        return _pieces


if __name__ == '__main__':
    pass

on_the_fly.py

#!/usr/bin/python3

from peer import Peer
from decoder import Decoder
from random import seed, random
from time import time
from rich.live import Live
from rich.table import Table
from rich import box


def get_from_peer() -> bool:
    n = int(random()*10**6)
    return n % 2 == 0


def main():
    seed(time())
    data = [97, 110, 106, 97, 110]
    peer_1 = Peer(data)
    peer_2 = Peer(data)
    dec = Decoder(len(data))

    session_1 = peer_1.begin(0, 2, True)
    session_2 = peer_2.begin(1, 2, False)

    itr_1 = session_1.get()
    itr_2 = session_2.get()

    tab = Table(title='On the fly Decoding', box=box.MINIMAL)
    tab.add_column('From Peer', style='yellow')
    tab.add_column('Received Piece No.', style='cyan')
    tab.add_column('Received Piece', style='magenta')
    tab.add_column('Decoded Pieces', style='green')

    itered = {0: 0, 1: 0}
    piece_count = 0
    with Live(tab, refresh_per_second=5):
        while not (itered[0] == 1 and itered[1] == 1):
            if get_from_peer():
                try:
                    piece = next(itr_1)
                    piece_count += 1
                    dec.add(piece)
                    tab.add_row('Peer 1', f'{piece_count}', f'{piece}',
                                f'{dec.decoded()}')
                except Exception:
                    itered[0] = 1

            if get_from_peer():
                try:
                    piece = next(itr_2)
                    piece_count += 1
                    dec.add(piece)
                    tab.add_row('Peer 2', f'{piece_count}', f'{piece}',
                                f'{dec.decoded()}')
                except Exception:
                    itered[1] = 1


if __name__ == '__main__':
    main()

peer.py

#!/usr/bin/python3

from functools import reduce
from typing import List, Tuple
from galois import GF
from prime_ring import PrimeRing


class Session:
    def __init__(self, gf: GF, data: List[int], idx: int, skip: int, include_base: bool) -> None:
        self._gf = gf
        self._data = data
        self._idx = idx
        self._count = len(self._data)
        self._skip = skip
        self._include_base = include_base
        self._pr = PrimeRing(256)

    def _encode_base(self) -> int:
        return reduce(lambda acc, cur: acc+cur, self._data, self._gf(0)).tolist()

    def _encode_at(self, idx: int) -> int:
        return reduce(lambda acc, cur: acc + cur,
                      [i[1]*self._gf(self._pr.cur()) if i[0] == idx else i[1] for i in enumerate(self._data)], self._gf(0)).tolist()

    def _encode_with_rich(self, idx: int) -> Tuple[int, int]:
        decodable = reduce(lambda acc, cur: acc + cur,
                           [i[1]*self._gf(self._pr.cur()) if i[0] == idx else i[1] for i in enumerate(self._data)], self._gf(0))

        rich = reduce(lambda acc, cur: acc+cur,
                      [self._gf(self._pr.cur())*self._data[i] if i == idx else self._gf(self._pr.next())
                       * self._data[i] for i in [i % self._count for i in range(idx, idx+self._count)]], self._gf(0))

        return decodable.tolist(), rich.tolist()

    def get(self) -> Tuple[int, int, int]:
        cur = None
        with_rich = False

        while True:
            if cur == None:
                cur = self._idx
                if self._include_base:
                    yield (None, self._encode_base(), None)

            if cur >= self._count:
                break

            self._pr.set(cur)
            _cur = cur
            cur += self._skip

            if not with_rich:
                with_rich = True
                yield (_cur, self._encode_at(_cur), None)
            else:
                with_rich = False
                yield (_cur, *self._encode_with_rich(_cur))


class Peer:
    def __init__(self, data: List[int]) -> None:
        self._gf = GF(2**8)
        self._data = [self._gf(i) for i in data]

    def begin(self, idx: int, skip: int, include_base: bool) -> Session:
        return Session(self._gf, self._data, idx, skip, include_base)


if __name__ == '__main__':
    pass

prime_ring.py

#!/usr/bin/python3

from typing import List


class PrimeRing:
    def __init__(self, under: int) -> None:
        self._all = self._prime_list(under)
        self._count = len(self._all)
        self._cur = None

    def _is_prime(self, num: int) -> bool:
        for i in range(2, num):
            if num % i == 0:
                return False

        return True

    def _prime_list(self, under: int) -> List[int]:
        buf = []
        for i in range(2, under):
            if self._is_prime(i):
                buf.append(i)

        return buf

    def set(self, idx: int):
        if idx > self._count:
            raise Exception("index > prime count")
        self._cur = idx

    def next(self) -> int:
        if self._cur == None:
            self._cur = 0
        else:
            self._cur = (self._cur+1) % self._count

        return self._all[self._cur]

    def cur(self) -> int:
        return self._all[self._cur]

    def prev(self) -> int:
        if self._cur == None:
            self._cur = 0
        else:
            self._cur = (self._cur-1) % self._count

        return self._all[self._cur]


if __name__ == '__main__':
    pass

requirements.txt

numpy==1.16.6
galois==0.0.17
rich==10.6.0

Motivation

You should start by reading this, if you've not already done so. It's a primary design of p2p data syncing protocol, which is demonstrated in this simulator. It makes use of modified version of Network Coding with generational coding features, while allowing progressive decoding.

Usage

• Enable virtual environment

python3 -m venv venv
source venv/bin/activate

• Install dependencies

python3 -m pip install -r requirements.txt

• Run simulation

Each run may produce different result in console

python3 on_the_fly.py

• Deactivate virtual environment

deactivate

• Output may look like