Peter Boothe

This is my academic and more serious home page. More frivolity and less organization can be found at my non-academic home page.

Andrzej can sometimes steer his students into dangerous waters.

Hi! I'm a PhD student in the University of Oregon Computer Science Department. I am advised by Andrzej Proskurowski.

For my PhD I'm taking a long term survey of the internet topology, and trying to track what political, economic, and technological factors have helped and hindered the internet's growth, robustness, efficiency, and internationality. This involves a bit of historical digging and reading all about various controversial decisions and events, but much more graph theory and statistics. The graph series I'm generally looking at is the internet's AS graph, and the best source of historical data for the AS graph is the University of Oregon Computing Center's Routeviews Project, but if you have access to other long-term internet data, I would love to get my hands on it!

I gave a presentation on some initial results at the UO CS grad research forum.

When I was in the throes of doing my area exam, I compiled a list of area exam tips and tricks. With other peoples' contributions included, it kind of morphed into an overall hints page, but I'm keeping the title.

I've also made a University of Oregon theme for Beamer that I encourage you to use if you want to make presentations in LaTeX and you want a UO theme.

If you'd like to get in touch with me, my email address is peter@cs.uoregon.edu, my office phone is 541-346-4436, and my office number is Deschutes 254 . My door is always open!

Academic Interests

Obviously, it's difficult to do all of these at the same time, so I have ended up specializing in the first three or four. I care a lot about all of them, however, and hope to work on the others in the future.

The Internet
Graph theory
Routing
Algorithms
Web Programming and Services
Computers and Freedom
CS Education
Computer science and the humanities
Recreational Mathematics
Programming Contests

Classes Taught and Assisted

I actually made up the Programming Python course all on my own, from topic forwards. It was lots of fun to design and teach, and it was so well received by the students that the department has put the class in permanent rotation in their summer class schedule!

Sole Instructor and Course Designer	Assisted
323 Data Structures Lab Winter 2004 399 Programming Python Summer 2004 399 Programming Python Summer 2005 122 Algorithms and Programming: An Introduction to Computer Science Summer 2006 323 Data Structures Lab Winter 2007 122 Algorithms and Programming: An Introduction to Computer Science Summer 2007	313 Data Structures Fall 2002 313 Data Structures Winter 2003 122 Algorithms and Programs: An Introduction to Programming in C++ Spring 2003 313 Data Structures Fall 2003 212 Introduction to Computer Science III Spring 2004 313 Data Structures Fall 2006

Curriculum Vitae

If you want to see the academic stuff I have read and reviewed instead of the stuff I have written, then that is available as a web page and as an RSS feed.

Peer Reviewed

R. Libeskind-Hadas, J. R. Hartline, P. Boothe, G. Rae, and J. Swisher. On Multicast Algorithms for Heterogeneous Networks of Workstations, Journal of Parallel and Distributed Computing, (special issue on cluster and network-based computing), Vol. 61, No. 11, November 2001, pp. 1665-1679.
James Hiebert, Peter Boothe, Randy Bush, and Lucy Lynch. Determining the Cause and Frequency of Routing Instability with Anycast, Proc. of Asian Internet Engineering Conference (AINTEC) 2006
Peter Boothe, Zdeněk Dvořák, Art Farley, and Andrzej Proskurowski. Graph Covering via Shortest Paths, Congressus Numerantium. Available here as well.

Talks

Peter Boothe. The Dynamics of Large Sparse Graphs. Talk given at the UO CIS Graduate Research Forum.
Peter Boothe and Randy Bush. Anycast Measurements Used to Highlight Routing Instabilities Talk given at NANOG34.
Peter Boothe, James Hiebert, and Randy Bush. How Prevalent is Prefix Hijacking on the Internet? Talk given at NANOG36.
Peter Boothe, Zdeněk Dvořák, Art Farley, and Andrzej Proskurowski. Graph Covering via Shortest Paths Talk given at the 38th Southeastern Conference on Combinatorics, Graph Theory, and Computing, and a later version of the same talk was given at a Simon Fraser University colloquium.

Other

Directed Research Project: A General Algorithm for Performing Graph Reductions May 2004
A113028 in the Online Encyclopedia of Integer Sequences
How Prevalent is Prefix Hijacking on the Internet? [Poster] University of Oregon CIS Department Poster Contest, 2005
Generating Realistic Internet Topologies Using Internet Topology Measurements University of Oregon CIS Department Poster Contest, 2007
Decoding Email Headers ... Technical assistance for Salon columnist Glenn Greenwald, 2007

Education and Work Experience

Graduate Student in Computer Science at the University of Oregon, 2002-???

Software developer at Gordian 2000-2002

Joint Major in Mathematics and Computer Science, Harvey Mudd College 1996-2000

My current status, .plan, and .project

[ix.cs.uoregon.edu] 
Login name: peter     			In real life: Peter Boothe
Directory: /home/users/peter        	Shell: /bin/bash
Last login Fri May  9 14:44 on pts/64 from dyna6-141.cs.uo
New mail received Sun May  4 12:51:00 2008;
  unread since Fri May  2 14:19:26 2008
Project: Do my area exam.
Plan:
Paper on the completeness of Routeviews is due on the 27th

How complete is Routeviews?  How wrong is everyone to treat it as symmetric
and complete?

    Theory approach:
      Formally write down the local optimality property of BGP, and then take
      the routeviews graph and add in the maximum number of edges that could be
      unseen without violating the optimality property at any of the ASs we
      have full feeds from.

    Statistical/Experimental approach:
      Look at the routeviews peers, and characterize those ASs - maybe Tiers 1
      through 3, maybe something like edge vs core - and then see how the
      routeviews view changed with each additional feed.  Then, we take the
      total number of ASs of each type, and try and generate a full view of
      what is going on

There are other approaches, but these seem the best.