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)))))))