Computer Networks Overview

We studied the Computer Networks course adapted from CMU 15-441 this semester, and I have learned a lot. In this post, I will give an overview of the network architecture from my understanding.

Computers are connected using wires (Here we ignore wireless networks). If two computers speak at the same time, their signals will corrupt. Therefore a protocol is to handle this condition. As a result, wire-connected computers composes a network (we learned the Ethernet protocol, but there are others).

If there are too many computers, the protocol may lose efficiency. The philosophy of computer science comes to help us. We add some kind of layering. By this kind of layering, we can avoid signal corruption. The equipment we use is called Router. The routers connect together, and each router has two interfaces, one is to connect other routers, and the other is to connect the lower layer computers.

Since there are more and more routers, if one computer wants to speak to another, the router must know exactly where to forward this signal. The routing algorithm is used to deal with this task.

However, the memory of the router is limited. For the sake of scalability, more layers should be used. BGP is used to add this layer. CIDR is used to cut IP spaces in order to alleviate the memory pressure of routers.

The topology of our network is established, and this course visited some concept and mechanisms used in data-link layer and transport layer. Encoding, checksum, TCP protocol and so on are introduced.

This post is behind schedule because my rake is broken for some unknown reasons. I reinstalled something to make it work. Next, I will write a post telling the story about some online package manager, such as apt-get, yum, brew, port, npm.

And I had to fix the rsa key problem before I can deploy. Things change quickly, and think some other new features corrupt this part. It is necessary to make things stable throughout time.

By the way, Microsoft bing dictionary is really powerful! It deserves a try!

Say Something About UNIX

I was always lost when talking about UNIX/Linux. Now I know the difference and connection between them better after asking google.

UNIX was first developed by Richie and Thompson in the 1960’s from AT&T, many groups contribute to it then, including Berkeley’s BSD. AT&T realized UNIX’s value then, and claim its ownership. However, BSD contributed much to it, so as a compromise, BSD could release their own code. Up to now, there are two main branches, AT&T has full ownership, and BSD has partly. It was then AT&T seperate UNIX and sold it to Novell which then sold it to SCO. The copyright was also granted to IBM, HP, and SUN. They can also modify the source code.

Linux was developed when BSD and AT&T engaged in the lawsuit about the copyright about UNIX, it was free and open, so many developers join to develop. Linux learned some features but it does not rely on UNIX, in which way it is defined as a UNIX-like OS.

We can have a look at the full hierarchy of UNIX:

UNIX hierarcky

UCD & Google

Quite busy recently. It seems that my schedule is full until 2015. I was writing a paper and accompanying my parents last several days; take a final on Friday; research in HKU from mid of July; take TOEFL & GRE after come back; write ps and fill in forms then. The deadline for most of Universities PhD program is around Nov. and Dec. so I can have a rest then.

So I can only write something in my life these days.

I went to UCD alumni meeting tonight and met an Apple engineering, he is very nice and we had a happy talk. It is the first time I am confirmed Apple office really locates near Yuanshen stadium and they have began to work! Hope we can be friends then.

Then I had a talk with head of Science of UCD. He is very funny, eulogize Ireland and abominate America. It seems that many (maybe most) Irish people is like him.

One thing to mention is that this is my first normal meeting (maybe like a party?). Lessons: I should have worn formal dress, and I need to learn to get involved in a conversation. I was wandering for a long time, hoping to talk to somebody, but they all talked very happily, I don’t know how to come by and say “hi”.

Next is a good news, I get the Google Excellence Scholarship. I was quite fretted these days, because I was competing with other top students in China. It is good that 4 out of 5 recommended Fudan University students finally got that award.

Enable Git in Eclipse

I have been using git for one year, but only recently through the Software Engineering class can I have the chance to learn it in detail.

Git is not rookie-friendly, I still remember the days I used git with my supervisor, I didn’t know anything.

Today, I will introduce a little about git from the knowledge I have till today. There are two main kind of model from Github, one is like SVN, everyone pull and commit, another is just git, using pull request.

SVN model

In this model, git works like svn, but the owner of the project needs to invite collaborators.

PULL REQUEST model

In this model, collaborators clone to local, revise the code, and request the owner to pull, the owner reviews the code and decides whether to merge.

Git in Eclipse

The last thing I want to tell is how to enable git from eclipse. The main steps are:

  1. Install Git plugin.
  2. Config your preference.
  3. Create a project using Git or clone to local and create from existing project.
  4. Using shortcuts from eclipse.

Thanks to 5老科!

Random Card Problem

Random Card Problem is quite popular in game company. I failed a phone interview a month ago because of this problem, so I search for the right answer and post here.

Problem statement is, design an algorithm so that you get a random placement of a set of n cards.

My original answer is as follows:

for each index i,
    get a random index j,
        change cards between i and j

However, this is wrong. To see why, let’s have a look at what a right answer looks like:

for each index i,
    get a random index j from i to n,
        change cards between i and j

There exist another good algorithm: we know each placement has a unique ID: its place in the whole possible placements. For example, assume n = 3, ID of ‘123’ is 1, ‘132’ is 2, ‘213’ is 3, ‘231’ is 4, ‘312’ is 5, and ‘321’ is 6. It is easy to get the placement from its ID, so we random an ID and get its placement.

Why my answer is wrong

From calculation, we know that, in the right solution, the probability a card stays in its original index is the same for each card, while it is not in my solution.

In the right solution, when i = 1, Pr(1st card stays in 1st place) = 1/n; when i = 2, Pr(2nd…) = (n - 1)/n * 1/(n - 1) = 1/n; when i = 3, Pr(3rd…) = … = 1/n…

Now you see why the right solution right, and you see why my solution wrong. I was surprised by the magical math here the first time I realized it.

Idea

I have been thinking of the idea of building smart home for a year.

“Smart Home” is a set of infrastructures that connects all funitures using wifi, and mobile app or web service can be used to control them. In order to do so, some simple mechanisms should be used.

What do you think of this idea? Feel free to contact me!

I Am Back

After about a whole year, I came back to my blog!

Theses days, I had many exams, and fortunately, I passed GRE (152+170+3.0), my next goal is to pass TOEFL. Fight!

Hopefully, I plan to write blogs once every week.

Iapfree

These days Find Something is very popular, and I just want to find some plugins to get more money for free. There are three according to my search on google.

The first is gameplayer(maybe developed by duowan.com) which is an app to change variables just like Knights from Kingsoft, then I found localiapstore, and found it was useful for the game CarotFantasy, but not useful for Find Something. The last one is iapfree, which is useful for many apps even for magazines…

There are some problems I met during this process. When I add some repo to cydia, I found nothing in that directory, and I just couldn’t download iapfree and couldn’t even find gameplayer, which wasted me much time.

At last, I was forced to find a way to install .deb file locally, and fortunatly found a way to creat my own repo. Just sign up from this myrepospace, actually this is a good way, you don’t need to load those files from each source every time you open cydia, what you need is only one source(except for one that was bound to cydia). And each time you find a useful .deb file, you can just upload it to your repo and download it from cydia. My repo is http://cydia.myrepospace.com/vvv214 welcome to use it!

By the way, I received a call when I was searching, which told me that I was employed by stu.fudan.edu.cn. After one and a half years of working in SU, finally I found a way to combine the student activity with my major. Hope this can benefit those both aspect!

Welly

Welly is a telnet app for mac. It was used to connect to the school bbs just like fterm on Windows.

At first I used terminal to connect, only to find unrecognized characters. Fudan bbs uses GBK charset, but I don’t know how to change the charset of a specific window of terminal, and I downloaded qterm, which was said to able to act like welly, but I found something may be wrong with it.(Actually I don’t know how to run it…) Then I came up with an idea to use crossover, but I just deleted this app yesterday. At last I found welly…

Actually it is a little slow compared with fterm in windows, I don’t know if it is because that I am using an ethernal network, I’ll try it tomorrow when I go back to school.

Octopress on Github

Just as you’ve seen, this webpage is generated by octopress on github, anyone who like to do like this, follow this webpage.

Actually, I’m a new starter, anyone who like to share any techniques or information with me is welcomed!

The instructions for writing a post is simple:

rake new_post["title"]
rake generate
rake deploy

After installing octopress, I install a theme for my octopress, and this is what it looks like now!