Mapping IXP access links

IXPs (Internet Exchange Points) are facilities where ISPs (Internet Service Providers) meet and can set up interconnection (peering) and exchange traffic between their mutual customers directly.

There was an interesting paper at IMC'09 called "IXPs: Mapped?", which fused data from various sources to get a more complete picture of peering at IXPs.

Here is one phenomenon that I think would be worth further research:

In the original model, the IXPs is at a colocation facility, where ISPs put their equipment (routers) and connect a router port to the exchange point switch via in-house cabling. But there's another option, where the ISP doesn't put a router up at the physical IXP facility, but instead connects an existing backbone router to the IXP by means of a leased line - could be a leased wavelength, or an Ethernet-over-{MPLS,SDH} service. Looking around me, I see this happening very frequently, e.g. quite a few medium-size Swiss ISPs lease bandwidth to Amsterdam, Frankfurt or London to connect to the large IXPs there (AMS-IX, DECIX, and LINX, respectively).

It is important to understand such non-local peering, because the impact of the access links can be quite large in terms of speed-of-light delay, and some transport media - e.g. Ethernet over MPLS - might be subject to unnoticed congestion. Also, long access links might be more difficult to upgrade in a timely manner when needed.

As an illustration, here's a traceroute between the ISP I work for (SWITCH, AS559) and an ISP in Gibraltar.

$ traceroute www.broadband.gi
traceroute to www.broadband.gi (85.115.130.100), 64 hops max, 52 byte packets
1  swiws1-v4 (130.59.4.2)  2.652 ms  0.271 ms  0.259 ms
2  swics5-10ge-1-4 (130.59.15.181)  0.334 ms  0.308 ms  0.317 ms
3  swics3-10ge-1-3 (130.59.15.189)  0.412 ms  0.336 ms  0.340 ms
4  swiez2-10ge-5-2 (130.59.36.18)  0.358 ms  0.347 ms  0.356 ms
5  swils2-10ge-1-1 (130.59.36.205)  4.001 ms  3.916 ms  3.983 ms
6  swiel2-10ge-1-2 (130.59.36.70)  4.081 ms  4.036 ms  4.069 ms
7  swice3-10ge-1-3 (130.59.37.65)  4.826 ms  4.843 ms  4.879 ms
8  ge-0-1-8-1.madrid.sapphire.gi (195.69.144.163)  58.489 ms  58.552 ms  58.530 ms
9  ge0-1-0-0.jcore2.gibraltar.sapphire.gi (85.115.128.63)  75.874 ms
ge0-0-5-0.jcore2.gibraltar.sapphire.gi (85.115.128.49)  78.614 ms  78.640 ms
10  85.115.128.18 (85.115.128.18)  76.205 ms  76.101 ms  76.203 ms
11  *  C-c C-c

Can you guess in which city we interconnect?

Google Code Jam 2009 - solutions in Common Lisp

Last year I had a lot of fun with the small puzzles of Google Treasure Hunt.  This year, there was no treasure hunt, so I decided to participate in Google Code Jam.  Code Jam seems to be quite a bit more competitive, with multiple rounds where only the top N scorers pass.  So far, I have passed the qualification round and the first online round.  I will almost certainly fail to pass the next round, because there will be only 250 participants to advance (and receive a T-shirt).  My natural rank seems to be in the high triple digits or low quadruple digits.  But maybe there will be a miracle!

Someone wrote a kind of mashup that walks the Google Code Jam submission/score database, and which allows queries e.g. per programming language.  Here's the statistics for Lisp:
http://www.go-hero.net/jam/09/lang/Lisp

I registered as "insertsomethingwitty" (I have never been good with pseudonyms), and you can find my submissions here: http://www.go-hero.net/jam/09/name/insertsomethingwitty

Bribe the Prisoners

In the two rounds I participated in ("Qualifier" and 1C), I managed to submit correct solutions for all problem sets except for the very last one, namely the "large input" for "Bribe the prisoners".  I took a bad approach to that one, and was lucky to even finish the small input set before the end of the round (2h30 for three problems).

After a nice walk, I found a simpler approach.  I had to apply memoization to make it efficient, and then I was able to run the large input set in about two minutes on my netbook - the limit is eight minutes.  Here is the new code.

(defun solve (file &optional (dest t))
  (with-open-file (s file)
    (let ((nsamples (parse-integer (read-line s))))
      (dotimes (k nsamples)
 (solve-case k s dest)))))

(defvar *memo* (make-hash-table :test #'equal))

(defun solve-case (caseno s dest)
  (clrhash *memo*)
  (let ((line (mapcar #'parse-integer (split-at-spaces (read-line s)))))
    (multiple-value-bind (p q)
 (values (first line) (second line))
      (let ((rel (mapcar #'parse-integer (split-at-spaces (read-line s)))))
 (assert (= (length rel) q))
 (format dest "Case #~D: ~D~%" (1+ caseno) (minbribe p rel))))))

(defun minbribe (p rel &aux entry)
  (cond ((endp rel) 0)
 ((endp (rest rel)) (1- p))
 ((setq entry (gethash (cons p rel) *memo*)) entry)
 (t (setf (gethash (cons p rel) *memo*)
      (reduce #'min (mapcar
       #'(lambda (prisoner)
    (minbribe-1 prisoner p rel))
       rel))))))

(defun minbribe-1 (prisoner p rel)
  (cond ((<= p 1) 0)
 (t (+ (- p 1)
       (multiple-value-bind (p1 rel1 p2 rel2)
    (split-cells prisoner p rel)
  (+ (minbribe p1 rel1)
     (minbribe p2 rel2)))))))

(defun split-cells (prisoner p rel)
  (do ((rel rel (rest rel))
       (seq1 '() (cons (first rel) seq1)))
      ((= (first rel) prisoner)
       (do ((rel (rest rel) (rest rel))
     (seq2 '() (cons (- (first rel) prisoner) seq2)))
    ((endp rel)
     (values (1- prisoner) (nreverse seq1) (- p prisoner) (nreverse seq2)))))))

Google Treasure Hunt 2008: Puzzle 4 (primes) solution

This is another one that lends itself to a nice solution in Common Lisp. It helps not to be too worried about efficiency in the beginning - "early optimization is the root of all evil". So I don't use Erastosthenes' sieve to enumerate primes, I just iterate over natural numbers (2, 3, k+2) and check for primality using a trivial PRIMEP. For each cardinality (number of consecutive primes that should be summed up), I maintain a vector of exactly that size, to be used as a ring buffer. Each time I get a complete sum-of-primes which is itself a prime, I note that this sum-prime can be represented as a consecutive-primes-sum of the given cardinality. When a number has as many entries as we have cardinalities, we have won.

;;; Question:
;;;
;;; Find the smallest number that can be expressed as
;;; the sum of 23 consecutive prime numbers,
;;; the sum of 33 consecutive prime numbers,
;;; the sum of 403 consecutive prime numbers,
;;; the sum of 1163 consecutive prime numbers,
;;; and is itself a prime number.
;;;
;;; For example, 41 is the smallest prime number that can be expressed as
;;; the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
;;; the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
;;;
;;; Your answer: ____________
;;;
(in-package :noc)

(defun primep (n)
 (let ((sq (truncate (sqrt n))))
   (do ((k 2 (1+ k)))
((> k sq) t)
     (when (zerop (rem n k))
(return nil)))))

(defun map-primes (fun)
 (map-primes-1 fun 2))

(defun map-primes-1 (fun k)
 (when (primep k)
   (funcall fun k))
 (map-primes-1 fun (if (= k 2) 3 (+ k 2))))

(defun make-vector-adder (size sum-fun)
 (let ((vec (make-array (list size)))
(count 0)
(fullp nil)
(sum 0))
   (let ((fun #'(lambda (k)
    (when fullp
      (decf sum (aref vec count)))
    (setf (aref vec count) k)
    (incf sum k)
    (incf count)
    (when (= count size)
      (setq count 0)
      (setq fullp t))
    (when (and fullp (primep sum))
      #+VERIFY
      (when (= sum 5457701)
        (format t "Sum of ~D consecutive primes:~%  " size)
        (dotimes (k size)
   (format t " ~D" (aref vec (rem (+ k count) size))))
        (terpri))
      (funcall sum-fun sum)))))
     fun)))

(defun solve (cardinalities)
 (let ((prime-to-card (make-hash-table :test #'equal)))
   (let ((adders
   (mapcar #'(lambda (k)
        (make-vector-adder
  k
  #'(lambda (sum)
      (let ((cards
      (cons k (gethash sum prime-to-card '()))))
        (when (= (length cards) (length cardinalities))
   (return-from solve sum))
        (setf (gethash sum prime-to-card) cards)))))
    cardinalities)))
     (let ((iterator #'(lambda (k)
    (dolist (adder adders) (funcall adder k)))))
(map-primes iterator)))))

;;; noc(38): (time (solve '(23 33 403 1163)))
;;; ; cpu time (non-gc) 2,480 msec user, 0 msec system
;;; ; cpu time (gc)     80 msec user, 0 msec system
;;; ; cpu time (total)  2,560 msec user, 0 msec system
;;; ; real time  2,747 msec
;;; ; space allocation:
;;; ;  10,128 cons cells, 13,369,008 other bytes, 0 static bytes
;;; 5457701

Google Treasure Hunt 2008: Puzzle 3 (network) solution

First I was kind-of proud to turn in the solution about 32 minutes after the puzzle was published, in spite of phone calls and other diversions. Then I noticed that I could hand-check my program's result in about two minutes. So this was mainly a test whether people are stupid enough to write a program instead of doing it manually (the fast way).

I happened to have some longest-prefix matching code ("patricia") lying around from another project. For brevity, this is not included. Feel free to ask me if you want this.

The nice thing about this solution is that it is quite general and pretty close to fully automated. If you have GNU Emacs and a Common Lisp system, you can cut&paste the puzzle from the browser (Firefox), convert it into Lisp form using the GNU Emacs command in the code, and then run the routing code with the given source and destination.

(Maybe I'll add dijkstra to it so that it can compute the routing table by itself, to make it useful as a simulator for traffic engineering experiments. :-)

;;;
;;; Google
;;; Google Treasure Hunt 2008
;;; Hello Simon Leinen 
;;; Question
;;;
;;; Below is a diagram of a computer network. The nodes are hosts on
;;; the network, and the lines between them are links. A packet is
;;; sent out from host P with a destination of 179.111.105.159. Which
;;; nodes does the packet pass through on its way to the destination?
;;; (include start and final node in your answer)
;;;
;;; Network
;;; Here is a network routing table you'll need to determine the path taken:
;;; Node  Ip address  Routing table entry  Routing table entry  Routing table entry  Default route
;;; A  73.109.79.84  8.158.16.5 => 143.130.31.174  30.235.90.120 => 202.180.56.184  111.60.99.0/24 => 192.149.202.205  212.37.231.51
;;; B  143.130.31.174  8.158.16.5 => 124.48.79.11  30.235.90.120 => 192.149.202.205  222.240.122.0/24 => 202.180.56.184  73.109.79.84
;;; C  124.48.79.11  212.37.231.51 => 212.37.231.51  111.60.99.67 => 143.130.31.174  192.149.202.0/24 => 103.163.170.32  190.170.232.73
;;; D  103.163.170.32  179.111.105.159 => 13.250.207.24  30.235.90.120 => 124.48.79.11  143.130.31.0/24 => 179.111.105.159  222.240.122.249
;;; E  13.250.207.24  111.60.99.67 => 247.230.125.27  222.240.122.249 => 103.163.170.32  8.158.16.0/24 => 111.60.99.67  8.158.16.5
;;; F  111.60.99.67  124.48.79.11 => 8.158.16.5  192.149.202.205 => 179.111.105.159  212.37.231.0/24 => 247.230.125.27  13.250.207.24
;;; G  179.111.105.159  111.60.99.67 => 30.235.90.120  103.163.170.32 => 103.163.170.32  190.170.232.0/24 => 250.24.51.219  111.60.99.67
;;; H  250.24.51.219  124.48.79.11 => 103.163.170.32  179.111.105.159 => 179.111.105.159  143.130.31.0/24 => 8.158.16.5  30.235.90.120
;;; I  8.158.16.5  179.111.105.159 => 250.24.51.219  143.130.31.174 => 247.230.125.27  111.60.99.0/24 => 13.250.207.24  111.60.99.67
;;; J  247.230.125.27  103.163.170.32 => 30.235.90.120  111.60.99.67 => 8.158.16.5  179.111.105.0/24 => 111.60.99.67  13.250.207.24
;;; K  30.235.90.120  73.109.79.84 => 124.48.79.11  13.250.207.24 => 179.111.105.159  8.158.16.0/24 => 250.24.51.219  103.163.170.32
;;; L  222.240.122.249  192.149.202.205 => 124.48.79.11  179.111.105.159 => 30.235.90.120  212.37.231.0/24 => 212.37.231.51  192.149.202.205
;;; M  192.149.202.205  222.240.122.249 => 143.130.31.174  179.111.105.159 => 222.240.122.249  212.37.231.0/24 => 202.180.56.184  73.109.79.84
;;; N  202.180.56.184  247.230.125.27 => 190.170.232.73  192.149.202.205 => 143.130.31.174  179.111.105.0/24 => 192.149.202.205  73.109.79.84
;;; O  190.170.232.73  212.37.231.51 => 212.37.231.51  30.235.90.120 => 124.48.79.11  143.130.31.0/24 => 222.240.122.249  202.180.56.184
;;; P  212.37.231.51  179.111.105.159 => 190.170.232.73  73.109.79.84 => 222.240.122.249  103.163.170.0/24 => 124.48.79.11  73.109.79.84
;;;
;;; Enter the nodes the packet passes through below
;;; (Note: Answer must start with P, end with the destination node name, and contain only node names.)
;;;
;;; Your answer:
;;;
;;;
;;; ©2008 Google - Terms of Service - Privacy Policy - Google Home
;;; Powered by Google

;;; Here is GNU Emacs code that convers cut&paste text from the
;;; Treasure Hunt web site (like the above) into the network
;;; definition in the Lisp format for the program in this file:
;;;
;;; (query-replace-regexp "\\(.\\)  \\(.+\\)  \\(.+\\) => \\(.+\\)  \\(.+\\) => \\(.+\\)  \\(.+\\) => \\(.+\\)  \\(.+\\)" "(defnode \\1
;;;   (\"\\2\" \"\\3\")
;;;   (\"\\4\" \"\\5\")
;;;   (\"\\6\" \"\\7\")
;;;   (\"0.0.0.0/0\" \"\\8\")" nil (if (and transient-mark-mode mark-active) (region-beginning)) (if (and transient-mark-mode mark-active) (region-end)))

(in-package :noc)

(defvar *addr->node* (make-hash-table :test #'eql))

(defvar *name->node* (make-hash-table :test #'eq))

(defclass node ()
 ((address :initarg :address :reader node-addr)
  (name :initarg :name :reader node-name)
  (routes :initform '() :accessor node-routes)
  (tree :accessor node-tree)))

(defun add-route (node route)
 (let ((prefix (first route))
(next-hop (ipv4-aton (second route))))
   (let ((slashpos (position #\/ prefix)))
     (if slashpos
  (setq prefix (cons (ipv4-aton (subseq prefix 0 slashpos))
       (parse-integer (subseq prefix (1+
          slashpos)))))
(setq prefix (cons (ipv4-aton prefix) 32))))
   (push (cons prefix next-hop) (node-routes node))))

(defmacro defnode (name addr &rest routes)
 `(let ((new-node (make-instance 'node
      :name ',name
      :address (ipv4-aton ,addr))))
    (dolist (route ',routes)
      (add-route new-node route))
    (init-routing-tree new-node)
    (setf (gethash ',name *name->node*)
      new-node)
    (setf (gethash (ipv4-aton ,addr) *addr->node*)
      new-node)
    (set ',name new-node)
    new-node))

(defun init-routing-tree (node)
 (let ((routes (node-routes node)))
   (let ((tree (make-patricia-tree '(8 8 8 8))))
     (dolist (route routes)
(let ((prefix (car route))
      (next-hop (cdr route)))
  (patricia-tree-insert tree (car prefix) (- 32 (cdr prefix)) next-hop)))
     (finish-patricia-tree tree)
     (setf (node-tree node) tree))))

(defnode A "73.109.79.84"
 ("8.158.16.5" "143.130.31.174")
 ("30.235.90.120" "202.180.56.184")
 ("111.60.99.0/24" "192.149.202.205")
 ("0.0.0.0/0" "212.37.231.51"))
(defnode B "143.130.31.174"
 ("8.158.16.5" "124.48.79.11")
 ("30.235.90.120" "192.149.202.205")
 ("222.240.122.0/24" "202.180.56.184")
 ("0.0.0.0/0" "73.109.79.84"))
(defnode C "124.48.79.11"
 ("212.37.231.51" "212.37.231.51")
 ("111.60.99.67" "143.130.31.174")
 ("192.149.202.0/24" "103.163.170.32")
 ("0.0.0.0/0" "190.170.232.73"))
(defnode D "103.163.170.32"
 ("179.111.105.159" "13.250.207.24")
 ("30.235.90.120" "124.48.79.11")
 ("143.130.31.0/24" "179.111.105.159")
 ("0.0.0.0/0" "222.240.122.249"))
(defnode E "13.250.207.24"
 ("111.60.99.67" "247.230.125.27")
 ("222.240.122.249" "103.163.170.32")
 ("8.158.16.0/24" "111.60.99.67")
 ("0.0.0.0/0" "8.158.16.5"))
(defnode F "111.60.99.67"
 ("124.48.79.11" "8.158.16.5")
 ("192.149.202.205" "179.111.105.159")
 ("212.37.231.0/24" "247.230.125.27")
 ("0.0.0.0/0" "13.250.207.24"))
(defnode G "179.111.105.159"
 ("111.60.99.67" "30.235.90.120")
 ("103.163.170.32" "103.163.170.32")
 ("190.170.232.0/24" "250.24.51.219")
 ("0.0.0.0/0" "111.60.99.67"))
(defnode H "250.24.51.219"
 ("124.48.79.11" "103.163.170.32")
 ("179.111.105.159" "179.111.105.159")
 ("143.130.31.0/24" "8.158.16.5")
 ("0.0.0.0/0" "30.235.90.120"))
(defnode I "8.158.16.5"
 ("179.111.105.159" "250.24.51.219")
 ("143.130.31.174" "247.230.125.27")
 ("111.60.99.0/24" "13.250.207.24")
 ("0.0.0.0/0" "111.60.99.67"))
(defnode J "247.230.125.27"
 ("103.163.170.32" "30.235.90.120")
 ("111.60.99.67" "8.158.16.5")
 ("179.111.105.0/24" "111.60.99.67")
 ("0.0.0.0/0" "13.250.207.24"))
(defnode K "30.235.90.120"
 ("73.109.79.84" "124.48.79.11")
 ("13.250.207.24" "179.111.105.159")
 ("8.158.16.0/24" "250.24.51.219")
 ("0.0.0.0/0" "103.163.170.32"))
(defnode L "222.240.122.249"
 ("192.149.202.205" "124.48.79.11")
 ("179.111.105.159" "30.235.90.120")
 ("212.37.231.0/24" "212.37.231.51")
 ("0.0.0.0/0" "192.149.202.205"))
(defnode M "192.149.202.205"
 ("222.240.122.249" "143.130.31.174")
 ("179.111.105.159" "222.240.122.249")
 ("212.37.231.0/24" "202.180.56.184")
 ("0.0.0.0/0" "73.109.79.84"))
(defnode N "202.180.56.184"
 ("247.230.125.27" "190.170.232.73")
 ("192.149.202.205" "143.130.31.174")
 ("179.111.105.0/24" "192.149.202.205")
 ("0.0.0.0/0" "73.109.79.84"))
(defnode O "190.170.232.73" 
 ("212.37.231.51" "212.37.231.51")
 ("30.235.90.120" "124.48.79.11")
 ("143.130.31.0/24" "222.240.122.249")
 ("0.0.0.0/0" "202.180.56.184"))
(defnode P "212.37.231.51"
 ("179.111.105.159" "190.170.232.73")
 ("73.109.79.84" "222.240.122.249")
 ("103.163.170.0/24" "124.48.79.11")
 ("0.0.0.0/0" "73.109.79.84"))

(defun print-path (node dest-addr)
 (format t "~S" (node-name node))
 (if (equal (node-addr node) dest-addr)
     (format t "~%")
   (let ((next-hop (patricia-tree-lookup (node-tree node) dest-addr)))
     (print-path (gethash next-hop *addr->node*) dest-addr))))

;;; noc(57): (print-path P (ipv4-aton "179.111.105.159"))
;;; PONMLKDEIHG
;;; nil

Google Treasure Hunt 2008: Puzzle 2 (zip) solution

Many have published one-liners for this. Just shows you how dense I am. Also, I was confused about the fact that the whole pathname, rather than just the filename (sans directory) should be matched. Whatever.

#!/usr/bin/perl -w

## Unzip the archive, then process the resulting files to obtain a
## numeric result. You'll be taking the sum of lines from files
## matching a certain description, and multiplying those sums together
## to obtain a final result. Note that files have many different
## extensions, like '.pdf' and '.js', but all are plain text files
## containing a small number of lines of text.
## 
## Sum of line 5 for all files with path or name containing bar and ending in .pdf
## Sum of line 5 for all files with path or name containing def and ending in .rtf
## Hint: If the requested line does not exist, do not increment the sum.
## 
## Multiply all the above sums together and enter the product below.
## (Note: Answer must be an exact, decimal representation of the number.) 

use strict;

sub sumup_lines_n_from_files ($$);

my $dir = 'GoogleTreasureHunt08_8189817998309559603';

my $result = sumup_lines_n_from_files (1, '.*EFG.*\.js$')
    * sumup_lines_n_from_files (4, '.*def.*\.js$');

print $result,"\n";
1;

sub sumup_lines_n_from_files ($$) {
    my ($lineno, $re) = @_;
    my $sum = 0;
    open (FILES, "find $dir -print |")
 or die "Cannot start find: $!";
    while () {
 chomp;
 next unless /$re/x;
 #warn "FOUND FILE: $_";
 next unless -r $_;
 open (FILE, $_) or die "open $_: $!";
 my $l = 1;
 while () {
     chomp;
     if ($l++ == $lineno) {
  warn "line $lineno: $_";
  $sum += $_;
     }
 }
 close FILE or die "close $_: $!";
    }
    close FILES
 or die "find $dir -name '$result': $!";
    return $sum;
}