{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "58fc6db9", "metadata": {}, "outputs": [], "source": [ "import json\n", "import math" ] }, { "cell_type": "code", "execution_count": 2, "id": "e07be4b3", "metadata": {}, "outputs": [], "source": [ "f = open(\"compressed_tree.json\")\n", "tree = json.loads(f.read())\n", "layers = tree[\"layers\"]\n", "classes = tree[\"classes\"]\n", "f.close()" ] }, { "cell_type": "code", "execution_count": 3, "id": "1516ff91", "metadata": {}, "outputs": [], "source": [ "field_width = {\n", "\t\"src\": 16,\n", "\t\"dst\": 16,\n", "\t\"protocl\": 8,\n", "}" ] }, { "cell_type": "markdown", "id": "f9193827", "metadata": {}, "source": [ "# Worst Case RMT" ] }, { "cell_type": "code", "execution_count": 4, "id": "5e37cfc5", "metadata": {}, "outputs": [], "source": [ "def worst_case_rmt(tree):\n", "\trmt = []\n", "\tstep = 0\n", "\n", "\ttcam_bits = 0\n", "\tram_bits = 0\n", "\n", "\tfor layer in layers:\n", "\t\tnum_ranges = len(layers[layer])\n", "\t\t# assume that each range requires all of 2*k prefixes when performing prefix expansion\n", "\t\t# therefore there are 2*k * R for R ranges and width k\n", "\t\tnum_prefixes = 2 * field_width[layer] * num_ranges\n", "\t\tprefix_width = field_width[layer]\n", "\n", "\t\ttcam = {\n", "\t\t\t\"id\": f\"{layer}_range\",\n", "\t\t\t\"step\": step,\n", "\t\t\t\"match\": \"ternary\",\n", "\t\t\t\"entries\": num_prefixes,\n", "\t\t\t\"key_size\": prefix_width\n", "\t\t}\n", "\t\ttcam_bits += num_prefixes * prefix_width\n", "\n", "\t\t# assume basic pointer reuse for metadata storage\n", "\t\tram = {\n", "\t\t\t\"id\": f\"{layer}_meta\",\n", "\t\t\t\"step\": step,\n", "\t\t\t\"match\": \"exact\",\n", "\t\t\t\"method\": \"index\",\n", "\t\t\t\"key_size\": math.ceil(math.log2(num_ranges)),\n", "\t\t\t\"data_size\": len(classes)\n", "\t\t}\n", "\t\tram_bits += num_ranges * len(classes)\n", "\n", "\t\trmt.append(tcam)\n", "\t\trmt.append(ram)\n", "\n", "\t\tstep += 1\n", "\n", "\treturn rmt, tcam_bits, ram_bits\n", "\n", "x, tcam_bits, ram_bits = worst_case_rmt(tree)\n", "f = open(\"worst_case_rmt.json\", \"w+\")\n", "f.write(json.dumps(x, indent=4))\n", "f.close()" ] }, { "cell_type": "code", "execution_count": 5, "id": "0dc1d6d4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "TCAM mapping: \n", "[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n", "SRAM mapping: \n", "[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n", "id mapping: \n", "[['dst_range', 'dst_meta'], ['src_range', 'src_meta'], ['protocl_range', 'protocl_meta'], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]\n", "TCAM bits: 13184\n", "RAM bits: 504\n" ] } ], "source": [ "! command python3 ideal-rmt-simulator/sim.py naive_rmt.json\n", "print(f\"TCAM bits: {tcam_bits}\")\n", "print(f\"RAM bits: {ram_bits}\")" ] }, { "cell_type": "markdown", "id": "2a628655", "metadata": {}, "source": [ "# Naive Range Expansion " ] }, { "cell_type": "code", "execution_count": 6, "id": "fb9febe9", "metadata": {}, "outputs": [], "source": [ "# shamelessly stolen from: https://github.com/autolyticus/range-to-prefix/blob/master/rangetoprefix.C\n", "\n", "def int_to_bin(i, width):\n", "\treturn bin(i)[2:].zfill(width)\n", "\n", "def increment_dc(pfx):\n", "\tidx = pfx.find(\"*\")\n", "\tif idx == -1:\n", "\t\tidx = len(pfx)\n", "\tidx = idx - 1\n", "\t#print(pfx, pfx[:idx])\n", "\treturn pfx[:idx] + \"*\" + pfx[idx+1:]\n", "\t\n", "def can_merge(pfx_a, pfx_b):\n", "\tpfx_a = pfx_a.replace(\"*\", \"\")\n", "\tpfx_b = pfx_b.replace(\"*\", \"\")\n", "\treturn pfx_a[:-1] == pfx_b[:-1] and pfx_a[-1] != pfx_b[-1]\n", "\n", "def merge(pfx_a, prefixes):\n", "\tpfx_a = increment_dc(pfx_a)\n", "\tprefixes[-1] = pfx_a\n", "\n", "\tfor i in range(len(prefixes) - 2, -1, -1):\n", "\t\tif can_merge(prefixes[i], prefixes[i+1]):\n", "\t\t\tprefixes.pop()\n", "\t\t\tpfx = increment_dc(prefixes[i])\n", "\t\t\tprefixes[i] = pfx\n", "\n", "def convert_range(lower, upper, width):\n", "\tprefixes = []\n", "\tprefix = int_to_bin(lower, width)\n", "\tprefixes.append(prefix)\n", "\tnorm_upper = min(upper, 2**width-1)\n", "\tfor i in range(lower+1, norm_upper+1):\n", "\t\tprefix = int_to_bin(i, width)\n", "\t\tif can_merge(prefix, prefixes[-1]):\n", "\t\t\tmerge(prefix, prefixes)\n", "\t\telse:\n", "\t\t\tprefixes.append(prefix)\n", "\treturn prefixes" ] }, { "cell_type": "code", "execution_count": 7, "id": "55167c28", "metadata": {}, "outputs": [], "source": [ "def naive_rmt(tree):\n", "\trmt = []\n", "\tstep = 0\n", "\n", "\ttcam_bits = 0\n", "\tram_bits = 0\n", "\n", "\tfor layer in layers:\n", "\t\tnum_prefixes = 0\n", "\t\tprefix_width = field_width[layer]\n", "\t\t# for each range in the layer, convert the ranges to prefixes using naive range expansion\n", "\t\tfor r in layers[layer]:\n", "\t\t\tif r[\"min\"] == None:\n", "\t\t\t\tr[\"min\"] = 0\n", "\t\t\telif r[\"max\"] == None:\n", "\t\t\t\tr[\"max\"] = 2 ** prefix_width\n", "\t\t\tprefixes = convert_range(r[\"min\"], r[\"max\"], prefix_width)\n", "\t\t\tr[\"prefixes\"] = prefixes\n", "\t\t\tnum_prefixes += len(prefixes)\n", "\t\t\ttcam_bits += len(prefixes) * prefix_width\n", "\n", "\t\ttcam = {\n", "\t\t\t\"id\": f\"{layer}_range\",\n", "\t\t\t\"step\": step,\n", "\t\t\t\"match\": \"ternary\",\n", "\t\t\t\"entries\": num_prefixes,\n", "\t\t\t\"key_size\": prefix_width,\n", "\t\t\t\"ranges\": layers[layer]\n", "\t\t}\n", "\n", "\t\tnum_ranges = len(layers[layer])\n", "\t\t# assume no pointer reuse for metadata storage\n", "\t\tram = {\n", "\t\t\t\"id\": f\"{layer}_meta\",\n", "\t\t\t\"step\": step,\n", "\t\t\t\"match\": \"exact\",\n", "\t\t\t\"method\": \"index\",\n", "\t\t\t\"key_size\": math.ceil(math.log2(num_ranges)),\n", "\t\t\t\"data_size\": len(classes)\n", "\t\t}\n", "\t\tram_bits += num_ranges * len(classes)\n", "\n", "\t\trmt.append(tcam)\n", "\t\trmt.append(ram)\n", "\n", "\t\tstep += 1\n", "\n", "\treturn rmt, tcam_bits, ram_bits\n", "\n", "x, tcam_bits, ram_bits = naive_rmt(tree)\n", "f = open(\"naive_rmt.json\", \"w+\")\n", "f.write(json.dumps(x, indent=4))\n", "f.close()\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "48011528", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "TCAM mapping: \n", "[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n", "SRAM mapping: \n", "[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n", "id mapping: \n", "[['dst_range', 'dst_meta'], ['src_range', 'src_meta'], ['protocl_range', 'protocl_meta'], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]\n", "TCAM bits: 3320\n", "RAM bits: 504\n" ] } ], "source": [ "! command python3 ideal-rmt-simulator/sim.py naive_rmt.json\n", "print(f\"TCAM bits: {tcam_bits}\")\n", "print(f\"RAM bits: {ram_bits}\")" ] }, { "cell_type": "markdown", "id": "2504b1ba", "metadata": {}, "source": [ "# Priority Aware Prefix Expansion" ] }, { "cell_type": "code", "execution_count": 9, "id": "64b7271e", "metadata": {}, "outputs": [], "source": [ "# for this technique, we note that given disjoint ranges [0,a][a,b],[b,c] ...\n", "# then if using a TCAM that selects the first matching prefix, then [0,a],[0,b],[0,c] would be equivalent\n", "# this is because if for some k