Thesis

Several weeks ago I successfully defended my MSc thesis. For anyone interested here is the abstract and a PDF version.

The IP Per Process Model: Bringing End-to-end Network Connectivity to Applications

Abstract:

The application of the end-to-end principle in the design of the Internet has been fundamental to its success. One of the most important advantages of the end-to-end principle is that it allows the introduction of new services and protocols into the network without requiring changes to intermediate nodes. This greatly reduces the difficulties associated with developing and deploying new transport layer protocols and network services.

Traditionally network protocol implementations are placed inside the operating system kernel. An alternative to this design found in the computing literature is user-level networking. User-level networking places the protocol implementation and processing inside the application. Among other advantages this design simplifies network stack development and deployment.

This thesis offers a network stack model based on user-level networking which has the primary goal of extending the benefits of the end-to-end principle to applications. This model is referred to as the IP per Process Model. A prototype of this model named Pnet/UNL has been built and evaluated against the Linux network stack. Performance evaluation shows this prototype to compare favorably against the Linux network stack on a 100 Mbps network but the performance gap widens at 1 Gbps.

Thesis in PDF format

Thesis writing using Lyx

When it came time to write my thesis several months ago I decided to use Lyx instead of using LaTeX directly. This is a short tutorial explaining this decision and how it was accomplished.

Lyx is a front-end for LaTeX. It gives you all of the power of LaTeX if you want it but also offers a more traditional word processor like interface. Lyx lets LaTeX handle all of the document layout and gives you the professional look that drives so many people to LaTeX. Lyx also allows you to write without having to see the LaTeX commands or worry about the document layout. The most important thing to realize is that Lyx is not a WYSIWYG editor like MS Word. This is a good thing. If you are used to WYSIWYG editors this can at first seem very strange. I personally find it quite liberating because I have the tendency to obsess over the visual details as I write. In a normal word processor this tendency manifests as losing my train of thought when I stop to format the document. When writing in LaTeX or HTML the same problem occurs when I switch to formating the tags. Lyx does however give you enough feedback about the layout through changing the font of chapter and section titles among other things that the writer does still get some idea of the eventual layout. Lyx also handles cross references and the bibliography in a nice intuitive manor.

Since the Lyx file format is text based it is also very easy to use standard version control software on the document as work progresses. Just as when coding, I view the use of version control software with a document of the size of a thesis as being absolutely essential. The ability to scrap a paragraph and know that you can quickly and easily revert to the old version if necessary frees the writer to attempt larger changes than would otherwise be convenient. It really doesn’t matter what version control system you use with Lyx. Any of Subversion, Mercurial, Bazaar or, if you are on Linux, Git will work great. At completion my thesis Git repository consisted of over three hundred commits.

A short note about figure creation is also in order. I used Inkscape for all of the figures in my thesis. Inkscape is a vector graphics program which uses SVG as the standard file format and is available for Linux, MacOS and Windows. I am not a graphic artist in any way but I found Inkscape easy to use once I figured out how all of the tools work. Making use of the various alignment and transformation tools is especially time saving. Since Lyx cannot make use of native SVG files my solution was to save the figure in SVG format in case I wanted to do future editing and also export an .eps file which Lyx has no trouble consuming.

If you writing a thesis it is quite likely that your university or department has a LaTeX document class available. You should make use of this resource because it will save you the large amount of work involved in getting the document to match the university requirements. Obviously using Lyx would lose some of its appeal if it was impossible to use the provided document class. Fortunately this is not the case.

If you look at your document settings in Lyx you will see a long list of document classes. I used the report class for my thesis. When first attempting to use the LaTeX document class from my university I spent a lot of time trying to get the document class to show up as an option in Lyx. You can find various pointers on how to do this but it never worked well for me and it was too much trouble. Fortunately I found a simpler solution. Rather than get Lyx to use the document class I wrote the document using the standard report class. When the document was complete I exported the document from Lyx to LaTeX (pdflatex). Once I had the LaTeX file it was simple to edit it and replace the document class name with the one provided by the University and add the additional LaTeX commands which were required. This task was probably simplified by the fact that the provided document class inherited from the standard report class. Modifying the LaTeX file may seem like a lot of work, especially having to make the changes manually again each time the document requires revision. Fortunately it is a simple matter to maintain a patch file with the necessary changes and apply it to the exported LaTeX file after revisions have been made. Note that there is little point exporting the document until it is very near completion.

The rest of this tutorial is specific to the UWO Computer Science document class. I hope this information will be useful to others as well. If you don’t already have a copy of the UWO CS Latex template I have made a local copy available.

After exporting your Lyx document to LaTeX (pdflatex) open up the file in an editor. In these examples the exported file is named thesis.tex. The first thing you need to do is replace

 \documentclass[12pt,english]{report}

with

 \documentclass[12pt,english]{uwo-thesis}

The rest of the modifications basically involve adding new LaTeX commands to the file. Since it is the way I did things, I am going to assume that within Lyx the beginning of your document contains the following in this order: title, abstract, table of contents, list of tables and list of figures. This is the order that the UWO thesis style guide requires.

Immediately after the \title LaTeX command add lines similar to the following (obviously filling in the values for your thesis).

\spinetitle{a shorter title}
\firstname{Dan L.}
\lastname{Siemon}
\degreeaward{Master of Science}
\university{University of Western Ontario}
\address{London, Ontario}
\copyyear{\the\year}
\supervisor{your supervisor}
\examinerA{first examiner}
\examinerB{second examiner}
\examinerC{third examiner}
\dedication{a dedication if you want}

These LaTeX commands are used to create the certificate that goes at the front of the completed thesis.

Next locate the \maketitle command in the file. Immediately after this command and before the \begin{abstract} add the following.

\makecertificate
\begin{frontmatter}

Following the close of the abstract section with \end{abstract} command you can add an acknowledgment section if you desire.

\begin{acknowledgements}
The past and present residents of MC240.
\end{acknowledgements}

Now you need to close the frontmatter section. This is accomplished by adding the following text after the \listoffigures command.

\end{frontmatter}

This leaves just one more requirement, the Vita which must be at the end of the thesis. I handled this requirement by creating a short LaTeX document called vita.tex and including it at the end of the file. Place the following immediately before the \end{document} command.

\include{vita}

All of these changes may seem like a lot of work. Fortunately this can be automated by creating a patch file. To create a patch file both the unmodified and modified files are required. First make a copy of your newly modified file. Then re-export the file from Lyx to obtain the unmodified version.

cp thesis.tex thesis.tex.mod

Export from Lyx again.

diff -u thesis.tex.mod thesis.tex > thesis.patch

Reapplying this patch after exporting from Lyx should be as simple as:

patch < thesis.patch

If you make large changes to the document the patch may fail to apply cleanly. In this case fix the file manually and re-create the patch file for future use.

Thanks to Andrew for a couple of the ideas presented here.

Graduation

Last Thursday was convocation (graduation) day at UWO. This year convocation turned out to be quite a media event due to the presence of Dr. Henry Morgentaler.

London Free Press article
Article from UWO’s website
Text of Dr. Morgentaler’s speach

Dr. Morgentaler was speaking for the morning convocation ceremony so I did not get to hear his speech. The speaker for the afternoon ceremony was Dr. Bessie Borwein. The full text of her speech can be found here.

“Bachelor of Science – Honors Computer Science with distinction” is what the paper now hanging on my wall says. I also received the University of Western Ontario Gold medal for Honors Computer Science for having the highest average in the program.

I was not planning on attending convocation but I am now glad I did. Missing the ceremony would have probably been a source of regret later in life. It is strange to me how much I now value that piece of paper hanging on the wall.

I have put some pictures from the day in my photo gallery. No, there are no Morgentaler pictures there.

History

I recently completed a summer term history course. The title of the course was Europe 1715 to present. Wow, I actually thought I had a clue about European history before this course. Was I ever wrong. The amazing mess that was Europe in the 1800s brings the current problems in other areas of the world into perspective. I think it’s a little too easy for people who grew up in ‘modern’ countries to think that our society has always been as stable and sane as now (or at least as stable as we think it is). This course showed me that this is certainly not true.

Also, I found the Enlightenment to be particularly interesting. The fact that ideas that we now take for granted such as people should be ruled by laws not rulers, equality of all people and the concept of individual identity come from only ~225 years ago (1750->1800 mostly) is amazing to me. These are just a few examples of Enlightenment ideas that are now central to our liberal (in a classical sense) societies.

The French revolutions of 1789 were the first major political events that centered around Enlightenment ideas. The backlash against this revolution resulted in the European Congress system that was designed to put the lid back on and restore Europe to pre-1789. That it took until the end of World War I for the ideas of the Enlightenment to come to the forefront of European politics is very alarming.

I can’t stop myself from seeing similarities between the Enlightenment and the current conversations about intellectual property. There were many entrenched interests who did their best to stop the ideas of the Enlightenment. These ideas were so powerful that even a hundred years of crushing attempts could not make them go away. The Internet and other digital technologies have fundamentally changed our world. The law hasn’t caught up to this fact yet. Companies and individuals who profit under the old system of scarcity and control are doing their best to make sure the law never does catch up. Sounds a lot like the last major intellectual revolution western society went through. I am pretty confident how this will end. The question is, do we need another century of innocent people getting jailed or worse before we see the end of the tunnel?

I need to be a little careful here. As my history professor said, despite popular belief history does not actually repeat itself. That doesn’t mean there are not any lessons to be learned though.

Course selection

It looks like I have pretty much got my fourth year Computer Science courses figured out.

CS325: Law in Computer Science
An examination of aspects of law and policy that relate to the creation, protection and implementation of software and hardware; attention is directed towards issues of current importance of which every computer scientist should be aware.

CS402: Distributed and Parallel Systems
Issues arising in distributed and parallel systems and applications; related architectures such as connection machines, shared memory multiprocessors.

CS413: Cryptography and Security
Survey of the principles and practise of cryptography and network security: classical cryptography, public-key cryptography and cryptographic protocols, network and system security.

CS444: Semantics of Programming Languages
Operational, denotational, and axiomatic semantics; lambda-calculus.

CS445: Analysis of Algorithms II
Parallel, distributed, probabilistic, and geometric algorithms; design and analysis; computational geometry; fractals and graphtals.

CS447: Compiler Theory
Syntax-directed translation; LR(k), LL(k), attribute grammars; code generation; optimization; compiler compilers; code generator generators.

CS457: Computer Networks II
Network layering, performance, management, modelling and simulation; faults and failures.

CS490: Thesis
A project or research paper completed with minimal faculty supervision. An oral presentation plus a written submission will be required.

It was pretty hard to decide which courses to take this year. The first big decision was to take the courses necessary for the Four-year BSc Honours Computer Science degree instead of the Four-year Bsc Honours Computer Science with Software Engineering Specialization degree. Although the Software Engineering sounds a little more impressive it seems to me to be the easy way out. The courses required for the Software Engineering specialization look easier and less interesting to me. Worse, I would not be able to take many of the more theoretical courses I listed above.

After making the above decision I still had to decide between
CS338A: Computer Graphics I
Graphics primitives. The viewing pipeline; clipping and visibility problems. The graphical kernel system; picture generation and user interfaces.

and

CS444: Semantics of Programming Languages
Operational, denotational, and axiomatic semantics; lambda-calculus.

It was a choice between specializing more in programming languages or broadening my knowledge with the Computer Graphics course. This was a tough decision because I know very little about graphics and would like to know more. I chose CS444.

The second course decision was between
CS325: Law in Computer Science
An examination of aspects of law and policy that relate to the creation, protection and implementation of software and hardware; attention is directed towards issues of current importance of which every computer scientist should be aware.

and

CS413: Foundations of Computer Science II
Formal languages; recursive functions; abstract complexity; automaton models; array machines; systolic systems; cellular automata.

I decided on CS325 for a couple of reasons. First, I have become very interested in intellectual properly issues. Second, I don’t want the spring term to be too hard because a lot of time will be consumed by my thesis.

I do feel like I should be taking another mathematics course or two but there just isn’t room.

It should be a very interesting year. I wish it were possible to take every course in the Computer Science department. Also, I still have to decide which option credit to take. I’m thinking economics.

Now, I just need to decide whether or not I will do a masters next year.