In this project, we developed a tool which can help detect failures in a virtualized environment. Besides detecting failures, it could also provide useful information regarding, for example, whether certain resiliency policy worked as it was desired to. Thus, it can help the corresponding engineer to better prioritize their time (for example, after some failure, the resiliency policy worked perfectly (i.e., no impact), then the corresponding engineer might not need to fix the bugs that caused the failure immediately, if he/she happened to have other tasks at hand.)

QPS is an “add-on” scheduling algorithm for input-queued crossbar switches. It builds upon “simple” Queue-Proportional Sampling, and achieves $O(1)$ time complexity per port. It can boost the performance (throughput or delay or both) of a large amount of existing switching scheduling algorithms (e.g., iSLIP, SERENA).

ForestStream is a novel measurement algorithm suite which combined streaming algorithm techniques and graph sampling techniques. Unlike traditional graph sampling techniques, ForestStream can unbiasedly sampling certain portion of trees from a graph forest, thus is able to achieve much higher accuracy than traditional graph sampling techniques.

In this post, we will deal with the following XOR problem. Given $l$ consecutive nonnegative integers which start from $s$, i.e., $s, s+1, \cdots, s + l - 1$, you are asked to get the XOR of them, i.e., $XOR_{x\in [s+l-1]\setminus [s-1]}x$, where $[s]={1,2,\cdots,s}$. An algorithm with complexity $O(l\log (s + l))$ is straightforward: XOR these numbers one by one (see the following pseudo-code).

def XOR(s, l):
    x = 0
    for s in xrange(s, s + l):
        x ^= s # note, for general case, you have to implement your own XOR for long-bit integers
    return x

Logarithmic Solution

Now, let’s see a logarithmic solution, i.e., an algorithm with complexity $O(\log (s + l))$.

As we know, XOR of multiple single-bit variable (i.e., $0$ or $1$) equals $1$ if the number of $1$’s is odd, otherwise $0$. Now, we decompose the XOR of $[s+l-1]\setminus [s-1]$ by bits, for the $i^{th}$ bit, we only need count how many 1’s. It appears that we still need $O(l)$ time to do the counting. However, the consecutiveness of these numbers make the appearance of $1$’s and $0$’s periodic. For example, for the $3^{rd}$ bit (from the lowest bit), roughly speaking the pattern is as follows.

Of course, you need pay a little attention to the beginning and ending parts, since $l$ might not divide $2^3$.

Generally,

• for the $k^{th}$ ($k>1$) bit you only need to count how many $1$’s are they in the first and last partial period (if applicable). Since there are always even number of $1$’s in a full period.
• for the first bit, clearly $1$’s appear $\lfloor\frac{l - b}{2}\rfloor + b$ times

The following pseudo-code shows how to XOR the $i^{th}$ bit. Clearly, it can be done in $O(\log(s + l))$, as there are at most $\log (s + l)$ bits, therefore, this algorithm can calculate the XOR in $O(\log^2(s+l))$ time. Note that, before calculating the XOR bit-by-bit, you should first get these bits and after finishing the XOR, you should assemble these bits into a decimal number. Clearly, these two operations can be done in $O(\log(s+l))$.

# base = 2 ** i
# bit is the value of the i-th bit
# r[i] is the i-th bit for the result
if base == 1:
    r[i] = ((l - bit) / 2 + bit) % 2
else:
    period = 2 * base
    preamble_len = period - bit * base - s % base
    preamble = min(l, preamble_len)
    if bit == 0:
        preamble = max(0, preamble - (base - s % base))
    padding = 0
    if l > preamble_len:
        padding_len = (l - preamble_len) % period
        padding = padding_len - base if padding_len > base else 0
    
    r[i] = (preamble + padding) % 2

Fastpass is a Datacenter network framework proposed by Jonathan Perry, et al.. Its authors published its codes, however, I encountered some issues while installing it on Ubuntu 16.04. Here is Long’s vagrant VM for building Fastpass.

• Issue 1: gcc version issue

  • error:

    include/linux/compiler-gcc.h:86:30: fatal error: linux/compiler-gcc5.h: No such file or directory
    

  • cause: the kernel version of my Ubuntu (i.e., Ubuntu 16.04) is higher than the kernel version used by fastpass (i.e., v3.10.25).

  • solution: before make -j22 adding

    echo "#include <linux/compiler-gcc4.h>" > include/linux/compiler-gcc5.h
    

  • source: compile-a-linux-2-6-kernel-module-with-newer-compiler

• Issue 2: Berkeley DB issue

  • error:

    E: Unable to locate package libdb6.0-dev
    E: Couldn't find any package by glob 'libdb6.0-dev'
    E: Couldn't find any package by regex 'libdb6.0-dev'
    

  • cause: it seems there is no package libdb6.0-dev for Ubuntu 16.04 (I only found libdb6.0-dev for Ubuntu 14.04)
  • solution: replace libdb6.0-dev with libdb-dev (if you still see the similar error, then you might need add the source to your /etc/apt/source/lsit )

As one of the most popular modern version control tools, git is getting more and more popular. As a result, Github becomes a necessary part of programmers’ daily life. In this post, we will introduce some tricks to help programmers play with Github. These tricks are extremely useful, when you are dealing with multiple Github accounts (e.g., one for company codes, one for personal codes).

Avoid Password with SSH: Single Account Case

The first trick is to avoid entering password while pushing local repositories to remote or pulling/fetching private remote repositories.

Generating SSH Key

$ ssh-keygen -t rsa -b 4096

Generally, we will see outputs as follows.

Generating public/private rsa key pair.
Enter file in which to save the key (/home/mininet/.ssh/id_rsa): git_key_example
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in git_key_example.
Your public key has been saved in git_key_example.pub.
The key fingerprint is:
38:44:30:a8:a4:6f:eb:c1:66:12:bb:28:dd:bd:7c:29 mininet@mininet-vm
The key's randomart image is:
+--[ RSA 4096]----+
|   .o..          |
| ..  o           |
|o.    .          |
|o    . .         |
|..    o S        |
| +o    .         |
|oo=o .   .       |
|o=o...E o        |
|+..   o+         |
+-----------------+

During the above process, you will be asked to

• enter the file name for your key pair (In the above example, we used git_key_example as the file name.). If you only enter the file name, the key pair would be stored in current directory. If you want to store your key in somewhere else, you can add the full path of your file.
• Enter a passphrase (If you use SSH out of security, then we strongly suggest you enter one. However, if you choose SSH just because you do not want to enter the password, then you are suggested to leave it empty. Because otherwise you will be asked to enter the same passphrase whenever you git push.).

After the above process, you will find the key pair in the directory you enter. In the above example (assume current directory is /home/mininet/.ssh/), you will find the following two new files:

• git_key_example
• git_key_example.pub The first one is the private key and the second is the public key.

Upload to Github

• Prepare (get the content of public key):

  $ cat git_key_example.pub
  ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDEKiWm5RBjQJOsNmGi6GQNAqhoovXA/qVm1i+nyZ0j18kQkCaeTSdGDUs9UiV9ts7vG4MLHucRLI4dh5hvOH3gr0W7MhB8JubOptKJWtjGaw4f1Vb3xxdKGJ7igHA/ud2N5omkJIptyKXrvybLkqnkLcGgxttvqheOGczzC2g0MIa7MxqhlALkdj0QVyjrtbqltB+k0+lAqyeLRJGrWqmRZ8FlPn1KslpWKq+LFAuKNg24YF7HxbGubdVVeGsKTOowrDBN5IGdEJvlqwZsVUvGnx1oznJzpfdw80KCcm1vFmMU6E3oo3OLfgjhRvcfl5DV+OznTPPr3KbybNSAUIr5lR00LkBhKH0nxiHcERi9/E6/95/fVovY8vV38wPLXBCq/jkmQmtUFHQ86C/1f0bgAAano56Ovd2p7ur5x2pe+sCUxwcQQ3kYOpesqQhCvpkIA6kDGznsGiY1418sCj8D7na1MoifvzsPfpAbO8zAO0YtITEfaaiBum9i4GbzMTl4AzuLIff03XhPRHlew/9McG6DlKm04A96QmRbUZQHzdUyivOSpG7HCFBrYmiEga1EPV8WRRU8SJu0hftV0Upk2T46KASygvo5A0wZ6YUWytHhY8Sdtrx56y4mOtol3RkQtR/vUGCjxIbtl3Lw1J3xoxQkxynesUM8bopBgkwxiQ== mininet@mininet-vm
  

• Open the browser and go to github.com, then

  Log in

  Find “SSH and GPG keys” in “Personal settings”

  “New SSH key”

  Paste the content of your public key.

Add Your SSH Key to ssh-agent

$ eval "$(ssh-agent -s)"
$ ssh-add /path/to/your_ssh_key

To avoid to enter the above commands every time after you restart your computer, you can add them in your bash configuration file (e.g., ~/.bashrc for Ubuntu, ~/.bash_profile for OS X).

Multiple Accounts Case

Assume you have two github account, for ease of presentation, we refer to them as A and B.

• Configure SSH keys for A and B, respectively by the above approach

• Edit ~/.ssh/config and add the following sentences at the end of the file:

  Host github_A
    HostName github.com
    User git
    IdentityFile path/to/ssh-private-key-for-A
  
  Host github_B
      HostName github.com
      User git
      IdentityFile path/to/ssh-private-key-for-B
  

• Change github.com to the corresponding host name you configured above. Suppose the remote repository associated with account A is git@github.com:A/example.git:

  $ git remote add remote_A git@github_A:xlong88/publications.git
  $ ... 
  $ git push remote_A master
  

  Similar for B.

PDF has become one of the most popular file type used on our electronic devices. However, the management of PDF files is not an easy task, especially when you have too many PDF files. For example, as a undergraduate/graduate student, you might obtain bunch of lectures in PDF format for a certain course (say Calulus). After you have taken this course for a long while, we encountered some concepts in Calculus, but you did not remember the details behind them. However, you are $100%$ sure that they must be in certain lectures (but you are not sure which lectures they locate in). At this time, you might want a tool to combining these lectures into a single file such that you can easily locate them.

In this post, we introduce a simple tool that can provide you a user-friendly GUI to combine multiple PDF files into a single one.

Dependencies

• PyPDF2
• Tkinter

Remarks: In the future, to support drag and drop, we might switch to Java.

Usage

• Clone from Github: git clone -b gui https://github.com/lgong30/pdfMerge
• Go to the repository: cd pdfMerge
• Install dependencies: pip install -r requirements.txt (Note that, if you get permission denied errors, please add a sudo before pip)
• Give the python script the permission to execute: sudo chmod +x window.py
• Run: ./window.py

TODO

• Add per-file bookmarks while merging
• Improve the “look” of this application
• Add the support for drag-and-drop

If ever played with GIT, then you might encountered a tedious situation, where you need create a .gitignore file for every repository even if many of your repositories share the same .gitignore file. Some of you might have stored these .gitignore files for various projects, however, the manual copy and paste are still tedious. Are there any tools that can help us “play against” .gitignore easier? In this post, we will introduce you one of such tools.

Requirements

• Sublime Text
• Sublime-Gitignore

Install & Usage

Please refer to the corresponding “official site” of Sublime Text or Sublime-Gitignore.

Customization

Of course, the template provided in Sublime-Gitignore might not satisfy your requirements. Then, you can customize the templates. Before that, you need another sublime text plugin (at least for sublime text 3), that is PackageResourceViewer.

• First, you need extract the package Sublime-Gitignore (HOWTO: please refer to the “official site” of PackageResourceViewer)
• Second, dive into the directory of all templates in Sublime-Gitignore (i.e., the sub-directory boilerplates under the root directory of package Sublime-Gitignore)
• Third, create or edit the corresponding .gitignore template

If you are using BasicTex on your Mac, you might get frustrated when you get errors on missing packages, especially when the latex source using too many packages that you did not install on your Mac. Is there any tools that could help you automatically install those missing packages. YES! texliveonfly provides you such capability. However, you might want this feature to be integrated into your text editor such as Sublime Text.

In this post, we help you design a sublime text plugin for supporting texliveonfly.

Usage

Press cmd+shift+f (unfortunately, current version needs you start your sublime text with the privilege of a superuser, in the future, we will try to figure out how to avoid this)

Installation

git clone https://github.com/lgong30/TexliveOnTheFly ~/Library/Application\ Support/Sublime\ Text\ 3/Packages/TexliveOnTheFly

TODO

• Provide customization feature
• Avoid the requirement for super user privilege