lpm

lpm.py

# http://web.mit.edu/devavrat/www/tcam.pdf

import random
import time

class Row(object):
    valid = False
    ip = None
    prefix = None

    def __repr__(self):
        if self.valid:
            return "%2d/%-2d" % (self.ip, self.prefix)
        else:
            return "empty"


class PrefixRange(object):
    def __init__(self, start):
        self.start, self.next = start, start

class LPMHalf(object):
    @staticmethod
    def bucket(prefix):
        if (prefix > 16):
            return prefix - 17
        else:
            return 16 - prefix

    def __init__(self, tcam, top, pol):
        self.tcam, self.top, self.pol = tcam, top, pol

        self.range = [PrefixRange(self.top) for _ in range(16)]

    def push(self):
        idx = self.top
        self.top += self.pol
        return idx

    def pop(self):
        self.top -= self.pol
        
    def insert(self, prefix, ip):
        idx = self.push()
        bkt = self.bucket(prefix)

        for i in range(bkt):
            r = self.range[i]

            if r.next - r.start != 0:
                old = self.tcam[r.start]
                new = self.tcam[idx]

                new.valid, new.ip, new.prefix = old.valid, old.ip, old.prefix
                old.valid = False

            idx = r.start
            r.start += self.pol
            r.next  += self.pol

        free = self.tcam[idx]
        free.valid, free.ip, free.prefix = True, ip, prefix
        self.range[bkt].next += self.pol

    def _delete_first(self, prefix, ip):
        bkt = self.bucket(prefix)
        r = self.range[bkt]

        lastrow = self.tcam[r.next - self.pol]

        for idx in range(r.start, r.next, self.pol):
            row = self.tcam[idx]
            if row.valid and row.prefix == prefix and row.ip == ip:
                if row is lastrow:
                    row.valid = False
                else:
                    row.valid, row.ip, row.prefix = lastrow.valid, lastrow.ip, lastrow.prefix
                    lastrow.valid = False

                r.next -= self.pol
                return r.next

        raise ValueError("Unable to remove unknown route %d/%d" % (ip, prefix))

    def delete(self, prefix, ip):
        bkt = self.bucket(prefix)
        idx = self._delete_first(prefix, ip)

        for i in range(bkt - 1, 0 - 1, -1):
            r = self.range[i]

            if r.next - r.start != 0:
                new = self.tcam[idx]
                old = self.tcam[r.next - self.pol]

                new.valid, new.ip, new.prefix = old.valid, old.ip, old.prefix
                old.valid = False

            idx = r.next - self.pol
            r.start -= self.pol
            r.next  -= self.pol

        self.pop()

class LPM(object):
    def __init__(self, tcam):
        self.tcam = tcam

        self.half = (LPMHalf(tcam, 0, 1),
                     LPMHalf(tcam, len(tcam) - 1, -1))

    def __repr__(self):
        txt = ""

        for i in range(len(self.tcam)):
            txt += repr(self.tcam[i])
            for h in [0, 1]:
                for r in range(16):
                    if self.half[h].range[r].start == i:
                        txt += " [%-2d" % (r + 17 if h==0 else 16 - r)
                    if self.half[h].range[r].next == i:
                        txt += " %2d]" % (r + 17 if h==0 else 16 - r)
            if self.half[0].top == i:
                txt += " TOP"
            if self.half[1].top == i:
                txt += " BTM"
            txt += "\n"

        return txt

    def insert(self, prefix, ip):
        if self.half[0].top > self.half[1].top:
            raise RuntimeError("TCAM Full")

        if prefix > 16:
            self.half[0].insert(prefix, ip)
        else:
            self.half[1].insert(prefix, ip)

    def delete(self, prefix, ip):
        if prefix > 16:
            self.half[0].delete(prefix, ip)
        else:
            self.half[1].delete(prefix, ip)            

tcam = [Row() for _ in range(50)]
lpm  = LPM(tcam)

prefixes = [int(random.random()*32) + 1 for _ in range(len(lpm.tcam))]
random.shuffle(prefixes)

outside = zip(prefixes, [i for i in range(len(lpm.tcam))])
active  = []

while True:
    if int(random.random()*100) > 45:
        if len(active) == len(tcam):
            continue

        r = (int(random.random() * 32) + 1, int(random.random() * 100))
        lpm.insert(r[0], r[1])
        active.append(r)
    else:
        if not active:
            continue

        r, = random.sample(active, 1)
        lpm.delete(r[0], r[1])
        active.remove(r)

    print
    print
    print repr(lpm)
    time.sleep(0.1)