Taking Technology to the MAX

Do what I can do for wikipedia

2009-12-24T13:08:00.007-05:00

Imagine a world in which every single person on the planet has free access to the sum of all human knowledge. That’s where we’re headed. And with your help, we will get there. -- Jimmy Wales

I use Wikipedia almost everyday. I love it, so I do what I can do.

Thank you for your gift of USD 35.00 to the Wikimedia Foundation,
received on December 24, 2009.

Your donation celebrates everything Wikipedia stands for: the power of
information, freedom, sharing, learning and discovery. Thank you so
much for helping keep Wikipedia freely available for its 330 million
readers around the world.

Many people love Wikipedia, but surprisingly few know it's run by a
non-profit. Please help us spread the word, by forwarding this e-mail
to a few of your friends.

If you have questions about your donation, please send a message to
donate@wikimedia.org. To learn more about the Wikimedia Foundation,
visit our blog at http://blog.wikimedia.org/ or our website at
http://wikimediafoundation.org/. Or, follow us at
http://twitter.com/wikimedia, http://identi.ca//wikimedia, or
http://bit.ly/wikiFacebook.

And again, thank you. I'm really, really happy to have
your help.

Sincerely Yours,

Sue Gardner
Executive Director, Wikimedia Foundation

[Wireless] Three kingdoms in China mobile market

2009-03-23T01:11:00.021-04:00

If you recently watched the movie "Red Cliff" directed by John Woo, you would know it is a story about a battle of the Three Kingdoms period in the history of China. Although this period is relatively short, it has been greatly romanticised in the cultures of China. Any Chinese people knows a bunch of legends of those three kingdoms (Cao Wei, Shu Han, and Dong Wu). By coincidence, currently there are three big mobile communication companies in China, they are China Mobile, China Unicom and China Telcom. Those three companies compete one another for the China mobile market, which is very similar to those three kingdoms combated for the territory.

Previously, only China Mobile and China Unicom own the operating license for 2G mobile systems in China. At that time, although China Unicom was considered as a competitor of China Mobile, it was still too weak to jeopardize China Mobile's dictatorial control of the mobile market. And China Telecom only has the largest wiring system and has been wishing for the mobile license for a very long time. In order to expediate the development of 3G systems, and to change the unbalanced competition pattern as well, in Jan 2009 China's Ministry of Industry and Information Technology issued 3G licenses to those three companies. China Mobile got TD-SCDMA, China Unicom will develop WCDMA and China Telecom has the grant for CDMA2000.

Technically, China Unicom benefits a lot from 3G license since WCDMA is the most mature system; China Telecom also got they desired - the mobile license; and China Mobile will face a fiercer competition from the other two companies since TD-SCDMA is still "weaker" in the view of development.

However, you have to take good with bad. China Unicom needs to spend a longer time and more efforts to integrate the WCDMA system into its own development. China Telecom lacks of mobile operating experience and cdma2000 has a dim future in 3G long term evolution. Although TD-SCDMA has no technology advantage, China Mobile has the largest 2G system in the world and has accumulated abundant operating experiences over years.

It seems that 3 licenses for 3G is a good choice for competition pattern change. However, my question is, why 3? From the view of history, three kingdoms period is one of the most "bloody" period in China. In the pointview of market, competition of two is the most stable pattern. Because when you have two opponents, you may select one as your ally to combat the strongest. However, this confederation may be variant along with time. When the strongest becomes weak, it may ally with another opponent to conterwork you. This will fluctuate the market and may not be good for the whole industry's developing. Just my two cents. :-)

[Software] Install VMware Tools on Fedora 9

2008-11-01T22:49:00.013-04:00

I bought a new PC with Window XP operating system. Like what I did on my old computer, I decided to install VMware workstation on Windows XP since I also need Linux/Unix environment for software development. I downloaded Fedora 9 ISO image from redhat.com and used it to build the linux guest OS on the VMware workstation. Everything for Fedora 9 installation went smoothly. After that, I began to install VMware Tools as usual (you can find a guide from VMware):

1) Select "Install VMware tools" on VMware, it will mount VMware Tools to "/media/VMware Tools" of the guest Linux OS,
2) start a terminal, type in "su", enter the root password,
3) rpm -Uhv /media/VMware\ Tools/VMware*.rpm, install the VMware Tools using RPM (or you can use extract the gz file using tar). Note, there's a space between VMware and Tools, so you need a backslash,
4) after installation, you should have a script file installed: /usr/bin/vmware-config-tools.pl
5) run rmware-config-tools.pl, it will ask you several questions, such as "which compile command to use", "kernel headers directory" etc.

However, when it goes to "kernel headers directory", it complained that the default directory /usr/src/include/linux does not exist or the kernel headers are not matched to the kernel you are running. In order to solve this problem, start a new terminal and run "rpm -qal | grep kernel", it will tell you what kernels have been installed on your guest OS and where they are located (for my case, it's under /lib/modules/2.6.6.xxx/include).

After changing the directory, it still doesn't work and continues complaining "mismatch" messages. The reason is that I upgraded the kernel but didn't reboot it. So the running kernel and the header files installed are not "synchronized" yet. Restart the OS and re-run vmware-config-tools.pl, now it's ok.

The last step of vmware configure is to set the dispaly resolution. After that, you need to restart X as it suggests. Unfortunately, another problem emerged: the mouse position messed up. I clicked the menu but it's not selected. I googled this problem, and found it's a xorg-x11-drv-vmmouse driver bug for Fedora 9 only. A work around is given in this link:

Edit /etc/X11/xorg.conf in the guest machine. Create the section if necessary:

Section "ServerFlags"
Option "NoAutoAddDevices"
EndSection

Restart X, everything goes well! Now you can enjoy the features provided by VMware, such as copy&paste between host and guest OSs, share files and folders etc.

Embedded C programming - for beginners (1)

2008-08-25T20:59:00.003-04:00

Here the beginner is me. :-) If you never touched embedded C programming before and want to learn it, join me. I have some experiences to share with you. We can teach and learn ourselves.

Embedded programming is always hardware related. You may at least need to buy a develop kit or emulator. The price is not that cheap (usually costs you several hundred bucks, with those bucks you can send roses to your GF everyday for two months). Can we save those bucks and still learn the fundamentals of embedded C programming? Congratualtion, you got it!

Thanks to Keil - An ARM company. If you never heared about Keil, congratulation again! you are the beginner and this article is right for you! Keil provides a great Evaluation Software supporting different paltforms but with very few limitations. It includes the assembler, compiler, linker, debugger, and IDE. Everything you need for embedded C learning is here. How to get it? Go to this webpage of Keil (http://www.keil.com/demo/) and you can get it free (you just need to fill out a simple form)!

Ok, next I'll show you how to write your first embedded C program.

Run Javascript under Windows using Mozilla's interpreter - SpiderMonkey

2008-07-06T19:33:00.007-04:00

Javascript is widely used in Web programming. Microsoft's Internet Explorer and Mozilla's Firefox both include its Javascript interpreter in the browsers. However, they also limit your capability of running Javascript in a web-only environment.

The good news is, Mozilla's interpreter was released as an open source. You can find it from http://www.mozilla.org/js/. It has two versions, one is written in C and is called SpiderMonkey. The other is written in Java and called Rhino.

Today, I installed SpiderMonkey on a windows xp computer. The installation is very simple:
1) Install Mozilla Developer Center - MozillaBuild
2) Go to SpiderMonkey's website to get the latestest version and build it under MozillaBuild.

After installation, you will get the executable interpreter js.exe in a directory whose name depends on the system you're building on (you can find this direcotry under mozilla/js/src/ with a suffix .OBJ).

If you are not accustomed to the MozillaBuild environment (unix-like) and is comfortable with Windows/Dos, you can modify the system environment by adding the path of js.exe into the PATH variable (right click "My computer" in Windows Explorer, and then select Advanced -> Environment Variables). Then under the DOS prompt environment (in Windows, Start -> Run -> cmd) , you can use "js file.js" to run your javascripts.

Call for Donations for the China Eearthquake!

2008-05-16T01:15:00.005-04:00

Sichuan Earthquake Facts
To date (May 15), 19,500 dead, and 80 percent of buildings toppled in one county
Thousands buried in the rubble of collapsed buildings
Chinese government estimates 4.9 million houses destroyed
More than 60,000 people are "missing or out of reach"
Rescuers digging through rubble to find survivors

Donation websites:
http://www.mercycorps.org/chinaearthquake/

http://donate.ifrc.org/

http://www.redcross.org.hk/

NPR's report (by Melissa Block)
Audio:
http://www.npr.org/templates/story/story.php?storyId=90447603
then click on "Listen Now"

Report:
http://www.npr.org/blogs/chengdu/2008/05/we_found_fu_guanyu_and.html#more

[Programming] Threads (4) - synchronization

2008-04-08T19:43:00.006-04:00

Threads (4) - synchronization

Previously we described the issue of joinable and detached thread scheduling. In practice, the situation is not that simple. Most of the threaded programs are concurrent programs, which means the operating system will run multiple threads at the same time. However, there's no way to know when a thread will be scheduled to run by the system. The order of thread's running is not deterministic.

Another big problem of threaded programming is that, unlike processes, threads share the same address space. This is one of the powerful aspects of threads - if one thread changes the value of a variable, other threads will see this modification subsequently. However, this sharing could also be dangerous without careful design and implemenation.

The third thing is that debugging a threaded program is not easy as debugging a single-thread program - you may not reproduce the same result in a multi-threaded program.

Therefore, the synchronization among threads is a very important issue. In order to understand the details of synchronization, let's first learn some new concepts one by one: critical section, atomic operation, race condition, mutex, semaphore, deadlock.

Critical section: it means a resource (usually implemented by a sequence of code) that should be exclusively used by a program for a period of its execution. In simple words, if a thread begins executing a critical section code, it must continue to the end without being canceled.

Race condition: since a critical section can only be exclusively used, when multi threads occur concurrently, they will compete for the critical section. In this situation, we say there is a race condition.

In order to eliminate race conditions and ensure a critical section being implemented successfully, we need a way to make operations atomic, which is described below.

Atomic operation: when we speak of an atomy, we usually mean that it is a tiny particle indivisible. So here the atomic operation has the similar meaning: once the operation starts, it will not be canceled, pasued or interrupted until it completes; at the meantime, no other operation will take place either.In multi-threaded programming, the operating system will provide and guarantee some operations to be atomic.

(to be continued)

[Wireless] China 3G phone (TD-SCDMA)

2008-04-02T14:22:00.007-04:00

In the area of 3G, China proposed and submitted its own standard (TD-SCDMA) to ITU-R in 1998 and got it approved as one of the 3G standardized technologies in the world. After that, China has been working on this standard for about 10 years. In order to support this self-own standard, China government postponed the 3G licence from year to year, and China Mobile Group (the world's largest mobile phone operator ranked by number of subscribers, with over 376.38 million customers by the end of Feb, 2008) was selected to build pre-commercial networks for TD-SCDMA system. Many of my previous colleagues in China participated in this project.

Yesterday (Apr 1, 2008), a video clip about China 3G/TD-SCDMA phone was released in sina.com (the largest Chinese-language infotainment web portal). In this clip, a video call, a piece of stream media and some java supported applications are demonstrated on a TD-SCDMA phone (the model is U980 of ZTE). The video call looks not bad. Although UMTS (WCDMA), cdma2000 EVDO, and even HSDPA have been widely deployed by some service providers in the United states, as I know no one supports video call yet.

The Olympics game is coming soon. Although China said TD-SCDMA might not make Olympics deadline, it's still very possible that TD-SCDMA phones will be offered on hand and showcased at that time.

[Programming] Threads (3) - joinable or detached thread

2008-03-31T19:51:00.014-04:00

Last time we've seen it's very easy to create a new thread in Linux by using the POSIX thread API functino pthread_create(). But wait, that example code has a bug. How does Linux schedule those two threads, namely, the main thread and the new created thread?

The answer is Nothing! If the new created thread terminates before the main thread, everything is ok. But it's very possible that the main thread stops first, especially when you are creating a new thread to do some time-cost calculation or operation. In this case, the memory used to passing parameters to thread function will be deallocated when the main thread is done, while the created thread may still be accessing this block of memory.

So we need a mechanism to avoid this. The POSIX thread standard provides a function called pthread_joint(). It's similar to the wait() function that a parent process used to collect child processes. With pthread_join(), the main thread will wait until the new created thread terminates, then the main thread returns. In addition, the pthread_join() also provides a way for the main thread to read return values from the created thread.

The prototype of pthread_join() is
int pthread_join(pthread_t thread, void **thread_return);

pthread_join() looks good but it doesn't suit for all cases. Sometimes we may just want the main thread to call a new thread, but don't need the main thread to wait for the return of the new thread. For example, we create a second thread to print some documents. It's not necessary to let the main thread wait, it can continue to serve other jobs while the print is onging. In this situation, we can make the thread detached instead of joinable. In order to do this, we need to set the second argument in the pthread_create() function, i.e. thread attributes.

As we did in the previous blog, setting thread attributes to NULL means the default attribute (thread is joinable) is used. If we need detached thread, we can use pthread_attr_init() function to initialize it, then call pthread_attr_setdetachstate() to set the attribute as detached. Indeed, POSIX thread provides a set of functions to set different attributes to a thread, such as scheculed, inherited etc. But for most applications, the detached attribute is typically of interest.

A typical program setting thread attributes to detached is as follows:

{
   ...
   pthread_attr_t threadAttr;
   pthread_t thread;

   pthread_attr_init(&threadAttr);
   pthread_attr_setdetachstate(&threadAttr, PTHREAD_CREATE_DETACHED);
   pthread_create(&thread, &threadAttr, thread_function, (void *)thread_arguments);
   pthread_attr_destroy(&threadAttr);
   ...
}

[Programming] Threads (2) - Thread Creation

2008-03-20T17:54:00.007-04:00

In Linux/Unix, threads are implemented using POSIX standard API (known as pthreads). All functions and data types related to threads are declared in the header file .

To create a thread, use the pthread_create() function. The prototype of pthread_create() is
#include <pthread.h>
int pthread_create(pthread_t *thread, pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);

The function is not hard to understand
1) the first argument is used to store the thread ID of the new created thread
2) the second argument is a pointer to a thread attribute object, you can use NULL as default or call pthread_attr_init() to initialize the attribue you want
3) the third argument is a pointer to the thread function, i.e., the function used for the new created thread. Don't be scared by the format, it's just an ordinary function pointer.
4) the last argument is used to pass parameters to the thread function, i.e. the thread function uses this passed value as its arguments

We'll use a simple example to show how it works. The code with comments is attached below



/** simple_thread.c */
#include <pthread.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

void * thread_function(void * dumb);
int main()
{
    // pthread_t is the thread type defined in POSIX thread
   pthread_t thread_id;

    int res;

   /** create the new thread
       the new thread ID is stored in thread_id
       the thread's attribute is set to default(NULL)
       it will call the thread_function()
       nothing is passed to the thread_function
   */
   res = pthread_create(&thread_id, NULL, &thread_function, NULL);
   if (res!=0)
   {
      perror("Thread creation failed.");
      exit(EXIT_FAILURE);
   }
   return 0;
}
void * thread_function(void * dumb)
{
   printf("the new thread is created.\n");
   return NULL;
}

Notice, since pthread functions are not included in the standard C library, you should add the pthread library yourself

cc -o simple_thread simple_thread.c -lpthread

[Wireless] New contender in Mobile TV - WiMAX

2008-03-12T22:41:00.008-04:00

The latest news about WiMAX is that NextWave plans to introduce Mobile TV over WiMAX, which is currently named as MXtv. It will support up to 30 frames/second of video, and provides up to 45 mobile TV channels with 300kbps in 10 MHz. Nextwave will develop this MXtv with its partner Huawei Technologies USA and Alcatel-Lucnet. The news said they will demonstrate the technology at CTIA Wireless 2008 next month in Las Vegas.

In recent years, IP TV gains a lot of attention. In the wireline domain, some technologies have been proposed to provide the "Final Mile" data stream transmission for the consumer's premises, such as Passive Optical Network, Ethernet in the First Mile over copper. In the wireless domain, Mobile TV can be supported by two-way cellular network (such as 3G) or one-way dedicated broadcast network (such as satellite). Now WiMAX becomes a new platform for Mobile TV. No matter which one dominates or some of them share the market, the new Multimedia era is running to use.

[Programming] Threads (1)

2008-03-12T01:31:00.005-04:00

Another important concept in multi-tasking operating system is threads. We have learned that a program can fork a child process to do a different thing. However, at times the overhead of creating a new child process is heavy, especially for some embedded systems which only have limited resources for use. The fact behind this is that a new copy of the original process will be created when forking, such as the memory space and file descriptors. That's what we mentioned before that child process is schedueled independently of the parent process.

In order to realize multi-tasking with light overhead, some new concepts are introduced to multi-tasking programming, such as light-weight process and threads. Sometimes people just call threads as light-weight processes for the sake of simplicity, although they are not the same thing (for details, you can refer to Light-weight process in wikipedia).

So in the view of the resource usage, the new created thread does not copy the original system resources used by the creating thread. It shares the same memory space (heap), global variables, file descriptors, signal handlers and other system resources as the original. However, threads have their own stack space.

If we take a look at the thread in the view of implementation, a thread exists within a process, or more precisely, a thread is a sequence of control within a process. Indeed, a process has at least one thread of execution (also called primary or main thread). This primary thread can create additional threads, and all these threads run the same program in the same process, but they may execute a different part of the program at any time.

[Programming] Processes (3) - Signals

2008-03-11T12:55:00.009-04:00

A Signal is a special message sent to a process to respond to some conditions. Some examples of the conditions are: illegal instructions, broken pipe, termination etc. Those signals are defined in the header file - singal.h. They are all with prefix SIG. The following table is a list of some signals.

Signal Name	Description
SIGILL	Illegal instruction, indicates the program's stack is corrupted
SIGINT	Terminal interrupt from keyboard by pressing Ctrl+C
SIGKILL	Ends a process immediately, which cannot be caught or ignored
SIGPIPE	Attempts to write on a broken pipe
SIGQUIT	Quit from keyboard
SIGTERM	Requests a process to terminate

For a full list of signals, you can find it by typing the command below:

% man 7 signal

Generally speaking, signals can be used in the next three situations:
1) send a signal to processes in response to some errors, such as SIGBUS(bus error), SIGSEGV(segmentation violation)
2) send a signal to another process, such as SIGTERM(terminate), SIGKILL(kill the process)
3) send a command to a running program using user-defined signals, such as SIGUSR1

When a process receives a signal, it will take some actions immediately - either to call another function or ignore it (ignore is also a kind of action). When it calls another function, the current executing program will be paused and the new function will be executed. When the function returns, the paused program will resume again.

You can aslo set or modify the actions to be taken on receipt of signals by using function sigaction().

[Programming] Processes (2) - Zombie processes

2008-03-11T02:36:00.001-04:00

Last time we mentioned that we can use fork() to create child processes. However, you should keep this in mind: the child process is schedulued independently of the parent process. It implies that you cannot predict which process will execute before or after another, namely, the order of the occurrence of multi processes cannot be forecast. This situation also occurs in multi-threaded programming.

Therefore, some advanced, even sophisticated mechanisms must be used in mutlitasking programming to control the programs running in the desired order.

For example, in some cases you may want the parent process to wait until its child processes have completed. This can be done using the wait family functions, such as wait(), waitpid(), wait3() etc.

However, we need to pay attention to the occurrence of "Zombie" processes. When a child process terminates, its association (such as exit status) with its parent does not vanish immediately, it is still in the system. In this case, this terminated child process becomes a "Zombie" process. It is the responsibility of the parent process to clean up the zombie child processes. The wait() function we mentioned above can do this clean up work.

If you have too many zombie processes in the system, you may suffer slower performance since they consume resources. So you need to avoid zombie processes. Fortunately, when the parent process exits, a special process called init() with process ID of 1 will do the clean up work automatically for you.

You may ask why we don't notify the parent process when a child terminates. Great, you make it! In Linux, child process can send signals to parent when it terminates. We'll touch it in the next post.

[Programming] Type casting problem in function's argument

2008-03-09T14:25:00.012-04:00

Recently someone asked a question of C programming on a discussion board: he has some codes which handle a fixed point array by passing the name of the array to a function, for example:


/** Code 1 */
// declaration of the function
void f(int *pt);

// an array of fixed point integer
int A[10];

// call the function
f(A);

The above codes work successfully. Now he tries to extend the code to a floating point array, as follows:

double B[10];
f((int*)B);

The compiler didn't complain any error, but the output result is something weird. For example, run the following codes on gcc or visual c, you suppose to get output as 3, but the result is -266631570,


/** Code 2 */
#include <stdio.h>
void test_fun(int* px);
int main()
{
 double a[10];

 a[0] = 3.14159;
 test_fun((int*)a);
 return 0;
}

void test_fun(int *px)
{
 printf("%d\n", *px);
}

We all know that we can type-cast a double variable to an integer variable like this:


/** Code 3 */
 double d=3.14;
 int c;
 c=(int)d;

And we can pass an array to a function by the array's name if they are in the same type (as the above code 1). But why cannot we do the similar thing for passing a floating point array's name to a funciton which accepts fixed point variables?

The answer to this question is: floating point and fixed point numbers are stored in different formats. For floating point number, it conforms with IEEE754. For example, for a 32-bit computer, a single-precision binary floating point number is stored in the format of sign(1 bit) + exponent (8 bits) + fraction (23 bits). So if you simply pass the array's name of floating point numbers as function's argument to an array that accommodates fixed point numbers, the function will read the 32-bit floating point number in fixed point format. The compiler doesn't complain because, yes, you can read it. But the result cannot be what you expect.

The solution to this question may be: 1) cast each element of the floating point array to a fixed point array first, then call the function; 2) re-write the function to support floating point, such as using templates...

[Wireless] Sprint nosedives! Then, WiMAX???

2008-02-29T21:32:00.004-05:00

Sprint-Nextel lost more than 20 percent of their stocks value after it annnounced fourth-quarter earning (or loss?) yesterday. The shares of its WiMAX partner - Clearwire, also dropped more than 10 percent in two days.

Now in market, most wireless firms are betting on 3G wireless networks. Even the new handset player, Apple, is going to launch a 3G-capable iPhone this year. Although 3G system was not deployed as fast as it was expected initially, it finally occupies a part of the wireless market and becomes bigger in years. Although WiMAX is newly designed with more advanced technologies, it may have a disadvantage than 3G in time-to-market.

So, who will drive wireless to the MAX? LTE or WiMAX? I bet nobody can answer this. What we know is: Sprint plans to launch commerical WiMAX service in Q2 2008. Ericsson plans to invest 1.5 billion dollars into next generation wireless systems (LTE or 4G) in three years.

But I'll say, no matter it's LTE, WiMAX or 4G, the winner is always OFDM+MIMO. :-)

[Wireless] Free global Wi-Fi network?

2008-02-26T15:27:00.004-05:00

Today I read an article "Is a free global Wi-Fi network possible?". It said a company called WeFi is hoping to provide a virtual global wi-fi network which is free to allow every to log on.

Actually, WeFi is not the first one working on this. You can find free Wi-Fi hotspots from some websites, such as gWifi.net, free-hotspot.com etc. The basic idea of this kind of free wi-fi network is to find unsecured hotspots to access in. However, the distinction of WeFi is that it provides a software that can automatically connect your device to the best available hot spot.So it saves time of switiching among different hotspots if there are some.

Nevertheless, the ratio of unsecured (free) access spots to all spots in a typical area is not as high as WeFi said to be 50 percent. By checking the hotspots map provieded by WeFi, I found this ratio is about 20 percent on average. We know current 802.11 products all support WEP or WPA and the vendor encourage people to set up a log-in password for data protection. Only some businesses (such as Panera Bread‎) may have open wi-fi spots. For individual wi-fi hotspot owner, unless he is generosity and can bear the low data rate as well as the risk of privacy intrusion, he may make his wi-fi open and free. My two cents: just finding and utilizing the existing open wi-fi resources may not make this virtual free wi-fi network long-lived. As a wi-fi user, I definitely hope the Internet access be free. But, I also know another phrase "There is no such thing as a free lunch."

[Programming] Processes (1)

2008-02-22T20:33:00.014-05:00

From today, we will digress to processes and threads programming.

One standard definition of process (IEEE Std 1003.1) is, "an address space with one or more threads executing within that address space, and the required system resources for those threads". It's like a circular defintion, because in order to understand this definition, you have to know what are threads first. This may not be a problem for those computer gurus, but for beginners, it's better to find a simple explanation, as follows.

The description of process in wikipedia is easy to understand: an instance of a computer program that is being sequentially executed. Further to say, a computer program is just a passive collection of instructions, while a process is the actual execution of those instructions. This is described from the view of the user. On the other hand, in the perspective of operating system, you can say process is the operating system's basic scheduling unit.

So what elements does a process consist of? It's easy to answer, since process is actaully a program. It contains: program code, data, variables, current context (execution status), working directory, access rights (mode and ownership), memory and other system resources allocated to the process etc. For Linux system, processes may share code and system libraries.

In Linux/Unix, you can
a) start a new process by the system() function;
b) replace the current process with a new process by the set of exec() funtions (execl, execv, execlp etc.);
c) or duplicate a new process by the fork() function.

In practice, system() is rarely used to start new processes, because it invokes the new program using a shell, which may cause security problems. So it's preferable to use exec() and fork(). The difference between exec() and fork() is: fork() creates a new child process which is an exact copy of its parent process, but exec() causes a process to cease being an instance of one program and to instead become an instance of another problem.

The flows of the system(), exec() and fork() call are shown in the following figures.

[Programming] Sockets programming - multiple clients - prologue

2008-02-21T13:39:00.007-05:00

Prologue

Previously we only talked about a very simple case: the server processes one client's request before accepting a connection to the next client. If the processing time for each client is long, and if multiple clients are coming, then the new clients have to wait a long time to be served. Obviously, this is not a good design for the case of multiple concurrent clients.

Several solutions are used in practice, such as:
1) Multi-process method (forked server processes)
2) Multi-thread method (threaded server processes)
3) Select
4) Poll

The first multi-process method calls fork() to create a child process. The main server blocks on accept(), waiting for a new connection. Once a new client comes in, the server calls fork(), the new child process will handel the new connection and the main server is able to serve other new incoming requests.

However, this method suffers the disadvantage that sharing information becomes more complex (you need to use message queues, semaphores etc), and it requires more CPU resource to start and manage a new process for each request.

The second multi-threaded solution offers the lightweight advantages of the first multi-process method. However, multi-threaded program is not easy to debug.

The third and fourth approaches, select() or poll(), offer a different method to block execution of the server until a new event occurs. They usually only uese one process to serve multiple client's request. The server will not need shared memory or semaphore for different clients to communicate. For example. select() works by blocing until something happens.

Oh, hold on, please. You interrupted me, because you already got lost by those new terminologies, such as process, thread, shared memory, semaphore. Yes, in order to understand those, we need to first learn somthing about process/thread. We will cover this in the next several posts.

[Programming] Sockets programming on Linux/Unix

2008-02-19T23:10:00.009-05:00

Last time we introduced the fundamental of sockets programming and gave an example (WinSock) on the Windows platform.
In deed, socket interface was first introduced in UNIX. In UNIX, socket interface is actually an extension of the concept of a pipe.
However, sockets are created and used differently from pipes because they make a clear distinction between client and server, and they can implement multiple clients attached to a single server.

Again, let's briefly go over the principles of sockets programming:
1) First, a server application creates a socket using the system call socket.
2) Next, ther server process gives the socket a name, using the system call bind.
3) Then the server process waits for a client to connect to the named socket using the system call listen, which creats a queue for incoming connections.
4) For incoming connections, the server can accept them using the system call accept.
5) When the server calls accept, a new socket is created that is distinct from the named socket. This new socket is used only for communication with this particular client. The named socket remains for further connections from other clients.
6) Once a connection is established, a two-way communication will be available between the server and the client. They can communicate with each other using sytem call read/write for AF_UNIX protocol or send/recv for AF_INET protocol.
7) After communication, a system call close or shutdown is called to release the named socket.

Client side:
1) The client creates an unamed socket by calling socket.
2) Then the client uses system call connect to establish with the server by using the server's named socket as an address.
3) If the connection is accepted by the server, then the client can communicate with server using read/write for AF_UNIX protocol or send/recv for AF_INET protocol.
4) Similarly, when communication is finished, a call of close/shutdown is called.

Here's a very simple example of socket server and client programs.


// Local server

#include <sys/types.h>
#include <sys/socket.h>
#include <sys/un.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main()
{
   int server_socketfd, client_socketfd;
   int server_len, client_len;
   struct sockaddr_un server_address;
   struct sockaddr_un client_address;

   unlink("server_socket");
   server_socketfd = socket(AF_UNIX, SOCK_STREAM, 0);

   server_address.sun_family = AF_UNIX;
   strcpy(server_address.sun_path, "server_socket");
   server_len = sizeof(server_address);
   bind(server_socketfd, (struct sockaddr *)&server_address, server_len);

   listen(server_socketfd, 10);
   while(1)
   {
      char s_sendbuf[] = "Welcome to server.";
      char s_recvbuf[255];
      printf("Server waiting\n");

      client_len = sizeof(client_address);
      client_socketfd = accept(server_socketfd, (struct sockaddr *)&client_address, &client_len);


      read(client_socketfd, s_recvbuf, 255);
      printf("Message received from client: %s\n", s_recvbuf);
      write(client_socketfd, s_sendbuf, strlen(s_sendbuf)+1);
      close(client_socketfd);
   }
}


// Local client


#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/un.h>
#include <unistd.h>

int main()
{
   int socketfd;
   int length, result;
   struct sockaddr_un address;
   char sendbuf[] = "Hi, this is client 1.";
   char recvbuf[255];

   socketfd = socket(AF_UNIX, SOCK_STREAM, 0);

   address.sun_family = AF_UNIX;
   strcpy(address.sun_path, "server_socket");
   length = sizeof(address);

   result = connect(socketfd, (struct sockaddr*)&address, length);

   if(result==-1)
   {
      perror("Error:client 1");
      exit(1);
   }

   write(socketfd, sendbuf, strlen(sendbuf)+1);
   read(socketfd, recvbuf,255);
   printf("Greeting from server: %s\n", recvbuf);
   close(socketfd);
   exit(0);
}

[Security] Winpcap installation problem: Error opening file for writing c:\windows\system32\drivers\npf.sys

2008-02-18T11:45:00.009-05:00

Recently a friend asked me to help him install the winpcap on his computer. Winpcap is the packet capture and network monitoring library for Windows. Some network analyzer (such as Wireshark, the new version of Ethereal) or url sniffer (such as Url helper) need winpcap.

However, my friend got an error when installing the winpcap. He tried both the old 3.x version and the new 4.x version of winpcap, but everytime he got an error message "error opening for writing, c:\windows\system32\drivers\npf.sys". We googled the internet and found many people suffered the same problem and no solution was provided so far. Some people said it's due to the insufficient priveledge of the user account to install a driver file, but my friend's account is the administrator. Some other people said you may need to first delete the old npf.sys in the system32\driver folder and then reinstall it again, but we checked this folder and didn't find a file called npf.sys existing. We also closed the firewall and anti-virus software, but the problem is still there.

Finally, we made another try by copying a virus-free npf.sys from another computer to my friend's computer. Then, we found the reason. The system prompts that we cannot copy npf.sys (34,064 bytes) to npf.sys (0 bytes). But we just mentioned that we already did the check, and we didn't have a file named as npf.sys installed. So the only reason will be: there's a sub-directory called npf.sys existing. We checked again, and Bingo, we got it! There's a directory called c:\windows\system32\drivers\NPF.SYS existing on the computer (notice, it's not a file, but a directory). This NPF.SYS directory is empty and with name in upper case. I suspect there's some other softwares (with high probability to be a trojan or spyware) installed this NPF.SYS directory into the system32\drivers folder (they pretended to be a file of winpcap, then they could capture or sniff your password over the network). Later, it may be removed by anti-virus programs. But, it's not cleaned up, the resudual NPF.SYS directory is still on your system.

In summary, if you encounterred the same question (Error opening file for writing c:\windows\system32\drivers\npf.sys), try to first check if you have a NPF.SYS directory installed under \windows\system32\drivers.

[Programming] Quick guide for network programming (2)

2008-01-25T20:38:00.001-05:00

Source code for Server's socket:


#include <winsock2.h> 
#include <stdio.h>

void main()
{
   WORD wVersionRequested;
   WSADATA wsaData;
   int err;

   wVersionRequested = MAKEWORD( 1, 1 );
   // call WSAStartup, initialize winsock.dll and negotiate the socket version
   err = WSAStartup( wVersionRequested, &wsaData );
   if ( err != 0 ) {
      // Tell the user that we could not find a usable WinSock DLL.                                  
      return;
   }


   if ( LOBYTE( wsaData.wVersion ) != 1 ||
        HIBYTE( wsaData.wVersion ) != 1 ) {
      // Tell the user that we could not find a usable WinSock DLL.                                  
      WSACleanup( );
      return;
   }

// a) create a socket
   SOCKET sockSrv = socket(AF_INET, SOCK_STREAM, 0);
// b) bind
   SOCKADDR_IN addrSrv;
   addrSrv.sin_addr.S_un.S_addr = htonl(INADDR_ANY); // INADDR_ANY use any IP address of the host, you can use inet_addr("127.0.0.1"); to designate a specific IP
   addrSrv.sin_family = AF_INET;
   addrSrv.sin_port = htons(6123);     // use a port number larger than 1024
   bind(sockSrv, (SOCKADDR *)&addrSrv, sizeof(SOCKADDR));
// c) listen
   listen(sockSrv, 5);
// d) accept
   SOCKADDR_IN addrClient;
   int len = sizeof(SOCKADDR);
   while(1) // waiting for requests from clients
   {
      SOCKET sockConn = accept(sockSrv, (SOCKADDR *)&addrClient, &len); // create a new socket for this connection
// e) send/recv
      char sendBuff[100];
      sprintf(sendBuff, "Welcome %s to server", inet_ntoa(addrClient.sin_addr));
      send(sockConn, sendBuff, strlen(sendBuff)+1, 0);

      char recvBuff[100];
      recv(sockConn, recvBuff, 100, 0);
      printf("%s\n", recvBuff);
// f) close the current socket and wait for another request
      closesocket(sockConn);     //release the socket for this connection
   }

}

Source code for Client's Socket programming:


#include <winsock2.h> 
#include <stdio.h>

void main()
{
   WORD wVersionRequested;
   WSADATA wsaData;
   int err;

   wVersionRequested = MAKEWORD( 1, 1 );
   // call WSAStartup, initialize winsock.dll and negotiate the socket version
   err = WSAStartup( wVersionRequested, &wsaData );
   if ( err != 0 ) {
      // Tell the user that we could not find a usable WinSock DLL.                                  
      return;
   }


   if ( LOBYTE( wsaData.wVersion ) != 1 ||
        HIBYTE( wsaData.wVersion ) != 1 ) {
      // Tell the user that we could not find a usable WinSock DLL.                                  
      WSACleanup( );
      return;
   }
// a) create a socket
   SOCKET sockClient = socket(AF_INET, SOCK_STREAM, 0);
// b) connect
   SOCKADDR_IN addrClient;
   addrClient.sin_addr.S_un.S_addr = inet_addr("127.0.0.1"); // loopback address
   addrClient.sin_family = AF_INET;
   addrClient.sin_port = htons(6123);
   connect(sockClient, (SOCKADDR *)&addrClient, sizeof(SOCKADDR));
// c) send/recv
   char recvBuff[100];
   recv(sockClient, recvBuff, 100, 0);
   printf("%s\n", recvBuff);
   send(sockClient, "This is from client B", strlen("This is from client B")+1, 0);

// d) close
   closesocket(sockClient);
   WSACleanup();
}

[Programming] Quick guide for network programming (1)

2008-01-25T15:06:00.001-05:00


 
When we talk about network programming, basically it includes two parts: one is the socket programming, another one is the multi-threaded programming.
 
 
I'll give a step-by-step guidance for network programming in my blog. We'll first talk about socket programming, then go to the multi-threaded programming. I'll use the windows system as a demonstration. A TCP server will be first started up, then a TCP cilent will communicate with the server from the loopback IP address 127.0.0.1 with port number 6123. (I suppose you have already known the fundamental of network protocols, such as TCP/UDP, IP, port number etc.) 
 
1) What is socket?
Shortly put, a socket is a combination of an IP address and a port number of a two-way communication link between two programs on the network. 
 
2) Types of sockets:
For old version of socket, it provides two types of sockets:
  "Stream Socket": provide connection-oriented, reliable data transmission service, use TCP protocol
  "Datagram Socket": provide connetionless service, packets may not be received in order, use UDP protocol

Now some new types of sockets have been added, such as: SOCK_RDM (Reliable message datagram), SOCK_SEQPACKET(pseudo-stream packet based on datagrams)
 
3) Flow of the stream socket communication

 On the server side, there are seven steps:
  a) create a socket (socket)
  b) bind the socket with a local IP address and a port (bind)
  c) set socket to 'listen' mode (listen)
  d) wait for client's request, when it arrives, accept the request and return 
     a new socket for the connection (accept)
  e) communicate with client using the new returned socket (send/recv)
  f) return, wait for another client's request
  g) close the socket (close)

 On the client side, there are four steps:
  a) create a socket (socket)
  b) send request to the server ((connect))
  c) communicate with server (send/recv)
  d) close the socket (close)
 
4) Step-by-step programming

 Follow the steps in 3), we first write the code for a TCP server. We use visual c++. You can find the source codes in the next post. Here is the explanation of the code. It's better to read the code and the following descriptions simultaneously.

  <1> create a Win32 Console Application, set project name to TCPServer

  <2> write a main function

  <3> initialize the win32 socket DLL, call function WSAStartup();

     int WSAStartup(          
        WORD wVersionRequested,
        LPWSADATA lpWSAData    
     );                       
     WSAStartup has two jobs to do:
        i) initiates use of Ws2_32.dll: if WinSock.dll or lower network subsystem is not initialized correctly or is not found, will return WSASYSNOTREADY. 
        ii) negotiate the socket version: 
           if requested version < MAX version supported by the WinSock.dll, use min(requested version, MAX version)
           if requested version < MIN version supported by the WinSock.dll, return WSAVERNOTSUPPORTED, then call function WSACleanUP() to release resource that has been allocated for WSAStartup

        The WSADATA or *LPWSADATA used in WSAStartup is a structure, it's defined as
        typedef struct WSAData
        {
                WORD wVersion; // winsock version
                WORD wHighVersion; // highest version in the current winsock library
                char szDescription[WSADESCRIPTION_LEN+1];// for special use
                char szSystemStatus[WSASYS_STATUS_LEN+1];// for special use
                unsigned short iMaxSockets; // maximum num of sockets that can be
                                            // opened, don't use it
                unsighed short iMaxUdpDg; // maximum length of packet, don't use it
                char FAR * lpVendorInfo; // reserved for vendor, never been used
        } WSADATA, *LPWSADATA;


  <4> create a socket

     SOCKET WSAAPI socket(
        int af, // for tcp-ip, it must be AF_INET or PF_INET
        int type, // for winsock 1.1, only SOCKET_STREAM or SOCKET_DGRAM
        int protocol // protocol to be used, is specific to the address family and 
                     // socket type, set to 0 for default
     );

     If no error occurs, it will return a descriptor referencing the new socket. Otherwise, return INVALID_SOCKET.

  <5> bind

     int bind(
        SOCKET s, // descriptor identifying an unbound socket
        const struct sockaddr* name, // the address to assign to the socket, 
                                     // it may be varied with different 
                                     // address families, so we should use the next 
                                     // parameter to indicate the 
                                     // length of this address structure
        int namelen // length of the value, in bytes
     );


     The sockaddr is defined as:
     struct sockaddr {
        u_short sa_family;
        char sa_data[14];
     };

     For different address family, we should use differnt structure to replace this sockaddr. 
     For TCP/IP, sockaddr_in is used. 
     The definition of sockaddr_in is:

     struct sockaddr_in {
        short   sin_family; // for IP address, it's AF_INET
        u_short sin_port; // port number
        struct  in_addr sin_addr; // IP address of the host, 
                                  // should use "network byte order"
        char    sin_zero[8]; // padding bytes, to make the length equals to the 
                             // sockaddr structure
     };
     where the "network byte order" is the same as the well-known big_endian order. 

    It will return 0, if successful; otherwise, return SOCKET_ERROR 

  <6> listen

     int listen(
        SOCKET s,        // descriptor identifying a socket
        int backlog      // max length of the queue of pending connections
     );

  <7> accept

     SOCKET accept(
        SOCKET s, // identifying a socket
        struct sockaddr* addr, // used to store the client's ip addr and port num
        int* addrlen // length of the 
     );

  <8> send/recv
     int send(
        SOCKET s,
        const char* buf,
        int len,
        int flags
     );

  <9> Include the header file , add ws2_32.lib to the project, the operation in Visual C++ is:
        project -> setting -> link -> Object/library modules, append ws2_32.lib to the end


  <10> Then let's go to the client side. First add a new project to the current workspace, name it as "TCPClient".

  <11> Similar as the Server code, first call WSAStartup to initialize the ws2_32.dll and negotiate the socket version, then create a socket

  <12> connect
       
     int connect(
        SOCKET s,
        const struct sockaddr* name,
        int namelen
     );

  <13> After connect, call function send/recv, and finnaly call closesocket and WSACleanup as in server side.

  <14> Include the header file  and add ws2_32.lib to this project too

  <15> Compile all files, run TCPServer first, then run TCPClient, we will get the following results, as shown in the figure
 
5) Some functions are used in the program for the conversion of the address, they are
   htons():  converts a u_short from host to TCP/IP network byte order 
   htonl():  converts a u_long from host to TCP/IP network byte order 
   ntohs():  converts a u_short from TCP/IP network byte order to host byte order
   ntohl():  converts a u_long from TCP/IP network byte order to host byte order
   inet_ntoa(): converts an (Ipv4) Internet network address into a string in Internet standard dotted-decimal format
   inet_addr(): converts a string containing an (Ipv4) Internet Protocol dotted address into a proper address for the IN_ADDR structure

[Algorithm] Reverse words in a string

2008-01-24T15:10:00.001-05:00

This is an interview problem. Given a string, such as "tell me something", output the string as "something me tell", i.e. reverse every word in the string. Here is a demo program in C code, it's easy to understand with the comments given in the code. The basic idea is, scan the string from the end, find the beginning and the end of each word, then write to a temporary buffer.


#include <iostream.h>
#include <stdlib.h>
#include <string.h>

void ReserveWordsInString(char string1[])
{
   // get the length of the input string
   int length=0;
   while (string1[length]!='\0')
      length++;
   // allocate memory space for a temporary buffer, used to store the temporary result
   char *buffer= (char *)malloc(length+1);

   // declare four indicators
   // MoveInd: from length to 0, used to traverse the input string
   // EndInd: indicate the end of a word that is to be reversed in the input string
   // BeginInd: indicate the begin of the word that is to be reversed in the input string
   // WriteInd: the indicator of the writing position in the temporary buffer
   int MoveInd, BeginInd, EndInd, WriteInd;
   // initialize the MoveInd to the end of the input string, WriteInd to the begin of the temporary buffer
   MoveInd = length-1;
   WriteInd = 0;

   while (MoveInd>=0)
   {
      if (string1[MoveInd]!=' ')  // if it's a word charactor
      {
         EndInd=MoveInd;
         // scan the current word, find the next non-word charactor
         while(MoveInd>=0 && string1[MoveInd]!=' ')
         {
            MoveInd--;
         }
         // copy the word to the temporary buffer
         for (BeginInd=MoveInd+1; BeginInd <= EndInd; BeginInd++, WriteInd++)
         {
            buffer[WriteInd]=string1[BeginInd];
         }

      }
      else
      {
         // write the non-word charactor directly to the temporary buffer
         buffer[WriteInd++]=string1[MoveInd--];
      }
   }
   // it is better to append \0 to the end of the buffer
   buffer[length]='\0';

   // copy the buffer to the input string for output
   for (int i=0; i<length; i++)
      string1[i]=buffer[i];

   // free the allocated memory for the buffer
   free(buffer);
}
void main()
{
   char string1[]="This is a C program, for word reverse.";
   // this is a tricky method in getting the size of an array, explanation is below the code
   int length = sizeof(string1)/sizeof(string1[0]);

   // Call the function
   ReserveWordsInString(string1);

   // output the result
   for (int i=0; i<length; i++)
   {
      cout<<string1[i];
   }
   cout<<endl;
}

Notes: In this program, we encountered a problem, how to get the length of an array or a string?

A well-known and tricky method is to use "sizeof(array)/sizeof(array[0]);", this works in the main program. However, if the array is the input argument of a function, this one doesn't work. Because in this case, the type of the array identifier "decays" into a pointer to the base type, and its value is set to the address of the first element in the array.
So, my opinion is, always traversing the array from the beginning to the end to get the length, like "for(int i=0; array[i]!='\0'; i++)".

A more decent algorithm is: first reverse the whole string in characters, e.g. reverse "tell me something" to "gnihtemos em llet", then using the similar method as above to locate the beginning and end of each word, then reverse each word in characters, e.g. reverse "gnihtemos" to "something". This is an in-place method, which avoids using the extra temporaray buffer.

Mobile IP - Quick learn

2007-12-31T12:17:00.001-05:00


A very short description of Mobile IP is given in this post:
    
Purpose of Mobile IP: 
    Keep the mobile node's IP address unchanged when mobile node moves
    
Main modules used in Mobile IP: 
    MN(Mobile Node) - has a permanent home address 
    CN(Correspondent Node) - a host in the traditional network 
    HA(Home Agent) 
    FA(Foreign Agent) 
    COA(Care-Of Address) - the 2nd IP address of the MN 
    
How Mobile IP works: 
    1) MN first finds the FA's info (because FA broadcasts its information     
       periodically) - Agent Discovery 
    2) If MN is still in its HA's area, nothing to do with Mobile IP; else MN needs     
       to get a COA 
    3) MN registers the COA to its HA through FA (HA maintains a table,     
       including MN's COA) - Registration 
    4) HA sends data to FA through a tunnel - Tunneling 
    5) FA sends data to CN (MS's data is sent to CN through FA, not going back     
       to HA) 
    
Further explanation: 
    
Agent Discovery
    Extend the ICMP (Internet Control Message Protocol) message
    IRDP (ICMP Router Discovery Protocol) - automatically find the local router
     1) HA/FA use ICMP/IRDP to broadcast their info - agent broadcast
     2) MN sends the agent request (also in broadcasting)
 How to determine the mobility? ("life time" in IRDP)
     1) Agent sends IRDP including a "life time" field
     2) MN compares the network prefix in the broadcast messages to check if it's
        moved
     3) if MN cannot receive any broadcast message
        i) try to contact HA, as if it's back to HA
        ii) try to use DHCP or manual configuration
Registration
    MN -> FA -> HA (bind the 1st IP and the 2nd IP addresses together)
    When MN returns HA, needs to cancel the registration

    MN's Co-located COA: MN sends registration request to HA directly, tunneling is  
        from HA to MN, COA is MN's address
    In this case, there's no FA and HA in the traditional network 
        (using DHCP/manual configuration to get 2nd IP)
    PROS: no FA needed; 
    CONS: MN needs two IP addr, two overlapped IP protocol stacks

    FA's COA: FA sends the registration request to HA for MN, tunneling is from HA 
        to FA, COA is the FA's address
       PROS: multiple MN can share one COA, so IP address is saved; 
       CONS: need FA
    
    Frequent registration: on the boundary of two networks
        1) Data link layer solution: 
           Use layer-2 capability to manage the mobility, to reduce layer-3 mobility
        2) Mobile IP multiple binding:
           Similar as soft hand-over in CDMA
           In HA, for one registered MN, binds multiple COAs for this MN (when MN is 
           on the boundary of multiple FAs)
    
Tunneling (data forwarding): assure transparent transmission
    1) CN's information is still forwarded to HA (for CN, any MN is treated as if it 
       is fixed)
    2) HA uses proxy ARP to capture this information 
       HA works as an agent of the MN to give the MAC back to the CN
    3) Use tunnel to forward data to FA (FA records MN's MAC addr when MN is 
       registering)
    4) Reverse data is delivered to CN directly
    
Functions of HA and FA:
HA: 
    1) Act as a router 
    2) Manage the MN's host routing (binding table, maintain different tunnel to 
       different COA) 
    3) Manage and operate tunnel's interface (encapsulate beared protocol and then 
       forward with bearing method)

FA:
    1) Manage and operate tunnel's interface
    2) Manage visited MN's list (in registration)
    3) Use ARP to access MN (FA gets the original IP packet, but FA cannot access MN 
       directly since FA and MN are not in the same network, so FA needs to use ARP)
    
Encapsulation process in Mobile IP:
    1) IP in IP encapsulation - an outer IP header is inserted to the front
    2) Minimum encapsulation - reduce redundant information of the inner IP datagram
    3) GRE (Generic Routing Encapsulation) - encapsulate a wide variety of network 
       layer packets inside IP tunneling packets

[Code] Non-recursive pre-order traversal of a tree

2007-09-10T22:32:00.001-04:00

Traversal of a tree data structure often uses recursive algorithm. Without recursion, how to solve the problem? Here is the demo code I programmed in C.


001 #include <iostream> 
002 using namespace std; 
003 /**  
004   Definition of NODE of the TREE  
005 */ 
006 typedef struct NodeT 
007 { 
008   struct NodeT *left; 
009   struct NodeT *right; 
010   char data; 
011 }NODE; 
012 /** 
013   Definition of Element of the STACK 
014 */ 
015 typedef struct ElementS 
016 { 
017   struct ElementS *next; 
018   NODE *data; 
019 }ELEMENT; 
020 /**  
021   recursive version of Pre-order traversal 
022   void PreOrder(NODE * root) 
023   Algorithm: 
024     Print out the ROOT's value 
025   Do a pre-order traversal on the LEFT sub-tree of the ROOT node 
026   Do a pre-order traversal on the RIGHT sub-tree of the ROOT node 
027 */ 
028 void PreOrder(NODE * root) 
029 { 
030   if (root) 
031   { 
032     cout << root->data << "->" ; 
033     PreOrder(root->left); 
034     PreOrder(root->right); 
035   } 
036   else 
037     return; 
038 } 
039 /**  
040    non-recursive version of Pre-order traversal 
041    void PreOrderNonRecur(NODE *root) 
042    Algorithm:    
043    create a stack 
044      PUSH the root node of the tree into the stack 
045      While the stack is not empty 
046      POP a node 
047      If the node is not NULL 
048        Print the value of the node 
049      PUSH the node's right child into the stack 
050      PUSH the node's left child into the stack 
051 */ 
052 bool CreateStack(ELEMENT **stack) 
053 { 
054   *stack=NULL; 
055   return true; 
056 } 
057 bool DeleteStack(ELEMENT **stack) 
058 { 
059   ELEMENT *next; 
060   while(*stack) 
061   { 
062     next=(*stack)->next; 
063     delete *stack; 
064     *stack=next; 
065   } 
066   return true; 
067 } 
068 bool Push(ELEMENT **stack, NODE *data) 
069 { 
070   ELEMENT *p = new ELEMENT; 
071   if(!p) return false; 
072   p->data = data; 
073   p->next = *stack; 
074   *stack=p; 
075   return true; 
076 } 
077 bool Pop(ELEMENT **stack, NODE **data) 
078 { 
079   ELEMENT *p; 
080   p=*stack; 
081   if(!p) return false; 
082   *data = p->data; 
083   *stack= p->next; 
084   delete p; 
085   return true; 
086 } 
087 void PreOrderNonRecur(NODE *root) 
088 { 
089   ELEMENT *theStack; 
090   NODE *data; 
091   NODE *curNode; 
092  
093   CreateStack(&theStack); 
094   Push(&theStack, root); 
095  
096   while(Pop(&theStack, &data)) 
097   { 
098     curNode = data; 
099     if(curNode) 
100     { 
101       cout<<curNode->data<<"->"; 
102       Push(&theStack, curNode->right); 
103       Push(&theStack, curNode->left); 
104     } 
105   } 
106   DeleteStack(&theStack); 
107 } 
108 void main() 
109 { 
110   NODE a,b,c,d,e,f,g; 
111   /**  
112     manually construct the tree 
113   */ 
114   a.left=&b; 
115   a.right=&c;   
116   b.left=NULL; 
117   b.right=&d; 
118   c.left=&e; 
119   c.right=&f; 
120   d.left=&g; 
121   d.right=NULL; 
122   e.left=NULL; 
123   e.right=NULL; 
124   f.left=NULL; 
125   f.right=NULL; 
126   g.left=NULL; 
127   g.right=NULL; 
128   a.data='a'; 
129   b.data='b'; 
130   c.data='c'; 
131   d.data='d'; 
132   e.data='e'; 
133   f.data='f'; 
134   g.data='g'; 
135  
136   cout<<"Recursive pre-order traversal of the tree: "<<endl; 
137   PreOrder(&a); 
138   cout<<"End of traversal"; 
139   cout<<endl; 
140  
141   cout<<"Non-recursive pre-order traversal of the tree: "<<endl; 
142   PreOrderNonRecur(&a); 
143   cout<<"End of traversal"; 
144   cout << endl; 
145 } 
146 /** 
147   the output should be 
148   a->b->d->g->c->e->f->END 
149 */

[WiMAX] Fundamentals of WiMAX - (6)

2007-09-01T11:33:00.001-04:00

We have introduced the basic idea of OFDM before. In this post, we will discuss OFDMA (Orthogonal Frequency Division Multiple Access) in Q&A style.

Q: What's the relationship between OFDM and OFDMA?
A: OFDMA can be considered as a version of OFDM optimized for multiple users. The basic idea behind OFDMA is Sub-Channelization, i.e. assigning subsets of subcarriers to different users.

Q: What's the advantage of OFDMA over OFDM?
A: We know OFDM has immuity to frequency-selective fading channel because it breaks a single high data rate stream into multiple low data rate streams, thereby the subcarrier's bandwidth is smaller than the coherence bandwidth of the channel. For a wireless system with multi users, the total system resources are shared by all users. However, in one time slot, OFDM only assigns the whole resource to only one user, i.e. one user occupies all subcarriers in one time. This makes OFDM not efficient in resource allocation. A new multiple-access technique becomes necessary. This is the purpose of OFDMA. By allowing users share subcarriers and time slots, additional flexibility can be provided by OFDMA: multi-user diversity. In addition, adpative modulation can be used in OFDMA for different users according to channel condition.

Q: How is the 'Sub-Channelization' realized?
A: In OFDMA, the sub-carriers are divided into groups of sub-carriers. Each group is called a sub-channel. The sub-carriers that form a sub-channel need not be continuous. Based on their channel conditions and QoS requirements, different sub-channels can be assigned (scheduled) to different users. This multiple access is performed before the IFFT operation, thereby the scheduling algorithm used for OFDMA is realized in both frequency and time domain.

(to be continued)

Redirect homepage too fast makes cookie setting failed in IE7

2007-08-02T19:07:00.000-04:00

Yesterday I got a problem of setting cookies with Javascript in IE7. The cookie string was always generated successfully, but the cookie could not be stored by IE7. I set the privacy level of IE7 to "Accept all cookies", but it doesn't work yet. A simplified demo of the Javasript code is listed below:


<script language="JavaScript">
    var name="visitor";
    var value=Math.random();
    var today = new Date();
    var expires=new Date(today.getTime()+(86400*1000));
    var path="";
    var domain="";
    var secure="";
    var cookieString = name + "=" +escape(value) + 
       ( (expires) ? ";expires=" + expires.toGMTString() : "") + 
       ( (path) ? ";path=" + path : "") + 
       ( (domain) ? ";domain=" + domain : "") + 
       ( (secure) ? ";secure" : "");  
    document.cookie = cookieString;
</script>
<html><head><META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://www.google.com"></head></html>

Finally I found the reason. In order to store the cookies in IE7, you must manually "allow the active contents" to run.

However, the code <META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://www.google.com"> refreshes the webpage too fast and thus you cannot unblock the active contents in time.

For <META HTTP-EQUIV="Refresh" CONTENT="n;url" > , n means the number of seconds to wait before loading the specified URL. If we increase this n (e.g., let n=10 ), then we will have enough time to unblock the active contents, and then the cookie can be stored successfully.

[Wireless] Avis Connect - Auto Wi-Fi

2007-07-24T22:25:00.002-04:00

Last Saturday in San Jose's International airport, I found Avis (a rental car company) is providing a service called auto Wi-Fi. The device looks like a cable modem with two antennas. It says then you can connect to the Internet everywhere you go. The price is $10.95 per day, which is really cheap compared with other paid Wi-Fi services. I'm a little surprised how it works to provide Wi-Fi service when driving, because Wi-Fi is just a short range system and needs to connect itself to a 'real' Internet access network. Mobile WiMAX can connect to Internet direclty but as I know currently the WiMAX network is still under construction.

When I came back home, I checked the Internet and found the answer: it is a combination of a Wi-Fi router and a high-speed cellular modem. The access to the Interent uses a patent-pending, enhanced-reception technology from Autonet Mobile, which roams among existing 3G cellular networks and can switch seamlessly between neighboring networks and high/low-speed connections as needed without interrupting the session. This idea is pretty smart.

Autonet promises the service will work on 95 percent of U.S. roads in the future. It sounds pretty good. Next time for traveling by car, I will have a shot and check how the service is going.

[WiMAX] Fundamentals of WiMAX - (5)

2007-07-12T02:25:00.001-04:00

In this post, let's take a quick look of the standardizations of WiMAX.

IEEE 802.16 Group was formed in 1998, its inital focus is to develop an air-interface standard for a LOS-based point to mulitpoint wireless broadband system working in 10G-66GHz band. In 2001, the original 802.16 standard was completed. After that, the task group produced 802.16a, which is an amendment to 802.16. This 802.16a is for NLOS applications in the 2G-11GHz band. Further revision is IEEE 802.16-2004 (fixed WiMAX), which replaced all previous specifications and formed the first version of WiMAX standard. It targeted fixed applications. In order to support mobile services, in 2005 a new amendament to IEEE 802.16-2004 called IEEE 802.16e-2005 (Mobile WiMAX) was approved by IEEE.

In short, WiMAX uses OFDM in the physical layer. The difference of the two specifications is: IEEE 802.16-2004 uses fixed-FFT-size OFDM, but IEEE 802.16e-2005 uses scalable OFDMA. Therefore, for fixed WiMAX, because FFT size is fixed, the subcarrier spacing will increase with larger bandwidth, and then the symbol time will decrease. It implies that a larger portion of OFDM subcarriers is needed as guard time to overcome delay spread of the channel, which means spectral efficiency is lowered. In the contrast, for mobile WiMAX, the subcarrier spacing is fixed but the FFT size is adjustable. This scheme can be used to balance to requirements of delay spread and Doppler spread of the channel for different operating environments.

In addition to OFDM, in physical layer WiMAX also supports some optional advanced techniques for increasing the link performance and reliability. These techniques include powerful FEC - Forward Error Correction coding (such as Turbo coding and LDPC - Low Density Parity Check code, which is very close to the Shannon channel capacity), channel interleaving, multiple antenna techniques - MIMO (please refer to Fundamentals of WiMAX - (3) ) and adaptive modulation. From here you can see that WiMAX almost integreted the most popular and advanced techniques of digital communications together. This is an advantage of creating a new system, because you do not have too much back-compatibility issues to take into account.

Another big portion of WiMAX's standard is specifying the MAC layer functions between the lower physical layer and the upper network and transport layers. The MAC layer should be able to accommodate different traffic types, support QoS (Quality of Service), provide security and mobility and so on. Those are just common functions and are considered in almost every wireless system. The distinct part of WiMAX's MAC layer from other similar systems is on the scheduling and channel-access schemes. In downlink, the Base Station allocates dedicated or shared resources periodically to each subscriber station. Then each MS will use this allocated rresource to request bandwidth. This procedure is called Polling. Polling can be done with unicast or multicast. In uplink, WiMAX specifies a contention access and resolution scheme for multiple MSs accessing the shared resource. If one MS already has an allocation for traffic sending, it will not be polled. But it can be allowed to request more bandwidth.

Is iPhone a phone?

2007-07-05T21:07:00.002-04:00

The long rumored iPhone has finally arrived. Someone tore down the iPhone and found the processor is using ARM chips, the ROM and RAM are from Samsung, and the touch screen is made by Epson Imaging Device Corp. They estimated the hardware cost of 8GB iPhone will be about $270, which means the margin is about $330. Of course the margin cannot be that high, because the development cost is not taken into account. But it can be anticipated that the profit will be considerable.

So many reviews have been posted on the Internet officially by some evaluation groups or personally by Apple fans after June 29. No doubt some Apple fans shouted acclaims and some others attacked its shortcomings severely. I cannot afford buying an iPhone, but I'll try to give my two cents here based on the reviews I have read recently.

Basically, iPhone is not just a cell phone, it is even not just a smart phone. It innovates the UI (user interface) in a revolutionary way, which makes it so distinct. Although it lacks some functions that some ordinary handsets or smart phones are supporting, such as no voice dialing, no speed dialing, no games, only supports GSM and EDGE etc, its defects cannot obscure the virtues. The reason is that Apple does not have too much experience and technique accumulations on cell phone design, but it grows fast.

Shortly put, the applications of iPhone can be enhanced, the bugs can be fixed, and the services can be enriched gradually. They will not be problems as long as people have belief on it. Especially from the view of the psychology, Americans love to see a burgeoning force challenges the conventional world and finally gets the success (Google is a lively example). Of course, those big guys in handset industry will not await their dooms. They will fight back definitely. For customers, this will always be a good news. For Apple, the next generation iPhone will be critical and crucial. People can forbear the weakness even flaw of the new product, but cannot tolerate them again. I guess Apple alreay noticed this kind of issue. So, we'll see.

[WiMAX] Fundamentals of WiMAX - (4)

2007-06-19T18:51:00.001-04:00

Today we are talking about another important technique used in WiMAX - OFDM.

From the characteristic of the channel propagation in wireless environment, we know that delay spread caused by multipath fading will generate severe Inter Symbol Interference (ISI) for high data rate transmission, because the symbol time is inversely proportional to the data rate. As we mentioned before (Why OFDM for WiMAX and B3G?), you can use CDMA technology with Rake receiver to solve this problem, but it elicits two new problems: one is that the complexity is high, another is that you may need a huge bandwidth to get the essential spreading gain. For WiMAX system, the second problem is more difficult to handle with. But for UWB (Ultra Wide Band) system, it is achievable. So that's why one of the UWB's candidate PHY proposal is using spreading spectrum technique (DS-UWB).

Fortunately, a smart multi carrier modulation scheme called OFDM can support high data rate effectively. The basic idea of OFDM is simple: if you can not change the channel, you can change the signal to adapt to it.

We know in order to have a channel that does not have ISI, the symbol duration should be larger than the delay spread (or equivalently, the signal bandwidth should not exceed the coherence bandwidth). If we can divide the high rate date stream into M lower-rate substreams, then each substream will have larger subsymbol duration. If the subsymbol duration exceeds the delay spread, it hence is ISI free. Euqivalently, in this scenario, each substream's bandwidth is lower than the coherence bandwidth of the channel. However, simply dividing the high rate stream to lower-rate streams is just like the conventional mulit carrier technique, you have to insert guard band between subcarriers, which leads to very inefficient use of the available spectrum. OFDM solves this problem by overlapping subcarriers. Of course, you can not overlap subcarriers arbitrarily, because overlapping introduces crosstalk between subcarriers. But, if those subcarriers can overlap in orthogonality, great, the crosstalk vanishes!

A block diagram of OFDM system is shown in the following figure:

The modulator part is illustrated as follows:

And a simplified baseband model of passing an OFDM signal through the channel is demonstrated in the next figure:

Finally, the time-frequency block structure of the OFDM signal is shown in the figure below (where CP means cyclic prefix, whose length should be larger than the maximum delay spread of the channel):

War without smoke - LTE, UMB, WiMAX...

2007-06-07T23:03:00.001-04:00

"OFDMA TDD WMAN", the new name of a subset of WiMAX, was recommended by ITU-R as an IMT-2000 radio technology last week. It's a good news for WiMAX. Someone said: WiMax Gets ITU Standards Boost. Yes, it is. But, still a long way to go.

Let's take a look at how many candidate technologies we may have for the future:
LTE of 3GPP, UMB of 3GPP2, WiMAX, Mobile WiMAX/WiBro, IEEE802.20...

Ericsson said they abandoned WiMAX and would focus on LTE only, Qualcomm must be supporting UMB and they claimed they have many patents on OFDM/WiMAX, they also proposed IEEE802.20, Korea will continue working on the WiBro, even in the wired acccess area, there will be some Passive Optical Networks (PON) emerging in the future...

So who will win this war? Nobody knows, and it is impossible that one of them beats all others. I think some of them must be co-existing. But, the following answer should always be true: " It's something unpredictable but in the end USER's right. " (Lyrics of the Time of your life by Green Day) :-)

Capacity of ad hoc networks

2007-06-04T20:11:00.001-04:00

Unlike the conventional cellular networks with single hopping from every terminal to
the base station, traffic in ad hoc networks may be relayed via intermediate nodes to the distant destination. The advantage of this multi-hop communication scheme is: the required transmission power can be reduced exponentially with shortened transmission distance, and more concurrent transmissions may be available in the whole network because of spatial reuse of the resource, such as frequency or channelizing codes. However, it is very difficult to achieve the best of both worlds. With shortened transmission link, the number of hops from the source to the destination increases too. Partial system bandwidth must be used to deliver those relayed traffic. On the other hand, more concurrent transmissions result in increased number of interferers. Therefore, one of the fundamental challenges in ad hoc network research is what capacity can be achieved and how to achieve it.

Capacity of a network means the theoretical bounds on the performance under perfect network operation. Generally speaking, capacity or throughput analysis of wireless ad hoc networks may be explored in the following three ways:

1) The first solution is to find the exact capacity region (defined as closure set of feasible rates) in the perspective of information theory as in the conventional cellular network.

However, it is very difficult to obtain the exact capacity region because multiple nodes in the network can cooperate in very complicated and sophisticated ways. As an example, even the capacity of the simplest relay channel, which consists of just three nodes, a source, a relay and a destination, is not fully solved yet.

Recently, a breakthrough on the network information theory was obtained in [Xie 04]. With the assistance of the Max-Flow Min-Cut lemma, the authors indicate that the network capacity is always upper bounded by sum of total power used by the transmissions of all the nodes in the network.

2) The second method is to study the long term available throughput coarsely, e.g. analyzing the asymptotic capacity and scaling law with respect to the network size.

This method recently gained much attention, although it is coarser than the first one. The well-known result is given by [Gupta 00], who demonstrates that capacity per user goes to zero as the number of the nodes per unit area goes to infinity. This is a pessimistic result, because it means large ad hoc network’s capacity is poor.

After Gupta’s work, many people engaged in the ad hoc network capacity and tried to find a better solution. One important paper is the one written by Grossglauser and David Tse in 2002. The policy is, introduce the mobility of nodes into traffic transmission. Source node will first transfer to near relays, and those relays will not transmit to desired destinations until they move close. The throughput can be increased to the order of N, but the delay is too high.

Recently an interesting paper [Jafar-tit05] shows that too much mobility may limit the capacity of ad hoc networks. His argument is when mobility is too high, the node cannot track the channel in time to get the instantaneous CSI, then makes it difficult to distinguish between nearest neighbors and distant nodes at each moment.

3) The third one is measuring the practical throughput under some specific configurations by numerical simulation.

Many great simulation platforms have been developed for this purpose and a lot of research work can be found in this area. Some well-known examples are Network Simulator 2 (NS2), OPNet, QualNet (commercial version of Glomosim) etc.

NS2 is free to use, but OPNet and QualNet require licenses. I used NS2 for about more than one year. The learning curve is a little bit long. If you just want to use existing funcational modules to run simulation, it's not too hard. You can use TCL/OTCL to set up environment and parameters. If you want to modify the existing modules or add something new, you have to know how to interface TCL/OTCL with C++, because the kernel of NS2 is programed in C++.

However, when I used it, the version 2.28 has a problem in the interference and noise calculation in the physical layer: the SNIR (Signal to Noise and Interference ratio) is not recalculated every time the interference changes. A paper given by Mineo Takai addressed this problem in depth. Fading channel was not supported either. Someone made an extension with Rayleigh and Ricean fading but it only worked with old version. Fortunately, I found a solution by modifying some lines of the source code. Moreover, a difficult thing is how to compare your results with other guys'. Especially when you modified the program, no one knows if your modification can be justified (I think most of the simulators have the similar problem, but commercial platforms may be better because they keep the consistency well). So finally I abandoned it.

[WiMAX] Fundamentals of WiMAX - (3)

2007-05-27T22:47:00.001-04:00

Today we are talking about one of the two core technologies of WiMAX: Multiple Antenna Techniques (let's abbreviate in MAT). Another important one is OFDM, which will be deferred to next topic. Like all 3G systems picked CDMA, we can anticipate that perhaps almost all upcoming 4G systems will employ OFDM and MIMO (Multiple Input Multiple Output) techniques. (Recent an interesting news is that Qualcomm just gave a tough talk on the patents of 4G. )

What can MAT provide? Generally speaking, MAT supports
1) spatial diversity,
2) beamforming,
3) and spatial multiplexing.

In old times (1970s), people only use multiple antenna in receiver owing to the cost and size consideration. In this case, with selection combining or maximal ratio combining (MRC), the performance under fading environment can be improved significantly due to receive diversity.

Later, people noticed that using MAT with beamforming can concentrate the power of the desired signal in a specific direction and lower down the interference to other links away from this direction. This is especially useful for multi user network. They call it smart antenna technique. One example is the TD-SCDMA system in 3G area.

In the late of 1990s, a key breakthrough was made for MAT. Transmit diversity schemes were invented, such as the space-time block code (STBC). Now the promising area of MAT is the spatial multiplexing.

For the receive diversity, you can find it from most of the wireless communication books. So we will focus our concentration on the transmit diversity and beamforming.

1) Transmit diversity
There are two types of transmit diversity, one is open-loop, another one is closed-loop. Open-loop means at the transmitter you don't need a feedback for the channel state from the receiver. On the contrary, closed-loop requires it. Thus you should guarantee the channel is with reciprocity. In some cases, you can assume the channel to be reciprocal, although it isn't.

Open-loop transmit diversity
The most popular open-loop transmit diversity scheme is STBC, where a special coding scheme (called Alamouti code, name of the inventor, who is currently the CTO of Intel's Mobility Wireless Group) is used in the transmitter. In short, a Nt*Nr STBC achieves the same diversity order and data rate as a Nr*Nt receive diversity system with MRC, but with a 10*log_10(Nt) transmit power penalty because of Nt transmit antennas.

For WiMAX or other OFDM-based system, the space/time coding can be coded over adjacent subcarriers rather than time slots.

Closed-loop transmit diversity
In this case, channel state information(CSI) is required at the transmitter. Because channel changes quickly in a highly mobile scenario, it is difficult to track the channel state in time and feedback it to the transmitter. Therefore, closed-loop transmit diversity tends to be suitable for fixed or low-mobility scenarios. Two important closed-loop schemes are: transmit selection diversity (TSD) and linear diversity precoding (LDP).

In TSD, only a subset of Nt transmit antennas are selected with good CSI, thereby comparing with STBC, TSD has less transmit power penalty because fewer transmit signals are sent.

In LDP, a linear precoder is used at the transmitter and a linear postcoder is applied at the receiver. They are used to improve the link reliability and can achieve higher SNR than the open-loop schemes.

Free talk - Analogy between wireless network and society

2007-05-25T15:39:00.000-04:00

Today when I was on the metro bus, an idea jumped into my mind: there is some similarity between the wireless network and the human society.

For example, a sensor network with data aggregation is as a community, a cellular network is like a country ruled by a dictatorial government, a pure ad hoc network can be considered with Anarchism (means abolition of governments), and a network with multiple access points is like a society with democracy (some nodes are 'elected' as access points).

The interesting thing is, what is good for the administration of the society, republic, federal , democracy or autocracy? Similarly, which network topology is effective for a wireless network? Why the existing mobile networks use the cellular architecture? Why most 802.11 networks are configured in IBSS (Infrastructure Basic Service Set)? Think about it...

[Wireless] Why OFDM for WiMAX and B3G?

2007-05-12T13:55:00.002-04:00

In the beginning of 3G (Third Generation) era, CDMA technique was widely employed for most systems. For instance, 3GPP selected WCDMA (Wideband CDMA) for FDD mode, TD-SCDMA for TDD mode; 3GPP2 extended cdmaone to CDMA2000. The main reason is to support higher data rate wireless service in 3G systems than that in 2G systems.

Wideband CDMA system has a large bandwidth, which can be used to achieve frequency diversity. However, there exists a contradiction between the large bandwidth and high data rate which can be shown in the following simple diagram:

Wide bandwidth -> frequency selective channel -> causes large delay spread in time domain
High data rate -> small symbol interval -> experiences serious Inter Symbol Interference

For CDMA system, in order to combat this multipath delay spread, usually it has to resort to the sophisticated RAKE receivers, which resolves multipath using muliple fingers.

However, when wireless system goes to the broadband era, wideband CDMA may not be adequate. Even 3GPP proposed HSPDA/HSUPA to support data rate up to 14.4M/5.8Mbps in 5MHz channel , 3GPP2 proposed 1xEV-DO for data rate 3.1M/1.8Mbps (revision A), 4.9M/1.8Mbps (revision B) in 1.25MHz channel, their capability of supporting much higher data rate is limited. One reason is that they have to use multiple codes simultaneously, which may result in self-interference.

That's why in B3G (Beyond 3G), LTE (Long-term evolution) of 3GPP and AIE (Air Interface Evolution) of 3GPP2 both pick OFDM combining MIMO instead of CDMA. Similarly, in IEEE802.11 series, the low date rate is working on CDMA (802.11b) but high date rate uses OFDM (802.11g and 802.11a). WiMAX is also using OFDM.

[WiMAX] Fundamentals of WiMAX - (2)

2007-05-08T22:05:00.000-04:00

In this part, we are going to give an overview of the wireless channel that may be experienced by WiMAX.

Generally speaking, the basic and important issues of wireless channel contain three aspects: pathloss, large-scale Shadowing and small-scale fading. You can find detailed descriptions of them in most of the books regarding wireless communications (chapter 4 and 5 of [1]). In summary, pathloss is inversely propotional to the distance between the transmitter and the receiver, Shadowing is mainly caused by obstructions within the propagation environment and is often log-normal distributed, small-scale fading is caused by multipath reflections (modeled by delay spread or coherence bandwidth) or motion between the transmitter and the receiver (modeled by Doppler frequency shift or coherence time).

So we will skip those fundamentals issues and assume that you have already known them very well. However, channel also varies over space if multiple antennae are used. Multiple antenna techniques emerged as a breakthrough in the last several years and some traditional books may lack of description on this part, thereby next we will give an outline of the spatial aspect of wireless channels.

Angular Spread

Like delay spread or Doppler spread, a parameter used to model the channel in space is the angular spread. It refers to the statistical distribution of the arriving signal's angle. A small angular spread means the received signal's energy is more focused, which implies less statistical diversity; contrarily, large angular spread means more statistical diversity available.

Coherence Distance

The dual of angular spread is coherence distance. A coherence distance Dc means that any physical positions separated by Dc have an uncorrelated received signal amplitude and phase. Coherence distance is often related to the wave length. Thus, higher frequency system has shorter coherence distance.

Coherence distance is often used to specify how far apart antennae should be separated to make received signals statistically independent. Small coherence distance means antenna array can be easily applied to provide rich diversity. This is particularly useful for mobile terminals which has the size constraint. Large coherence distance implies that large separation between two antennas is needed. In this case, it would be preferable to use beamforming with antenna array.

Channel model for OFDM

Since WiMAX is using OFDM, the channel model with multidimension correlation should be considered. When channel is highly frequency selective, it requires a large number of closely spaced subcarriers to combat the ISI (Inter Symbol Interference). On the other hand, when the channel is with large Doppler frequency shift (high mobility), it will degrade the subcarrier orthogonality. In the frequency domain, it will cause significant ICI (Inter Carrier Interference) as subcarriers become more closely spaced.

Emperical model

An emperical channel model for MIMO was proposed and developed by 3GPP (Third Generation Partnership Project). It is described in the technical report TR 25.996 [2]. This model can be used for systems such as WiMAX, 802.11n and 802.20 which use MIMO techniques.

Reference:
[1] Theodore S. Rappaport, "Wireless Communications: Principles and Practice (2nd Edition)," Prentice Hall PTR, December, 2001
[2] Spatial channel model for Multiple Input Multiple Output (MIMO) simulations http://www.3gpp.org/ftp/Specs/archive/25_series/25.996/

[WiMAX] Fundamentals of WiMAX - (1)

2007-05-06T19:48:00.000-04:00

WiMAX (Worldwide Interoperability for Microwave Access) is one kind of wirless broadband access technology. In my country, China, WiMAX is going to be deployed for the 2008 Olypmic games. Actually, in China there is another technology called McWill (Multicarrier Wireless internet Local Loop), which is a synchronous CDMA system using Smart Antenna , SWAP signaling , synchronous CDMA and Software Radio. This McWill is developed by a Chinese company. I remembered in the end of 2006, the news said McWill would be used for 2008 Olympic games. However, just after several months, the latest news says that WiMAX is authorized by the committe of the Olympic games and China Mobile is goint to deploy it in 2008. It looks like McWill lost the game. It is really a pity.

Ok, let us go back to our topic and concentrate on techniques. From today, I'm going to give a series of introduction of WiMAX, mainly focuses on its fundamental issues, such as overview, history, technicall challeges, physical layer, MAC layer etc. I think it also helps me consolidate my knowledge on WiMAX.

History of WiMAX

Before WiMAX, there already exist many wireline broadband access techniques, such as DSL(Digital Subscriber Line), cable modem, FTTP(Fiber to the premises ) and VDSL. This market grows quickly. When I came to the US in 2001, the rate of Verizon's is about 768Kbps. Now I'm using Comcast's cable modem with rate 5Mbps. Recently, Verizon is promoting its FIOS system which is said to support rate at 15-40Mbps.

Later, people found it is necessary to provide broadband access service in wireless, because it offers additional benifits and convenience. For example, it may be easier to install than wire-line access, the cost may be lower, it can be portable and mobile.

Generally speaking, wireless broadband access can be categorized into two types:
1) Fixed wireless broadband,
2) Mobile broadband.

As for WiMAX, it has evolved through four stages. [1]
1) Narrowband WLL (Wireless Local Loop) system
2) First generation LOS (Line of Sight) broadband system
3) Second generation NLOS (Non Line of Sight) broadband system
4) Standard-based broadbank system.

Next, let us take a quick look of those four stages.

1) Narrowband WLL

It is mainly based on DECT or CDMA. As I know, WLL on CDMA at 450MHz has been using in China for a long while.

2) LOS

In 1990s, LMDS(Local Multipoint Distribution System), works on 2.5 or 3.5GHz. Operator: Nextlink. Now it is almost dead. [2]

In late 1990s, MMDS(Multichannel Multipoint Distribution System), works on 2.5GHz. Operators: MCI, Sprint.

Starting in 2006, MMDS frequencies in the 2110-2155 MHz range are being re-allocated for the Advanced Wireless Services (AWS-1). [3]

3) NLOS

It is proposed to overcome the LOS issue, and improve link performance under multipath conditions. It may use OFDM, CDMA or multiantenna techniques.

4) Standard-based

It is the well-known IEEE 802.16x [4], a seriers of standards for Wireless Metropolitan Area Network (WMAN).

December 2001, IEEE 802.16 standards completed for > 11GHz.
Wireless WAN-SC, uses single carrier modulation techniques. MAC layer is with TDM.
January 2003, IEEE 802.16a standard completed.
Works in the 2GHz to 11GHz range, enables NLOS deployments by using OFDM. MAC is using OFDMA.
June 2004, IEEE 802.16-2004 standard completed and approved.
It replaces 802.16, 802.16a, 802.16c with a single standard. It is also called Fixed WiMAX.
December 2005, IEEE802.16e-2005 approved.
Supports vehicular mobility applications. It is also referred to as Mobile WiMAX.

Similar to 802.11x, IEEE established the specifications for WiMAX but left to the industry the task of converting them into an interoperable standard and the task of certification. WiMAX Forum (analogous as Wi-Fi Alliance) was formed to do those tasks.

References:
[1] J.G.Andrews, Arunabha Ghosh and Rias Muhamed, "Fundamentals of WiMAX-understanding Broadband Wireless Networking", Prentice Hall, Feb, 2007

[2] http://en.wikipedia.org/wiki/MMDS

[3] http://en.wikipedia.org/wiki/LMDS

[4] http://en.wikipedia.org/wiki/Wimax

Export figure to pdf in Matlab

2007-04-28T19:23:00.000-04:00

In LaTex, if the figure is in pdf format, you can click pdfLaTex just once to generate the output. Otherwise, if the figure is in eps format, you have to click button three times to do the same thing by using the LaTex -> dvi2ps -> ps2pdf workflow.

The good thing is, Matlab can export figure to pdf format. Unfortunately, when saving a figure to a pdf file in Matlab, you'll find the figure doesn't fit the layout very well, i.e. there is a large margin from the figure to the page boundary. Those margins will be inserted into the LaTex output when you include these pdf figures.

A solution is:
1) After you plot the figure in Matlab, go to 'File->Export Setup', input the size of the output you want, e.g. Width: 6 inches, Height: 5 inches. Then click 'Apply to Figure' button.
2) Don't close the 'Export Setup' window. Go to 'File->Print Preview->Paper', input the same size in the Width and Height options.
3) Don't close the 'Print Preview' window. Go back to the 'Export Setup' window, and click 'Export', then select pdf format and save it.
4) Check the output pdf file, you'll see it is perfect.

Making Slides Using LaTex

2007-04-27T08:48:00.002-04:00

Recently I'm preparing for my dissertation slides. I used to create transparencies with PowerPoint because of its simplicity, but it is really difficult to cope with mathmatical equations. You have to reserve space for equations in the text, and if you modify some equations later, you may have to readjust their reserved space one by one.

So I transfer to LaTex, although I need some time to learn it, it is powerful. It has rich overlay and dynamic effects. The layout, the colors and the fonts can easily be changed. The most important thing for me is that it can merge text and mathematical formulae smoothly and can reuse LaTex codes of my previous papers.

There are some well-known existing packages for slides making in LaTex, such as Beamer, Proper, Foiltex etc. I didn't spend too much time on investigating and comparing those packages pros and cons. I just select the Beamer.

After half day's learning, I can create slides with Beamer quickly. Beamer can handle graphics but with less flexibility, e.g. locating the position of figures freely is not that easy. Fortunately, I found another package called 'pstricks' which can do this kind of work easily. However, pstricks does not support PdfLaTex. The workflow of pstricks is LaTex->dvips->pspdf.

The following figure is a demo of the slides created by Beamer.

Error LNK2001: unresolved external symbol...

2007-04-25T15:30:00.000-04:00

Recently, when I used the templates in C++, I got a link error: unresolved external symbol "public: __thiscall ...". My work has three files: fc.h, fc.cpp and main.cpp.


------------------------------------------------

// fc.h

template <class T>

class fc

{

    public:

       func();

};

// end of fc.h//

------------------------------------------------

// fc.cpp

template <class T>fc <class T>::func() { }

// end of fc.cpp//

------------------------------------------------

// main.cpp

#include "fc.h"

int main()

{

    fc A;

    A.func();

}

------------------------------------------------

However, when I removed the template declaration from the header file, or put all three files just in one body, the link runs smoothly. Finally, I found the reason and the solution of this kind of problem from the Internet [1].

At least three cases are related to this link error:
1. Forget to define a declared member function, especially the constructor.
2. Static member or class.
3. Using template with splitted declaration and definition.

For the first scenario, in general, people will not forget to define a member function after the declaration. So this kind of link erro seldom appears. But sometimes people may have declared the constructor but forget the definition and think the system will do it automatically. It is right that system may creat the default constructor if you don't declare it. But this doesn't work when the declaration has been made.

For the second case, if a class has a declared static member, because you cannot initialize it inside the class body (it belongs to the class, not the object), so if you forget defining this static member outside the body, the link error will also occur.

The thrid one is the well-known fallacy: templates behave similarly as ordinary classes and functions with respect to the separation between their declarations and definitions. This is not true. The reason is that a template actually is NOT real code. A good anologic example is: the MS-Word has some letter templates, but they are not real letters until you fill them out. Therefore, one thing we need to remember: templated functions and classes don't actually exist until you use them! A solution is: a header file including template declarations also constains their definitions. However, this seems to violate the rule of the separation of the declaration and definition.

Reference:
[1] http://www.informit.com/guides/content.asp?g=cplusplus&seqNum=298&rl=1

Cooperative Diversity for Wireless Networks

2007-04-15T23:50:00.000-04:00

Cooperative diversity can emmulate an antenna array and then exploit spatial diversity in wireless networks with fading channels. It exploits the broadcast nature of the wireless medium and allows radios to jointly transmit information through relaying.

Traditionally, in ad hoc networks, packets are forwarded from the source to the destination through multi hops serially. The well-known capacity of wireless networks obtained by Gupta and Kumar in 2000 is with this strategy. By using Cooperative diversity, the source and the relay nodes may cooperate together for data transmission. The capacity of this kind of network has been investigated by Xie and Kumar.

The use of cooperative diversity is manifold:
1) Increase capacity (enlarge capacity region)
2) Improve reliability in terms of diversity gain
3) Diversity-multiplexing tradeoff

Different algorithms can be applied for cooperative communication, some examples are:

1) Amplify-and-Forward
In this case, relays just simply amplify the received signal with a linear transformation.
2) Decode-and-Forward
Relays first detect and decode the received signals and then re-encode them. This decoding and re-encoding procedure can be considered as a non-linear transformation.
3) Selection and dynamic relaying
In this case, cooperative terminals adapt their transmission format according to the measured channel state information.
4) Incremental relaying
This scheme exploits limited feedback from the destination terminal for relaying.

Incorporating the cooperative diversity into the network is still an open problem.

Reference:
[1] J. Nicholas Laneman, "Cooperative diversity: models, algorithms and architectures," Cooperation in wireless networks, Springer, 2006

Adaptive modulation v.s. High order diversity

2007-04-11T11:30:00.000-04:00

Today's learning: adaptive modulation may become unnecessary as the diversity order is increased. It can be viewed as a lower-complexity alternative to diversity technologies, such as MIMO.

Remember, adaptive modulation or diversity only offers advantages over fading channels. Adaptive modulation can employ high-order modulation schemes to adapt to the channel state and then increase the system throughput. Diversity utilizes the independent property between two or more links. When only one receiver is provided, adaptive modulation can be employed. But when more than two receivers are available, it is better to use diveristy technologies.