NetFundamentals Seminar - Presentation Today
Posted on 2007-01-29 19:00 by Timo at Permlink with Comments. Tags: netfundamentals seminar university talk
Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.
Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.
Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.
NetFundamentals Seminar - Technical Report Finished
Posted on 2006-12-19 18:19 by Timo at Permlink with Comments. Tags: netfundamentals seminar university technical report
Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.
The technical report can be downloaded as PDF (470 KB)
Abstract
One of the computer science papers most worth reading is Gallager's algorithm for minimum delay routing. The merit of Gallager's paper is its rigorous mathematical approach to a problem, which is more often taken care of using heuristics. The approach is founded on a well designed mathematical network model, which is custom-tailored to describe the minimum total delay routing problem. Mathematical observations on the model lead to two conditions for achieving global optimization, which are based on the marginal delay of links and neighbors. From these observations and conditions an iterative, distributed routing algorithm is naturally derived. Gallager finishes his analysis by proving in detail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.
SDIOS06 - Source Code and Ready-To-Run Image
Posted on 2006-09-14 09:26 by Timo at Permlink with Comments. Tags: sdios06 university sdl
As promised the source code to SDIOS06 was released under the GPL.
SDIOS06 is a toy operating system developed during the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. It was designed and written by Timo Bingmann, Matthias Braun, Torsten Geiger and Andreas Mähler. Two games were ported to a custom SDL implementation using the VMware "hard"-ware: SDLjump and SuperTux. For more information and screenshots see my blog entry 20060727-SDI-Demo.
The source code archive was published on the L4Ka.org page: http://www.l4ka.org/projects/SDIOS06/
A local copy of the source archive (7.4 MB) is available as well. The README file contains a great deal of information about SDIOS06's design and modules. The complete source code can be browsed on the web.
To make demonstration as easy as possible a ready-to-run binary vmware image (3.8 MB) can be downloaded. The image contains SDIOS06 installed on a virtual vmware disk image. The VMware image can be run using the free VMware Player.
Talk about Study Thesis - Slides and Movie
Posted on 2006-08-02 19:43 by Timo at Permlink with Comments. Tags: study thesis study thesis large graphs university talk
At the University of Karlsruhe it is common to give a concluding talk after finishing a study thesis (Studienarbeit). I presented my study thesis "Visualisation of Very Large Graphs" today at the mid-day seminar of the Theoretical Computer Science Group. The slides of the talk are available as PDFs below:
studythesis-talk-visualisation.pdf (1.6 MB) - also available with two slides per page (1.6 MB) or four slides per page (1.6 MB).
During the talk I showed a movie, in which a r-tree of the autobahnen of Germany is constructed incrementally. I actually produced two movies for this purpose: in the first the edges are added in a given sequential order and in the second the order is randomized. Both movies are encoded using transcode and the XviD codec.
Sequential Movie (3.6 MB)
Randomized Movie (5.1 MB)
The talk was received very well, and I may continue in this field with my diploma thesis.
The visualisation library is used by a route planning algorithm developed at the Theoretical Computer Science Group. By integrating my study thesis it was possible to create a Java web applet which animates the route planning algorithm. The Java applet is currently available at http://algo2.iti.uni-karlsruhe.de/schultes/hwy/demo/.
SVG Logo der Universität Karlsruhe
Posted on 2006-08-01 19:22 by Timo at Permlink with Comments. Tags: university karlsruhe svg logo
Für meinen morgigen Vortrag zur Studienarbeit, habe ich (viel zu) lange nach einem vektor-gezeichneten Logo der Univerisität Karlsruhe (TH) gesucht. Es war nur sehr schwer eines zu finden. Aus einem nach langen Stöbern gefundenen PDF habe ich dann folgende SVG, PDF und EPS Grafiken mit Inkscape erzeugt, die bestimmt jemand anderem etwas Mühe ersparen:
 | SVG | SVG (Inkscape) | EPS | |
 | SVG | SVG (Inkscape) | EPS |
Hinweis: Die Grafiken sind keineswegs offiziell oder sonst wie von der Univerität bereitgestellt.
Presented Practical Work for SDI (System Design and Implementation)
Posted on 2006-07-27 20:00 by Timo at Permlink with Comments. Tags: sdios06 university sdl
Today was the final demo presentation day for the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. Goal of the course was to implement a simple operating system on top of the L4 microkernel, which is developed at the Group.
Our practical course group was one of the two groups to demonstrate a working system on the last day of the semester. The presented operating system contained following basic components:
- An initial root task,
- a pager (memory server and task server combined) creating virtual address spaces,
- a root name server for servers to register their facilities,
- a minix file system server which extends the name space to files,
- a (virtual) console server reading keyboard input and writing to the screen buffer,
- and a limited shell with two utility programs: ls and cat.
Furthermore we utilized the VMWare video "card" to enable graphics output. The "hardware" is well documented in the source code to the X11 video driver contributed by VMWare.
The frame buffer and keyboard input was linked up to a ported SDL implementation. After adding a lot of POSIX library function calls like fopen, opendir and getenv, it was possible to compile our favourite games: SDLjump and SuperTux. Both run very well on our operating system from scratch project.
Some screenshots of the shell, sdijump and supertux are available. In future the whole source code and compiled binary images may become available
A big thank you to my friends Matthias Braun, Torsten Geiger and Andreas Mähler, who made this practical work possible and especially fun!
Studienarbeit "Visualisierung sehr großer Graphen" fertiggestellt
Posted on 2006-06-20 17:31 by Timo at Permlink with Comments. Tags: study thesis study thesis large graphs university
Heute habe ich meine Studienarbeit "Visualisierung sehr großer Graphen" am Institut für Theoretische Informatik fertig gestellt und abgegeben. Die Studienarbeit ist eine 3-4 monatige wissenschaftliche Arbeit und dient als Vorbereitung auf die Diplomarbeit.
Die Studienarbeit kann zum Durchlesen als PDF (2,4 MB) herunter geladen werden. Auf diesen Abschnitt folgenden die deutsche und englische Zusammenfassung der Arbeit. Weiter gibt es eine Version zum Ausdrucken (PDF 15,3 MB) mit einer hochauflösenden Vektorgraphik im Anhang.
Zusammenfassung
In dieser Studienarbeit wird untersucht, mit welchen Methoden sehr große Graphen wie ein Straßennetzwerk von Europa effizient und komfortabel visualisiert werden können. Als Ausarbeitung entsteht ein C++ Rahmenwerk für die Datenhaltung eines Graphen mit Attributen und ein Java Applet, das mit dem Datenhaltungs-Server mittels CORBA kommuniziert. Das Rahmenwerk kann leicht in bestehende Graphanwendungen integriert werden, um deren Algorithmen zu animieren.
Als Basis-Graphstruktur wird ein Adjazenz-Array verwendet und um Strukturen erweitert, die zu jedem Knoten und jeder Kante beliebig viele Attributwerte speichern. Zwei der Knotenattribute werden als Zeichenkoordinaten verwendet. Der Grundgraph und die Datenhaltung der Attributwerte wird auf möglichst kompakte Art und Weise gelöst. Graphanwendungen können eine Liste von temporären Änderungen erzeugen, die mit dem großen globalen Graphen zusammengeführt werden können. Um das Vorgehen der Graph-Algorithmen zu visualisieren, werden deren Funktionsaufrufe in einer Änderungsfolge kodiert, welche als Animation zum Java Client übertragen wird.
Um die Geschwindigkeit einer Ausschnittsanfrage zu erhöhen, wird die mehrdimensionale Indexstruktur R-Tree verwendet. Diese ermöglicht Anfragezeiten, die linear zur Anzahl der zurückgelieferten Kanten und unabhängig vom gewählten Ausschnitt sind. Es können komplexe Filterausdrücke aus Vergleichsbedingungen mit boolschen und arithmetische Operatoren verwendet werden, um die angezeigten Kanten in einem Visualisierungsauschnitt einzuschränken und so komfortabel bestimmte Aspekte der Anwendungs-Algorithmen zu untersuchen oder hervorzuheben.
Als Referenzanwendung wird das Rahmenwerk von der am Institut für Theoretische Informatik in Karlsruhe entwickelten Routenplanungsanwendung zur Visualisiserung mittels Web Applet verwendet.
Abstract
This study thesis investigates and implements methods used to efficiently visualize very large graphs like a street network of Europe. A C++ server framework is designed, which implements a data management library for graphs with attributes. A Java applet communicates with the data server via CORBA and draws sections of the graph. The graph data management library can easily be integrated into existing graph application to visual and animate calculations.
The data management library uses the adjacency array structure for representing the base graph. It is extended by similar data structures to hold an arbitrary number of attributes for each vertex and edge. The data structures are optimized towards highest storage efficiency. To modify the static global graph an application may construct a list of changes, which are efficiently merged into permanent data storage. To visualize the workings of an algorithm its function call sequence can be recorded into a list of graph changes. This change time line can be transfered to the Java client and displayed as an animation.
To accelerate access to arbitrary sections of the graph the spatial index structure R-Tree is used. It enables query times to linearly increase with the number of returned edges and be independent of the section size or position.
Furthermore complex filter expressions including comparisons and arithmetic operators can be applied to limit the displayed edges. This enables the client to explore the graph's details comfortably and highlight interesting aspects of an algorithm.
The graph data management library is used in a route planning application, which is being developed in a research group of the University of Karlsruhe. It will be used to visualize the route using a web applet.
Talk in SDI Lab: Naming Service Design in a Multi-Server Operating System
Posted on 2006-06-01 17:00 by Timo at Permlink with Comments. Tags: sdios06 university talk
As part of my work for the SDI Lab work this summer, I held a short talk about how to design a name service in a multi-server operating system like L4.
The slides are available here:
| 1 Slide per page: | NameServiceDesign.pdf | 163 kB |
| 2 Slides per page: | NameServiceDesign-1x2.pdf | 163 kB |
| 4 Slides per page: | NameServiceDesign-2x2.pdf | 158 kB |
Here the table of contents:
- Goals
- Name Catalogs
- Object Representation
- Catalogs
- IDL Interfaces
- Resolve Interface
- Bind Interface
- Extension / Ideas
Homepage zu meinem Tutorium zu Info3 im WS2005
Posted on 2006-05-03 20:09 by Timo at Permlink with Comments. Tags: university compsci tutorium
Hier findet man noch die alte Homepage, welche ich im WS2005 für mein Tutorium in Info3 gemacht habe.
Dort konnten meine Tutoranden ihren Punktestand und eventuelle Neuigkeiten abfragen.
Info2 SS2005 Probeklausur der Tutoren
Posted on 2006-05-03 19:11 by Timo at Permlink with Comments. Tags: university compsci tutorium
Zum Abschluss der Tutorien von Informatik 2 im Sommersemester 2005 haben die Tutoren zusammen eine Probeklausur erstellt. Diese wurde im letzten Tutorium geschrieben und anschließend einige Lösungshinweise zu den schwierigeren Aufgaben gegeben.
Kopie der ursprünglichen Veröffentlichung:
Achtung: Die auf dieser Seite bereitgestellten Aufgaben spiegeln die Meinung der Tutoren der Vorlesung Informatik 2 wieder. Die Aufgaben stammen nicht von den Verantwortlichen der Informatik 2 Vorlesung. Die Aufgaben sind lediglich als Hinweis zur Vorbereitung der Klausur gedacht. Die Aufgaben der Probeklausur decken nur einen Teil des gesamten Stoffes der Informatik 2 Vorlesung ab. Auch Themen, die in der Probeklausur nicht behandelt werden, sind Teil des Vorlesungstoffes und können in der offiziellen Informatik 2 Klausur behandelt werden.
Alle Tutoren werden die Probeklausur in ihrem Tutorium schreiben lassen, dies erfolgt entweder in der vorletzten oder letzten Vorlesungswoche. Schaut euch die Probeklausur also möglichst nicht an, bevor ihr die Probeklausur im Tutorium schreibt.
Probeklausur: (Revision r44)
Probeklausur Informatik 2 SS2005
Lösungshinweise zur Probeklausur Informatik 2 SS2005
Beim Vorbereiten der Probeklausur sind einige Aufgaben entstanden, die nicht in die Probeklausur übernommen wurden, da sonst der Umfang der Probeklausur weit über 60 min liegen würde. Diese Aufgaben können zum Üben benutzt werden.
Zusätzliche Übungsaufgaben: (Special Director's Cut Limited Edition) (Revision r44)
Übungsaufgaben
Lösungshinweise zu den Übungsaufgaben
Vortrag "Objekt-orientiertes Programmieren in C"
Posted on 2006-05-03 16:19 by Timo at Permlink with Comments. Tags: university talk c++
Im Sommersemester 2005 habe ich am Praktikum "Real-Life Programming" am IPD Lehrstuhl der UniKa teilgenommen. Hier platt die Beschreibung von der Homepage zitiert:
Wie programmiert man richtig?
Viele performancekritische Software wird immer noch in C geschrieben. C erlaubt dem Compiler einen sehr großen Optimierungsspielraum, in diesem Praktikum wird geübt, wie dieser ausgenutzt werden kann und wie die dabei auftretenden Klippen zu umschiffen sind.
In diesem Kontext könnt ihr lernen:
- Den Umgang mit den UNIX Entwicklungswerkzeugen
- Schreiben von portablem Code
- Verständnis des Übersetzungsprozesses von C
- Analysieren des durch Übersetzer erzeugten Assemblertextes
- Programmieren, so dass der Übersetzer guten Code erzeugen kann
- Wie man die Performance von Programmen steigern kann
- Umgang mit großen Projekten
- Das Finden von Fehlern in großen und alten Softwaresystemen
- Beherrschen von Debugging und Profiling Werkzeugen
- Kniffe des C-Präprozessors
- Die "Geheimnisse" von C
In diesem Zusammenhang haben zwei Komilitonen und ich einen Vortrag über "Objekt-orientiertes Programmieren in C" (ohne ++) ausgearbeitet und gehalten. Weiteres Schwerpunktthema war die Darstellung von C++ in Maschine, also wie der C++ Übersetzer dann die Klassen abbildet.
| Vortragsfolien: | OOC-Folien.pdf | 179 kB |
| Handout: | OOC-Handout.pdf | 122 kB |
| Beispielcode: | OOC-Beispiele.tar.gz | 4 kB |
Hier noch ein Auszug des Inhaltsverzeichnisses:
- Objekt-Orientierte Konzepte
- OO in C
- Kapselung und Geheimnisprinzip
- Vererbung und Polymorphie
- Generiztiät
- Darstellung von C++ in Maschine
- vtable
- Name-Mangling
- Run-Time-Type Information (RTTI)
Diese Folien geben einen kompetenten Überblick über den Themenbereich.
