Friday, July 11, 2014

802.11 n and ac Transmit Beamforming: Crash Course

Theory


Beamforming: Form the beam in the direction of destination. Simple, isn't it? Well for starters that's the aim, but we have lot of obstacles in the path, read the mathematics part and you will "its not that simple after all." :-).

Traditional antenna, radiates omnidirectionally meaning everywhere, but for some use cases we need to focus on specific areas/directions, like when there are multiple destinations we want to make sure the one with whom we are speaking gets the best SNR.

For 11n, this was simpley a SNR improvement technique, but for 11ac with the introduction of MU-MIMO we need to communicate with multiple users simultaneously without any cross-interference. So the need for beamforming is more in 11ac.

Generally we use this in cases where the No of antennae are more than the no of spatial streams like 4X2, 8X4 etc.

Beamforming gains are expected to be approximately 3 dB in the transmitted direction. In practice, this gain will typically be one step up in data rates (increasing one MCS number) for a mid-range transmission.

Beamforming is achieved by combining elements in a phased array in such a way that signals at particular angles experience constructive interference while others experience destructive interference


Basic Mathematics


Lets take a look at how do we arrive at those angles, and lets try to keep the mathematics simple and not delve in the gory details.

MIMO communication can be modeled as below

Yk = HkXk + n

X ==> Vector of Tx signal using Ntx antennae [ x1 x2 …xNtx]
Y ==> Vector of Rx signal using Nrx antennae [y1 y2 …yNrx]
H ==> Channel Matrxix Ntx X Nrx.
k  ==> Subarrier
n  ==> Constant Noise in the Channel

Now in order to make sure transmitted signal is steered towards the receiver, we have to tune the transmit signal in such way that we control the phase and amplitude so that the resulting signal will be received by that particular receiver with good SNR.

In mathematical form, we need to calculate the matrix Qk referred as steering matrix, such that Yk is optimized.

Yk = HkQkXk + n

Qk has values known as weights to control phase and amplitude for all Transmit Antennae for that particular subcarrier k.

X is the beamformer
Y is the beamformee

Still with me? Lets do the same for MU-MIMO,

Yku = HkuQkuXku + n

u==> user, specific beamformee.

Qku has values known as weights to control phase and amplitude for all Transmit Antennae for that particular subcarrier k and for that particular beamformee u.


Types 

Explicit Feedback


Qk is formed based on the Feedback from the receiver. So Y will send some training data known as sounding data, based on which X estimates the channel characteristics and derives Qk.

This sounding known as NDP (Null Data packet) sounding uses a special packet with Length 0 as the name indicates.

Here channel need not be reciprocal, as feedback is given based on NDP (from beamformer-beamformee) which is same direction as data packet.

Implicit Feedback


Beamformer X chooses Qk, and adjusts it based on the feedback of beamformee Y.There is not extra data being sent by beamformer, it only prepares the feedback based on the normal data signal from beamformee.

But as the feedback is based on the channel characteristics from Y to X, based on which X decides Qk for X to Y, so this only works when the channel is reciprocal.

Uncompressed


The feedback sent by beamformee comprises of entire beamforming feedback matrices, known commonly as Vk based on which Qk is derived.

Compressed

The feedback sent by beamformee comprises of angles instead of the full matrix which will be decompressed in to full matrix Vk at beamformer.

To understand how we derive Qk from Vk we need to understand SVD (Singular Value Decomposition) which is complex matrix factorization technique outside the scope of this article.

For 11ac only compressed beamforming technique is allowed.

That's the most we can go without getting our hands dirty with some advanced mathematics (SVD, matrices) etc. Hope this throws some light on inner details of beamforming.

References:

1) IEEE specs
2) Wikipedia.

Revision Info:


1) Fixed the definitions of explicit and implicit beamforming: Thanks to Ashok Bandi.

Friday, March 21, 2014

Finding and Installing the right device driver for your HW in Linux

The biggest problem making any hardware work is finding the right driver, how many of us spent days trying different driver packages and finally nothing works, especially in windows!

Because i get lots of queries in this area, here's a tutorial to find the right driver for your WiFi card, of course in Linux. 

The below procedure is automated and happens when you insert a device, creating a network interface ready to use (Will explain this in another article). 

But, for some reason if that's happening, this procedure helps us to find the kernel version which/from which that HW is supported.

Steps:

1) Insert the device :-)

2) Depending on the BUS interface it uses, issue the command "lsusb/lspci", check for the device in the list. 
For Eg: Lets take a belkin WiFi adapter.

# lsusb
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 001 Device 002: ID 8087:0020 Intel Corp. Integrated Rate Matching Hub
Bus 002 Device 002: ID 8087:0020 Intel Corp. Integrated Rate Matching Hub
Bus 001 Device 003: ID 413c:2107 Dell Computer Corp.
Bus 001 Device 004: ID 04ca:0061 Lite-On Technology Corp.
Bus 001 Device 028: ID 050d:615a Belkin Components F7D4101 / F9L1101 802.11abgn Wireless Adapter [Broadcom BCM4323]

If it is not appearing in this list, check dmesg for any errors. If not pray to god. (This will probably be another article :-))

Make a note of the ID, in this case 050d:615a the first part is Vendor ID representing the maker of the chipset, second part identifies the chipset itself the Product ID.

We will use these ID's to find the right driver for this chipset.

3)  As discussed in earlier articles the depmod comes to our aid, it creates a mapping file called "modules.alias" which has the mapping information of ID to driver.

Refer depmod and modules.alias (go to DETAILS section).

Now we will check the file modules.alias in all kernel version to check for any supported driver for this chipset.

grep -irn "v050dp615a" /lib/modules/<kernel version>/modules.alias

Note: Append "v" before vendor ID and "p" before product ID. 

4) Ff no results are found, best thing is to check for latest vanilla kernel and do a binary search from there, generally if its not supported in latest it will be not supported, unless its an old HW for which support was removed in latest.

The problem here is to access the modules.alias (which will be in the kernel installation directory, generally /lib/modules) we need a compiled kernel, so it might take time if the latest kernel is not already compiled and installed.

(Any scripts are welcome here).

5) If you find a driver, just do a modprobe -v <driver name>. 

Eg: 

alias usb:v0B05p1761d*dc*dsc*dp*ic*isc*ip*in* rt2800usb
modprobe rt2800usb.

If still the driver is not found, probably that chipset is not supported in Linux, is that even possible? Linux has a very good support for supporting different HW's.

Don't worry we still have ways to make it work. NDISWrapper comes to the rescue. We can use NDIS wrapper in below scenarios (from #4)


  1. No open source driver provided in the Ubuntu repositories.
  2. The driver provided by default in Ubuntu is not working out.
  3. The proprietary driver provided by the card vendor is not working out.
  4. Test ndiswrapper performance versus alternative driver(s).
  5. Test hardware failure for your card.


NDIS Wrapper:

NDIS is similar to mac80211 in Windows, all the network drivers Ethernet, wireless, Bluetooth use this layer which implements the entire WDM driver model and make life easier for windows network device driver developers.

This functionality is ported to linux, where we can take any NDIS based windows driver (any windows network driver) and make it work in linux.

(Detailed discussion in another article, lets not deviate here. For those of you cant wait, see #5 for some basic idea on how it works, summary here.)


  • NDISwrapper is composed of two main parts, 

    • Command line tool used at installation time 
    • Windows subsystem used when an application calls the Wi-Fi subsystem.

  • "compile" a couple or more of Windows files, and the NDISwrapper's version of Windows DDK into a Linux Kernel Module. This is done with a tool named "ndiswrapper". 

  •  A Linux application can then send request to this Linux driver that automatically does the needed adaptations to call its—now—internal Windows driver and DDK.


Please follow the below steps, to install the windows driver in linux.



  1. wget <Link to the windows driver binaries, *.sys, *.inf>
  2. cd <Directory>
  3. ndiswrapper -i <INF file name>
    • This command will install the windows driver in Linux through the ndiswrapper utility.
  4. ndiswrapper -l
    • check the list of windows driver installed using ndis wrapper.
  5. Install the ndiswrapper Linux driver if not already installed (Distro Specific installation/ download from source).

    1. depmod -a
      • rebuild the modules database, so that next step will work.
    2. modprobe ndiswrapper
      • Load the ndiswrapper driver
    3. Steps from #1 for reference. 



Now download this file to your desktop:http://downloads.sourceforge.net/project/ndiswrapper/stable/ndiswrapper-1.59.tar.gz Right-click it and select 'Extract Here.' Then do:
cd ~/Desktop/ndiswrapper-1.59
make
sudo make install
sudo modprobe ndiswrapper

Note: Even the though the example is related to a wifi device driver, but the same procedure can be applied to any device driver.

Happy Device Driving!

References: 

1) http://askubuntu.com/questions/394159/belkin-n600-usb-wireless-adapter-on-ubuntu-12-04 

2) http://www.cyberciti.biz/faq/linux-ndiswrapper-wpa_supplicant-howto/

3) http://sourceforge.net/apps/mediawiki/ndiswrapper/index.php?title=Main_Page

4) https://help.ubuntu.com/community/WifiDocs/Driver/Ndiswrapper 

5) http://en.wikipedia.org/wiki/NDISwrapper#Use

Thursday, January 23, 2014

Building Linux Kernel Modules Faster: Internal and external


*For Newbie Linux Kernel and Device Driver developers*.

Most repetitive activity for Kernel and Device Driver developers. is building modules they work on and installing them. So lets discuss few tricks to build them faster way.

Traditionally, when we change a source code of a module, we need to 


a) Build the entire kernel again
make; make module;make modules_install;make install
(optionally using "-jN" option to make)
b) reboot and use the new modules.

But we can avoid reboot by 

a) Build the entire kernel again
b) Remove the old module 
c) Insert the new module.

Building the kernel itself is a time consuming process, especially when we just want to update code specific to our module. So for that we make use linux kernel's support and procedures for building external modules  i.e., modules which are not present in the kernel tree for modules in the kernel tree. Sounds Confusing?

Lets say we have written a new module and wanted to compile it, then we write a makefile which invokes the kernel makefile with below option:

make modules M=<Dir_of_new_Module>

But to compile a internal module (module which is present in the kernel tree) we use the same trick, except the makefile is already present. Just follow the below procedure

Procedure: 

  1. make silentoldconfig  (Optional)
    • whenever Kconfig is changed., For other cases like make and make modules (without M=) this is run by kernel makefile itself.
  2. make modules M=<path_to_dir>
  3. make modules_install M=<path_to_dir>
  4. Remove the old module and Re-Insert the new one.

Still interested of know-how, see the steps in detail:

Details:


1) Whenever we change Kconfig, .config will be updated and we need to tell the kernel makefile to use the new .config instead of using old one.This does that.

2) This uses the makefile in the module sub directory and compiles the files w.r.t #1 .config options.

3) This will install the compiled modules in to the install path /lib/modules//`uname -r`/kernel/ (or) /lib/module/`uname -r`/extra/ depending on whether the module is internal/external. In our case its always extra as we are using "M=" option for building modules. We can add some prefix (extra folder name under the above paths).

Also it used the depmod utility (through a wrapper shell script: scripts/depmod.sh) to generate the below files which will later be used by modprobe.


  • /lib/modules/`uname -r`/modules.alias
  • /lib/modules/`uname -r`/modules.alias.bin
  • /lib/modules/`uname -r`/modules.builtin
  • /lib/modules/`uname -r`/modules.builtin.bin
  • /lib/modules/`uname -r`/modules.ccwmap
  • /lib/modules/`uname -r`/modules.dep
  • /lib/modules/`uname -r`/modules.dep.bin
  • /lib/modules/`uname -r`/modules.devname
  • /lib/modules/`uname -r`/modules.ieee1394map
  • /lib/modules/`uname -r`/modules.inputmap
  • /lib/modules/`uname -r`/modules.isapnpmap
  • /lib/modules/`uname -r`/modules.ofmap
  • /lib/modules/`uname -r`/modules.order
  • /lib/modules/`uname -r`/modules.pcimap
  • /lib/modules/`uname -r`/modules.seriomap
  • /lib/modules/`uname -r`/modules.softdep
  • /lib/modules/`uname -r`/modules.symbols
  • /lib/modules/`uname -r`/modules.symbols.bin
  • /lib/modules/`uname -r`/modules.usbmap

Lets discuss the important ones below: 
  • /lib/modules/`uname -r`/modules.dep
    • Depmod is a utility which will use the "System.map" and try to work out the dependencies between the modules and create a file called "modules.dep", used by modprobe to insert (insmod) the modules in proper order.
    • /lib/modules/`uname -r`/modules.order and /lib/modules/`uname -r`/modules.symbols will be used in that process.
  • /lib/modules/`uname -r`/modules.alias
    • It identifies the HW devices each device driver supports and writes to a file "module.alias" using which the linux kernel device model can insert the driver along with its dependencies (using modprobe and modules.dep) when it  enumerates a new HW device using PCI/USB ..
  • /lib/modules/`uname -r`/modules.builtin
    • This gives a list of modules which are staically linked to the kernel forming part of vmlinuz.
  • /lib/modules/`uname -r`/modules.<BUS>map
    • These files will the known drivers for devices and give informtion regarding the device like vendorid, subsystemid, deviceclass etc.
    • This is used to create module.alias
4) Now that we have all the necessary files, use below commands "-v" is for verbose and "-r" is for using rmmod. By default it used insmod.
  •     modprobe -v -r 
  •     modprobe -v 
Installing depmod and modprobe: Install the "https://www.kernel.org/pub/linux/utils/kernel/module-init-tools/" package with your distro specific instructions.


Common Caveats:


1) If you are not seeing the changes in the new module: 

Probably you are re-inserting the old modules add "-v" to the modprobe and check the timestamps in the path from where modprobe is insmod-ing the module and your module in the kernel tree.  
Running "make modules_install" again should do, if all else fails then try copying manually.

2) If you are seeing a warning about module version check, while inserting the module: 

Probably you are using the above procedure for two dependent modules, like changing a function in cfg80211 and using that one in mac80211. 
Its better to use a directory which hold the directory of both of these, in the above case use "make modules  modules_install M=net/". For more details read Module Versioning Section in R#3.


References:

1) Linux kernel Makefile :-) 
2) Building External Modules
3) Kernel Docs: Building Linux kernel