Wednesday, November 30, 2005

 

Problems too difficult to solve?

It is fascinating to me that even in this day and age there are still problems we cannot solve at all, or problems we don't know how to solve easily. On the other hand, if we knew how to solve all problems there wouldn't have been many challenges now, would there? Keep in mind that I'm talking more from an I.T background than philosophical. In other words I'm talking about the problems we can (or try to) solve with computers.

Let me explain my ranting about problem solving:
My wife is an auditor and I'm a software programmer. When she came across a specific problem the other day, she thought that I would be her helping hand, until I discovered that it's actually not that easy to solve her dilemma.

The problem is the following:
You have a number of invoice totals, as well as one or more grand totals. Some (or all) of the invoices make up some (or more) of the grand totals when you add them together. You need to figure out which invoices make up which totals. I suppose this is needed mostly because of lost or incomplete documentation, but it's the job of the auditors to match these totals.

Consider this example:
Invoice 1: 35.55
Invoice 2: 865.23
Invoice 3: 87.29
Invoice 4: 63.99

Total 1: 99.54
Total 2: 952.52

In this example, we could say that Total 1 is made up of Invoice 1 and Invoice 4 (35.55 + 63.99 = 99.54) and Total 2 is made up of Invoice 2 and Invoice 3 (865.23 + 87.29).

The example above is quite easy. You can solve it by just looking at the values. But consider 100 invoices for example…. Computer to the rescue… or so we thought!

I first tried a brute force way, but the number of combinations just becomes unmanageable for a lot of invoices. If you've got 4 invoices, the total number of combinations to make up a total is 15, but if you've got just 20 invoices, the number of possibilities jump to 1048575! (go figure this one!).

I then tried a more fuzzy approach like genetic algorithms. This approach can get me close to the desired result, but rarely solves the problem completely.

After a bit of investigation, I realized that my problem is very similar (if not exactly the same) as the famous traveling salesmen problem. This opened up a whole can of worms! The computing industry has done a lot of research on problems like this. There is even a whole complexity theory!

I'm not going to go into too much detail now, as it's almost a textbook on its own. My point is just that the more we find out, the more we realize how little we know (if that makes sense!)

Some problems are considered impossible to solve, others can be solved but is very hard. This means that with our finite computing resources, it is not viable to solve the problem in the time we would like. I can for example solve my wife's problem by running 10 computers for 1 week, but it would be futile if they need the answer tomorrow.

One way to try and solve these problems is basically to throw computing power at it. I suppose this is why we invented grid computing. Consider for example the SETI@HOME project. (I suppose this is not the best example for my problem, as SETI has more to do with processing huge amounts of data). A better example might be solving of protein-related diseases like the one also hosted on BOINC. (BOINC actually now hosts a couple of grid computing problems including SETI).
Although throwing more computing power at problems is a good idea, the fundamental problem is that it will always be a limited resource. One thing that might come to the rescue here is something that my little brain still can't grasp and that is quantum computing.

In the computing industry, some technologies actually rely on the fact that some problems are very difficult to solve. Consider most of the encryption standards. They rely on the fact that it is very difficult to compute prime numbers quickly. What do you think will happen if somebody comes up a formula to compute all prime numbers?

Some good advice from me: If you discover a way to solve NP-Complete problems quickly, I suggest to make a visit to the patent office before you tell your buddies!

Some related links if you are interested:
[The software said it required Windows 95 or better, so I installed Linux]

Monday, November 21, 2005

 

OpenVPN on Suse 10

I work for a company where we do projects on-site for clients. Some of these projects result in us being away from the office for long periods of time. Being in the "connected" world we are, it is very helpful to connect to our company network at all times.
I suppose there are several options for connecting to a private network. One example would be dialup through RAS (Remote Access Server). One of the downsides of this approach is that it actually cost me money to connect to the other network (yes, we do pay for all telephone calls..even local ones). The target RAS server could "phone" me back, but the point is that someone still pays for the actual call.
This is where VPN (Virtual Private Network) comes in handy. A VPN is a way for one to establish connection to a private network in a secure way if you are already on a public network (like the internet). There are various options when it comes to VPN solutions. We are currently using OpenVPN at our company. This is an open-source project licensed under the GPL. I will describe my scenario by example:

My company (Company A) exposes an OpenVPN server on the internet, which means anyone can actually connect to this server from anywhere. I'm currently sitting at Company B, which allows me access to the internet through an authenticated proxy. This means that I could access the OpenVPN server at Company A. The OpenVPN server is conveniently exposed on the SSL port 443 and the communication is encrypted. This means that the proxy (or any other tool) at Company B cannot "see" what we actually communicate.
To gain access to the private network, one also needs client-side OpenVPN software, which will actually establish connection with the OpenVPN server at Company A. In my case, this client is configured to connect to the OpenVPN server at Company A, using the http proxy at Company B.
To prevent anyone from connecting to the VPN server (and therefore gaining access to Company A's private network), we do authentication and encryption via a public/private key pair. These keys were generated for me at Company A. The private key is also encrypted with a password. Whenever I startup my VPN client, it requests the encryption password and then uses the public/private key pair to authenticate me to the target VPN server (public / private keys, authentication and encryption could be a whole new blog in it's own right!).
When connection is established between client and server in a VPN environment, the client-side mimics a network card in the Operating System through software only. This means that it exposes a network interface to applications, but this network interface is not a physical network card in the system. This special network interface just accepts IP traffic and routes everything over the VPN to the VPN server. This makes integration from client-side applications trivial. The software network interface is implemented as a TUN / TAP interface. There is support for such a module in most operating systems.

I always had the OpenVPN client-side software installed and running on my Windows O/S. I know wanted to install this on my new Suse 10 O/S.
This is basically what I did:
  1. I couldn't find an OpenVPN installation RPM or package on the Suse DVD and therefore downloaded the source distribution from http://openvpn.net.
  2. The installation instructions required OpenSSL and LZO to be installed. OpenSSL was installed by default, but I had to add the OpenSSL development libraries with Yast as well.
  3. LZO was also installed, but I also needed the development libraries, which I downloaded and installed from http://www.oberhumer.com/opensource/lzo/
  4. According to installation instructions, I configured my OpenVPN build with: ./configure --with-lzo-headers /usr/local/include/ --with-lzo-lib /usr/local/lib/ - which worked fine.
  5. Build the source with make, which also worked fine.
  6. Installing the binaries with make install failed with the following error:
    /usr/bin/install -c 'openvpn' '/usr/local/sbin//usr/local/include/-openvpn'
    /usr/bin/install: cannot create regular file `/usr/local/sbin//usr/local/include/-openvpn': No such file or directory
    make[1]: *** [install-sbinPROGRAMS] Error 1

    Still not sure why this happens, as it seems like the paths are screwed. I gave up on trying to fix this, as I've got the binary built in the local directory and it seems that I can run it (I can always copy this to another directory if I wanted to).

According to the installation instructions, one has to do the following to get the TUN/TAP driver working under Linux:

(1) make device node: mknod /dev/net/tun c 10 200

(2a) add to /etc/modules.conf: alias char-major-10-200 tun

(2b) load driver: modprobe tun

(3) enable routing: echo 1 > /proc/sys/net/ipv4/ip_forward


Note that either of steps (2a) or (2b) is sufficient. While (2a)
only needs to be done once per install, (2b) needs to be done once
per reboot. If you install from RPM (see above) and use the
openvpn.init script, these steps are taken care of for you.

This is where my problems started:
  1. I already have a device called /dev/net/tun
  2. I don't even have an /etc/modules.conf file in my Suse installation!
  3. It looks like my TUN driver is loaded:
modprobe -l | grep tun.ko
/lib/modules/2.6.13-15-smp/kernel/drivers/net/tun.ko

When running the OpenVPN client, it connects successfully to the server, but when it tries to start the TUN/TAP interface, I get the following error:

Cannot allocate TUN/TAP dev dynamically

I searched the web, and struggled with this for a while, until one of my colleagues pointed me in the direction of an already built OpenVPN RPM for Suse 10: ftp://rpmfind.net/linux/SuSE-Linux/i386/update/10.0/rpm/i586/openvpn-2.0.2-2.2.i586.rpm

I installed this and what do you know.. everything just worked.. I can connect and use my company's private network in my Linux O/S!
Being a software developer I like to know why something worked after I struggled with a problem for a while, but in this case I cannot explain why the RPM works, but my custom build does not. This is quite frustrating - How can I figure out what exactly an RPM does (besides just copying binaries)?
I'll see if I get time to look at this again, but at least it's working.

Until next time, when I hopefully get to my VMWare attempt.

[What's the difference between a C++ programmer and God? God knows he's not a C++ programmer]

Monday, November 14, 2005

 

Windows to Suse - Round 2

After my previous hard work with changing my Linux fonts, I had to re-install Open Suse 10 on my laptop, losing everything I already did!

I suppose it was partly my own fault, but I learned a valuable lesson anyway.

This is what I did before:
As I’m using Windows currently, I used Partition Magic to create empty partitions for my Linux installation. I then hibernated my Windows and went ahead with my Linux installation. During the Linux installation, I formatted the partitions with the Reiser file system and configured everything.

I could then switch back between Linux and Windows without any issues, until I shut-down Windows for the first time after my Linux installation. This broke my Linux with file system errors. The Reiser file system tried it’s best to recover from this, but with no result. The only explanation I’ve got for this is that Windows wrote some data to the Linux partitions when I shut it down. I suppose it did this because it previously knew about those partitions (which I basically changed at runtime because Windows was hibernated).


I repeated my installation, but this time I just deleted the partitions in Windows. This caused my disk to just have a segment of unallocated space. I then shutdown Windows properly and installed Linux. During the installation I created and formatted the Linux partitions. After this, my Linux and Windows were happily sharing the same disk… at last!

I obviously had to re-configure my fonts (as described in my previous blog entry).

I improved my Linux installation with the following:

  1. I installed my WiFi PCMCIA network card. This was surprisingly a no-brainer. I plugged the device (Gigabyte 802.11) in while Linux was running and it detected the new hardware. I just configured the SSID and WEP keys we use at our company and I could join the network. Everything seems to be working fine, except for the signal strength indicator (LED lights) on the PCMCIA card itself. It shows no signal, although I can browse the network. Wonder if this has to do with the driver? I’ll look at this again in the future. My first idea is to get it working; I’ll then make it work better ;-)
  2. I installed OpenOffice 2. The default Open Suse 10 ships with some 1.9.x version of OpenOffice, but I had the installation files for 2.0, so I did not select the default installation of OpenOffice 1.9.x. I also learned an interesting RPM feature with the installation of OpenOffice. The tarball you download consist of a lot (+- 20) RPM files in the same installation folder…now where do I begin? Should I just try to install any one and try to get the dependencies right…this could prove to give you a well-deserved headache! After a bit of googling, I got the following idea: rpm -ivh *.rpm which just sorts out all the dependencies itself and install in the correct order. After this my OpenOffice was also working fine (at least from a quick glance).
  3. I also installed the Exhange plugin for Evolution, which I would like to use to read my e-mail from an Exchange server at a client. I first tried to just setup the account, but there was no Exchange option as a server type. I then downloaded the plugin from the Suse site under the Gnome utilities (as Evolution is a Gnome app). After this I had the option of selecting the Exchange server, but I haven’t setup the account yet. I’ll get to this soon.

Will keep you updated with my progress..

[Software is either in beta, or obsolete, or both]

Wednesday, November 09, 2005

 

Windows fonts on Suse Linux

I've always been a supporter of the Linux OS. This is not because I'm an expert, but rather because I believe in healthy competition. Users need the freedom to choose.
I've been using M$ Windows myself for a couple of years now, mainly because I've started out using DOS then on to Windows 3.1 (the DOS with icons ;-) ), 98, 2000, XP.
During this time, I've accumulated a number of tools and utilities on Windows which I use for software development. I got so used to the tools and environments that I consider myself to be more productive on the Windows environment than on others.

I've always had a dual-boot on my laptop, but I basically just "checked-out" latest versions of Linux distros. Last week I installed OpenSuse 10.0, the opensource version of Novell's Suse Linux distro. I must say that I was pleasantly surprised with the quality and effort these guys make in order to get Linux mainstream for end users. I still feel that it would be ok to introduce Linux to a normal end-user if it is the first OS they see (first interaction with a computer), but if you have someone who's been using Windows for a while, they could still find it frustrating to take the plunge. I'll justify this statement through a couple of blog entries as I share my experience to (possibly) migrate to the Linux environment.

I'll start this experience with my installation and setup on my Dell Inspiron 5150 laptop.

I installed OpenSuse 10 from a DVD. The installation went fine (and I'm really impressed with the installer), until the first reboot to configure the system. The OS failed to boot, with a number of error messages. I do not really have the experience to find the problem in detail, but using the "trial-and-error" mentality, I re-installed but chose the installation without ACPI (Advanced Configuration and Power Interface) support. This time everything went fine.

I then started to use my new installation a bit. I was impressed with the interface and applications they ship with the installation, but there was something wrong with the whole interface. The text was blurry, making it difficult to read. I started playing around with some settings, but could not really improve the situation. It's not that I want my Linux installation to look (and work?) exactly like my Windows, but I must admit that Windows has a very clear and crisp interface. I'm using a 1400 x 1050 resolution on both Linux and Windows.

My first attempt to improve the situation was to install the latest Nvidia drivers for my graphics card for Linux. This did not really improve the general visual experience.

I then started playing around with the fonts and read something interesting on the web. It has to do with the rendering of fonts on Linux. You need good TrueType fonts, which renders well for lower resolution media (like screens). You also need a good renderer for these fonts.
The best way to render TrueType fonts are by means of True Type Byte Code Interpreters
(BCI). Most of this technology is patented by Apple, but Linux supports a FreeType interpreter which implements this technology. Luckily, this interpreter (freetype2) is bundled with OpenSuse 10.0, which means that it should be able to interpret the fonts, I just need to get good TrueType fonts - and what better place than Windows itself. Because I've got a license for my Windows installation, I just copied (imported) all the Windows TrueType fonts into Linux.
I then followed the instructions on the OpenSuse site to change the default fonts of Linux windows to match those of M$ Windows (Windows makes heavily use of the Tahoma font).
I also had to switch off anti-aliasing for small-sized fonts, as this make them look bad.

I must say that after this, I'm one step closer to start using Linux. I can at least sit and work with X for more than an hour without my eyes hurting!

In the next blog I'll tackle my next obstacle (not sure what this is yet ;-) )

[Computers are like Air-Conditioners.
They don't work properly, if you open windows.]


Tuesday, November 08, 2005

 

Why Cheetah?

Two of my friends maintain their own blogs, so you could say that I was inspired by them to create my own, or maybe to inspire them to blog about more usefull stuff :-) (for obvious reasons I won't mention their names here..)

Firstly I should maybe clarify why the blog is called "Cheetah", and no, I'm not an animal laying under the African sun with my WiFi laptop.. wait.. that doesn't sound too far off? I am a supporter of a local rugby team in South Africa called: (you guessed it), Cheetahs.

There was nothing special to being a Cheetah supporter, until the 22nd of October 2005 when they won the Currie Cup for the first time in 29 years! My wife and I witnessed this historic event and are very proud. (You see, we're not sure if we'll have to wait another 30 years for this to happen!).

[There are only 10 types of people in this world: those who understand binary and those who don't.]

This page is powered by Blogger. Isn't yours?