Friday, March 28, 2008

ASUS EEPC horror story

Last week I was at the Tridentcom conference in Innsbruck. There, while attending a talk, I saw first-hand the horror of a presentation gone completely wrong, the discomfort of the audience, and the pain of an embarrassed speaker as his ASUS EEPC failed miserably. The presenters beautiful slides were cut horizontally (about 30% of the lower part of each slide was missing) because the ASUS EEPC could not drive the overhead projector properly. Every other laptop, including old clunky student-budget ones, running Windows , Linux, and Mac OS, were successful in beaming presentations. But not the ASUS EEPC.

There are many objective reviews of laptops on the Internet based on specifications, design, speed, etc. They try to compare products side by side so that potential buyers can choose the product that is best for them. Still, somethings are considered standard and not even mentioned - like the assurance that the power adaptor will charge the laptop's battery, the battery won't burst, the USB ports will work, and the VGA output will work. Seasoned customers are smart enough to get a mix of online and off-line opinions about a product before buying it. But sometimes when products are just released, it is hard to ascertain whether a product will serve its purpose down the road. I hope this EEPC horror story gives folks some additional information before they buy it.

Its all nice to tout the small, cheap ASUS EEPC. But seriously, didn't VGA-out technology mature like 15 years ago? And ASUS cannot even get this right in 2008? My 2 cents - get a second or third hand Pentium 3 laptop or something instead.

Monday, March 24, 2008

Recursion and "Towers of Hanoi"



Figure 1: rules of the Hanoi puzzle. Click to enlarge

I was thinking of my first algorithms class and remembered the "Towers of Hanoi" problem. This problem is used to introduce the concept of recursion. It can also use the stack data structure (LIFO) quite naturally, making it a universal favorite in assignments. An Internet search yields 1000's of websites discussing the problem. Heres adding yet another discussion to this timeless classic!

Problem Setup
Here is the setup and the rules of the Hanoi puzzle
  1. There are 3 towers labeled 0,1, and 2.
  2. There are N circular discs, each of different radius, that are initially placed around tower 0.
  3. Any circular disc can only be placed above a disc of larger radius, or as the first disc of the tower.
The objective is to move the N discs from tower 0 to tower 2 following the rules mentioned above.

Figure 1 explains the problem graphically and shows the rules of the Hanoi puzzle.

Solution

In order to solve the puzzle recursively, look at Figure 2. The first requirement on moving the largest (red) disc from tower 0 (source tower) to tower 2 (destination tower) is that there should be no discs over this red disc. This means that the other 2 discs (green and yellow) should be moved to tower 1 (auxiliary tower) and the setup should be in state 1. Then, the red disc can be moved to tower 2 (state 2).

Now the problem is reduced to one with just 2 discs (yellow and green). These need to be moved from tower 1 (the source) to tower 3 (the destination) using tower 0 as a temporary go-between (auxiliary tower).


Figure 2: Top level steps. Click to enlarge


But wait, how do we accomplish the transition from state 0 to state 1?
Figure 3 shows the intermediate steps to accomplish this. The aim is to move the green and yellow discs from tower 0 (source) to tower 1 (destination) using tower 2 as the auxiliary tower.

Figure 3: Mini-steps from state 0 to state 1. Click to Enlarge

So the high-level idea is to have a function that recursively places the discs in the appropriate towers. This will be clear in the C++ "Hanoi" function shown below. I have used STL data-structures (vector and stack) in order to simplify the explanation.




#include <stack>
#include <vector>

#include <iostream>

using namespace
std;

//Each Tower is a Stack (LIFO)
vector <stack <int>*> towers; //Vector of pointers to stacks

//Printing the tower contents. This is only for eye-candy.

void PrintTowers()
{

stack <int> tempStack;
for
(int ii=0;ii<towers.size();ii++) {

cout << std::endl<< "Tower " << ii <<": ";
while
(!towers[ii]->empty()) {

tempStack.push(towers[ii]->top());
towers[ii]->pop();
}


while
(!tempStack.empty()) {
towers[ii]->push(tempStack.top());

cout <<tempStack.top()<<" ";
tempStack.pop();
}

cout << " <-- TOP";
}
}


//Move from Tower "from" to Tower "to"
void MoveDisc(int from, int to)
{

towers[to]->push(towers[from]->top());

towers[from]->pop();
}


//Recursive function Hanoi - the most interesting function
//When this function exits, it has moved the lowest
//Tower (as specified by numDiscs) from the sourceTower to the
//destTower using the auxTower as a temporary holder
void Hanoi(int sourceTower, int destTower, int auxTower, int numDiscs)
{


if
(numDiscs==0)
return
;
Hanoi(sourceTower, auxTower, destTower, numDiscs-1);

MoveDisc(sourceTower,destTower);
Hanoi(auxTower,destTower,sourceTower,numDiscs-1);
}


int
main()
{

int
numDiscs;

cout << "Please enter the number of discs: ";

cin >> numDiscs;

//Initialize the Towers by allocating 3 stacks
for (int ii=0;ii < 3;ii++)

towers.push_back(new stack<int>);

//Initial condition: all the discs are on Tower 0
for (int jj=numDiscs-1;jj >=0 ;jj--)

towers[0]->push(jj);

//Print setup of towers
cout <<std::endl<<"Initially";

PrintTowers();

//Enter recursive function here
Hanoi(0, 2, 1, numDiscs);

//Print setup of towers
cout <<std::endl<<"Finally";
PrintTowers();

//Don't forget to delete the vector of stacks.

for (int ii=0;ii < 3; ii++)

delete
towers[ii];

cout << std::endl << "Done.";


return
0;
}

Saturday, March 22, 2008

Our world needs electricity, lots of it.



(Click to enlarge)

I visited the UN data website and downloaded data about the total electricity production of countries and matched it with their populations in order to obtain the electricity produced per 1000 inhabitants (for each country). I have plotted a histogram of this in the figure above.

This histogram is disturbing.

The smaller issue is that inhabitants of most countries have lesser electricity than the world average. This means that a few energy-rich countries are producing (and probably consuming) most of the world's electricity. I have marked some of the representative countries on the histogram. There is a table at the end of this post containing the parsed data in case you want to look up your own country and/or use the data (After citing the UN data source, off course).

The bigger issue is that countries with low electricity per capita (bars toward the left of the figure) are striving to move the per capita electricity production higher to improve quality of life. For example, both India and China are lower than the world average. And I have the impression that these countries are really looking to improve their citizen's living conditions. And remember, populations are increasing too (see one of my previous posts), making it necessary to pump up electricity production even faster.

Producing more electricity is a positive development. But the problems associated with increasing production are the issue here. Here are some questions:
  1. Where are we going to get the energy to increase electricity production so rapidly?
  2. What will be the environmental cost of creating so much additional capacity? I hope it is renewable energy. Hope. Hope. Hope.
  3. Or, does this analysis indicate that even in the next decades electricity will be a premium, for-the-well-off, limited quantity luxury given the lack of such a massive energy source?

Tough cookies.

We really need a breakthrough with some new technology here.



Here is the table containing data used in the analysis.
Country, million kWh per 1000 inhabitants (German notation: "," is the decimal point)

Afghanistan 0,019507403
Albania 0,529214445
Algeria 0,219150336
American Samoa 0,936753525
Angola 0,032618392
Anguilla 1,036227154
Antigua and Barbuda 0,325148424
Argentina 0,727408376
Armenia 1,07765584
Aruba 1,457768448
Australia 2,492244294
Austria 2,280999506
Azerbaijan 0,617455344
Bahamas 1,40738335
Bahrain 2,551090802
Bangladesh 0,027811644
Barbados 0,739895798
Belarus 0,819169464
Belgium 1,54779036
Belize 0,174199589
Benin 0,006949106
Bermuda 2,726961075
Bhutan 0,549439336
Bolivia 0,149749265
Bosnia and Herzegovina 0,69957433
Botswana 0,118195712
Brazil 0,49861704
British Virgin Islands 0,454215116
Brunei Darussalam 2,030329213
Bulgaria 1,545853099
Burkina Faso 0,005598074
Burundi 0,004199119
Cambodia 0,013614697
Cameroon 0,049170704
Canada 3,765512578
Cape Verde 0,157851016
Cayman Islands 2,346954443
Central African Republic 0,010259031
Chad 0,002858379
Chile 0,798215316
China 0,386906459
Colombia 0,296546128
Comoros 0,006266434
Congo 0,025762836
Cook Islands 0,57208238
Costa Rica 0,44965969
Croatia 0,849392177
Cuba 0,379683488
Cyprus 1,34517727
Czech Republic 1,708438639
Democratic People's Republic of Korea 0,402276274
Democratic Republic of the Congo 0,043802793
Denmark 2,471503772
Djibouti 0,146728575
Dominica 0,353841391
Dominican Republic 0,582812306
Ecuador 0,273103278
Egypt 0,280151791
El Salvador 0,184723191
Equatorial Guinea 0,026854067
Eritrea 0,036892038
Estonia 1,702729723
Faeroe Islands 1,804792034
Falkland Islands (Malvinas) 3,025210084
Fiji 0,199264292
Finland 3,139151247
French Guiana 0,728790884
French Polynesia 0,442041685
Gabon 0,325406584
Gambia 0,018552543
Georgia 0,977777798
Germany 1,51273341
Ghana 0,065320583
Gibraltar 1,202749141
Greece 1,20759618
Greenland 1,844280122
Grenada 0,304075563
Guadeloupe 0,937493585
Guam 3,274604022
Guatemala 0,162208554
Guinea 0,022771058
Guinea-Bissau 0,01315024
Guyana 0,415837246
Haiti 0,023772922
Honduras 0,212566084
Hungary 0,856203515
Iceland 5,200654647
India 0,126738013
Indonesia 0,116874477
Iran (Islamic Republic of) 0,639435492
Iraq 0,300043035
Ireland 1,518598487
Israel 1,541832479
Jamaica 0,425354403
Japan 2,168335174
Jordan 0,389966498
Kazakhstan 1,231640364
Kenya 0,034242581
Kiribati 0,032607632
Kuwait 4,02037037
Kyrgyzstan 0,710476911
Lao People's Democratic Republic 0,08121598
Latvia 0,940571111
Lebanon 0,601385281
Liberia 0,054622645
Libyan Arab Jamahiriya 0,865970274
Lithuania 1,330189073
Luxembourg 3,631083653
Madagascar 0,012230063
Malawi 0,01376068
Malaysia 0,829451232
Maldives 0,165934635
Mali 0,0098182
Malta 2,28753381
Marshall Islands 0,303244006
Martinique 1,000262695
Mauritania 0,058047217
Mauritius 0,554314346
Mexico 0,490100396
Mongolia 0,322392649
Montserrat 1,776830135
Morocco 0,172225006
Mozambique 0,115377076
Myanmar 0,024954518
Namibia 0,034659007
Nauru 0,989021857
Nepal 0,022551405
Netherlands 1,3307455
Netherlands Antilles 1,126657796
New Caledonia 1,528705938
New Zealand 2,168356638
Nicaragua 0,099770455
Niger 0,007916051
Nigeria 0,041604152
Niue 0,612745098
Oman 1,189848435
Pakistan 0,123101766
Palau 2,583594177
Panama 0,508432302
Papua New Guinea 0,117468448
Paraguay 1,25604174
Peru 0,228699463
Philippines 0,185003073
Poland 0,844522287
Portugal 1,269159686
Puerto Rico 1,370991383
Qatar 3,553189833
Republic of Korea 1,389956686
Romania 0,876196974
Russian Federation 1,619416414
Rwanda 0,004223616
Saint Helena 0,625097672
Saint Kitts and Nevis 0,407016973
Saint Lucia 0,40932771
Saint Pierre and Miquelon 4,254648598
Saint Vincent and the Grenadines 0,29377943
Samoa 0,157741576
Sao Tome and Principe 0,032760677
Saudi Arabia 1,420230761
Senegal 0,048341849
Seychelles 1,110695412
Sierra Leone 0,008771297
Singapore 2,347562131
Slovakia 1,624096551
Slovenia 1,496430224
Solomon Islands 0,02963471
South Africa 0,835171394
Spain 1,888334973
Sri Lanka 0,126093294
Sudan 0,030204543
Suriname 0,859729307
Swaziland 0,122718045
Sweden 3,694381387
Syrian Arab Republic 0,398277093
Tajikistan 0,678298553
Thailand 0,52931205
The former Yugoslav Republic of Macedonia 0,767583489
Timor-Leste 0,042163059
Togo 0,007694068
Tonga 0,080514488
Trinidad and Tobago 1,118059532
Tunisia 0,326482221
Turkey 0,532316671
Turkmenistan 0,811252681
Turks and Caicos Islands 0,163538984
Uganda 0,010743706
Ukraine 1,119794335
United Arab Emirates 3,827701301
United Kingdom 1,358755508
United Republic of Tanzania 0,01426794
United States of America 3,558514712
Uruguay 0,629035396
Uzbekistan 0,440301803
Vanuatu 0,055719101
Viet Nam 0,140517355
Western Sahara 0,131690083
Zambia 0,196892977
Zimbabwe 0,178739129

Wednesday, March 19, 2008

GENI and Networking Research: Inside out, or outside in?

The Global Environment for Network Innovations (GENI) idea is to build an experimental facility that researchers can use to experiment with new communications and networking technology, distributed systems, cyber-security aspects, and applications. A couple of weeks ago I attended a talk given by Craig Patridge, chief scientist at BBN technologies. Craig is heading the GENI project office tasked with implementing GENI. He is an engaging speaker and got me thinking about the merits of building GENI.


GENI is a sort of first for the National Science Foundation (NSF) and the network research community. NSF occasionally funds large infrastructure projects like building astronomy telescopes and particle accelerators but this is the first time that a networking infrastructure is being funded. The interesting thing is that the infrastructure comes first and then protocols or services follow. Moreover, the infrastructure will be built based on requirements specified by the research community. Is this the future of network research?


The current Internet is an engineering marvel. It scaling property is absolutely remarkable - 100s of millions of hosts in a federated environment with completely different underlying access technologies just work. Then the creative engineers and innovators come in to shape the Internet APIs (e.g. IP communication stack) into myriad applications - email, VOIP, P2P, Web 2.0, digital libraries, and whatever else they can think of.


The Internet was first built by engineers, and later scientists highlighted several flaws in its design. This has sometimes served as a good feedback loop for refining the Internet over time. For example, security researchers have continually unearthed security holes in the IP socket stack. Scientists, coming from the outside, study the insides of the Internet and contribute to refining the already-built Internet.


But can researchers with limited engineering experience design a new communication infrastructure such as the GENI infrastructure? I very much doubt this. Researchers are seldom successful in building viable commercial technologies. They are very smart but usually focused on one or few problems. It is not at all clear if GENI could deliver the next Internet.

But lets back-pedal a little. Is GENI supposed to be building the next Internet? Answer: perhaps not. But what I find troubling about the GENI (or FIRE - the European counterpart) is that there is that almost the whole OSI stack - network, transport, session and applications - is supposed to come from the research community. I really really wonder who is going to write all this up? Off course there can be a module-based approach to plugging in pre-existing pieces into GENI, but then how is this Internet design revolutionary, and does this justify building GENI in the first place? Why not stick with something more real like PlanetLab?


I don't believe scientists can build another Internet from the inside out. Shouldn't building a new network, from the inside, be left to the engineers?

Sunday, March 16, 2008

Bullish about mobile/cellular networks

(Click to enlarge. Source: UN data)

We all know that cellular mobile networks are rapidly expanding all over the world - in fact the rate of adoption of cellular mobile technology has been faster than that of the Internet. I am bullish about this technology's role in human development. The bar-graph says it all. Amen!

Saturday, March 8, 2008

The Internet gets a heavy tail

(Click to enlarge)

The above plot shows the growth of the Internet in the World, again from UN data. There are 3 histograms (2004, 2001, 1998) of the number of countries (Y axis) vs. the size of the Internet population in the countries (X axis). I have left out the countries with less than 1m users because they are the vast majority in the data - partly due to low Internet adoption in backward areas and partly due to small populations.

The key points seen immediately
  1. The number of Internet users is (surprise surprise) growing rapidly over the years.
  2. USA leads every other country, but since the total US population is only about 300m (see my previous post), US Internet users' growth is saturating.
  3. On the other hand, China is growing very quickly. I suppose by 2008 (present) the number of users there must have got close to the US number (if not ahead).
But lets look at a more holistic trend here. This is the "long fat tail" that shows up in the 2004 data - the bars concentrated on the left hand side have started spreading out to the right in the 2004 histogram. This means that the Internet is increasingly becoming multinational with a significant representation of people from many countries, bringing up these questions
  1. Where is the Internet content suitable for people from different cultures and not just western cultures?
  2. Are we doing enough to localize Internet applications for these large multicultural groups joining the Internet?
Finally, for those interested, here is a table showing the number of Internet users, as reported by the most recent data from UN Statistics (2004). I have ranked the countries based on the number of Internet users in the rightmost columns of the table. Again, if you look at the top 10 countries in this table, only 2 have a high number of English native speakers. In addition, 5 out of the top 10 countries are not "Northern hemisphere western countries".

Please use this data only after citing the UN source.




Country #Internet users Rank (2004)
United States 185000000 1
China 94000000 2
Japan 64160000 3
United Kingdom 37600000 4
Germany 35200000 5
India 35000000 6
Korea, Republic of 31580000 7
Italy 28870000 8
France 25000000 9
Brazil 22000000 10
Canada 20000000 11
Russian Federation 16000000 12
Indonesia 14508000 13
Spain 14332800 14
Mexico 14036500 15
Australia 13000000 16
Turkey 10220000 17
Netherlands 10000000 18
Malaysia 9879000 19
Poland 9000000 20
Thailand 6972000 21
Sweden 6800000 22
Argentina 6153600 23
Viet Nam 5870000 24
Iran (Islamic Republic of) 5500000 25
Czech Republic 5100000 26
Romania 4500000 27
Philippines 4400000 28
Chile 4300000 29
Belgium 4200000 30
Colombia 4050240 31
Austria 3900000 32
Egypt 3900000 33
Ukraine 3750000 34
South Africa 3566000 35
Morocco 3500000 36
Switzerland 3500000 37
China, Hong Kong Special Administrative Region 3479700 38
Finland 3286000 39
Peru 3220000 40
Israel 3200000 41
Portugal 2951000 42
Denmark 2725000 43
Hungary 2700000 44
Belarus 2461090 45
Singapore 2421780 46
Venezuela 2312680 47
Slovakia 2276060 48
New Zealand 2110000 49
Pakistan 2000000 50
Greece 1955000 51
Norway 1792000 52
Nigeria 1769660 53
Saudi Arabia 1586000 54
Serbia and Montenegro 1517020 55
Kenya 1500000 56
United Arab Emirates 1384840 57
Croatia 1303000 58
Bulgaria 1234000 59
Ireland 1198000 60
Sudan 1140000 61
Jamaica 1067000 62
Costa Rica 1000000 63
Lithuania 968000 64
Slovenia 950000 65
Uzbekistan 880000 66
Puerto Rico 862000 67
Tunisia 835000 68
Zimbabwe 820000 69
Latvia 810000 70
Dominican Republic 800000 71
Syrian Arab Republic 800000 72
Guatemala 756000 73
Uruguay 680000 74
Estonia 670000 75
Ecuador 624579 76
Jordan 600000 77
Kuwait 600000 78
Lebanon 600000 79
El Salvador 587475 80
Algeria 500000 81
Haiti 500000 82
Senegal 482000 83
Azerbaijan 408000 84
Republic of Moldova 406000 85
Kazakhstan 400000 86
Ghana 368000 87
Bolivia 350000 88
United Republic of Tanzania 333000 89
Malta 301000 90
Bangladesh 300000 91
Panama 300000 92
Cyprus 298000 93
Sri Lanka 280000 94
Luxembourg 270810 95
Kyrgyzstan 263000 96
Oman 245000 97
Cote d'Ivoire 240000 98
Zambia 231000 99
Iceland 225610 100
Bosnia and Herzegovina 225000 101
Honduras 222273 102
Togo 221000 103
Libyan Arab Jamahiriya 205000 104
Mongolia 200000 105
Reunion 200000 106
Uganda 200000 107
Mauritius 180000 108
Yemen 180000 109
Georgia 175600 110
Angola 172000 111
Papua New Guinea 170000 112
Cameroon 167000 113
Qatar 165000 114
Occupied Palestinian Territory 160000 115
Trinidad and Tobago 160000 116
The former Yugoslav Republic of Macedonia 159000 117
Bahrain 152721 118
Armenia 150000 119
Barbados 150000 120
China, Macao Special Administrative Region 150000 121
Cuba 150000 122
Paraguay 150000 123
Guyana 145000 124
Mozambique 138000 125
Nicaragua 125000 126
Nepal 120000 127
Ethiopia 113000 128
Martinique 107000 129
Benin 100000 130
Bahamas 93000 131
Madagascar 90000 132
Guadeloupe 79000 133
Guam 79000 134
Namibia 75000 135
New Caledonia 70000 136
Myanmar 63688 137
Fiji 61000 138
Botswana 60000 139
Brunei Darussalam 56000 140
Saint Lucia 55000 141
Burkina Faso 53200 142
Democratic Republic of the Congo 50000 143
Eritrea 50000 144
Mali 50000 145
Gambia 49000 146
Malawi 46140 147
Guinea 46000 148
French Polynesia 45000 149
Lesotho 43000 150
Cambodia 41000 151
Gabon 40000 152
Bermuda 39000 153
French Guiana 38000 154
Greenland 38000 155
Rwanda 38000 156
Congo 36000 157
Iraq 36000 158
Swaziland 36000 159
Turkmenistan 36000 160
Belize 35000 161
Chad 35000 162
Faeroe Islands 32000 163
Suriname 30000 164
United States Virgin Islands 30000 165
Guinea-Bissau 26000 166
Burundi 25000 167
Cape Verde 25000 168
Aruba 24000 169
Niger 24000 170
Liechtenstein 22000 171
Lao People's Democratic Republic 20900 172
Dominica 20500 173
Antigua and Barbuda 20000 174
Bhutan 20000 175
Sao Tome and Principe 20000 176
Seychelles 20000 177
Grenada 19000 178
Maldives 19000 179
San Marino 15000 180
Somalia 15000 181
Mauritania 14000 182
Micronesia, Federated States of 12000 183
Andorra 11000 184
Saint Kitts and Nevis 10000 185
Sierra Leone 10000 186
Central African Republic 9000 187
Djibouti 9000 188
Comoros 8000 189
Saint Vincent and the Grenadines 8000 190
Vanuatu 7500 191
Gibraltar 6295 192
Samoa 6000 193
Equatorial Guinea 5000 194
Tajikistan 5000 195
Palau 4000 196
Solomon Islands 3000 197
Tonga 3000 198
Tuvalu 3000 199
Kiribati 2000 200
Marshall Islands 2000 201
Netherlands Antilles 2000 202
Cayman Islands 1300 203
Liberia 1000 204
Nauru 300 205
Korea, Democratic People's Republic of 0 206