--- title: 'Route Tables' source: 'https://academia.sh/en/courses/compute-and-networking-in-the-cloud/route-tables' course: 'Compute and Networking in the Cloud' language: en updated: '2026-09-13T05:07:38+00:00' license: 'CC BY-SA 4.0' objectives: - 'Computes the longest prefix match flow by flow and works out which rule the winning row falls to' - 'Runs three rule widths against the same flow set: counts the flows that reach, the ones swallowed silently, and the ones swallowed at a fee' - "Sweeps a single row's removal and measures the touch count rule duplication produces when a new subnet, new destination, and new zone are added" --- # Route Tables Five route tables are modeled and the winning row for every flow is worked out by longest prefix match: how many flows a widely written rule swallows silently, how many units the same flow costs a narrowly written rule to swallow, how many instances and how many units a single row's drop affects, and how many tables the same rule repeats across. The previous lesson closed with five route tables, and five was just a number. Inside those tables is written where a packet leaving a subnet goes: into the block's own interior, into a peered network, into a private link, or outside. A packet can match more than one row, and which one wins depends on a single rule — the longest prefix. This rule does two things at once. The expected side: traffic bound for the block's own interior is never caught by another row, no matter how widely that row is written. The unexpected side is that writing a row grants no transport ability — the winning row can point to a target, that target may not carry the address, and the packet does not come back. Both sides sit in the same table, often the same row; what tells them apart is not how the row is written but what the target it points to actually carries. - **CN13.** Five tables, six rules, and eight flows belong to the course's fictional regional measurement network. No real network is routed; what is measured is the model built with `node`. The prefix match is computed with real address arithmetic. - **CN14.** All targets are chosen from private address blocks and blocks reserved for documentation. - **CN15.** Writing a table row grants no transport capacity; the range each target actually carries is modeled separately. In reality this separation lives in the connection's own configuration. - **CN16.** The eight flows and their periodic volumes are written by hand; there is no randomness, and every run produces the same numbers. - **CN17.** The egress fee is counted as two fictional units per hundred volume units. It is not a currency; it carries the ratio between the paths. - **CN18.** The four zones' private tables are assumed identical. In reality zones differ from one another; it lowers the duplicate count without changing the touch count. ## The Route Table Model The model keeps two things apart: the row written into the table, and the range the target actually carries. The `CARRIES` dictionary is the second, and the model's main claim lives there. The `result` function first finds the winning row, then checks whether the target that row points to carries the address, and returns one of four outcomes. ```js // route.mjs — route table model and longest prefix match; no real network export const toInt = (ip) => ip.split('.').reduce((a, o) => a * 256 + Number(o), 0); export const block = (c) => { const [ip, e] = c.split('/'); const n = Number(e), b = 2 ** (32 - n); const start = Math.floor(toInt(ip) / b) * b; return { prefix: n, start, end: start + b - 1 }; }; export const contains = (c, ip) => { const b = block(c), a = toInt(ip); return a >= b.start && a <= b.end; }; export const PRIVATE_RANGES = ['10.0.0.0/8', '172.16.0.0/12', '192.168.0.0/16']; export const isPrivate = (ip) => PRIVATE_RANGES.some((c) => contains(c, ip)); // What the target actually carries; writing a row does not grant transport capacity (CN15). null: carries everywhere, billed. export const CARRIES = { 'local': ['10.42.0.0/20'], 'peer-central': ['10.0.0.0/16'], 'peer-backup': ['10.44.0.0/14'], 'peer-legacy': ['10.8.0.0/14'], 'private-link': ['172.20.0.0/14'], 'gateway': null, }; export const longestMatch = (t, ip) => t.filter(([c]) => contains(c, ip)) .sort((a, b) => block(b[0]).prefix - block(a[0]).prefix)[0]; // longest prefix wins export const result = (t, ip) => { const s = longestMatch(t, ip); if (!s) return { row: '-', target: '-', outcome: 'no route', billed: false }; const carries = CARRIES[s[1]]; const outcome = carries === null ? (isPrivate(ip) ? 'gateway-wasted' : 'gateway') : carries.some((c) => contains(c, ip)) ? 'reaches' : 'black hole'; return { row: s[0], target: s[1], outcome, billed: outcome.startsWith('gateway') }; }; const COMMON = [['10.42.0.0/20', 'local'], ['172.20.0.0/14', 'private-link'], ['0.0.0.0/0', 'gateway']]; export const SET = { wide: [...COMMON, ['10.0.0.0/8', 'peer-central']], narrow: [...COMMON, ['10.0.0.0/16', 'peer-central']], full: [...COMMON, ['10.0.0.0/16', 'peer-central'], ['10.44.0.0/14', 'peer-backup'], ['10.8.0.0/14', 'peer-legacy']], }; // [name, destination address, periodic flow volume] — the fictional measurement network's flows (CN16) export const FLOW = [ ['internal reading collector', '10.42.3.14', 4200], ['internal data store', '10.42.9.7', 9100], ['central hall record', '10.0.4.7', 2600], ['old measurement archive', '10.8.3.1', 340], ['shared connection endpoint', '172.20.5.9', 780], ['backup collection', '10.44.2.3', 150], ['external packet store', '198.51.100.9', 60], ['external measurement service', '203.0.113.4', 1900], ]; export const FEE = (h) => Math.round(h * 2) / 100; // 2 fictional units per 100 volume units (CN17) export const ZONES = 4; ``` The three table sets grow from the same skeleton: three common rows plus one form of the peering rule on top. The `wide` set tries to cover the entire internal address space with a single row, the `narrow` set writes only the range that is actually peered, and the `full` set adds the two targets the others leave out. Of the flow list's eight rows, two go into the block's interior, three go to the organization's other blocks, one goes to the shared connection, and two go outside; the volumes are periodic, and they are what determines the fee. ## Winning Row ```js // run1.mjs — the winning row is worked out for every flow, then three table sets are compared import { SET, FLOW, FEE, result, contains } from './route.mjs'; console.log(`wide set (${SET.wide.length} rows), winning row flow by flow:`); console.log(`${'flow'.padEnd(30)} ${'target address'.padEnd(17)} ${'matches'.padStart(7)} ` + `${'winning row'.padEnd(14)} ${'next hop'.padEnd(14)} outcome`); for (const [name, ip] of FLOW) { const matches = SET.wide.filter(([c]) => contains(c, ip)).length, r = result(SET.wide, ip); console.log(`${name.padEnd(30)} ${ip.padEnd(17)} ${String(matches).padStart(7)} ` + `${r.row.padEnd(14)} ${r.target.padEnd(14)} ${r.outcome}`); } console.log(`\n${'set'.padEnd(7)} ${'rows'.padStart(6)} ${'reaches'.padStart(8)} ${'black hole'.padStart(11)} ` + `${'gateway-wasted'.padStart(15)} ${'billed volume'.padStart(14)} ${'egress fee'.padStart(13)}`); for (const [name, t] of Object.entries(SET)) { const r = FLOW.map(([, ip, h]) => ({ ...result(t, ip), h })); const n = (s) => r.filter((x) => x.outcome === s).length; const volume = r.filter((x) => x.billed).reduce((a, x) => a + x.h, 0); console.log(`${name.padEnd(7)} ${String(t.length).padStart(6)} ${String(n('reaches')).padStart(8)} ` + `${String(n('black hole')).padStart(11)} ${String(n('gateway-wasted')).padStart(15)} ` + `${String(volume).padStart(14)} ${String(FEE(volume)).padStart(13)}`); } ``` ``` wide set (4 rows), winning row flow by flow: flow target address matches winning row next hop outcome internal reading collector 10.42.3.14 3 10.42.0.0/20 local reaches internal data store 10.42.9.7 3 10.42.0.0/20 local reaches central hall record 10.0.4.7 2 10.0.0.0/8 peer-central reaches old measurement archive 10.8.3.1 2 10.0.0.0/8 peer-central black hole shared connection endpoint 172.20.5.9 2 172.20.0.0/14 private-link reaches backup collection 10.44.2.3 2 10.0.0.0/8 peer-central black hole external packet store 198.51.100.9 1 0.0.0.0/0 gateway gateway external measurement service 203.0.113.4 1 0.0.0.0/0 gateway gateway set rows reaches black hole gateway-wasted billed volume egress fee wide 4 4 2 0 1960 39.2 narrow 4 4 0 2 2450 49 full 6 6 0 0 1960 39.2 ``` The first two rows are the rule's expected side: traffic bound for the block's interior matches three rows at once, and `/20` wins. Whoever wrote the `10.0.0.0/8` row knew it would not break this, and they were right. The fourth and sixth rows are the same rule's other side. `10.8.3.1` and `10.44.2.3` also match the `/8` row, that row wins, and the packet goes to the peering connection — but that connection only carries the `10.0.0.0/16` range. The winning row is written correctly; the target it points to does not carry the address. The packet leaves, does not come back, produces no fee, and leaves no trace on the bill. The matches column makes the rule's mechanics visible: six of the eight flows match two or three rows at once, and only two match a single row. Nowhere in the table is it written which row wins; the winner is decided on the spot, once the prefix lengths are sorted. The consequence is this: adding a new row can change a flow's path without changing any existing row. The bottom three rows are the real comparison. In the wide set, two flows disappear silently. Narrowing the rule — writing `/16` instead of `/8` — zeroes out the black hole, but it does not fix the flows, it only drops them onto the default path. Both leave through the egress gateway, try to reach a private address, still do not arrive, and this time cost 9.8 extra units a period: 49 units, against the wide set's 39.2. The narrow set's difference looks like a loss, and it is not. A silent failure turned into a billed failure; a billed failure has a row somewhere. The correct answer is the third row: adding two rows makes a six-row set, all eight of the eight flows reach, and the egress fee drops back to the wide set's fee. Narrowing the rule did not fix it; writing the two missing targets did. ## Missing Row and Duplication ```js // run2.mjs — five tables' duplication, then a single row is dropped from the zone-3 table import { SET, FLOW, FEE, ZONES, result } from './route.mjs'; const PUBLIC = [['10.42.0.0/20', 'local'], ['0.0.0.0/0', 'gateway']]; const TABLES = [['public', PUBLIC], ...Array.from({ length: ZONES }, (_, i) => [`private-zone-${i + 1}`, SET.full])]; const rowCount = TABLES.reduce((a, [, t]) => a + t.length, 0); const unique = new Set(TABLES.flatMap(([, t]) => t.map((r) => r.join(' ')))); const tableCount = (r) => TABLES.filter(([, t]) => t.some((x) => x.join(' ') === r.join(' '))).length; const INSTANCES_PER_ZONE = 141; // private instances per zone (from the previous lesson's distribution) const baseline = FLOW.map(([, ip, h]) => ({ ...result(SET.full, ip), h })); const baselineVolume = baseline.filter((x) => x.billed).reduce((a, x) => a + x.h, 0); console.log(`${TABLES.length} tables, ${rowCount} rows, ${unique.size} unique rules, ${rowCount - unique.size} duplicates`); console.log(`\nif a single row is dropped from the zone-3 table (${INSTANCES_PER_ZONE} instances affected):`); console.log(`${'dropped row'.padEnd(15)} ${'next hop'.padEnd(14)} ${'tables'.padStart(8)} ${'broken'.padStart(8)} ` + `${'new outcome'.padEnd(12)} ${'fee delta'.padStart(12)}`); for (const r of SET.full) { const without = SET.full.filter((x) => x !== r); const after = FLOW.map(([, ip, h]) => ({ ...result(without, ip), h })); const broken = after.filter((x, i) => x.outcome !== baseline[i].outcome); const volume = after.filter((x) => x.billed).reduce((a, x) => a + x.h, 0); const delta = FEE(volume) - FEE(baselineVolume); console.log(`${r[0].padEnd(15)} ${r[1].padEnd(14)} ${String(tableCount(r)).padStart(8)} ` + `${String(broken.length).padStart(8)} ${[...new Set(broken.map((x) => x.outcome))].join(',').padEnd(12)} ` + `${String(delta > 0 ? `+${delta.toFixed(1)}` : delta.toFixed(1)).padStart(12)}`); } console.log(`\nperiodic egress fee (full set): ${FEE(baselineVolume)} units`); console.log(`table touched when a new subnet is added: 1 (association)`); console.log(`tables touched when a new destination network is added: ${ZONES} (${ZONES} rows, the same row ${ZONES} times)`); console.log(`when a new zone is added: 1 new table, ${SET.full.length} rows, 1 gateway`); ``` ``` 5 tables, 26 rows, 6 unique rules, 20 duplicates if a single row is dropped from the zone-3 table (141 instances affected): dropped row next hop tables broken new outcome fee delta 10.42.0.0/20 local 5 2 gateway-wasted +266.0 172.20.0.0/14 private-link 4 1 gateway-wasted +15.6 0.0.0.0/0 gateway 5 2 no route -39.2 10.0.0.0/16 peer-central 4 1 gateway-wasted +52.0 10.44.0.0/14 peer-backup 4 1 gateway-wasted +3.0 10.8.0.0/14 peer-legacy 4 1 gateway-wasted +6.8 periodic egress fee (full set): 39.2 units table touched when a new subnet is added: 1 (association) tables touched when a new destination network is added: 4 (4 rows, the same row 4 times) when a new zone is added: 1 new table, 6 rows, 1 gateway ``` The row that looks most ordinary is the most expensive. If the local route drops, in-block traffic slides onto the default path, leaves through the gateway, and adds 266.0 units a period — roughly seven times the full set's entire egress fee. Traffic between the reading collector and the data store both stops and gets billed. The default route dropping works the other way: the fee falls by 39.2 units and two external flows are left without a route. Access is cut while the bill drops. The third column says why this goes unnoticed. Every row is written into four or five tables, and the drop was made from only one zone's table: 141 instances are affected, and the 475 instances in the other three zones are not. Three-quarters of the same request works and one-quarter does not. This is the hardest failure shape a single broken row produces — intermittent, passes on retry, and blamed on the network itself rather than the route table. A single row dropping looks like a remote possibility on paper, yet the sweep models real work. Four identical tables are not written by one hand; one gets fixed by hand, one gets regenerated from a template, one gets temporarily changed during an incident and never restored. There is a reason to add a row; there is no reason to verify the row exists in all four of the four tables — because nothing looks broken. The last three lines give duplication's bill. Only six of the twenty-six rows are unique; twenty are copies. Adding a new subnet costs a single touch, because the subnet is associated with an existing table. Adding a new destination network costs four touches and four identical rows. Writing three of the four and skipping one lands exactly on the state the sweep above produced. The irreversible item here is not the row itself. A route row is written, deleted, fixed — this is the easiest item to reverse in the entire course. What cannot be reversed is what happens during the period the row is wrong: the 490 volume units of measurement swallowed silently cannot be collected again, and the 266.0 units already paid does not come back. Three items stay with the team — rule width, table count, and which subnet is associated with which table. Two items are handed off: the longest prefix match rule itself, and the local route being written into every table automatically. Both are closed to debate, and they produce half the numbers above. ## Summary - Longest prefix match protects in-block traffic: `10.42.3.14` matches three rows, and `/20` wins. The same rule works in the opposite direction too — the `10.0.0.0/8` row also wins the `10.8.3.1` and `10.44.2.3` flows, and since the peering connection only carries `10.0.0.0/16`, both fall into a black hole. - Writing the rule as `/16` instead of `/8` drops the black hole count from 2 to 0 but does not fix the flows: the same two flows dropped onto the default path leave and still do not arrive, and the periodic fee rises from 39.2 units to 49 units. What fixes it is not narrowing but writing the two missing targets; the 6-row set delivers all eight of the eight flows and brings the fee back to 39.2 units. - A single row dropping does not cost equally: the local route costs +266.0 units, the peering rows between +3.0 and +52.0 units, and the default route −39.2 units with two flows left routeless. The change that lowers the fee is the same change that cuts off access. - 5 tables hold 26 rows, only 6 of them unique, 20 duplicates. Every rule is written into 4 or 5 tables; a row dropped from one zone's table affects 141 instances and leaves 475 untouched, and the failure looks intermittent. - A new subnet costs 1 touch, a new destination network costs 4 touches and 4 identical rows, a new zone costs 1 table plus 6 rows plus 1 gateway. The irreversible item is not the row, but the 490 volume units of measurement swallowed and the 266 units paid during the period the row was wrong. ## Next Step In the last two runs, the gateway appeared as both the fix and the bill: every flow leaving went out through it, every flow dropped onto the wrong path fell there, and every new zone asked for one more. The gateway itself was never measured. The next lesson's question counts a private subnet's instances' relationship with the outside in three arrangements: what setting up no gateway at all blocks, and by name; how many instances' traffic a single translation gateway routes through one point, and which bottleneck and which failure point that creates; how splitting the gateway per zone divides that up and what it raises the cost to — and how far giving every instance a public address raises the externally reachable surface, in item count.