Science, Engineering, Research

Brute-Force Sudoku Solver

2012-03-02T13:53:00.000+01:00

This post has a backstory that I do not want to discuss (in short: I am stupid!) but I had to write a Sudoku solver. Here is a backtracking solver that applies a brute-force approach. It does only create a 9x9 Sudoku board as example and can also only solve 9x9 boards but you can easily extend it to arbitrary sizes. This is not very nice code but it works and solves the board in about 2-3 seconds.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import pylab
import numpy as np
from collections import Counter

def initialize_board(board):
    '''
    example board from wikipedia page
    '''
    board[0][0] = 5
    board[0][1] = 3
    board[1][0] = 6
    board[2][1] = 9
    board[2][2] = 8

    board[0][4] = 7
    board[1][3] = 1
    board[1][4] = 9
    board[1][5] = 5

    board[2][7] = 6

    board[3][0] = 8
    board[4][0] = 4
    board[5][0] = 7

    board[3][4] = 6
    board[4][3] = 8
    board[4][5] = 3
    board[5][4] = 2

    board[3][8] = 3
    board[4][8] = 1
    board[5][8] = 6

    board[6][1] = 6

    board[7][3] = 4
    board[7][4] = 1
    board[7][5] = 9
    board[8][4] = 8

    board[6][6] = 2
    board[6][7] = 8
    board[7][8] = 5
    board[8][7] = 7
    board[8][8] = 9

    return board

def check_rows_columns(board):
    for i in range(board.shape[0]):
        row = data = board[i]
        column = board.transpose()[i]
        dups_rows = [1 for key, value in Counter(row).iteritems() if key != 0.0 and value > 1]
        dups_columns = [1 for key, value in Counter(column).iteritems() if key != 0.0 and value > 1]
        if len(dups_rows) or len(dups_columns):
            return False
    return True

def check_sub(sub):
    dups = [1 for key, value in Counter(pylab.flatten(sub)).iteritems() if key != 0.0 and value > 1]
    if len(dups):
        return False
    return True

def check_subs(board):
    for row in xrange(3):
        for column in xrange(3):
            sub = board[row*3:(row+1)*3, column*3:(column+1)*3]
            if not check_sub(sub):
                return False
    return True

def check_board(board):
    return check_rows_columns(board) and check_subs(board)

def create_board():
    board = np.zeros((9, 9))
    board = initialize_board(board)
    return board

def solve_board(board, pos=0):
    if pos >= 9*9:
        return True
    if board[pos%9][pos/9] > 0:
        return solve_board(board, pos+1)

    for i in xrange(1, 10):
        board[pos%9][pos/9] = i
        if check_board(board) and solve_board(board, pos+1):
            return True
    board[pos%9][pos/9] = 0
    return False

def main():
    board = create_board()
    if not check_board(board):
        print 'ERROR: initial board violates rules'
        sys.exit(1)
    solvable = solve_board(board)
    if not solvable:
        print 'ERROR: board not solvable'
    else:
        print board

if __name__ == '__main__':
    main()

Matplotlib: Draw Ellipses

2012-03-01T10:13:00.006+01:00

Just a concise example:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pylab import *
from matplotlib.patches import Polygon, Ellipse
from matplotlib.collections import PatchCollection

# example data
data = [(0.1, 0.1, 0.15, 0.07), (0.1, 0.4, 0.5, 0.1), (0.6, 0.5, 0.25, 0.17)]

fig = figure()
ax = gca()
ellipses = list()
for x, y, width, height in data:
ellipses.append(Ellipse((x, y), width, height, edgecolor='black', facecolor='red', alpha=0.5))
ax.add_collection(PatchCollection(ellipses, match_original=True))
fig.savefig('/tmp/ellipse_example.pdf')

Ellipses are a nice way to visualize confidence intervals on two axis for your data instead of using error bars for the representation.

Starting X11 Applications over SSH AND showing the GUI on the remote host

2012-02-26T17:46:00.002+01:00

Most people know that you can start an application on a remote computer and have the GUI tunneled/forwarded over an SSH session by connecting as follows:

ssh -X ${USER}@${HOST}

(Of course you have to set the USER and HOST variables appropriately.)

But how do you actually start an application after you have logged in over SSH and display the GUI on the remote machine's Xserver? This can be achieved quite simple. You have to set the XAUTHORITY variable to the file that contains the "magic cookie" as follows:

export XAUTHORITY=/home/$USER/.Xauthority

Subsequently, set the DISPLAY variable (usually to ":0") as follows:

export DISPLAY=':0'

That's it! Keep in mind that if you want to disconnect after starting the application, you should probably use screen, tmux, or nohup.

Depending on the application that you have started, you may actually be able to control it on the shell that you logged into over SSH, e.g., you can still control mplayer when started on a remote host.

Shell Script Programming in Bash

2012-02-21T13:06:00.000+01:00

Shell script is an easy way to automate common tasks but shell script certainly has its oddities and pitfalls.

Greg's Wiki provides a good overview of common Bash pitfalls. Freddy Vulto has additionally published a summary of Bash error handling in his wiki. Both sources are excellent reads for any shell script developer.

Piercing Holes in NATs

2012-02-15T22:52:00.000+01:00

In contrast to the 90s when we were still using dial-up connections from a single computer to the Internet over modems, nowadays everyone has a device at home that you may often refer to as router. In fact, this is usually a DSL modem, a cable model, or similar device that is also providing switching and routing functionality.

By having multiple computers connected to the Internet over a single line, it became necessary to be able to differentiate the connections, e.g., made with browsers from the (internal) computers B₁, B₂, and B₃ to the same website (external) A. Thus there are multiple connections that are multiplexed and we need a way to determine if inbound packets from C are destined to B₁, B₂, or B₃ that are all addressed by a shared external, routable IP address. The following figure depicts the scenario:

Network Address Translation (NAT), also sometimes Network Address Port Translation (NAPT), maps the internal and external tuples for the IP addresses and the port numbers, that we are using for transport layer multiplexing, to each other. Thus your router that incorporates NAT functionality is able to forward the packets if these mappings are learned, e.g., when B₁ initializes an (outbound) connection to A.

This approach has an additional benefit: security. If there is not matching mapping because an internal computer has not initialized a connection, inbound packets are simple dropped. Hence NAT devices enable a simple but effective firewall. While this probably has prevented incidents for many non-tech-savvy people, it has a quite unpleasant side effect. Services like VoIP cannot be easily realized, if the two entities that want to communicate are both behind NAT devices. An external entity may act as relay/proxy to enable communication but this way all data has to traverse the relay (security?!?) and a relay has to be known or discovered in the first place.

The IETF provides an approach to overcome this problem. Session Traversal Utilities for NAT (STUN) as specified in RFC 5389 is used by the Interactive Connectivity Establishment (ICE) protocol that itself is defined in RFC 5245. You find an informative figure that depicts the STUN algorithm which determines the type of NAT that has to be traversed here. In addition, ICE also supports Traversal Using Relays around NAT (TURN) as specified in RFC 5766 and RFC 6156 where an external relay is actually used. You can find an ICE implementation in libnice which should be available in most Linux distributions. STUN, TURN, and ICE enable thus communication over NAT devices in a transparent way for most applications.

Data Structures for C Developers

2012-02-10T18:25:00.000+01:00

Just a brief introduction to a simple solution for a common problem (and also shameless self-advertisement).

The C standard library offers little to none of the data structures that developers, that are accustomed with higher level programming languages, e.g., Java and C++, will expect when they are faced with C programming. Of course, you find them in the GLib but often you may want to avoid this dependency, especially due to the size of the library.

uthash has been developed by Troy D. Hanson and offers, despite its name, hash maps, linked lists, arrays, and strings. What makes this solution so interesting is that the data structures are implemented as C preprocessor macros. Thus, you only have to include the provided header files and there are no run-time dependencies. uthash is also available in Debian and Ubuntu (and probably other Debian based distributions) as I am the corresponding package maintainer.

So give the data structures in uthash a chance and don't start to implement them yourself, like many others have. Troy provides a simple but elegant solution that is also adequately documented.

IEEE 802.1QinQ and VMware

2012-02-04T15:00:00.000+01:00

The IEEE 802.1Q standard defines virtual LANs, i.e., a way to setup logical/virtual topologies on a physical topology. The frames are extended by an additional VLAN header that is evaluated by the switches. QinQ, Q-in-Q, and double-tagging refer to VLANs that are created within VLANs, i.e., the frames may have multiple VLAN headers (see IEEE 802.1ad).

I am certainly no expert in VMware's products, but from what I have been told by our technical department, topologies are realized in VMware ESX(i) by VLANs. If you are unlucky as me, when I asked for a bunch of VMs for teaching and experiments, there may not be enough VLAN ids available to create sophisticated network topologies. First of all, the creation of topologies is somehow not easily done in VMware ESX(i) and VLAN ids may be valid for the whole campus/company. As they are limited to 12 bit (some equipment may even support less!) you may have only very few available, if you cannot isolate your experimental network (was off my responsibilities). Thus you may end up with a sufficient number of VMs but that are fully meshed, i.e., each host can reach any other directly.

QinQ can be a solution for this problem. The VLANs of VMware ESX(i) are transparent for the VMs. We can create virtual interfaces in Linux with vcontrol that add a specific VLAN header to the frame before it is sent out over another interface. Thus by assigning VLAN ids to specific interfaces on the VMs, you can easily setup any topology you want to study.

Unfortunately, VMware ESX(i) does not like double-tagged frames and they are quietly dropped by the virtual switches (or somewhere else, does not matter). So how can we enable QinQ despite this miss-behavior? Actually the solution is quite simple. The VLAN header is identified by the ethertype 0x8100 in the Ethernet frame. If you change this value, the switches are not able to detect the double-tagged frames anymore as they will not apply any sophisticated detection algorithms if the ethertype is unknown. These algorithms would require too many resources on the switches.

You can replace the ethertype in several ways but what worked the best for me was actually to replace the value, e.g., in the e1000e NIC's kernel module source code and to rebuild it. You additionally have to disable any VLAN support that may be available in the hardware. If you forget this, the hardware will actually insert the VLAN header with the correct ethertype.

If you are successful, you will be able to use QinQ depite VMware's "feature". Although this approach violates the corresponding standards, network protocols often have no protection against similar attacks. That is something you always have to consider. An IP datagram may be "disguised" by the ethertype that actually identifies an ARP packet.

You can basically use most ethertypes to disguise your QinQ frames but I would advise to use 0x885B or 0xx88B6 as they are defined as local experimental ethertypes in IEEE 802: "for public use and vendor-specific protocol development". This way you should prevent problems due to accidental evaluation of the frames by network hardware that does not know about the proposed solution.

Ethernet Bridging Troubles on VMware

2012-02-03T11:28:00.001+01:00

Ethernet bridging should be a straight forward task. Usually, computer science students learn about it in the computer networks / telematics lecture and it sounds pretty trivial. Unfortunately this is not always the case. When I tried to extend our testbed deployment to an external partner by a layer 2 tunnel (Ethernet bridging with OpenVPN), I ran into several problems. Descriptions of these problems can be found on several mailing lists or in forums but I neither found an in detail discussion of the fundamental problem nor a simple solution.

Lets assume that we have the following network architecture:

Host A shall be bridged into the LAN where Host C resides. Host B is the tunnel endpoint and connects into the LAN with interface eth. The OpenVPN server on Host B reads and writes frames from/to the virtual Ethernet interface tap which is bridged by br with eth. vSwitch is a virtual switch in VMware ESX(i) and Host B is actually a virtual machine. I omitted a cascade of additional (real) switches that are found between vSwitch and Host C as they do not matter in this example. Actually, I do not exactly know about the LAN and which VMware solution is applied for the virtualization as this infrastructure is not managed by me. We will thus consider the infrastructure as black box in the following.

So what problem did I experience? Simply speaking, frames did not arrive from Host C at Host A:

As depicted and marked as Problem 1, ARP Requests (broadcast frames) did traverse the bridge and vSwitch and were answered by ARP Replies (unicast frames), but the replies did not arrive at Host B. Further on (Problem 2), while ARP Requests from Host C arrived at Host B and where successfully answered, unicast frames (ICMP Echo Request in this example) sent by Host C and destined to Host A did not arrive at Host B. Both problems are easily explained. vSwitch is actually a very simple virtual switch and will only deliver frames to Host B that are destined to the MAC address of Host B's eth interface. The switch cannot support multiple MACs per port. Thus there is only one solution: switch on the promiscuous mode for vSwitch so that all frames that are received by vSwitch are delivered to Host B.

This was realized thanks to our technical department and Host A and Host B were actually able to communicate in some cases as this configuration introduces a new problem. I observed the following packet flow:

The ARP Reply was received by Host B but the bridge br forwarded the unicast frame over the wrong port (resp. dropped the frame to prevent a loop): P2 and not P1 where Host A is actually reachable. Thus the fundamental question is: why did the bridge use the wrong port? Bridges learn on which ports the stations/hosts/MAC addresses are actually reachable by evaluating the source addresses in the Ethernet frames. Shouldn't br know that Host A is reachable via port P1 because of the ARP Request? In fact, I noticed with brctl showmacs that Host A's MAC was sometimes reachable via P1 but most often via P2.

This is easily explained. Promiscuous mode has a slightly different meaning than usual. VMware writes in its documentation, that the promiscuous mode in ESX Server "makes a virtual switch port act as a SPAN port or mirror port". This somehow results in the following packet flow:

The virtual switch sends a copy of the ARP Request back to Host B. Thus, while br did firstly detect Host A as reachable via P1, the copy arrived later and the bridge overwrote P1 by P2 in the forwarding table. Of course, this is not a fault of the bridge as Host A may have moved. It simply has to learn based on the observed frames. You can actually monitor duplicates of all broadcast frames on eth on Host B that are received by vSwitch - even broadcasts that do not originate from Host B or are forwarded by it. Thankfully this does not happen with unicast frames.

So what is the solution to this problem? In fact there are several:

Replace Host B and vSwitch with real hardware (costly)
Replace vSwitch by a Nexus 1000V (untested but certainly costly)
Consider other solutions, e.g., based on ProxyARP (untested, may introduce additional problems)
Disable learning in the bridge: brctl setageing br 0 (quick and easy solution but unicast packets are always flooded)
Filter the copies of the frames on br resp. eth on Host B

The last options is actually what I evaluated and what I actually used in the end. But why should it be that easy? My first idea was to filter the ARP Request copies that we accidentally received from the virtual switch. Unfortunately, I was unable to solve the problem with arptables as I cannot drop the frames before the bridge learns. arptables provides only the filter table with the INPUT, FORWARD, and OUTPUT chains. We can use only the FORWARD chain as the others apply only if the frame is generated on or destined to Host B. Unfortunately, the bridge has already learned/updated the mapping in the forward state. Thus after consulting this helpful figure, I opted for an ebtables rule that is evaluated early enough:

ebtables -t broute -A BROUTING --src $EXT_MAC --in-if $IFACE -j DROP

There is only one issue with this solution: you need one rule for every external host/MAC address. This is not a problem in our case as we know which wireless mesh routers are located outside of our campus.

This ends my discussion of this particular problem that kept me busy for some time. I hope that my documentation will help others and save time. Feel free to comment.

Tales from my Job Hunt

2012-01-31T09:37:00.004+01:00

There are several facts that I learned in the last weeks when I have been applying for jobs in the IT industry. Some of them are surprising and some are slightly discouraging.

There are several job advertisements for jobs that do not actually exist. You notice these jobs if your application process is closed, e.g., after exactly 72 hours after submission. Usually you get an email that that states that they selected someone more qualified (but you are nevertheless a "highly qualified applicant") whereas the position is still open and advertised. But why are there advertisements if these companies do not actively seek new employees? While there is little information on the web available from what I found

these are either permanent advertisements to collect information about the current job market state,
they are only looking for experts that match all requirements
they want to attract professionals from competing companies, or
they are permanent advertisements to get applications if a position is available at short notice.

If you are asked about the expected salary, provide a reasonable interval. Of course, it is honest to argue that your actual salary depends on many factors, like the work hours per week, bonuses, training courses/certifications, etc. This figure is an important criterion if you are a potential fit for the position or if you are too expensive to begin with. At the same time, it is also important to know what your work is actually worth. It may also be a negative factor if you demand a too low salary as you may not earn much less currently because you are doing a poor job.
The positions Project Manager, Team Manager, IT Manager, etc can mean anything from managing a small developer team to being responsible for a multi-million Euro project. The PMI thus differentiates several classes of companies in their book, depending on the power and responsibilities of the manager, e.g., strong or weak matrix. Unfortunately, this is not always clear from the job advertisements and you may apply for positions that do not fit. There are also similar positions that are prefixed with the terms Functional or Technical that usually do not refer to positions where the manager is responsible for everything and is actually working in a team of managers. Some few companies offer Junior or Trainee positions that are a good opportunity to continue your career.
Making your profile available at job markets/career websites/social networks like Monster, StepsStone, Xing, LinkedIn has advantages but also several disadvantages. You will get contacted by several headhunters that may offer interesting job opportunities but you are also contacted by a large number of agencies - sometimes even by multiple recruiters of the same company that are responsible for distinct regions or professions. It gets tiring if you have 5 telephone interviews and two on-site interviews per week, especially as you often do not know if these agencies actually have interesting jobs to offer (keep in mind that you still have a job during the job hunt and need to take some days off work for the interviews!). Nevertheless, it is a good training to present yourself and to plan where you want to be in 5-10 years.
You will also get contacted by so called IT service providers (IT Dienstleister in German). These companies may offer permanent positions but they are actually sending their employees to their clients to support the on-site teams for a particular project. These projects last from 6 months to 3 and maybe sometimes 5 years. While the IT service providers claim that they will try to get a subsequent project at the same location, they cannot guarantee it. Thus you may be either loosing your job or have to move every year(s). This is certainly not a job I aspire. Yes, you have to be mobile nowadays, but making a career in a single company sounds much better. If you are worrying about your job every year, you cannot focus on your current task.
Include ALL your technical skills in your resume. The human resource employees and even the department manager may not know which common skills you can expect from graduate students nowadays. For example, I am a researcher with focus on computer networks and of course are using relational databases. I expect that this skill is common and nothing special (but I am somehow alone with this opinion). Unfortunately, you are often required to list some specific programs, programming languages, etc in your resume because many companies do not expect that you are able to acquire the necessary knowledge yourself in a few weeks and/or require special training courses (costly!). If you are a computer scientist, you should have a good understanding of most topics in IT and be able to learn - but again, this may not be assumed.
German companies want German applications - sometimes even when the job offer is in English and the offer lists business-fluent English as a mandatory skill: "...we accept English resumes, but our official working language is German and we are a German company...". This applies even for some large, global corporations! This is quite surprising as English is the primary language in the academic research domain and even meetings (and some lectures) are often held in English.
Most companies were basically "offline" for three weeks over Christmas and New Year's Eve and they took 1-2 weeks to get started again. You should not expect any notification during this time. This really surprised me, especially as we are talking about some large, well known, global corporations that sometimes expect that their employees are available at all times. I got feedback and where asked for interview dates 1.5 months after my submission! Please note that these were usually no job advertisements with a specific submission deadline where you expect a longer time for feedback if you submit early.

Despite these experiences, there are actually some very interesting offers with a reasonable salary and working conditions. Several headhunters told me that the companies currently have problems to find employees that plan to stay for 2+ years and/or to take on responsibilities. Thus the free lance market is currently booming and the companies are skeptical if they should invest in the training of new employees. Maybe this partially explains the job advertisement issue that is discussed?!

Multi-Hop Routing on Android

2012-01-18T13:37:00.001+01:00

I have been contacted by multiple people in the last months that are interested in our ongoing research work to enable multi-hop routing on the Android platform. In fact we have a working prototype since over a year.

The left image depicts our DES-SERT Android app that enables to download, configure, and monitor routing daemons written for the DES-SERT routing framework. Unfortunately, we were unable to make it publicly available as it does not yet fulfill our quality requirements. I am busy with my PhD thesis and several student helpers of the team left because projects ended. Thus the DES-SERT on Android sub-project is currently on hold for an indefinite time.
The provisioning of a mature and user friendly solution is actually not an easy task. While I like the Android platform, I think it is kept back by several deficiencies. To name a few:

A packaging system should be provided. This enables easier software deployment below the Dalvik VM but also enables frequent security updates! (Has this changed in Android >=3 ???)
Scrap the Bionic libc and switch to some common open source alternative to improve the compatibility and to ease software development!
The wireless drivers and their configuration are "weird" and proprietary.

My propositions to improve the platform:

Provide a platform that fully complies to the Linux Standard Base to fulfill your users expectations about the installed standard utilities, the init process, etc (or at least provide a packaging system so that everyone can easily extend and update its installation).
Define Android as the Dalvik VM, the required libraries, and everything running on the VM and leave everything else to the open source community, distributions, etc. The Android Runtime and the Application Framework should be the only dependency to run Android apps on any (Linux based) OS. While this is already partially realized, there is still a long way to go to provide and use Android apps in a pervasive way.
Understand the mobile phone, tablet, etc as a full-fledged mobile computer with multi-user support, under full user control, and with a lifetime longer than 1-2 years. It is a mobile computer that is currently held back by proprietary solutions that provide us only with a subset of the features that we have come to love (printing anyone?).

Porting and maintaining the DES-SERT routing framework has taken much more work than it should have been. I assume that many other novel applications are held back at this time because companies care mostly only about the apps (that's were the money is at) and universities do not have the resources for dedicated, long-term projects to develop and support such solutions.

Attack of the Mesh Routers

2011-12-18T19:34:00.001+01:00

Hey look what I found! An advertisement poster for our then small research group that I created in 2008 with Inkscape.

The poster depicts a rather aggressive variant of our old mesh router design. You can find more information about the new design on the DES-Testbed Hardware page.
I wonder if any student joined our group because of the poster...

Positions in the IT Industry

2011-12-18T12:48:00.000+01:00

As I am currently looking for a new job (after I have finally submitted by PhD thesis and my contract ends), I have noticed that there is no brief overview and description of the positions in the software/IT industry. Interestingly, there are different titles for some positions, while a title may also have a significantly different meaning. You find a brief description of the most common positions in the following. Please feel free to post comments. Of course, most positions are available as new grad, junior, and senior variants whereas the work experience to reach the senior level may vary significantly (often times 5+ years). Several titles can also be prefixed by IT or similar terms.

Software Engineer

AKA: Programmer, Software Developer, Software Development Engineer
Tasks: Programmer that implements code based on a specification
Note: Some software engineers, e.g., for embedded systems often times have more freedom how they solve a particular problem, as there is no OOAD involved.

Software Architect

AKA: IT Architect
Tasks: Models/designs the architecture of the application based on the requirement specification usually in an object oriented way using UML or related description languages

Requirements Engineer

Tasks: Applies requirement analysis techniques to specify the requirements of the application based on the customers demands, questionnaires, interviews, etc
Note: May be the same person as the software architect but usually separated in current, larger projects.

Test Engineer

AKA: Software Engineer in Test, Quality Assurance Engineer, Quality Manager
Tasks: Specifies, automates, and evaluates tests to find bugs in the application
Note: Quality manager may either represent an alternative title for test engineer or be the position of the manager of the test team

Consultant

AKA: Business Analyst, Product Analyst, IT Auditor
Tasks: Analyses business processes in a company, usually in a team, and proposes changes for the optimization; can be an internal or external consultant; IT Business Analysts are often internal consultants

Consultant (alternative)

AKA: Contingent Worker
Tasks: Depends on the job/project
Note: Blatantly misleading description to fool applications, usually underpaid employment without job security. The worker is employed by a specific IT service company and leased to other companies for a project. He/she may be permanently employed by the client afterwards but there is no guarantee. Acceptable position if you are a highly skilled, well paid specialist. Alternatively, free lance work may be more promising than this position.

Researcher

AKA: Research and Development Engineer, Research Scientist
Tasks: Specifies a research and development plan for a project, either conducts the research independently or in a team
Note: Somehow a hybrid position of a academic researcher and a software engineer. There may be a hierarchy of research scientists.

Project Manager

AKA: Team Manager, IT Manager, Application Owner, Product Owner, Product Manager, Technical Program Manager
Tasks: Develops business cases, leads the developer team, reports to the upper management, works on proposals to acquire new projects, coordinates, and communicates with the client
Note: While the listed positions may have different focus, all of them include the responsibility for a particular product/team/application and include (some) human resource management and less software engineering related tasks.

Technical Writer

AKA: Technical Communicator
Tasks: Writes and maintains documentation about the product for developers, consumers, etc. He/she may also be employed by a publisher and act as an editor for publications.

System Administrator

AKA: IT Communication Service Specialist
Tasks: Takes care that the IT infrastructure runs and all other departments can do their job. He/she may also be responsible to setup and maintain the hardware infrastructure.

Solution Designer

AKA: Solution Engineer, Conceptual Designer, Creative Planer
Tasks: Examine the business requirements and proposes solutions; hybrid position of a system architect and requirements engineer or may alternatively work closely with both of these

IT Supporter

AKA: Technical Supporter, Customer Service
Tasks: Is contacted by consumer, customer, or internal persons because of problems; either provides solutions for known problems or communicates problems to the specific department or person, e.g., some project manager
Note: Depending on the employment this may also be a hybrid position for highly skilled people that includes the tasks of the test engineer to reproduce the reported defect and the tasks of the software engineer and system architect to fix the problem. This may be especially be true in B2B scenarios, e.g., support for a commercial compiler or development environment.

That is quite a list! Again, please consider that the title may have limited significance. The job description/description of the tasks will be more detailed. Nevertheless, despite the job advertisement you may end up doing something totally different in some companies depending on the current requirements ... but isn't that why we are in this domain? No day is like the other and there are always new problems and challenges :-)

Improved description environment

2011-12-14T23:22:00.000+01:00

The LaTeX description environment is frequently used but has some limits. Consider the following example:

\begin{description}
\item[Short Label] Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

\item[Looooooooooooong Label:] Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
\end{description}

The description labels and the text will not be aligned which just looks unprofessional. Fortunately, the KOMA-Script classes provide the labeling environment:

\begin{labeling}[\vspace{2em}]{Looooooooooooong Label:}
\item[Short Label] Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

\item[Looooooooooooong Label:] Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
\end{labeling}

The optional parameter (in square brackets) allows to specify a custom separator for the labels and the text and may be some white space like in this example. The mandatory parameter (in curly brackets) specifies the width of the widest label in the labeling environment. Thus a clean looking alignment can be achieved.

Pseudo-color plot

2011-12-12T13:14:00.000+01:00

matplotlib provides several functions to plot scientific data. Often times, I plot 3-dimensional data in 2-dimensonal formats as the third dimension sometimes obscures particular parts in the plot or such plots are problematic in publications. Pseudo-color plots are a good alternative as they are 2-dimensonal plots (x and y axes) whereas the third dimension is represented by color.

The normal ax.pcolor() function unfortunately draws a grid around the cells that are rather ugly (click on the image to enlarge):

Although there are the shading and edgecolor options, they show not the desired effect. You can use the ax.pcolorfast() function that improves the speed of the plotting as it does not draw any lines:

Random Waypoint Model

2011-12-09T10:13:00.000+01:00

Most MANET simulations of the last decade use the random waypoint model.
The nodes select a random destination, usually in a square or rectangular area, a random velocity from (0, vmax], and then move towards the destination.
When they arrive, they may either wait for a random time (may be omitted in some simulations) or immediately select a new random destination and velocity.

The model has particular problems that have already been discussed in literature. For example, a low lower bound of the velocities may result in many nodes that are stuck in their movement, i.e., they selected velocity 0 units/s or they may never arrive during the simulation time. Further on, the node accumulate in the center of the simulation area, as there is a larger probability to travel through the center than along the border.

You can see an example of the mobility model in the following animation that I implemented in Python in an afternoon.

The edges in the graph represent wireless links that are created when the nodes are within communication range. A very simple free space like model is assumed.

Simulation are often times fairly abstract and the models are not good representatives for the real world. You should always be critical when using common models and ask yourself if the models are actually applicable in your scenario and if and how the models are affecting your results.

Random graph with custom node degree distribution

2011-11-27T22:19:00.000+01:00

Random and regular graphs are often used in simulations but sometimes you need some custom node degree distribution. This may be because the system you are modeling is not following a distribution which is available in common graph generators. NetworkX is my Python graph module of choice and actually supports everything to solve this problem:

import networkx as nx G1 = nx.havel_hakimi_graph(range(1,10)*2) G2 = nx.expected_degree_graph(range(1,10), selfloops=False)

The nodes in graph G1 will have exactly the given degree sequence, while the node degree distribution in G2 is similar. Of course, you should have a look at the documentation as there may be some specific details to consider. Further on, also consider that the structure of the graph may not be what you expect. The graph generators will often not create graphs that model wireless multi-hop networks very well. Links/edges can exist between far away nodes/vertices - in fact there is no relationship between the positions and the probability to insert an edge. The diameter of the generated graph will thus be much smaller than in geometric graphs with the same parameters.

KDE with Gnome/Unity Look

2011-11-27T11:19:00.000+01:00

I like KDE and since version 4.6 it is finally usable again and feels like the 3.x versions. What I don't like is the default look and the themes that are provided by most distributions. Gnome and Unity have a much nicer design (we are not discussing the usability and customizability!). After some some tinkering around I got the following result.

Looks pretty unlike KDE, doesn't it?

Wallpaper: warty-final-ubuntu
Icons: Humanity-Dark
Desktop Theme: Ambiance
Window Decoration: Ambiance Aurorae
Color Theme: Human (don't know the source anymore)
Style: Oxygen (will probably be changed in the future)

The look is not perfect but much nicer than the out-of-the-box Kubuntu style.

Sequential Figure and Table Numbering

2011-11-25T18:12:00.000+01:00

For some publishers it is mandatory to use a sequential numbering scheme for your floats. Sequential numbering of the figures and tables can be achieved with the help of the caption package:

\usepackage{caption}

\captionsetup{%
figurewithin=none,
tablewithin=none
}

Although I prefer the format with the Chapter number as prefix, e.g., Table 2.1 this scheme makes sense when you have few floats in your document.

Margins in matplotlib Figures

2011-11-21T09:21:00.000+01:00

matplotlib creates figures that may have unnecessarily large margins around the content. You can enforce a tighter format as follows:

fig.savefig('/tmp/figure.pdf', bbox_inches='tight')

Restore Cursor Position in VIM

2011-11-20T17:27:00.000+01:00

A very handy tip is available in the Vim Tips Wiki. Your cursor will be automatically moved to the last position in the file of your previous session. Just include the following in your Vim runtime configuration file:

function! ResCur()
  if line("'\"") <= line("$")
    normal! g`"
    return 1
  endif
endfunction

augroup resCur
  autocmd!
  autocmd BufWinEnter * call ResCur()
augroup END

Named Tuples in Python

2011-11-20T16:01:00.000+01:00

As a developer that discovered Python after years of C programming, I sometimes miss the ability to access my tuples by names. In C you often times have a list of structures where you access a particular member in a loop.


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct _my_struct {
    uint8_t foo;
    uint8_t bar;
    struct _my_struct* next;
} my_struct;

int main(int argc, char** argp) {
    my_struct* list = NULL;
    my_struct* s1 = (my_struct*) malloc(sizeof(my_struct));
    my_struct* s2 = (my_struct*) malloc(sizeof(my_struct));
    s1->foo = 5;
    list = s1;
    s1->next = s2;
    s2->foo = 8;
    s2->next = NULL;
    
    my_struct* cur = list;
    uint32_t  accu = 0;
    while(cur != NULL) {
        accu += cur->foo;
        cur = cur->next;
    }
    printf("accu = %d\n", accu);
}

Please, ignore that I am not checking the return value of malloc as this is just a simple example! The member names enable that you do not have to remember the position inside the structure (respectively the offset). In fact, the compiler may reposition all members.
How can you realize this in Python? Often times you have data in a list of tuples, e.g., tuples like (foo, bar). The sum of the foo member can be calculated as follows:

tuples = list() tuples.append((5, 0)) tuples.append((8, 0)) sum_of_foos = sum([t[0] for t in tuples])

Although lists and tuples are powerful data structures of Python, the code is rather ugly. Suppose you have 100 values inside a tuple. Will you be able to remember at which position foo resides? Will you be able to remember after some refactoring when the positions changed?
Python provides named tuples in the collections module.

import collections MyTuple = collections.namedtuple('MyTuple', 'foo bar') tuples = list() s1 = MyTuple(foo=8, bar=0) tuples.append(s1) s2 = MyTuple(foo=5, bar=0) tuples.append(s2) print sum([s.foo for s in tuples])

As you can see, named tuples can make your life easier even though you have to add definitions of all tuple types. Whether the overhead is acceptable, that is up to you and the size of your software project.

LaTeX and matplotlib

2011-11-18T09:44:00.000+01:00

Although it should be the content that decides the "fate" of submissions to scientific journals or conferences, the presentation is also an important factor. While it has become a rare event that papers contain figures/graphs that have been created in some spreadsheet application, as many people nowadays use gnuplot or matplotlib, the figures may still not completely fit the document. Fonts and font sizes have to be matched. While I have no sound approach for the size, the font can be matched easily - at least with matplotlib and LaTeX.

LaTeX uses the Computer Modern font from Donald Knuth. matplotlib can be configured to use LaTeX for the typesetting. Either include the following in your matplotlib rc file:

text.usetex: true

or in your Python code:

matplotlib.rc('text', usetex=True)

This enables LaTeX processing, so that you may also use mathematical formulas as follows in your strings:

'Something $\delta \frac{foo}{bar}$'

If you require some particular LaTeX package or other LaTeX specific settings, just include them as follows:

matplotlib.rcParams['text.latex.preamble'] = '\usepackage{euler}'

If you observe that the font outside of the mathematical environments does not match the LaTeX font, it may be that matplotlib is using a non-serif font but Computer Modern is serif. Configure matplotlib and everything should be fine:

matplotlib.rcParams['font.family'] = 'serif' matplotlib.rcParams['font.serif'] = 'Computer Modern Roman'

Computer Modern should be the default serif font but it shouldn't hurt to configure it implicitly.

Example:

The labels on the axes are not in a mathematical environment while the tick labels are set in the Euler font. The image was created by the following code in the IPython shell started with the -pylab parameter:

matplotlib.use('Agg')
matplotlib.rc('text', usetex=True)
matplotlib.rcParams['text.latex.preamble'] = '\usepackage{euler}'
matplotlib.rcParams['lines.linewidth'] = 2
matplotlib.rcParams['font.family'] = 'serif'
matplotlib.rcParams['font.serif'] = 'Computer Modern Roman'
matplotlib.rcParams['font.size'] = '24'
fig = figure()
ax = fig.gca()
ax.plot(pylab.linspace(0, 100, 101))
ax.set_xlabel('x-axis')
ax.set_ylabel('y-axis')
fig.savefig('/tmp/example.png')

What Every Computer Scientist Should Know About Floating-Point Arithmetic

2011-11-16T14:31:00.000+01:00

David Goldberg published a fundamental paper about the accuracy of floating point arithmetic in 1991. Indeed, every computer scientists should have read it and understood the problem. If haven't, here is the PDF.

LaTeX Figure Filenames

2011-11-15T21:24:00.000+01:00

The grffile is a LaTeX package that enables support for some unsupported figure filename patterns. For example the following filename will produce an error due to the multiple dots: data_p=1.0.pdf. Quite helpful but this feature should have been enabled by default.

Know Your Distributions

2011-11-14T09:29:00.000+01:00

When I was recently evaluating and fitting some data, I found some nice documents that give an overview to statistical distributions.

Univariate Distribution Relationships by Leemis et al. (PDF can be easily found via Google)
Probability Cheat Sheet by Peleg Michaeli
Engineering Statistics Handbook by NIST

Of course, Wikipedia provides also some concise information.

Terminal Emulator

2011-11-14T09:01:00.000+01:00

Ever had to debug or communicate with an embedded system over the serial line? Are you happy with minicom or putty? Try hterm! It may not be open source but it puts all options in plain view, you can show the output a binary/ascii/hex, and it is available for Linux and Windows thanks to the wxwidgets toolkit.

Forcing Float Positions in LaTeX

2011-11-13T23:29:00.000+01:00

One of the common annoyances for LaTeX beginners is that you are not explicitly specifying the position of floating environments, e.g., figures and tables. There are some ways to force the positions like the [h] option but none is really perfect.
The placeins package defines the \FloatBarrier command, beyond which floats may not pass. In addition, you may also specify that floats are always positioned in the section where they are referenced.

Protocol Headers in LaTeX

2011-11-13T23:10:00.000+01:00

Ever had to include a figure with a protocol header in your scientific publication or thesis written in LaTeX? Use the bytefield package to produce a professional output and avoid bitmap or vector images created in external programs. As you stay within LaTeX, your fonts will match perfectly. The package may also be abused to typeset other types of figures, e.g., a Gantt chart.

Python for Scientifc Research

2011-11-13T23:01:00.000+01:00

Python certainly has established itself as an all-purpose language with a rich module library. We use Python for mostly everything in the DES-Testbed: running experiments, evaluating data, and plotting. Unfortunately, some developers still do not know about the most powerful modules and write everything from scratch - reinventing the wheel.
Thus everyone in the research domain should have a look at the following tutorials:

numpy: arrays, matrices, and histograms
scipy: mathematical algorithms, convenience functions, distributions, fft, image processing, fitting, ...
matplotlib: 2D plotting library (but also includes some 3D plots)

The combination of numpy, scipy, and matplotlib is a good substitute for R and Matlab. There are also several gnuplot modules but I never found one I liked. Although I have to admit, that gnuplot plots look somehow more professional but this is just a matter of individual taste.

And do not forget one of the most important rules of scientific publishing: avoid bitmap images, use vector formats!

Essential Unix Tutorials

2011-11-13T22:38:00.000+01:00

Bruce Barnett has compiled some nice tutorials, e.g., about sed, awk, and shell quoting. The tutorials are a little bit older but still relevant and every novel shell script developer should read them.

moreutils

2011-11-13T22:34:00.000+01:00

The moreutils package extends the standard tool set of shell script developers by some useful programs.

combine: combine the lines in two files using boolean operations
ifdata: get network interface info without parsing ifconfig output
ifne: run a program if the standard input is not empty
isutf8: check if a file or standard input is utf-8
lckdo: execute a program with a lock held
mispipe: pipe two commands, returning the exit status of the first
parallel: run multiple jobs at once
pee: tee standard input to pipes
sponge: soak up standard input and write to a file
ts: timestamp standard input
vidir: edit a directory in your text editor
vipe: insert a text editor into a pipe
zrun: automatically uncompress arguments to command

I am an avid user of ifdata!

Bitcoin Introduction

2011-11-13T22:29:00.000+01:00

Jeffrey Paul is giving a talk at Freie Universität Berlin about Bitcoin, the digital Peer-to-Peer currency.

Wednesday, 23.11.2011, 18:00
Computer Science Lecture Hall
Takustraße 9
14195 Berlin

/tmp as tmpfs

2011-11-13T22:22:00.000+01:00

Bastien Roucaries started a very interesting discussion on debian-devel about the decision to mount a tmpfs as /tmp and the associated problems that arise. Some programs require significantly more memory in /tmp than is available.

curses Based File Manager

2011-11-13T22:16:00.000+01:00

ranger is an interesting curses based file manager with a multi-column display (Miller Columns). An interesting alternative for the Midnight Commander.
ranger also provides a vim-like console and hotkeys.

Code Obfuscation

2011-11-13T22:10:00.000+01:00

International Obfuscated C Code Contest is accepting submissions again. Write code that simply looks funny and is unreadable but still has some function. For example, the last contests submissions include tiny operating system and flight simulators.

Hiding malicious code in innocent programs

2011-11-13T21:59:00.000+01:00

The Underhanded C Contest annual contest where contestant may submit solutions for a given problem. The catch: the code has to look innocent but a specific malicious behavior has to be hidden. The submissions a very nice exercise for code reviewers - although some submissions would not pass QA due to their violation of common coding standards.

About this Blog

2011-11-01T22:50:00.000+01:00

What's this Blog about and why does it exit? In the last years I wrote several tutorials and answered hundreds of questions for my students. As I am currently (finally!) finishing my PhD, my time at Freie Universität Berlin slowly comes to an end. I am migrating the information to this blog so that it is not lost in the future if no one is taking care of our Wikis, Mailinglists, etc. In addition, it serves as my personal information dump that may be of use for someone else.