From 87b60bf7e8ad12b3efd3d6f37df0d029f50d2d91 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 19 Dec 1998 11:51:47 +0000
Subject: Added several tools for fib hashing function analysis. It turned out
 we can use very simple function which is monotonic with respect to
 re-hashing:

	n ^= n >> 16;
	n ^= n << 10;
	h = (n >> (16 - o)) & ((1 << o) - 1);

where o is table order. Statistical analysis for both backbone routing
table and local OSPF routing tables gives values near theoretical
optimum for uniform distribution (see ips.c for formulae).

The trick is very simple: We always calculate a 16-bit hash value n and
use o most significant bits (this gives us monotonity wrt. rehashing
if we sort the chains by the value of n). The first shift/xor pair
reduces the IP address to a 16-bit one, the second pair makes higher
bits of the 16-bit value uniformly distributed even for tables containing
lots of long prefixes (typical interior routing case with 24-bit or even
longer prefixes).
---
 misc/cisco2list | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)
 create mode 100755 misc/cisco2list

(limited to 'misc/cisco2list')

diff --git a/misc/cisco2list b/misc/cisco2list
new file mode 100755
index 0000000..6f5466f
--- /dev/null
+++ b/misc/cisco2list
@@ -0,0 +1,20 @@
+#!/usr/bin/perl
+#
+#  Convert Cisco routing table listing to list of prefixes
+#
+
+$loc = ($ARGV[0] eq "-l");	# Print only local prefixes
+
+while (<STDIN>) {
+	($loc ? /^[OR]\s/ : /^B\s/) || next;
+	/^[ORB]( E[12])?\s+(\d+\.\d+\.\d+\.\d+)(\s|\/\d+\s)/ || die "Cannot parse $_";
+	$net = $2;
+	$len = $3;
+	if ($len =~ /^\s*$/) {
+		# Magic rule :)
+		$len = ($net =~ /\.0$/) ? 24 : 32;
+	}
+	$len =~ s/^\///;
+	$net =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/;
+	printf "%02x%02x%02x%02x/%d\n", $1, $2, $3, $4, $len;
+}
-- 
cgit v1.2.3